A Comprehensive Review of the A<sup>*</sup> Algorithm: Evolution, Applications, and Future Trends in Path Planning

Despite being a fundamental problem to autonomous robotics and intelligent navigation systems, path planning is still a challenge. The A* algorithm is often used among search-based techniques for optimal search performance, as it's a tradeoff of computation. The above techniques have been developed for various applications as many versions of A* Dynamic A* (D*), D* Lite, Hybrid A*, and Anytime A* are suggested to deal with dynamic environments, real-time constraints, and kinematic restrictions. This paper comprehensively and structurally reviews the A* algorithm and its major extensions, encompassing historical development, methodological improvements, practical applications, and upcoming research trends. This review differs from the descriptive surveys conducted in this book, comparing classical and hybrid approaches (to include semi-quantitative analysis) on different computational complexity, re-planning mechanisms, scalability, and applicability to robotic systems. It lays out the current challenges, implementation frameworks, and practical libraries as well, giving a comprehensive view linking theory evolution with real-world applications with robots. The goal of the review is to be a reference framework for researchers concerned with how this trend of A*-based planning is transforming into dynamic, cooperative and intelligent navigation systems.