Navigating the Landscape of Mobile Robot Path Planning: A Comprehensive Review

By Soham NandiReviewed by Susha Cheriyedath, M.Sc.Oct 27 2023

In a review published in the journal Machines, the authors conducted a comprehensive study on mobile robot path planning. They covered environmental modeling, provided open-source map datasets, and analyzed evaluation metrics.

Background

Mobile robot path planning involves designing optimal routes in various environmental conditions. While autonomous navigation solutions exist, there is a lack of comprehensive examinations of critical path-planning technologies for both single-robot and multi-robot scenarios. These technologies encompass aspects like environmental modeling, path quality evaluation, and planning techniques.

The gaps in current research include an absence of a systematic examination of path planning technologies, limited differentiation between single-robot and multi-robot path planning, and the lack of open-source map datasets and comprehensive evaluation metrics for path planning. Additionally, there is a need to categorize and compare path-planning algorithms.

The authors of the present study addressed these gaps by providing a detailed exploration of path-planning techniques, introducing various environmental mapping methods, and offering open-source map datasets. 

Mobile Robot Navigation

Mobile robot navigation is a critical field involving the development of robots that can autonomously navigate diverse environments. Key components include:

• Localization: Precisely determining a robot's position and orientation using advanced sensors like laser rangefinders, cameras, global positioning systems (GPS), and inertial measurement units (IMUs).
• Map Construction: Creating detailed models of the environment using sensors like laser rangefinders and cameras to perceive objects and terrain features.
• Path Planning: Algorithms determining the best navigation strategies based on objectives and constraints, ensuring cost-effective and practical paths. Sensors like laser rangefinders, cameras, and GPS aid in obstacle detection and global positioning.

Recent progress in mobile robot navigation technology includes various map types and path planning approaches, optimization of objectives (e.g., path length, energy consumption, safety), and standardized testing protocols like Single Agent Path Planning and Multiple Agent Path Planning test maps. The customization of path planning for specific robots and scenarios is crucial.

Single-Agent Path Planning Finding (SAPF)

The authors discussed intelligent optimization algorithms used for mobile robot path planning. These algorithms were inspired by natural phenomena and can be categorized into three main types: Evolutionary Algorithms, Swarm Intelligence Algorithms, and Bio-inspired Algorithms. The most prominent algorithms within this domain are Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), and Genetic Algorithms (GA).

• ACO is introduced as a method inspired by the behavior of ants in finding paths. The researchers enhanced traditional ACO by introducing uneven initial pheromone distributions, adaptive state transitions, and improved state transition formulas. Additionally, multi-objective ACO algorithms were developed to handle conflicts among multiple optimization objectives.
• PSO simulated the collective behavior of particles to find optimal paths. Researchers focused on optimizing parameters like inertia weight, introducing dynamic learning factors, and using auxiliary techniques to enhance population diversity and mitigate premature convergence. Multi-objective PSO (MOPSO) algorithms were introduced to simultaneously optimize multiple conflicting objectives.
• GA simulated genetic processes to search for optimal solutions. Researchers addressed issues like premature convergence, slow convergence, and susceptibility to local optima. They introduced Multi-Population Migration Genetic Algorithms and explored visual space enhancement for improved performance.

Neural networks, deep learning, and reinforcement learning were employed for path planning. Researchers utilized deep learning techniques to improve environmental perception and adaptability. Reinforcement learning was used to enhance navigation and path planning in dynamic environments. 

Fuzzy Logic algorithms were used for adaptive path planning. These algorithms considered fuzziness and uncertainty in sensor data and environmental conditions. The researchers employed fuzzy logic for obstacle avoidance, deceleration, and steering.

Multi-Agent Path Finding (MAPF)

MAPF algorithms were used to plan the paths of multiple robots collaboratively. MAPF introduced complexity compared to SAPF as it involved considering interactions among multiple robots. The authors categorized MAPF into centralized and distributed planning paradigms, highlighting their characteristics.

• Centralized Planning
  • Problem Description: Centralized MAPF (CMAPF) dealt with challenges in obstacle avoidance, optimal path selection, and motion conflicts among multiple robots. As the number of robots increased, algorithmic complexities grew due to escalating motion conflicts.
  • Solution: Various algorithms were proposed to address motion conflicts. Notable approaches included Priority Planning (PP) and Conflict-Based Search (CBS), which assigned priorities to robots and resolved conflicts accordingly. These methods enhanced efficiency and performance in multi-agent systems.
• Distributed Planning
  • Problem Description: Distributed MAPF (DMAPF) decentralized computational tasks and decision-making among individual robots to reduce central computation and communication overhead. It involved path planning and velocity planning phases, where robots independently plan paths and navigate to avoid collisions.
  • Solution: Several strategies were presented to tackle DMAPF challenges. These included heuristic MAPF algorithms, ant colony algorithms, deep reinforcement learning, and artificial bee colony approaches. Information-sharing modes can be localized, global, or hybrid, depending on the collaborative scenario and requirements.

Conclusion

The paper provided a comprehensive overview of mobile robot path planning, encompassing both SAPF and MAPF. It distinguished itself by incorporating recent literature, covering a broad research scope, and discussing conventional and artificial intelligence methodologies in path planning.

In SAPF, the paper categorized algorithms into classical, bio-inspired, and artificial intelligence categories. It detailed classical algorithms like graph search, random sampling, and potential field-based approaches. Bio-inspired algorithms included ACO, PSO, and GA. For MAPF, the paper differentiated between centralized planning, which focused on conflict decoupling, and distributed planning, which emphasized efficient task execution. It provided a comprehensive comparison of the pros and cons of common optimization algorithms in SAPF and MAPF.

The authors believe that path planning will continue to be a crucial concern in robotics, and advancements in these areas will play a pivotal role in enabling more sophisticated and capable mobile robot systems.