A Comprehensive Comparative Study of State-of-the-Art Path-Planning Algorithms for Autonomous Robots

Abstract

The problem of path planning is one of the most crucial and challenging issues in the fields of intelligent systems and autonomous robotics. A robot’s ability to move quickly and easily from a starting position to a goal position without hitting anything is directly related to how useful the robot is in real life. This paper compares five advanced path-planning algorithms: A* (A-Star), D* Lite (Dynamic A-Star Lite), RRT* (Rapidly exploring Random Tree Star), PRM* (Probabilistic Roadmap Star), and APF-D (Adaptive Potential Field with Dynamic Awareness). The paper addresses the difficult problem in dynamic environments where objects enter, exit, and move around continuously within the robot environment, as it moves through the environment, which is becoming more prevalent in the real world, such as in warehouses, hospitals, and urban and outdoor environments. Six performance measures, namely path length, computation time, memory, optimality ratio, success rate, and replanning latency, are used to test our five algorithms on a standard simulator in Matlab. Experiments are conducted in four different conditions, from very quiet to very dynamic, with a high number of obstacles. Results indicate that A* fails to perform well in dynamic environments and performs nearly optimally in static environments, while APF-D and D* Lite adapt to changes in the environment much better. An experimental study was carried out by 50 independent simulations in static and dynamic environments, where in each simulation, the hybrid solution was evaluated. The APF-D algorithm showed a success rate of 92.8% in highly dynamic environments, which is better than that of A* (58.8%), RRT* (76.8%), and PRM* (70.5%), whereas the success rate of D* Lite was found to be 89.3%. Additionally, APF-D decreased the average time taken for replanning by around 25% in comparison to other graph-based algorithms.