Historical Evolution and Future Optimization of A*-Based Path Planning in Static and Dynamic Environments.

Abstract

Path planning is a crucial component of autonomous navigation, with the A* algorithm serving as a foundational solution since its introduction in the 1960s. This paper reviews the evolution of A*-based methods in both static and dynamic environments, examining their strengths, weaknesses, and improvements. In static settings, techniques such as bidirectional search, quad-tree decomposition, Theta*, and GPU-based parallel processing have notably enhanced computational efficiency and path quality, achieving up to 60% faster planning and 15–25% shorter paths through line-of-sight optimizations. In dynamic environments, methods like D* Lite, velocity obstacle models, and LSTM-based predictive planning have improved real-time adaptability, reducing emergency stops by 65% and re-planning costs by 70%. A comparative analysis of 120 studies highlights key trade-offs: static planners offer 97% reliability but require around 82ms to compute, while dynamic planners achieve faster responses at 28ms but produce paths that are 13% less optimal. Emerging technologies, including quantum computing and neuromorphic chips, promise planning speedups of up to 10,000 times, though challenges remain in balancing speed, adaptability, and path optimality, particularly in complex 3D or highly dynamic environments. This paper systematically examines advancements in algorithmic strategies, hardware accelerations, and new computational paradigms, while addressing persistent limitations in modern path planning.