Heuristic D* Algorithm Based on Particle Swarm Optimization for Path Planning of Two-Link Robot Arm in Dynamic Environment

  • Firas A. Raheem Department of Control and Systems Engineering/ University of Technology
  • Umniah I. Hameed Department of Control and Systems Engineering/ University of Technology


 Finding a path solution in a dynamic environment represents a challenge for the robotics researchers, furthermore, it is the main issue for autonomous robots and manipulators since nowadays the world is looking forward to this challenge. The collision free path for robot in an environment with moving obstacles such as different objects, humans, animals or other robots is considered as an actual problem that needs to be solved.  In addition, the local minima and sharp edges are the most common problems in all path planning algorithms. The main objective of this work is to overcome these problems by demonstrating the robot path planning and obstacle avoidance using D star (D*) algorithm based on Particle Swarm Optimization (PSO) technique. Moreover, this work focuses on computational part of motion planning in completely changing dynamic environment at every motion sample domains. Since the environment type that discussed here is a known dynamic environment, the solution approach can be off-line. The main advantage of the off-line planning is that a global optimal path solution is always obtained, which is able to overcome all the difficulties caused by the dynamic behavior of the obstacles. A mixing approach of robot path planning using the heuristic method D* algorithm based on optimization technique is used. The heuristic D* method is chosen for finding the shortest path. Furthermore, to insure the path length optimality and for enhancing the final path, PSO technique has been utilized. The robot type has been used here is the two-link robot arm which represents a more difficult case than the mobile robot. Simulation results are given to show the effectiveness of the proposed method which clearly shows a completely safe and short path.


Download data is not yet available.


H. Miao, Y.-C. Tian and Y.M. Feng, “Robot Path Planning in Dynamic Environments using a Simulated Annealing Based Approach”, Faculty of Science and Technology Queensland University of Technology, 2014.

F. A. Raheem and M. M. Bader, “Development of Modified Path Planning Algorithm Using Artificial Potential Field ( APF) Based on PSO for Factors Optimization,” American Scientific Research Journal for Engineering, Technology, and Science, 37, 316-328, 2017.

Kikuo Fujimura, “Motion Planning in Dynamic Environments”, Springer-Verlag Tokyo, 1991. https://doi.org/10.1007/978-4-431-68165-6

A. Stentz, The Focused D* Algorithm for Real-Time Replanning. Proceedings of the International Joint Conference on Artificial Intelligence, Montreal, 20-25 August 1995, 1652-1659, 1995.

Enric Cervera I Mateu, “Perception –Based Learning for fine motin planning in robot manipulation”,Jaume-I University of Castello. Spain, 1997.

Z. Shiller, F. Large and S. Sekhavat, “Motion Planning in Dynamic Environments: Obstacles Moving Along Arbitrary Trajectories”, Mechanical and Aerospace Engineering, University of California, Proceedings of the IEEE International Conference on Robotics & Automation Seoul, Korea. May 21-26, 2001.

R. S. M. Asghari and O. A. Tabataba , “Mobile Robot Path Planning by RRT* in Dynamic Environments”, MECS, April 2015.

B. Asadi, “Single and Dual Arm Manipulator Motion Planning Library”, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Hamburg, 28 September-2 October 2015.

A. Vemula, “Safe and Efficient Navigation in Dynamic Environments,” Carnegie Mellon University, Pittsburgh, no. July, 2017

Mark W. Spong, Seth Hutchinson, M. Vidyasagar “Robot Modeling and Control” united states of America first edition, Wiley, Hoboken, 2006.

John J. Craig “Introduction to Robotics Mechanics and Control” United States of America third edition, Pearson Prentice Hall Pearson Education, Inc., Upper Saddle River, NJ. 2005.

A. T. Sadiq, F. A. Raheem, and N. A. F. Abbas, “Optimal Trajectory Planning of 2-DOF Robot Arm Using the Integration of PSO Based on D * Algorithm and Cubic Polynomial Equation,” First Int. Conf. Eng. Res., no. March, pp. 458–467,2017.

A. T. Sadiq, F. A. Raheem, and N. A. F. Abbas, “Robot Arm Path Planning Using Modified Particle Swarm Optimization Based on D * Algorithm” Al-Khwarizmi Engineering Journal, Vol. 13, No. 3, pp. 27-37, 2017.

P. Boonyaritdachochai, et al., "Optimal congestion management in an electricity market using particle swarm optimization with time-varying acceleration coefficients," Computers & Mathematics with Applications, vol. In Press, Corrected Proof, 2010.

Poli, R., Kennedy, J. and Blackwell, T. Particle Swarm Optimization: An Overview. Swarm Intelligence, 1, 33-57, 2007

K. T. Chaturvedi, et al., "Particle swarm optimization with time varying acceleration coefficients for non-convex economic power dispatch," International Journal of Electrical Power & Energy Systems, vol. 31, pp. 249-257, 2009.

Ni, J.J., Wu, W.B., Shen, J.R. and Fan, X.N. An Improved VFF Approach for Robot Path Planning in Unknown and Dynamic Environments. Mathematical Problems in Engineering, 2014, Article ID:461237.


How to Cite
Raheem, F., & Hameed, U. (2019). Heuristic D* Algorithm Based on Particle Swarm Optimization for Path Planning of Two-Link Robot Arm in Dynamic Environment. Al-Khwarizmi Engineering Journal, 15(2), 108- 123. https://doi.org/10.22153/kej.2019.01.004