Global Path Planning for Mobile Robot Based on Improved Dijkstra Algorithm and Particle Swarm Optimization


Article Preview

A novel method of improved Dijkstra algorithm and particle swarm optimization is proposed to evaluate global path planning for mobile robot. The first step is to make the MAKLINK graph which is used to describe the working space of mobile robot. The limited length value of free linkage line is conducted to substitute the constant weights in the adjacent matrix, which is well correlated with the fact that the number of paths is drastically less than that using the conventional Dijkstra method. Then the particle swarm optimization is adopted to investigate the global path from the several possible paths. Therefore, the proposed method facilitates reducing the computing time which enhances the efficiency of particle swarm optimization when performs the global path planning for mobile robot. Furthermore, simulation result is provided to verify the effectiveness and practicability.



Edited by:

Zhenyu Du and Bin Liu




N. C. Chen et al., "Global Path Planning for Mobile Robot Based on Improved Dijkstra Algorithm and Particle Swarm Optimization", Applied Mechanics and Materials, Vols. 26-28, pp. 909-912, 2010

Online since:

June 2010




[1] J. Barraquand, B. Langois, J.C. Latombe: IEEE Transactions on Robotics and Automation, Man and Cybernetics Vol. 22 (1992), p.224.

[2] Ge S. S., Cui Y J: IEEE Transactions on Robotics and Automation Vol. 16 (2000), p.615.

[3] Boschian V., Pruski A.: Journal of Intelligent and Robotic Systems Vol. 8 (1993), p.201.

[4] Y. Ting, W. I. Lei, H.C. Jar: Computers and Industrial Engineering Vol. 42 (2002), p.299.

[5] Lozano Perez. T.: IEEE Journal of Robotics and Automation, Vol. 3 (1987), p.224.

[6] Horacio Martínez-Alfaro, Simón Gómez-García: Expert Systems with Applications Vol. 15 (1998), p.421.

[7] Yung N H C. Cang Ye: IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics Vol. 29 (1999), p.314.


[8] Lebedev D: Modeling and Analysis of Information Systems Vol. 18 (2001), P. 2.

[9] M. Gemeinder, M. Gerke: Applied Soft Computing Vol. 3 (2003), p.149.

[10] Dorigo M, Gambardella L. M.: IEEE Transactions on Evolutionary Computation Vol. 1 (1997), p.53.

[11] Kennedy J, Eberhart R C.: Proc. of IEEE Intl. Conf. on Neutral Networks, (1995), p.1942-(1948).

[12] QIN Yuan-qing, SUN De-bao, LI Ning.: Robot Vol. 26 (2004), p.222.

[13] Guanzheng Tan, Huan He and Aaron Sloma: J. CENT. South Univ. Technol. Vol. 13 (2006), p.80.