International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 15, No. 6, 8 Dec. 2023
Cover page and Table of Contents: PDF (size: 517KB)
An Improved Sampling Dijkstra Approach for Robot Navigation and Path Planning
Full Text (PDF, 517KB), PP.51-64
Views: 0 Downloads: 0
Author(s)
Index Terms
Dijkstra, Improved Dijkstra, Path Planning, Robot Navigation, Mobile Robot, Shortest Path
Abstract
The task of path planning is extremely investigated in mobile robotics to determine a suitable path for the robot from the source point to the target point. The intended path should satisfy purposes such as collision-free, shortest-path, or power-saving. In the case of a mobile robot, many constraints should be considered during the selection of path planning algorithms such as static or dynamic environment and holonomic or non-holonomic robot. There is a pool of path-planning algorithms in the literature. However, Dijkstra is still one of the effective algorithms due to its simplicity and capabilities to compute single-source shortest-path to every position in the workspace. Researchers propose several versions of the Dijkstra algorithm, especially in mobile robotics. In this paper, we propose an improved approach based on the Dijkstra algorithm with a simple sampling method to sample the workspace to avoid an exhaustive search of the Dijkstra algorithm which consumes time and resources. The goal is to identify the same optimal shortest path resulting from the Dijkstra algorithm with minimum time and number of turns i.e., a smoothed path. The simulation results show that the proposed method improves the Dijkstra algorithm with respect to the running time and the number of turns of the mobile robot and outperforms the RRT algorithm concerning the path length.
Cite This Paper
Ayman H. Tanira, Iyad M. I. AbuHadrous, "An Improved Sampling Dijkstra Approach for Robot Navigation and Path Planning", International Journal of Intelligent Systems and Applications(IJISA), Vol.15, No.6, pp.51-64, 2023. DOI:10.5815/ijisa.2023.06.05
Reference
[1]B. Tang, Z. Zhu, and J. Luo, “Hybridizing Particle Swarm Optimization and Differential Evolution for the Mobile Robot Global Path Planning,” Int J Adv Robot Syst, vol. 13, no. 3, 2016, doi: 10.5772/63812.
[2]M. Dirik and A. Fatih Kocamaz, “RRT-Dijkstra: An Improved Path Planning Algorithm for Mobile Robots,” Journal of Soft Computing and Artificial Intelligence, 2020. [Online]. Available: www.dergipark.org.tr/en/pub/jscai
[3]Y. Zhuang, Y. Sun, and W. Wang, “Mobile robot hybrid path planning in an obstacle-cluttered environment based on steering control and improved distance propagating,” International Journal of Innovative Computing, Information and Control, vol. 8, no. 6, 2012.
[4]T. T. Mac, C. Copot, D. T. Tran, and R. De Keyser, “Heuristic approaches in robot path planning: A survey,” Rob Auton Syst, vol. 86, 2016, doi: 10.1016/j.robot.2016.08.001.
[5]C. Zheng and R. Green, “Vision-based autonomous navigation in indoor environments,” in International Conference Image and Vision Computing New Zealand, 2010. doi: 10.1109/IVCNZ.2010.6148876.
[6]N. Sariff and N. Buniyamin, “An overview of autonomous mobile robot path planning algorithms,” in SCOReD 2006 - Proceedings of 2006 4th Student Conference on Research and Development “Towards Enhancing Research Excellence in the Region,” 2006. doi: 10.1109/SCORED.2006.4339335.
[7]N. B. Sariff and N. Buniyamin, “Ant Colony System for Robot Path Planning in Global Static Environment Faculty of Electrical Engineering,” Selected Topics in System Science and Simulation in Engineering, 2010.
[8]K. Karur, N. Sharma, C. Dharmatti, and J. E. Siegel, “A Survey of Path Planning Algorithms for Mobile Robots,” Vehicles, vol. 3, no. 3, 2021, doi: 10.3390/vehicles3030027.
[9]G. Klančar, A. Zdešar, S. Blažič, and I. Škrjanc, Wheeled Mobile Robotics: From Fundamentals Towards Autonomous Systems. 2017.
[10]P. Li, X. Huang, and M. Wang, “A novel hybrid method for mobile robot path planning in unknown dynamic environment based on hybrid DSm model grid map,” in Journal of Experimental and Theoretical Artificial Intelligence, 2011. doi: 10.1080/0952813X.2010.506283.
[11]E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numer Math (Heidelb), vol. 1, no. 1, 1959, doi: 10.1007/BF01386390.
[12]P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, 1968, doi: 10.1109/TSSC.1968.300136.
[13]A. Stentz, “Optimal and efficient path planning for partially-known environments,” in Proceedings - IEEE International Conference on Robotics and Automation, 1994. doi: 10.1007/978-1-4615-6325-9_11.
[14]D. Ferguson and A. Stentz, “Using interpolation to improve path planning: The Field D* algorithm,” J Field Robot, vol. 23, no. 2, pp. 79–101, Feb. 2006, doi: 10.1002/rob.20109.
[15]K. Daniel, A. Nash, S. Koenig, and A. Felner, “Theta*: Any-angle path planning on grids,” Journal of Artificial Intelligence Research, vol. 39, 2010, doi: 10.1613/jair.2994.
[16]K. Xiao, C. Gao, X. Hu, and H. Pan, “Improved Theta*: Improved any-angle path planning on girds,” Journal of Computational Information Systems, vol. 10, no. 20, 2014, doi: 10.12733/jcis12043.
[17]S. M. LaValle, “Rapidly-Exploring Random Trees: A New Tool for Path Planning,” In, vol. 129, 1998.
[18]S. M. LaValle and J. J. Kuffner, “Randomized kinodynamic planning,” International Journal of Robotics Research, vol. 20, no. 5, 2001, doi: 10.1177/02783640122067453.
[19]P. Martin and A. P. del Pobil, “Application of artificial neural networks to the robot path planning problem,” in Applications of Artificial Intelligence in Engineering, 1994.
[20]C. Li, J. Zhang, and Y. Li, “Application of artificial neural network based on Q-learning for mobile robot path planning,” in Proceedings of IEEE ICIA 2006 - 2006 IEEE International Conference on Information Acquisition, 2006. doi: 10.1109/ICIA.2006.305870.
[21]M. Zhao, N. Ansari, and E. S. H. Hou, “Mobile manipulator path planning by a genetic algorithm,” J Robot Syst, vol. 11, no. 3, 1994, doi: 10.1002/rob.4620110302.
[22]F. Liu, S. Liang, and D. X. Xian, “Optimal Path Planning for Mobile Robot Using Tailored Genetic Algorithm,” TELKOMNIKA Indonesian Journal of Electrical Engineering, vol. 12, no. 1, 2014, doi: 10.11591/telkomnika.v12i1.3127.
[23]H. Shorakaei, M. Vahdani, B. Imani, and A. Gholami, “Optimal cooperative path planning of unmanned aerial vehicles by a parallel genetic algorithm,” Robotica, vol. 34, no. 4, 2016, doi: 10.1017/S0263574714001878.
[24]J. Y. Jhang, C. J. Lin, C. T. Lin, and K. Y. Young, “Navigation Control of Mobile Robots Using an Interval Type-2 Fuzzy Controller Based on Dynamic-group Particle Swarm Optimization,” Int J Control Autom Syst, vol. 16, no. 5, 2018, doi: 10.1007/s12555-017-0156-5.
[25]T. W. Liao, “A procedure for the generation of interval type-2 membership functions from data,” Applied Soft Computing Journal, vol. 52, 2017, doi: 10.1016/j.asoc.2016.09.034.
[26]W. Liu, H. Niu, M. N. Mahyuddin, G. Herrmann, and J. Carrasco, “A Model-free Deep Reinforcement Learning Approach for Robotic Manipulators Path Planning,” in International Conference on Control, Automation and Systems, 2021. doi: 10.23919/ICCAS52745.2021.9649802.
[27]D. Guo et al., “A vehicle path planning method based on a dynamic traffic network that considers fuel consumption and emissions,” Science of the Total Environment, vol. 663, 2019, doi: 10.1016/j.scitotenv.2019.01.222.
[28]F. R. Souza, T. R. Câmara, V. F. N. Torres, B. Nader, and R. Galery, “Mine fleet cost evaluation - dijkstra’s optimized path,” Revista Escola de Minas, vol. 72, no. 2, 2019, doi: 10.1590/0370-44672018720124.
[29]S. Shao, W. Guan, B. Ran, Z. He, and J. Bi, “Electric Vehicle Routing Problem with Charging Time and Variable Travel Time,” Math Probl Eng, vol. 2017, 2017, doi: 10.1155/2017/5098183.
[30]S. A. Fadzli, S. I. Abdulkadir, M. Makhtar, and A. A. Jamal, “Robotic indoor path planning using dijkstra’s algorithm with multi-layer dictionaries,” in 2015 IEEE 2nd International Conference on InformationScience and Security, ICISS 2015, 2016. doi: 10.1109/ICISSEC.2015.7371031.
[31]A. H. M. Santos et al., “Optimizing routing and tower spotting of electricity transmission lines: An integration of geographical data and engineering aspects into decision-making,” Electric Power Systems Research, vol. 176, 2019, doi: 10.1016/j.epsr.2019.105953.
[32]H. Il Kang, B. Lee, and K. Kim, “Path planning algorithm using the particle swarm optimization and the improved dijkstra algorithm,” in Proceedings - 2008 Pacific-Asia Workshop on Computational Intelligence and Industrial Application, PACIIA 2008, 2008. doi: 10.1109/PACIIA.2008.376.