1. Introduction

The fundamental challenges in mobile robot navigation encompass three pivotal aspects: localization, map construction, and path planning [1]. Localization takes precedence in navigation, with the aim of meticulously pinpointing the robot’s position and orientation within the environment. This precision is of paramount importance for achieving effective navigation and successful task execution. Localization methods leverage data from an array of cutting-edge sensors, including laser rangefinders, visual cameras, GPS, and IMUs, harmoniously amalgamating information from diverse sources to meticulously estimate the robot’s precise position. These advanced sensors provide the robot with an abundant wellspring of real-time data, empowering it to discern its exact location and orientation in the environment. Map construction involves the intricate modeling of objects and structural features within the environment, thereby aiding the robot in comprehending and nimbly navigating its surroundings. Robots gather comprehensive environmental insights through sensor data and deftly employ advanced technologies such as Simultaneous Localization and Mapping (SLAM) to artfully craft map models. Pivotal sensors such as laser rangefinders and visual cameras play a pivotal role in this meticulous map construction process, adeptly perceiving objects and terrain features within the environment. Their acumen facilitates the meticulous creation of map models. These map models may manifest as 2D grid maps, topological representations, or intricate 3D point cloud maps, bestowing invaluable insights into the environmental structure and obstacle layout, thereby illuminating the path planning and navigation strategies. Path planning emerges as the keystone in mobile robot navigation [2]. Drawing from the robot’s profound understanding of the environment map and the precise location of its intended target, path planning algorithms adeptly discern fitting navigation strategies based on distinct objectives and constraints. The outcome is the generation of judiciously selected, cost-effective, and practicable paths. During the path planning and navigation phases, sensors such as laser rangefinders, RGB-D cameras, and Global Positioning Systems (GPS) assume a pivotal role in real-time obstacle detection and the precise determination of the robot’s global position.

1.1. Working Environment Description of the Robot

1.1.1. SLAM Technology

Figure 2. Mobile robot motion navigation process.

In accordance with the varying sensor configurations on board robots, SLAM can be broadly categorized into two major classes: LIDAR-based and vision-based. The extraction of semantic information from visual data are pivotal for intelligent robots to perform higher-level tasks. Consequently, emerging research directions have given rise to Semantic SLAM [4].

Laser-based SLAM has achieved a relatively mature status both in theory and practice. Laser-based SLAM systems such as Gmapping, Hector SLAM, LSD-SLAM, ORB-SLAM, and RTAB-Map, have been effectively applied in both research and industrial domains [5]. In particular, the open-source Cartographer SLAM system from Google has significantly advanced the application of laser-based SLAM to its pinnacle, with these exemplary technologies readily available on GitHub. In engineering applications, it is also possible to simulate laser data for mapping and navigation using RGB-D cameras, although the response time is considerably slower compared to the use of original laser data.

Early research on visual SLAM was constrained by the state of visual computing theory and technology, leading to a relatively slow progression. It was only around 2007 that real-time visual SLAM systems, such as MonoSLAM [6], began to emerge. Subsequently, from around 2013 onward, the open-sourcing of notable solutions like DVO-SLAM [7], RGBD-SLAM V2 [8], ORB-SLAM2 [9], MAPLAB [10], and others has garnered widespread attention and fostered rapid development in the field of visual SLAM. At present, visual SLAM systems are capable of achieving positioning and mapping with an accuracy level of around 5 cm.

1.1.2. Map Model

In the realm of mobile robot path planning research, modeling of the real-world environment is imperative. The scaled maps, topological maps, semantic maps, and behavior maps depicted in Figure 6a–d exemplify the diverse levels of abstraction employed to describe and model the environment. These map types serve as common and distinct strategies for environmental representation, as detailed below:

Figure 6. Map Types: (a) Scale map; (b) Topological map; (c) Semantic Map; (d) Behavioral Map; (e) Satellite map; (f) Indoor Map; (g) Traffic map; (h) Hybrid map.

(1)

Scale Map: Also known as a measurement map, the metric map typically relies on grids or pixels to partition the environment into a series of discrete units. Each unit signifies a state and can represent either free space or obstacles. The metric map can express the physical dimensions of the real world. It encompasses various types such as occupancy grid maps, depth maps, and probabilistic maps.

(2)

Topological Map: The description of a robot’s location often does not involve the actual physical dimensions of the world. Instead, it leverages connectivity and distance relationships among different locations to depict the robot’s position. This type of map comprises two main categories: node-based and edge-based topological maps. Topological maps find utility in scenarios where the environment exhibits certain regularities, as seen in city road networks.

(3)

Semantic Map: A semantic map is typically feature-based, wherein environmental entities are labeled to enhance the robot’s perception and understanding. This labeling facilitates heightened autonomy and intelligence by imparting a sense of meaning to the robot’s perception of its surroundings.

(4)

Behavior Map: Employed to represent a robot’s behavior and task information, the behavior map outlines the actions a robot needs to undertake to accomplish specific tasks. Behavior maps are often generated using robot control systems and planning algorithms, offering utility across decision-making, execution, and autonomous learning applications.

Various map types have emerged to cater to diverse application environments and data sources. The map types shown in Figure 6e-h are designed to address a variety of application scenarios and data sources and are well suited to meet the complex needs of mobile robot navigation.

(1)

Satellite Map: Leveraging satellite imagery, satellite maps encapsulate ground landscapes to vividly portray actual terrains and natural features such as mountains, forests, lakes, and rivers.

(2)

Indoor Map: Specially tailored for navigation within confined environments, indoor maps cater to spaces like shopping complexes, airports, museums, and medical centers. They commonly incorporate intricate floor plans for varying levels, annotated landmarks, directional cues, designated paths, and the precise locations of diverse amenities.

(3)

Traffic Map: The domain of traffic maps encompasses roads, traffic signs, signals, and other vehicular infrastructure. Robots adeptly employ these vital data to chart optimal routes, ensuring adherence to traffic regulations and road etiquettes for both safe and efficient navigation.

(4)

Hybrid Map: Bridging the attributes of diverse map genres, hybrid maps wield the potential to offer a comprehensive and precise repository of geographic information. These maps are particularly invaluable for navigating complex terrains, facilitating intricate path planning. For instance, integrating a metric map with a topological counterpart can yield precise robot positioning and navigation. Similarly, coupling a semantic map with a behavior map expedites task planning and execution.

As delineated in Table 3, different map types are tailored to diverse application scenarios, equipping robots with varying tiers of environmental insights. Quite often, achieving heightened accuracy in path planning necessitates a synergistic integration of multiple map categories.

Table 3. Analysis of robot work map.

Types	Advantages	Disadvantages	Applications	Results
Scale Map	Simplifies construction; supports various navigation algorithms.	Mapping precision is hard to measure; struggles with unstructured environments.	Robot path and motion planning in static settings.	[25]
Topological Map	Handles complex environments; suitable for large-scale areas.	Difficulty representing detailed information; manual topological definitions needed.	Highways traffic management systems; large-scale robot formations.	[26]
Semantic Map	Describes object semantics; aids advanced robot tasks.	Requires advanced sensors and algorithms, struggles with dynamic objects.	Semantic setting modeling and robot speech interaction.	[27]
Behavior Map	Provides essential behavioral information; supports autonomous learning.	High construction and maintenance costs, limited accuracy and scope.	Autonomous planning, learning, and multitasking for robots.	[28]
Satellite Map	Offers genuine terrain and natural features.	Maps may lack real-time accuracy and updates.	Outdoor navigation and exploration for robots.	[29]
Indoor Map	Facilitates indoor navigation and localization.	Costly map creation and maintenance, necessitating real-time updates.	Indoor robot.	[30]
Traffic Map	Improves traffic efficiency, safety, and energy conservation.	Challenges in data acquisition and high maintenance costs; complex systems.	Security patrols and logistics robots.	[31]
Hybrid Map	Integrates multiple map types for comprehensive environmental data.	Persistent high costs in map creation and maintenance.	Autonomous vehicles and intelligent inspection robots.	[32,33]

1.2. Path Indicators

The path planning for mobile robots typically entails the formulation of pertinent objective functions aligned with distinct task requisites or scenario preferences. Such functions encompass factors including path length, turning angles, energy consumption, and safety considerations, among others. These models can manifest as single-objective or multi-objective frameworks. For example, Xiang et al. [36] employed the minimization of path length as their optimization objective. Li et al. [37] factored in obstacles and ground friction, thereby translating a multi-criteria path planning problem into the context of low-energy consumption path planning.

When dealing with Multi-Objective Path Planning (MOPP), researchers commonly utilize Pareto optimization or weighted aggregation methods. The Pareto optimization approach generates a set of Pareto front solutions by reconciling multiple conflicting objective functions. This set serves as a basis for decision-makers to make informed choices. For example, Yu et al. [38] focused on minimizing path length while enhancing safety as objective functions. They utilized an enhanced version of the artificial bee colony algorithm to search for the Pareto optimal solution set for these functions. In response to challenges such as the high computational complexity of Pareto algorithms, difficulties in handling highly nonlinear problems, and complexities in solving non-convex problems, evolutionary methods have emerged. These include the NSGA-II algorithm [39], NSGA-III algorithm [40], SPEA2 algorithm [41], and multi-objective particle swarm optimization [42]. On the other hand, the weighted aggregation method is rooted in single-objective optimization. It allows for the assignment of weights to different indicators, enabling a comprehensive evaluation tailored to specific application requirements.

3. Single-Agent Path Planning Algorithm

3.1. Classical Class Algorithms

3.1.1. Graph Search Algorithms

Graph search algorithms employ a graph data structure to represent the environment. In this representation, nodes correspond to potential robot positions, while edges represent permissible movements between these positions. Throughout the search process, these algorithms consider environmental obstacles, the dynamic constraints of robots, and the cost associated with traversing a path. Path optimization aims to determine the best path, whether it is the shortest, most cost-effective, or meets other optimization criteria. In 1956, E.W. Dijkstra introduced the Dijkstra algorithm [51], which is capable of computing the shortest path from a starting node to any other node in a weighted directed or undirected graph. To enhance the search speed of the Dijkstra algorithm, Hart et al. [52] proposed the A* algorithm that employs heuristic information to guide the search process. The A* algorithm takes into account the cost to reach each node from the starting node and the estimated cost to reach the goal node. In response to issues such as low search efficiency and high memory overhead in the traditional A* algorithm, various classic variants and improvements of A* have emerged, including Weighted A* (WA*) [53], Adaptive A* (AA*) [54], Theta* [55], and Jump Point Search (JPS) [56], as depicted in Table 7 and Figure 8. Pu et al. [57] introduced a dual adaptive A* algorithm, which encompasses adaptive multi-objective heuristic functions and adaptive node expansion strategies. Lai et al. [58] proposed a centrally constrained adaptive A* algorithm that assigns dynamic weights to nodes at different positions and incorporates adaptive thresholds into the heuristic function to enhance adaptability. The Theta* algorithm, initially introduced by Daniel et al. [59], permits path searches along arbitrary angles, and subsequently marked the more efficient Lazy-Theta* [60]. Moreover, Luo et al. [56] applied the variable step-size concept of the Theta* algorithm to the JPS algorithm, further improving the path quality and smoothness of the traditional JPS.

Figure 8. A* Evolution.

Table 7. An improved version of the A* algorithm.

Algorithm	Time	Characteristics	Research
WA*	-	Fine-tuned heuristic weight factor to adjust the algorithm’s emphasis on heuristic estimates and path costs during exploration.	[53] [58]
AA*	-	Updated heuristic function based on the actual exploration path costs to guide the search direction more accurately, thereby enhancing search efficiency.	[54] [58]
Theta*	2010	Implemented improvements upon the A* algorithm to reduce path deviations and eliminate the need for re-exploring visited nodes.	[55] [59]
Lazy-Theta*	2010	Computation of path cost is performed only when genuinely required, resulting in an enhancement of search efficiency.	[60]
JPS	2011	Leveraged map symmetry and accessibility to bypass numerous unnecessary nodes, consequently reducing search overhead.	[56]
D*	1994	A self-correcting path planning algorithm evolved from the A* algorithm, applicable to dynamic environments.	[61]
LPA*	2001	Employed two priority queues to manage current path estimates and enhanced path information, adjusting paths incrementally based on cost and heuristic information to achieve optimal routes.	[62]
D* Lite	2002	Built upon the LPA* approach, incorporated ideas of incremental path updating and repairing to enable efficient path adjustments in dynamic environments.	[63]
TLPA*	2013	Integrated the concept of suboptimal constraints into the LPA* framework, facilitating a reduction in state expansions.	[64]
TD* Lite	2013	Introduced a suboptimal re-planning algorithm for navigation, combining TLPA* truncation rules with D* Lite principles.	[64]
MOD* Lite	2016	A multi-objective incremental search algorithm.	[65]
MOPBD*	2022	Multi-objective incremental search algorithm with more efficient scaling of nodes	[66]

3.1.2. Random Sampling Algorithms

In 1998, LaValle introduced the Rapidly-exploring Random Tree (RRT) [67]. The core idea behind RRT involves exploring paths in unknown environments through random sampling and gradual tree expansion. However, this approach cannot guarantee the discovery of the optimal path and is susceptible to biases induced by target point preferences and environmental attributes. For instance, in environments abundant with obstacles or constrained passages, the algorithm’s convergence rate is slow, leading to a sharp decline in efficiency. Researchers have continually endeavored to optimize the RRT algorithm. Table 8 highlights several variants of the current RRT algorithm, such as RRT-Connect [68], RRT* [69], RRT*-Smart [70], RRT*-Connect [71], and Informed RRT*-Connect [72].

Table 8. RRT algorithm variants.

Algorithm	Time	Characteristics	Research
RRT-Connect	2000	Finding a feasible path to connect two trees using two RRT trees growing and joining step by step for continuous spaces.	[68,73]
RRT*	2011	Connect the tree nodes through the minimum spanning tree algorithm and iteratively optimize to find a better path.	[69,74,76]
RRT*-Smart	2012	Intelligent sampling strategy is introduced to dynamically adjust the distribution of sampling points according to the structure of the tree and the location of the target point to accelerate the path search.	[70,77]
RRT*-Connect	2015	The iterative process of RRT-Connect algorithm is optimized to improve the path quality.	[71,78]
Informed RRT*-connect	2020	Heuristic information is introduced to improve the RRT*-Connect algorithm, which makes the path planning more efficient and better quality.	[72]

In 1996, the Probabilistic Roadmap Method (PRM) was introduced by Kavraki et al. [79]. This method involves sampling in the configuration space, performing collision detection, and testing connectivity to effectively represent the connectivity of path graphs. It addresses the challenge of constructing valid paths in high-dimensional spaces. The primary advantage of PRM is that its complexity is mainly influenced by the difficulty of pathfinding, showing relatively minor correlation with the scale of planning scenarios and the dimensionality of configuration space. However, in cases where paths need to traverse dense obstacles or narrow passages, the efficiency of PRM may decrease. To overcome these limitations, researchers have conducted extensive studies to enhance its performance, resulting in various variants such as PRM* [80], Lazy PRM [81], PRM-D* [82], among others as illustrated in Table 9.

Table 9. PRM algorithm variants and improvements.

Algorithm	Time	Characteristics	Research
PRM*	2010	A roadmap is constructed using an incremental approach that continuously improves the quality of the paths using a shortest path search algorithm as it samples and connects nodes.	[80]
Lazy PRM	2000	Minimizes the number of collision checks performed during planning, thus minimizing the planner’s runtime.	[81]
HPPRM	2020	Improved adaptability of the algorithm to multi-class complex environments.	[83]
Fuzzy-PRM	2019	Achieved dual metric optimization of path length and smoothness.	[84]
PRM-D*	2023	Dynamically adapts to environmental changes and unknown dynamic obstacles during the planning process.	[82]

3.1.3. Potential Field Algorithms

In 1986, the Artificial Potential Field (APF) method was introduced by Platonov [85]. This approach is based on the concept of applying a virtual force field to the robot, where the robot is moved toward the target point due to the combined effects of attraction from the target and repulsion from obstacles. The existing literature has predominantly focused on addressing the local minimum problem of APF by optimizing and enhancing the attraction and repulsion potential functions or introducing additional constraints. Fan et al. [86] applied APF to underwater robots and proposed a method involving regular hexagon guidance to improve path planning and prevent falling into local minima.

In 1993, the Elastic Band Algorithm (EBA), introduced by Quinlan et al. [91], serves as a method for both path planning and motion control of mobile entities. Its fundamental premise revolves around confining the robot’s trajectory within a band-like region known as the “elastic band.” This strategic confinement within the elastic band effectively prevents collisions with obstacles [92]. Following its inception, the EBA framework underwent extensions to encompass scenarios involving nonholonomic motion and systems with multiple degrees of freedom. However, these adaptations did not comprehensively integrate time and dynamic constraints [93]. It was only through the subsequent development of the Time-Elastic Band (TEB) algorithm by Rosmann et al. [94] that the integration of time-based information enhanced the elastic band’s efficacy. This allowed for the accommodation of dynamic constraints and direct trajectory adjustments, thereby rendering it applicable to both holonomic and nonholonomic mobile robots. Subsequent scholars have predominantly directed their efforts toward refining the traditional TEB algorithm by addressing dynamic time parameter adjustments, trajectory smoothing, motion constraints, multi-objective optimization, and dynamic environmental considerations. 

In 1991, the Vector Field Histogram (VFH) method, introduced by Borenstein et al. [97], provides a technique for mobile robot path planning and obstacle avoidance. It utilizes laser radar or other perceptual devices to collect environmental data and represents the surroundings as a two-dimensional vector field. By calculating obstacle density in various directions within the vector field, VFH generates a histogram to guide the robot’s path selection. The VFH algorithm boasts several advantages, including high reliability, computational efficiency, and robustness. However, this algorithm is not without limitations; for instance, it can often become trapped in local minima within narrow areas. Consequently, numerous scholars have proposed solutions to address this concern.

3.2. Intelligent Optimization Class Algorithms

Intelligent optimization algorithms are stochastic methods inspired by natural phenomena observed in biological populations. Based on their functionalities and design principles, these algorithms can be categorized into evolutionary algorithms, swarm intelligence algorithms, and bio-inspired algorithms.

(1)

Evolutionary Algorithms: Evolutionary algorithms simulate the process of biological evolution, incorporating operations such as selection, crossover, and mutation to search for optimal solutions within solution spaces. Prominent algorithms in this category include genetic algorithms and evolution strategies.

(2)

Swarm Intelligence Algorithms: Swarm intelligence algorithms emphasize collaboration and communication among individuals in a group. They utilize information sharing and coordination among members to collectively solve problems. Notable algorithms in this category include particle swarm optimization and ant colony optimization.

(3)

Bio-inspired Algorithms: Bio-inspired algorithms mimic the behavior, structures, and mechanisms of living organisms to address problems. These algorithms draw inspiration and principles from biology. Representative examples are immune algorithms and artificial fish swarm algorithms.

From the progression of path planning research depicted in Figure 9, it is evident that mainstream swarm intelligence algorithms are applied to problem-solving in path planning. However, variations exist in algorithm performance and researcher preferences.

Figure 9. Proportion of published papers on various algorithms from 2010 to 2022.

3.2.1. Ant Colony Optimization

Ant Colony Optimization (ACO), introduced by Italian scholar M. Dorigo [103] in 1992, has found notable applications in the field of mobile robot path planning due to its features of positive feedback, distributed computation, and robustness. Addressing the inherent issues of slow convergence and susceptibility to local optima in the basic ACO, numerous researchers have undertaken optimizations and improvements in the structural design, parameter selection, and optimization of pheromones. Wang et al. [104] introduced an uneven distribution of initial pheromones and established an iterative threshold, effectively reducing the initial blind search of ants and enhancing the algorithm’s search capability. Jiao et al. [105] employed adaptive state transition and pheromone update strategies, ensuring the relative importance of pheromone intensity and heuristic information during iterations. This enhancement has, to some extent, improved the algorithm’s adaptability to different environments and its ability to escape local optima. Akka et al. [106] refined the state transition formula, favoring neighboring nodes with more exits as the next choice. They introduced segmented multi-heuristic functions and implemented rewards and penalties for optimal and worst paths, thereby promoting diversity in search and mitigating the impact of ineffective pheromones

Traditional ACO mainly addresses single-objective optimization problems. However, multi-objective ant colony algorithms can handle conflicts among multiple optimization objectives. Li et al. [107] introduced an improved heuristic function and pheromone update strategy based on factors such as path length, number of turns, and smoothness of slope. They comprehensively computed the transfer probability, guiding ants towards paths with optimal overall performance. 

3.2.2. Particle Swarm Optimization

Kennedy et al. [117] introduced Particle Swarm Optimization (PSO) in 1995, drawing inspiration from the behavior of biological collectives. PSO is a cluster optimization algorithm that simulates the flight of particles in a search space to discover optimal paths. Each particle represents a potential path solution and continuously adjusts its position based on its own experience and information from neighboring particles during the search process. This collaborative and information-sharing approach enables the Particle Swarm Optimization algorithm to effectively discover collision-free and efficient paths in the context of path planning. Nonetheless, it faces challenges such as susceptibility to local optima, sensitivity to parameters, and limitations in handling high-dimensional problems. To address these issues, numerous scholars have proposed enhancement strategies. The selection of PSO’s parameters significantly impacts its performance and outcomes. Inertia weight has the most significant influence on particle swarm algorithm performance. Therefore, research in this domain is extensive, encompassing fixed inertia weights [118], time-varying adaptive inertia weights [119], linearly decreasing inertia weights [120], and fuzzy logic-controlled inertia weights [121]. Improvements to other parameters include dynamic learning factors [122] and adaptive adjustment of acceleration coefficients [123]. Apart from parameter optimization, auxiliary techniques can be introduced to enhance PSO’s population diversity and mitigate premature convergence.

Over the past decade, the Multi-Objective Particle Swarm Optimization algorithm (MOPSO) [42] has been introduced, allowing for the simultaneous optimization of multiple conflicting objectives. Xu et al. [128] proposed an enhanced MOPSO for path planning of unmanned aerial vehicles over known static rugged terrains. This approach considers collision-free path metrics such as height, length, and angle-of-change rate minimization. The solutions provided by MOPSO typically form a set of optimal solutions known as the Pareto optimal solution set.

3.2.3. Genetic Algorithm

The Genetic Algorithm (GA), proposed by Holland in 1975 [134], emulates the genetic, selection, and crossover processes observed in natural populations to search for optimal solutions. However, Forrest et al. [135] have noted that while Standard Genetic Algorithms (SGA) possess merits such as flexible search capabilities and strong scalability, they also exhibit shortcomings including inferior individual convergence, sluggish convergence speed, susceptibility to local optima, and limited population diversity. In response to these limitations, researchers have introduced novel strategies to enhance the performance of GAs and improve the quality of generated paths. In an effort to overcome issues like premature convergence, low-quality convergence paths, inadequate population diversity, and the challenge of escaping local optima in the realm of robot path planning, Hao et al. [136] have proposed the Multi-Population Migration Genetic Algorithm. This innovative approach aims to leverage the strengths of the GA while mitigating its weaknesses.

3.3. Artificial Intelligence Class Algorithms

3.3.1. Neural Network Algorithm

Neural networks (NN), pioneered by McCulloch and others in 1943, represent a computational paradigm rooted in mathematical formulations and threshold logic algorithms. In contemporary times, NN has found widespread utility across domains such as artificial intelligence and machine learning [147]. Differing from conventional path planning approaches, neural network algorithms, by means of learning and optimization, excel at enhancing the precision and efficiency of path planning in intricate and dynamic settings. This superiority is rooted in the neural networks’ capability to extract pivotal information from perceptual inputs encompassing environmental maps, sensor data, robot status, task requisites, and other multifaceted data dimensions. Through the processes of deep learning and training, neural networks can autonomously identify and comprehend this information, proficiently integrating it into the path planning process. This leads to path planning that is more intelligent and adaptable, ultimately yielding heightened accuracy and robustness in path planning outcomes. Huang et al. [148] have introduced an algorithm that integrates an enhanced self-organizing map NN with a novel velocity synthesis technique for dynamic task allocation and path planning involving multiple autonomous underwater robots. Nevertheless, it is important to acknowledge that NN is not without limitations. Navigating through unstructured and complex environments poses a significant challenge for robots. Through NN, specific types of robots can acquire knowledge about optimal paths to traverse in such intricate terrains [149].

3.3.2. Fuzzy Logic Algorithm

The Fuzzy Logic (FL) algorithm, proposed by Zadeh in 1965, has been widely applied across various research and development domains, including data classification, decision-making, image processing, and pattern recognition [166]. Fuzzy logic algorithms play a pivotal role in enhancing adaptive path planning for mobile robots in the domains of navigation and path planning [167]. This process involves the application of fuzzy sets and fuzzy rules to input data to effectively handle fuzziness and nonlinear relationships. It encompasses the mapping of sensor data, such as distance and velocity, to fuzzy sets, followed by the utilization of a series of fuzzy rules to interpret these fuzzy inputs. Consequently, this process generates corresponding fuzzy outputs, detailing the navigation actions that the robot should undertake. These actions may include obstacle avoidance, deceleration, or steering, with each action accompanied by a membership degree reflecting its confidence level. Through this approach, fuzzy logic algorithms comprehensively account for environmental fuzziness and uncertainty, enabling robots to intelligently adapt to a diverse range of navigation scenarios and produce path planning solutions that are more contextually relevant and applicable.

Fuzzy Logic (FL) presents inherent limitations that must be addressed for effective integration in mobile robot path planning. These limitations encompass factors such as the reliance on expert knowledge for defining fuzzy inference rules, the intricacies of optimizing paths based on these rules, the potential expansion of rule sets with increasing obstacle complexity, and the adaptability of rules to changing environments. To overcome these challenges and enhance FL’s performance, researchers often combine FL with other algorithms, resulting in innovative hybrid approaches. Zagradjanin et al. [177] devised a hybrid approach that combined the D* lite algorithm for global path planning and FL for local path planning. This integration was further extended to multi-robot coordination within complex environments. 

4. Multi-Agent Path Planning Algorithms

In comparison to SAPF, MAPF introduces a higher degree of complexity as it necessitates the consideration of collaborative interactions among multiple robots, ensuring their secure task completion. The extension of the problem from SAPF to MAPF introduces the concept of collaborative planning, thereby accentuating its inherent challenge. The resolution of MAPF problems typically necessitates the integration of appropriate path planning algorithms and conflict resolution strategies to cater to the path planning requirements. Presently, scholars both domestically and internationally have delved deeply into the realm of single-robot path planning, yielding a substantial body of research achievements. These advancements in the field of single-robot navigation have consequently laid a robust foundation for subsequent inquiries into Multi-Agent Path Finding (MAPF) technology. In recent years, the collaborative efforts of various planning algorithms, collision avoidance techniques, and multi-objective optimization studies have synergistically propelled progress in the MAPF domain. Categorized based on the problem in [188], MAPF can be classified into centralized and distributed paradigms, and the characteristics of the two types of methods are shown in Table 12.

Table 12. Comparison of MAPF Algorithms.

MAPF	Advantages	Disadvantages
Centralized	Centralized planner for all agents in static or small-scale environments, fast and high-quality.	As the number of agents and environmental complexity increase, replanning becomes time-consuming
Distributed	Independent actions based on current observations, scalable to large-scale environments, and real-time path replanning.	Slower planning and learning in small, static environments compared to centralized algorithms.

4.1. Centralized Planning

4.1.1. Problem Description

The study of Centralized Multi-Agent Path Finding (CMAPF) is closely aligned with domains such as Intelligent Unmanned Warehousing [189] and Intelligent Transportation [190]. The research not only encompasses the challenges of obstacle avoidance and optimal path selection for individual robots, but also delves into the intricacies arising from various motion conflicts that impact both the efficiency of multi-robot task execution and the success rate of path planning [191]. The escalation of motion conflicts among robots is directly correlated with the number of robots, and a larger scales of robotic presence correspondingly amplifying the algorithmic complexities within the solution space [192,193].

Table 13. CMAPF conflict types.

Conflict Type		Recognition Methods	Constraints Type
Basic Conflicts	Node Conflict	Two robots occupy the same grid center at the same time step	Obstacle constraints
	Alignment Conflict	Two robots exchange positions within a time step	Obstacle constraints
Deep Conflicts	Placeholder conflict	Robot path step is larger than conflict time step and solution space exists	Length Constraints
	Target Conflict	The robot path step is much larger than the conflict time step.	Length constraints
	Blocking conflicts	When two or more robots try to pass through a narrow passage in opposite directions	Range Constraints
	Cycle conflict	When each robot moves to a vertex previously occupied by another robot, a “rotating loop” pattern is formed within the same time step.	Range Constraints

4.1.2. Solution

In addressing the challenges posed by motion conflicts, Huang et al. [194] proposed an improved Ant Colony Optimization (ACO) algorithm that relies on parameter optimization and vertex conflict resolution. They also devised strategies for conflict prediction and resolution, effectively mitigating vertex conflicts and enhancing the overall reliability of multi-agent systems. In a similar vein, Wen et al. [195] took into consideration various constraints and the distinctive motion characteristics present in robotic environments. They introduced the CL-MAPF (Multi-Agent Path Finding for Car-Like robots) algorithm, which was designed to reduce conflicts between robots’ movements and enhance the efficiency of the algorithm. To further amplify the efficiency of resolving issues within CMAPF scenarios and to augment the success rate of planning, researchers in recent years have introduced approaches that are more finely attuned to the specific concerns of MAPF. Notably, techniques such as Priority Planning (PP) [196] and Conflict-Based Search (CBS) [191] have emerged, as comprehensively outlined in Section 5.1.

Among the various methods, the Priority Planning (PP) algorithm has gained substantial traction as a preferred approach among researchers. Cap et al. [196] introduced a class of multi-robot path planning algorithms based on Prioritized Planning (PP), along with several rules for determining priorities. Wang et al. [197] proposed a method that integrates priority assignment and path planning to achieve optimal execution cost and time for a group of robots.

4.2. Distributed Planning

4.2.1. Problem Description

Distributed Multi-Agent Path Finding (DMAPF) constitutes a critical challenge within the realm of multi-robot collaborative tasks, addressing the intricacies of autonomous robot task planning and cooperation. DMAPF decentralizes computational tasks and decision-making across individual robots, thereby diminishing the burden on central computation and mitigating communication overhead [207]. This paradigm splits the robot’s motion navigation quandary into two distinct phases: the path planning stage, where each robot independently devises an optimal path; and the velocity planning stage, wherein each robot circumvents collisions with both obstacles and fellow robots. In the velocity planning phase, following the acquisition of conflict-free paths through SAPF algorithms during the path planning stage, real-time monitoring and identification of potential conflict types become essential for implementing appropriate conflict resolution strategies.

4.2.2. Solution

Diverse Modes of Information Sharing in Distributed Multi-Robot Path Planning vary according to the scope and methodology of information exchange. These modes encompass localized information sharing, global information sharing, and hybrid information sharing, each tailored to distinct collaborative scenarios [198,199,200,201,202,203,204,205,206,207].

(1)

In the context of localized information sharing, robots interact exclusively with their immediate neighbors. Amoolya et al. [213] and Lijina et al. [214] employed WiFi and Bluetooth technologies, respectively for localized information exchange. Liu et al. [215] proposed a decoupled multi-robot path planning technique, blending an enhanced ant colony algorithm and distributed navigation. Global paths are determined via Ant Colony Optimization (ACO), while local navigation relies on a “first-come, first-served” collision avoidance strategy. Chang et al. [216] addressed the challenge of unknown environments with static and dynamic obstacles, introducing a layered multi-robot navigation and formation approach driven by deep reinforcement learning and distributed optimization. This hierarchical framework empowers each robot to navigate to a global goal based on its local perception within the unfamiliar environment, resulting in optimal formations with minimal communication.

(2)

In the context of global information sharing, all robots access global information to attain optimal solutions. Dong et al. [217] proposed a Collaborative Complete Coverage Path Planning (CCPP) algorithm for multiple agents in unknown environments. Causa et al. [218] devised a multi-UAV path planning algorithm catering to scenarios with heterogeneous global navigation satellite system coverage. Addressing the issue of unnecessary detours due to dynamic obstacle avoidance through re-planning, Wang et al. [219] introduced the Globally Guided Reinforcement Learning (G2RL) method, addressing multi-robot path planning in a fully distributed reactive manner.

(3)

Hybrid information sharing involves establishing local information sharing regions around each robot, interconnected to form a global information sharing network. Each robot considers neighbor information while also accessing global data to attain an optimal global solution. To address dynamic multi-robot path planning [220,221], an adaptive hybrid algorithm was introduced. This algorithm ensures safety in unknown dynamic environments through dynamic obstacle avoidance rules and enables collaborative obstacle avoidance within the motion conflict range using proposed priority obstacle avoidance rules. Fan et al. [222] introduced a method utilizing Received Signal Strength Indicator (RSSI) to gauge distributed robot motion conflicts. In case of a conflict, one robot proceeds, and upon reaching an RSSI threshold or designated avoidance wait-time, the other robot navigates.

 

This entry is adapted from the peer-reviewed paper 10.3390/machines11100980