International Journal of Scientific & Technology Research

Home About Us Scope Editorial Board Contact Us

IJSTR >> Volume 9 - Issue 3, March 2020 Edition

International Journal of Scientific & Technology Research  
International Journal of Scientific & Technology Research

Website: http://www.ijstr.org

ISSN 2277-8616

A New RT Shortest Path Planning Algorithm For Mobile Robot Navigation In Known Terrain

[Full Text]



Ravi teja Tirumalapudi, Rajay Vedaraj.I.S



Bug1 algorithm, Bug2 algorithm, Graph search, Mobile robotics, Obstacle avoidance, Path planning algorithms, Path Search.



Shortest path planning is the basic and fundamental topic in the navigation system of mobile robotics, but this is the main research field of mobile robotics. Previously so many path planning algorithms are proposed. This paper proposed a new methodology for mobile robot path planning in known terrain with rotation and transformation obstacles, inspired by the bug algorithm. Using the Rotation and Transformation algorithm find the optimal shortest path in known terrain. It works by moving a mobile robot in path detect any obstacle whether it moves rotation or transformation, a mobile robot will assume the new shortest path avoid that obstacle. This path is the best path compared by standard bug2 algorithm consider it has a avoid different shapes obstacles to reach goal point. This algorithm is tested in a mobile robot having a laser sensor, shown and included simulation results.



[1] Zhang Han Ye, Lin Wei Ming and Chen Ai Xia,” Path planning for the mobile robot: A review”, Symmetry 10(10), 2018.
[2] You, Yangwei, Caixia Cai, and Yan Wu. "3D Visibility Graph based Motion Planning and Control." (2019).
[3] Ellips Masehia, M. R. Amin‐Naseri, " A voronoi diagram‐visibility graph‐potential field compound algorithm for robot path planning", journal of field robotics 2014, 21(6), pp 275-300.
[4] Wang, Haiyan, and Zhiyu Zhou. "A heuristic elastic particle swarm optimization algorithm for robot path planning." Information 10.3 (2019): 99.
[5] Hwang, Yong Koo, and Narendra Ahuja. "A potential field approach to path planning." IEEE Transactions on Robotics and Automation 8.1 (1992): 23-32.
[6] Lingelbach, Frank. "Path planning using probabilistic cell decomposition." IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA'04. 2004. Vol. 1. IEEE, 2004.
[7] Bhattacharya, Subhrajit, Maxim Likhachev, and Vijay Kumar. "Topological constraints in search-based robot path planning." Autonomous Robots 33.3 (2012): 273-290.
[8] Siméon, Thierry, J-P. Laumond, and Carole Nissoux. "Visibility-based probabilistic roadmaps for motion planning." Advanced Robotics 14.6 (2000): 477-493.
[9] Edsger W. Dijkstra, “A Note on Two Problems in Connection with Graphs” Numerische Mathematik. 23 (3), pp 269–271, 1959.
[10] Duchoň, František, et al. "Path planning with modified a star algorithm for a mobile robot." Procedia Engineering 96 (2014): 59-69.
[11] Reher, Jenna, and Wenlong Ma. "Dynamical Path Planning For Humanoid Robot Atlas Via D* Lite." (2019).
[12] Stentz, Anthony (1994), "Optimal and efficient path planning for unknown and dynamic Environments ", CMU-RI-TR-93-20, The Robotics institute, Carnegie Mellon University, Aug 1993.
[13] Xu, Feiyi, et al. "A new global best guided artificial bee colony algorithm with application in robot path planning." Applied Soft Computing (2020): 106037.
[14] Dakulović, Marija, and Ivan Petrović. "Two-way D∗ algorithm for path planning and replanning." Robotics and autonomous systems 59.5 (2011): 329-342.
[15] Ferguson, Dave, Maxim Likhachev, and Anthony Stentz. "A guide to heuristic-based path planning." Proceedings of the international workshop on planning under uncertainty for autonomous systems, international conference on automated planning and scheduling (ICAPS). 2005.
[16] Mohanty, Prases Kumar, and Dayal R. Parhi. "Path planning strategy for mobile robot navigation using MANFIS controller." Proceedings of the International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA) 2013. Springer, Cham, 2014.
[17] Tu, Jianping, and Simon X. Yang. "Genetic algorithm based path planning for a mobile robot." 2003 IEEE International Conference on Robotics and Automation (Cat. No. 03CH37422). Vol. 1. IEEE, 2003.
[18] Garcia, MA Porta, et al. "Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation." Applied Soft Computing 9.3 (2009): 1102-1110.
[19] Qin, Yuan-Qing, et al. "Path planning for mobile robot using the particle swarm optimization with mutation operator." Proceedings of 2004 international conference on machine learning and cybernetics (IEEE Cat. No. 04EX826). Vol. 4. IEEE, 2004.
[20] Park, Min Gyu, Jae Hyun Jeon, and Min Cheol Lee. "Obstacle avoidance for mobile robots using artificial potential field approach with simulated annealing." ISIE 2001. 2001 IEEE International Symposium on Industrial Electronics Proceedings (Cat. No. 01TH8570). Vol. 3. IEEE, 2001.
[21] Wu, Qing, et al. "Real-Time Dynamic Path Planning of Mobile Robots: A Novel Hybrid Heuristic Optimization Algorithm." Sensors 20.1 (2020): 188.
[22] Lumelsky, Vladimir J., and Alexander A. Stepanov. "Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape." Autonomous robot vehicles. Springer, New York, NY, 1990. 363-390.
[23] Lumelsky, V., and Alexander Stepanov. "Dynamic path planning for a mobile automaton with limited information on the environment." IEEE transactions on Automatic control 31.11 (1986): 1058-1063.
[24] Fujimura, Kikuo, and Hanan Samet. "A hierarchical strategy for path planning among moving obstacles (mobile robot)." IEEE transactions on robotics and Automation 5.1 (1989): 61-69.
[25] Zhu, Qiuming. "Hidden Markov model for dynamic obstacle avoidance of mobile robot navigation." IEEE Transactions on Robotics and Automation 7.3 (1991): 390-397.
[26] Zelinsky, Alexander, et al. "Planning paths of complete coverage of an unstructured environment by a mobile robot." Proceedings of international conference on advanced robotics. Vol. 13. 1993.
[27] Yang, Shuai, et al. "A New Intelligent Trajectory Planning Algorithm Based on Bug2 Algorithm: Bridge Algorithm." 2019 IEEE International Conference on Robotics and Biomimetics (ROBIO). IEEE, 2019.
[28] Le, Than. "Real-Time Search-based Planning in Structure Environments." (2020).