Optimal Path Planning for Navigation Using a Generalized Genetic Algorithm
Keywords:
A star search algorithm, D star algorithm, Probabilistic Road Mapping, Rapidly-exploring Random Tree, Genetic AlgorithmAbstract
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.
References
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.
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.
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.
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.
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.
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.
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.
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..
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.
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.
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
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
