A comprehensive review of path planning algorithms for autonomous navigation

Abstract

• The paper categorizes path planning algorithms into classical, metaheuristic , and AI/ML-based approaches, providing a structured comparison of their strengths, limitations, and applications. • Classical algorithms like Dijkstra’s, A* , and Potential Field Methods are explored in depth, including their deterministic nature, mathematical foundation, and constraints in dynamic or high-dimensional environments. • Nature-inspired algorithms like Genetic Algorithms, Particle Swarm Optimization, Ant Colony Optimization , and Simulated Annealing are highlighted for their flexibility in handling complex, non-linear, and high-dimensional path planning problems. • The paper details the impact of Reinforcement Learning (RL), Neural Networks , and Hybrid AI-Classical systems in enabling real-time, adaptive, and data-driven path planning, especially in unpredictable environments. • Key challenges discussed include high-dimensional search spaces, dynamic environments, trade-offs between optimality and computational efficiency, scalability issues, and handling uncertainty. • Techniques like Rapidly-Exploring Random Trees (RRT) and Probabilistic Roadmaps (PRM) are analyzed for their effectiveness in high-dimensional spaces and applications requiring scalable planning. • Algorithms such as Proximal Policy Optimization (PPO), MAPPO, SAC , and MADDPG are presented as state-of-the-art solutions for single-agent and multi-agent navigation in dynamic settings. • Emphasis is placed on Multi-Agent Path Planning (MAP) techniques and architectures like Centralized Training with Decentralized Execution (CTDE) and Hierarchical RL , which are crucial for collaborative robotics. • Simulation platforms like OMPL, ROS, MoveIt, CARLA , and AirSim are discussed as standard tools for benchmarking and developing path planning systems. • The paper identifies emerging trends such as the integration of AI with classical planners, real-time path planning using edge/cloud computing, semantic-environment understanding , and explainability and ethics in decision-making for autonomous systems. Path planning enables autonomous agents such as robots, self-driving vehicles, and UAVs to navigate from a starting point to a target destination while avoiding obstacles and adhering to operational constraints. As autonomous technologies become more prevalent in real-world applications, the demand for robust, adaptive, and computationally efficient path planning algorithms has intensified. This paper presents a comprehensive review of path planning strategies, focusing on classical, metaheuristic, and AI-based approaches. It explores the challenges posed by dynamic environments, non-holonomic constraints, and varying levels of environmental knowledge. The review also examines the strengths and limitations of each algorithmic category, highlighting their suitability for diverse applications ranging from industrial automation to autonomous navigation. Furthermore, the paper discusses emerging trends, including the integration of machine learning and reinforcement learning techniques, and outlines future research directions aimed at enhancing the adaptability and performance of path planning systems in complex, unstructured environments.