Several Global Path Planning Algorithms and Modification

Abstract

Mobile robots are being used in a wide range of scenarios with increasing frequency. But it is also an extremely difficult field with an interdisciplinary nature. Path planning (PP) is one of the most challenging problems in robotics, which can be further categorized into global navigation and reactive navigation. This article will focus on global navigation, aiming to provide a general review of several important global PP algorithms on their principles and significant improvement as well as propose some tenable modification suggestions. Dijkstra algorithm, as the most classic and mature algorithm, has been executed many modifications to address its inherent limitations. For instance, an optimizing data storage structure has been employed to obtain enhanced efficiency. The genetic algorithm is the most important evolution algorithm, giving a satisfactory result especially in large-scale searching. Modification of GA has also been conducted by introducing newly designed operators to facilitate the evolution and combining the APF method to guarantee a smoother path. A star is another popular heuristic algorithm, introducing a turning factor based on Dijkstra to reduce the searching area. It has also been improved in various aspects, particularly in refining its heuristic function. A neural network encoder has also been utilized to generate a satisfactory path after constructing a differentiable A star module. Three algorithms are then compared to further analyze their characteristics respectively, followed by proposed enhancements tailored to each algorithm. Through the content above, this paper gives a compact view of the main PP algorithms and suggests some potential directions for future modification.