Comparison between Waveform and Bug Path Planning Algorithm for Mobile Robot

Abstract:

Mobile robots frequently find themselves in a circumstance where they need to find a trajectory to another position in their environment, subject to constraints postured by obstacles and the capabilities of the robot itself. This study compared path planning algorithms for mobile robots to move efficiently in a collision free grid based static environment. Two algorithms have been selected to do the comparison namely wavefront algorithm and bug algorithm. The wavefront algorithm involves a breadth-first search of the graph beginning at the goal position until it reaches the start position. The bug algorithm uses obstacles borders as guidance toward a goal with restricted details about the environment. The algorithms are compared in terms of parameters such as execution time of the algorithm and planned path length by using Player/Stage simulation software. Results shown that wavefront algorithm is a better path planning algorithm compared to bug algorithm in static environment.

• Periodical: Applied Mechanics and Materials (Volume 607)
• Pages: 774-777
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.607.774
• Online since: July 2014
• Authors: Swee Ho Tang, Che Fai Yeong*, Eileen Lee Ming Su
• Keywords: Bug Algorithm, Mobile Robot, Path Planning, Player/Stage, Wave Front Algorithm

References

[1] G. Nagib and W. Gharieb, Path planning for a mobile robot using genetic algorithms, " in Electrical, Electronic and Computer Engineering, 2004. ICEEC , 04. 2004 International Conference on, 2004, pp.185-189.

DOI: 10.1109/iceec.2004.1374415

[2] A. Stentz, Optimal and Efficient Path Planning for Partially Known Environments, in Intelligent Unmanned Ground Vehicles. vol. 388, M. Hebert, C. Thorpe, and A. Stentz, Eds., ed: Springer US, 1997, pp.203-220.

DOI: 10.1007/978-1-4615-6325-9_11

[3] A. Nooraliei and R. Iraji, Robot path planning usingwavefront approach with wall-following, in Computer Science and Information Technology, 2009. ICCSIT 2009. 2nd IEEE International Conference on, 2009, pp.417-420.

DOI: 10.1109/iccsit.2009.5234918

[4] V. J. Lumelsky and A. A. Stepanov, Dynamic path planning for a mobile automaton with limited information on the environment, Automatic Control, IEEE Transactions on, vol. 31, pp.1058-1063, (1986).

DOI: 10.1109/tac.1986.1104175

[5] J. Ng and T. Braunl, Performance comparison of Bug navigation algorithms, Journal of Intelligent & Robotic Systems, vol. 50, pp.73-84, Sep (2007).

[6] I. Kamon and E. Rivlin, Sensory-based motion planning with global proofs, Ieee Transactions on Robotics and Automation, vol. 13, pp.814-822, Dec (1997).

DOI: 10.1109/70.650160

[7] V. Lumelsky and T. Skewis, Incorporating Range Sensing in the Robot Navigation Function, Ieee Transactions on Systems Man and Cybernetics, vol. 20, pp.1058-1069, Sep-Oct (1990).

DOI: 10.1109/21.59969

[8] I. Kamon, E. Rimon, and E. Rivlin, TangentBug: A range-sensor-based navigation algorithm, International Journal of Robotics Research, vol. 17, pp.934-953, Sep (1998).

DOI: 10.1177/027836499801700903

[9] B. P. Gerkey., R. T. Vaughan., and A. Howard., The Player/Stage Project: Tools for Multi-Robot and Distributed Sensor Systems, in Proceedings of the 11th International Conference on Advanced Robotics, 2003, pp.317-323.