Optimal Path Planning for Navigation Using a Generalized Genetic Algorithm

Ramya S.¹

Section:Review Paper, Product Type: Journal-Paper
Vol.9 , Issue.5 , pp.7-13, Oct-2021

Online published on Oct 31, 2021

Copyright © Ramya S. . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

Abstract :
Finding an optimal collision-free route from an arbitrary point to a designated point with obstacles in a given environment is essential to design an algorithm for path planning. The main goal is to search a workspace to find the shortest path within a minimal amount of time, by starting at the source point and exploring adjacent objects until the destination point is reached. This paper gives an overview of path planning algorithms like A*, D star, PRM, and RRT, which gives an optimal path to find the way in a given workspace. This paper also presents how to coalesce the Genetic Algorithm with other path planning algorithms to find an optimal path in a given workspace.

Key-Words / Index Term :
A star search algorithm, D star algorithm, Probabilistic Road Mapping, Rapidly-exploring Random Tree, and Genetic Algorithm

References :
[1]. M. Kurant, A. Markopoulou and P. Thiran, "On the bias of BFS (Breadth First Search)," 2010 22nd International Teletraffic Congress (lTC 22), Amsterdam, Vol: 5, pp. 1-8, doi: 10.1109/ITC.2010.5608727,2010.
[2]. B. Swami and R. Singh, "Performance analysis of DFS based ordered walk learning routing protocol in MANET," 2015 International Conference on Green Computing and Internet of Things (ICGCIoT), Noida, Vol: 3, pp. 195-198, doi: 10.1109/ICGCIoT.2015.7380456,2015.
[3].M. Nazarifard and D. Bahrepour, "Efficient implementation of the Bellman-Ford algorithm on GPU," 2017 IEEE 4th International Conference on Knowledge-Based Engineering and Innovation (KBEI), Tehran, Vol: 2, pp. 0773-0778, doi: 10.1109/KBEI.2017.8324901,2017.
[4]. N. Makariye, "Towards shortest path computation using Dijkstra algorithm," 2017 International Conference on IoT and Application (ICIOT), Nagapattinam, Vol: 6, pp. 1-3, doi: 10.1109/ICIOTA.2017.8073641, 2017.
[5]. J. Yao, C. Lin, X. Xie, A. J. Wang and C. Hung, "Path Planning for Virtual Human Motion Using Improved A* Star Algorithm," 2010 Seventh International Conference on Information Technology: New Generations, Las Vegas, NV, 2010, pp. 1154-1158, doi: 10.1109/ITNG.2010.53.
[6]. Xiaowu Liu, Riqiang Deng, Jinwen Wang, Xunzhang Wang, COStar: A D-star Lite-based dynamic search algorithm for codon optimization, Journal of Theoretical Biology, Volume 344, 2014, Pages 19-30, ISSN 0022-5193.
[7]. Sigurd Lazic Villumsen, Morten Kristiansen, PRM Based Motion Planning for Sequencing of Remote Laser Processing Tasks, Procedia Manufacturing, Volume 11, 2017, Pages 300-310, ISSN 2351-9789.
[8]. R. Kala, A. Shukla, R. Tiwari (2011) Robotic path planning in static environment using hierarchical multineuron heuristic search and probability based fitness, Neurocomputing, 74(14-15), 2314-2335..
[9]. Xiaoman Cao, Xiangjun Zou, Chunyang Jia, Mingyou Chen, Zeqin Zeng, RRT-based path planning for an intelligent litchi-picking manipulator, Computers and Electronics in Agriculture, Volume 156, 2019, Pages 105-118, ISSN 0168-1699.
[10]. S. Doostie, A.K. Hoshiar, M. Nazarahari, Seungmin Lee, Hongsoo Choi, Optimal path planning of multiple nanoparticles in continuous environment using a novel Adaptive Genetic Algorithm, Precision Engineering,Volume 53, 2018, Pages 65-78, ISSN 0141-6359.
[11]. Gasparetto A., Boscariol P., Lanzutti A., Vidoni R. (2015) Path Planning and Trajectory Planning Algorithms: A General Overview. In: Carbone G., Gomez-Bravo F. (eds) Motion and Operation Planning of Robotic Systems. Mechanisms and Machine Science, vol 29. Springer, Cham. https://doi.org/10.1007/978-3-319-14705-5_1