Path-Planning Approaches for Multiple Mobile Robots

Version	Summary	Created by	Modification	Content Size	Created at	Operation
1		Shiwei Lin	--	4169	2022-09-14 11:25:07	\|
2	format correct	Vivi Li	-21 word(s)	4148	2022-09-15 04:35:59	\|

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

Numerous path-planning studies have been conducted due to the challenges of obtaining optimal solutions. The multi-robot path-planning approaches have been classified as classical approaches, heuristic algorithms, bio-inspired techniques, and artificial intelligence approaches. Bio-inspired techniques are the most employed approaches, and artificial intelligence approaches have gained more attention.

multi-robot path planning bio-inspired algorithms robots

1. Introduction

Robot applications have been widely implemented in various areas, including industry ^[1], agriculture ^[2], surveillance ^[3], search and rescue ^[4], environmental monitoring ^[5], and traffic control ^[6]. A robot is referred to as an artificial intelligence system that integrates microelectronics, communication, computer science, and optics ^[7]. Due to the development of robotics technology, mobile robots have been utilized in different environments, such as Unmanned Aerial Vehicles (UAVs) for aerospace, Automated Guided Vehicles (AGVs) for production, Unmanned Surface Vessels (USVs) for water space, and Autonomous Underwater Vehicles (AUVs) for underwater.

To perform tasks, employing a set of vehicles cooperatively and simultaneously has gained interest due to the increased demand. Multiple robots can execute tasks in parallel and cover larger areas. The system continues working even with the failure of one robot ^[8], and it has the advantages of robustness, flexibility, scalability, and spatial distribution ^[9]. Each robot has its coordinates and independent behavior for a multi-robot system, and it can model the cooperative behavior of real-life situations ^[10]. For reliable operation of the robot, the robotics system must address the path/motion planning problem. Path planning aims to find a collision-free path from the source to the target destination.

Path planning is an NP-hard problem in optimization, and it involves multiple objectives, resulting in its solution being polynomial verified ^[11]. The robots are aimed to accomplish the tasks in the post-design stage with higher reliability, higher speed, and lower energy consumption ^[12]. Task allocation, obstacle avoidance, collision-free execution, and time windows are considered ^[13]. Multi-robot path planning has high computational complexity, which results in a lack of complete algorithms that offer solution optimality and computational efficiency ^[14].

Substantial optimality criteria have been considered in path planning, such as the rendezvous and operation time, path length, velocity smoothness, safety margin, and heading profiles for generating optimal paths ^[15]. During missions, the robot systems have limitations, such as limited communication with the center or other robots, stringent nonholonomic mission constraints, and limited mission length because of weight, size, and fuel constraints ^[16]. The planned path must be a smooth curve due to nonholonomic motion constraints and support kinematic constraints with geometric continuity. Furthermore, the path’s continuity is significant for collaborative transport ^[17].

Path-planning approaches can be divided into offline and real-time implementation. Offline generation of a multi-robot path cannot exploit the cooperative abilities, as there is little or no interaction between robots, leading to the multi-robot system not ensuring that the robots are moving along a predefined path or formation ^[18]. Real-time systems have been proposed to overcome the problems created by offline path generation, and these can maximize the efficiency of algorithms.

Decision-making strategies can be classified as centralized and decentralized approaches. The centralized system has the central decision-maker, and thus the degree of cooperation is higher than in the decentralized approach. All robots are treated as one entity in the high-dimensional configuration space ^[19]. A central planner assigns tasks and plans schedules for each robot, and the robots start operation after completion of the planning ^[20]. The algorithms used in the centralized structure are without limitation because the centralized system has better global support for robots.

However, the decentralized approach is more widely employed in real-time implementation. Decentralized methods are typical for vehicle autonomy and distributed computation ^[21]. These have the robots communicate and interact with each other and have higher degrees of flexibility, robustness, and scalability, thereby, supporting dynamic changes. The robots execute computations and produce suboptimal solutions ^[20]. The decentralized approach includes task planning and motion planning, and it reduces computational complexity with limited shared information ^[22].

Many surveys have been conducted for the mobile robot path planning strategies ^[23]^[24]^[25]; however, these papers only focus on single robot navigation without cooperative planning. This entry’s motivation is to introduce the state-of-art path-planning algorithms of multi-robot systems and provide an analysis of multi-robot decision-making strategies, considering real-time performance. This entry not only investigates 2D or ground path planning but also the 3D environment.

2. Multi-Robot Path Planning Approaches

Figure 1 presents the classification of multi-robot path-planning algorithms, and it is divided into three categories: classical approaches, heuristic algorithms, and artificial intelligence (AI)-based approaches. The subcategories are linked to the primary categories and only display the significant subcategories. The classical approaches include the Artificial potential field, sampling-based, and graph-based approaches. The heuristic algorithms mainly consist of A* and D* search algorithms. The AI-based approaches are the most common algorithms for multi-robot systems, and the bio-inspired approaches take most of the attention. Metaheuristic has been applied to most of the research, and the famous algorithms are PSO and GA. From ^[26], GA and PSO are the most commonly used approaches.

Figure 1. Classification of multi-robot path planning approaches.

2.1. Classical Approaches

2.1.1. Artificial Potential Field (APF)

The APF uses its control force for path planning, and the control force sums up the attractive and the repulsive potential field. The illustration of APF is shown in Figure 2; the blue force indicates the attractive field, and the yellow force represents the repulsive field. The APF establishes path-planning optimization and dynamic particle models, and the additional control force updates the APF for multi-robot formation in a realistic and known environment ^[27]. Another APF-based approach is presented for a multi-robot system in a warehouse.

Figure 2. Illustration of the APF algorithm.

It uses the priority strategy and solves the drawbacks of traffic jams, local minima, collisions, and non-reachable targets ^[28]. An innovative APF algorithm is proposed to find all possible paths under a discrete girded environment. It implements a time-efficient deterministic scheme to obtain the initial path and then uses enhanced GA to improve it ^[29]. A potential field-based controller in ^[30] supports robots to follow the designed path, avoid collision with nearby robots, and distribute the robots stochastically across different paths in topologically distinct classes.

An improved APF is proposed to overcome the traditional APF’s shortcomings, including target unreachable and local minimum in ^[31] for real-time performance with dynamic obstacles for realizing local path planning. A collision avoidance strategy and risk assessment are proposed based on the improved APF and the fuzzy inference system for multi-robot path planning under a completely unknown environment ^[32].

APF is applied in the approximate cost function in ^[33], and integral reinforcement learning is developed for the minimum time-energy strategy in an unknown environment, converting the finite horizon problem with constraints to an infinite horizon optimal control problem. APF is introduced for the reward functions and integrates Deep Deterministic Policy Gradient and Model Predictive Control to address uncertain scenes ^[34].

2.1.2. Sampling-Based

The rapidly exploring random tree (RRT) searches high-dimensional and nonconvex space by using a space-filling tree randomly, and the tree is built incrementally from samples to grow towards unreached areas. The sampling-based approach’s outline is demonstrated in Figure 3, and the generated path is highlighted in green. For a multi-robot centralized approach, multi-robot path-planning RRT performs better in optimizing the solution and exploring search space in an urban environment than push and rotate, push and swap, and the Bibox algorithm ^[35]. The discrete-RRT extends the celebrated RRT algorithm in the discrete graph with a speedy exploration of the high-dimensional space of implicit roadmaps ^[36].

Figure 3. Demonstration of the RRT algorithm.

2.2. Heuristic Algorithms

2.2.1. A* Search

The A* search algorithm is one of the most common heuristic algorithms in path planning. Figure 4 shows the simple example of the gird-based A* algorithm, and the path is highlighted in green. It uses the heuristic cost to determine the optimal path on the map. The relaxed-A* is used to provide an optimal initial path and fast computation, and Bezier-splines are used for continuous path planning to optimize and control the curvature of the path and restrict the acceleration and velocity ^[17].

Figure 4. Simple example of the A* algorithm.

A two-level adaptive variable neighborhood search algorithm is designed to be integrated with the A* search algorithm for the coupled mission planning framework. It models the path planning problem and the integrated sensor allocation to minimize travel costs and maximize the task profit ^[37]. For the multi-AGV routing problem, the improved A* algorithm plans the global path and uses a dynamic RRT algorithm to obtain a passable local path with kinematic constraints, avoiding collisions in the grid map ^[38].

Additionally, Ref. ^[39] utilized the A* algorithm for the predicted path and generated a flyable path by cubic B-spline in real-time for guidance with triple-stage prediction. With the computational efficiency of cluster algorithms and A*, the proposed planning strategy supports online implementation. An optimal multi-robot path-planning approach is proposed with EA* algorithm with assignment techniques and fault-detection algorithm for the unknown environment based on the circle partitioning concept in ^[40]. A proposed navigation system integrates a modified A* algorithm, auction algorithm, and insertion heuristics to calculate the paths for multiple responders. It supports connection with a geo-database, information collection, path generation in dynamic environments, and spatio-temporal data analysis ^[41].

The D* algorithm is employed for multi-robot symbiotic navigation in a knowledge-sharing mechanism with sensors ^[8]. It allows robots to inform other robots about environmental changes, such as new static obstacles and path blockage, and it can be extended for real-time mobile applications. Additionally, D* Lite is applied with artificial untraversable vertex to avoid deadlocks and collisions for real-time robot applications, and D* Lite has fast re-planning abilities ^[9].

A cloud approach is developed with D* Lite and multi-criteria decision marking to offer powerful processing capabilities and shift computation load to the cloud from robots in the multi-robot system with a high level of autonomy ^[42]. An integrated framework is proposed based on D* Lite, A*, and uniform cost search, and it is used for multi-robot dynamic path-planning algorithms with concurrent and real-time movement ^[43].

2.2.2. Other Heuristic Algorithms

A constructive heuristic approach is presented to perceive multiple regions of interest. It aims to find the robot’s path with minimal cost and cover target regions with heterogeneous multi-robot settings ^[6]. Conflict-Based Search is proposed for multi-agent path planning problems in the train routing problem for scheduling multiple vehicles and setting paths in ^[44]. For multi-robot transportation, a primal-dual-based heuristic is designed to solve the path planning problem as the multiple heterogeneous asymmetric Hamiltonian path problem, solving in a short time ^[45]. The linear temporal logic formula is applied to solve the multi-robot path planning by satisfying a high-level mission specification with Dijkstra’s algorithm in ^[46].

A modified Dijkstra’s algorithm is introduced for robot global path planning without intersections, using a quasi-Newton interior point solver to smooth local paths in tight spaces ^[47]. Moreover, cognitive adaptive optimization is developed with transformed optimization criteria for adaptively offering the accurate approximation of paths in the proposed real-time reactive system; it takes into account the unknown operation area and nonlinear characteristics of sensors ^[18].

The Grid Blocking Degree (GBD) is integrated with priority rules for multi-AGV path planning, and it can generate a conflict-free path for AGV to handle tasks and update the path based on real-time traffic congestion to overcome the problems caused by most multi-AGV path planning is offline scheduling ^[48]. Heuristic algorithms, minimization techniques, and linear sum assignment are used in ^[49] for multi-UAV coverage path and task planning with RGB and thermal cameras. ^[50] designed the extended Angular-Rate-Constrained-Theta* for a multi-agent path-planning approach to maintaining the formation in a leader–follower formation.

Figure 5 displays the overview of the mentioned heuristic algorithms. The heuristic algorithms are widely used in path planning, and the heuristic cost functions are developed to evaluate the paths. The algorithms can provide the complete path in a grid-like map. However, for the requirement of flexibility and robustness, bio-inspired algorithms are proposed.

Figure 5. Search algorithms.

2.3. Bio-Inspired Techniques

2.3.1. Particle Swarm Optimization (PSO)

PSO is one of the most common metaheuristic algorithms in multi-robot path planning problems and formation. The flowchart of PSO is shown in Figure 6. It is a stochastic optimization algorithm based on the social behavior of animals, and it obtains global and local search abilities by maintaining a balance between exploitation and exploration ^[51]. Ref. ^[52] presents an interval multi-objective PSO using an ingenious interval update law for updating the global best position and the crowding distance of risk degree interval for the particle’s local best position. PSO is employed for multiple vehicle path planning to minimize the mission time, and the path planning problem is formulated as a multi-constrained optimization problem ^[53], while the approach has low scalability and execution ability.

Figure 6. Flowchart of the PSO algorithm.

An improved PSO is developed with differentially perturbed velocity, focusing on minimizing the maximum path length and arrival time with a multi-objective optimization problem ^[54]. The time stamp segmentation model handles the coordination cost. Improved PSO is combined with modified symbiotic organisms searching for multi-UAV path planning, using a B-spline curve to smooth the path in ^[55]. For a non-stationary environment, improved PSO and invasive weed optimization are hybrids for planning a path for each robot in the multi-robot system, balancing diversification and intensification, and avoiding local minima ^[56].

PSO is adapted for a leader–follower strategy in multi-UAV path planning with obstacle avoidance ^[51]. A distributed cooperative PSO is proposed for obtaining a safe and flyable path for a multi-UAV system, and it is combined with an elite keeping strategy and the Pythagorean hodograph curve to satisfy the kinematic constraints in ^[57]. The enhanced PSO is improved by greedy strategy and democratic rule in human society inspired by sine and cosine algorithms. The projected algorithm can generate a deadlock-free path with preserving a balance between intensification and diversification ^[58].

For the multi-robot path planning issue, a coevolution-based PSO is proposed to adjust the local and goal search abilities and solve the stagnation problem of PSO with evolutionary game theory in ^[59]. An improved gravitational search algorithm is integrated with the improved PSO for a new methodology for multi-robot path planning in the clutter environment, and it updates the particle positions and gravitational search algorithm acceleration with PSO velocity simultaneously ^[60].

A hybrid algorithm of democratic robotics PSO and improved Q-learning is proposed to balance exploitation and exploration, and it is fast and available for a real-time environment. However, it cannot guarantee the completeness of the path, and it is hard to achieve robot cooperation ^[61]. PSO-based and a B-Spline data frame solver engine is developed for uninterrupted collision-free path planning. It is robust to deal with current disturbances and irregular operations and provides quick obstacle avoidance for real-time implementation ^[15].

A wireless sensor network is presented for locating obstacles and robots in a dynamic environment. It combines a jumping mechanism PSO algorithm and a safety gap obstacle avoidance algorithm for multi-robot path planning ^[7]. The jumping mechanism PSO estimates the inertia weight based on fitness value and updates the particles. The safety gap obstacle avoidance algorithm focuses on robots struck when avoiding obstacles. Ref. ^[62] designed the hybrid GA and PSO with fuzzy logic controller for multi-AGV conflict-free path planning with rail-mounted gantry and quay cranes; however, it is inapplicable to real-time scheduling.

2.3.2. Genetic Algorithm (GA)

GA is widely utilized for solving optimization problems as an adaptive search technique, and it is based on a genetic reproduction mechanism and natural selection ^[63]. The flowchart of GA is indicated in Figure 7. Ref. ^[64] uses GA and reinforcement learning techniques for multi-UAV path planning, considers the number of vehicles and a response time, and a heuristic allocation algorithm for ground vehicles. GA solves the Multiple Traveling Sales Person problem with the stop criterion and the cost function of Euclidean distance, and Dubins curves achieve geometric continuity while the proposed algorithm cannot avoid the inter-robot collision or support online implementation ^[16].

Figure 7. Flowchart of the GA algorithm.

A 3D sensing model and a cube-based environment model are involved in describing a complex environment, and non-dominated sorting GA is modified to improve the convergence speed for the Pareto solution by building a voyage cost map by the R-Dijkstra algorithm in ^[65] as an omnidirectional perception model for multi-robot path planning. Ref. ^[66] applies the sensors in the area to obtain a minimal cost and solves the traveling salesman, and GA is adapted for persistent cooperative coverage.

Efficient genetic operators are developed to generate valid solutions on a closed metric graph in a reasonable time and are designed for multi-objective GA for multi-agent systems ^[67]. GA assigns the regions to each robot, sets the visiting orders, and uses simultaneous localization and mapping to create the global map in ^[68] for coverage path planning. Ref. ^[69] presents GA to optimize the integration of motion patterns that represent the priority of the neighbor cell and divides the target environment into cell areas, and then uses a double-layer strategy to guarantee complete coverage.

A domain knowledge-based operator is proposed to improve GA by obtaining the elite set of chromosomes, and the proposed algorithm can support robots that have multiple targets ^[70]. For intelligent production systems, the improved GA is aimed at complicated multi-AGV path planning and maneuvering scheduling decision with time-dependent and time-independent variables. It first addresses AGV resource allocation and transportation tasks, and then solves the transportation scheduling problem ^[71].

An improved GA was presented with three-exchange crossover heuristic operators than the traditional two-exchange operators, which consider double-path constraints for multi-AGV path planning ^[72]. Ref. ^[63] proposed a boundary node method with a GA for finding the shortest collision-free path for 2D multi-robot system and using a path enhancement method to reduce the initial path length. Due to the short computational time, it can be used for real-time navigation, while it can only be implemented in a known environment without dynamic obstacles.

A high degree of GA is employed for optimal path planning under a static environment at offline scheduling, and online scheduling is aimed to solve conflicts between AGVs for the two-stage multi-AGV system ^[73]. The evolution algorithm is used for planning a real-time path for multi-robot cooperative path planning with a unique chromosome coding method, redefining mutation and crossover operator in ^[74].

2.3.3. Ant Colony Optimization (ACO)

Ants will move along the paths and avoid the obstacle, marking available paths with pheromone, and the ACO treats the path with higher pheromone as the optimal path. The principle of ACO is demonstrated in Figure 8, and the path with a higher pheromone is defined as the optimal path marked by green. For collision-free routing and job-shop scheduling problems, an improved ant colony algorithm is enhanced by multi-objective programming for a multi-AGV system ^[75].

Figure 8. Changes of the ACO algorithm with different timeslots.

For multi-UGVs, a continuous ACO-based path planner focuses on coordination and path planning. It is integrated with an adaptive waypoint-repair method and a probability-based random-walk strategy to balance exploration and exploitation and improve the algorithm’s performance, resolving the coordination with a velocity-shifting optimization algorithm ^[76].

K-degree smoothing and the improved ACO are integrated as a coordinated path planning strategy for the multi-UAV control and precise coordination strategy in ^[77]. Voronoi models the environment by considering various threats, and the improved ACO’s pheromone update method and heuristic information are redefined for path planning, then using a k-degree smoothing method for the path smoothing problem. For precision agriculture and agricultural processes, ACO, Bellman–Held–Karp, Christofides, and Nearest Neighbor based on K-means clustering are used for the optimization path of multi-UAV ^[78].

2.3.4. Pigeon-Inspired Optimization (PIO)

Pigeon navigation tools inspired PIO, and it uses two operators for evaluating the solutions. Social-class PIO is proposed to improve the performances and convergence capabilities of standard PIO with inspiring by the inherent social-class character of pigeons ^[79], and it is combined with time stamp segmentation for multi-UAV path planning. Ref. ^[80] analyzing and comparing the changing trend of fitness value of local and global optimum positions to improve the PIO algorithm as Cauchy mutant PIO method, and the plateau topography and wind field, control constraints of UAVs are modeled for cooperative strategy and better robustness.

2.3.5. Grey Wolf Optimizer (GWO)

GWO is inspired by the hunting behavior and leadership of grey wolves, and it obtain the solutions by searching, encircling, and attacking prey. An improved grey wolf optimizer is employed for the multi-constraint objective optimization model for multi-UAV collaboration under the confrontation environment. It considers fuel consumption, space, and time ^[81]. The improvements of the grey wolf optimizer are individual position updating, population initialization, and decay factor updating. An improved hybrid grey wolf optimizer is proposed with a whale optimizer algorithm in a leader–follower formation and fuses a dynamic window approach to avoid dynamic obstacles ^[82].

The leader–follower formation controls the followers to track their virtual robots based on the leader’s position and considers the maximum angular and linear speed of robots. Ref. ^[83] proposed a hybrid discrete GWO to overcome the weakness of traditional GWO, and it updates the grey wolf position vector to gain solution diversity with faster convergence in discrete domains for multi-UAV path planning, using greedy algorithms and the integer coding to convert between discrete problem space and the grey wolf space.

2.4. Artificial Intelligence

2.4.1. Fuzzy Logic

Fuzzy logic uses the principle of “degree of truth” for computing the solutions. It can be applied for controlling the robot without the mathematical model but cannot predict the stochastic uncertainty in advance. As a result, a probabilistic neuro-fuzzy model is proposed with two fuzzy level controllers and an adaptive neuro-fuzzy inference system for multi-robot path planning and eliminating the stochastic uncertainties with leader–follower coordination ^[84]. The fuzzy C-means or the K-means methods filter and sort the camera location points, then use A* as a path optimization process for the multi-UAV traveling salesman problem in ^[5].

For collision avoidance and autonomous mobile robot navigation, Fuzzy-wind-driven optimization and a singleton type-1 fuzzy logic system controller are hybrids in the unknown environment in ^[85]. The wind-driven optimization algorithm optimizes the function parameters for the fuzzy controller, and the controller controls the motion velocity of the robot by sensory data interpretation. Ref. ^[86] proposed a reverse auction-based method and a fuzzy-based optimum path planning for multi-robot task allocation with the lowest path cost.

2.4.2. Machine Learning

Machine learning simulates the learning behavior to obtain the solutions. It is used for path planning, embracing mobile computing, hyperspectral sensing, and rapid telecommunication for the rapid agent-based robust system ^[87]. Kernel smooth techniques, reinforcement learning, and the neural network are integrated for greedy actions for multi-agent path planning in an unknown environment ^[10] to overcome the shortcomings of traditional reinforcement learning, such as high time consumption, slow learning speed, and disabilities of learning in an unknown environment.

The self-organizing neural network has self-learning abilities and competitive characteristics for the multi-robot system’s path planning and task assignment. Ref. ^[88] combined it with Glasius Bio-inspired neural network for obstacle avoidance and speed jump while the environment changes have not been considered in this approach. The biological-inspired self-organizing map is combined with a velocity synthesis algorithm for multi-robot path planning and task assignment. The self-organizing neural network supports a set of robots to reach multiple target locations and avoid obstacles autonomously for each robot with updating weights of the winner by the neurodynamic model ^[89].

Convolution Neural networks analyze image information to find the exact situation in the environment, and Deep q learning achieves robot navigation in a noble multi-robot path-planning algorithm ^[90]. This algorithm learns the mutual influence of robots to compensate for the drawback of conventional path-planning algorithms. In an unknown environment, a bio-inspired neural network is developed with the negotiation method, and each neuron has a one-to-one correspondence with the position of the grid map ^[91]. A biologically inspired neural network map is presented for task assignment and path planning, and it is used to calculate the activity values of robots in the maps of each target and select the winner with the highest activity value, then perform path planning ^[92]. The simple neural network diagram is exhibited in the following Figure 9.

Figure 9. Diagram of a three-layer neural network.

Moreover, a multi-agent path-planning algorithm based on deep reinforcement learning is proposed, providing high efficiency ^[93]. Another multi-agent reinforcement learning is developed in ^[94], and it constructs a node network and establishes an integer programming model to extract the shortest path. The improved Q-learning plans the collision-free path for a single robot in a static environment and then uses the algorithm to achieve collision-free motion among robots based on prior knowledge in ^[95]. The reinforcement learning framework is applied to optimize the quality of service and path planning, describe the users’ requirements, and consider geometric distance and risk by reinforcement learning reward matrix with a sigmoid-like function ^[96].

An attention neural network is used for generating the multimachine collaborative path planning as attention reinforcement learning, and it can meet high real-time requirements ^[97]. A deep Q-network is implemented with a Q-learning algorithm in a deep reinforcement learning algorithm for a productive neural network to handle multi-robot path planning with faster convergence ^[98]. The meta-reinforcement learning is designed based on transfer learning in ^[99], and it improves proximal policy optimization by covariance matrix adaptation evolutionary strategies to avoid static and dynamic obstacles.

Multi-agent reinforcement learning is improved by an iterative single-head attention mechanism for multi-UAV path planning, and it calculates robot interactions for each UAV’s control decision-making ^[100]. Fuzzy reinforcement learning is proposed for the continuous-time path-planning algorithm, combining a modified Wolf-PH and fuzzy Q-iteration algorithm for cooperative tasks ^[101].

References

Cardarelli, E.; Digani, V.; Sabattini, L.; Secchi, C.; Fantuzzi, C. Cooperative cloud robotics architecture for the coordination of multi-AGV systems in industrial warehouses. Mechatronics 2017, 45, 1–13.
Tevyashov, G.K.; Mamchenko, M.V.; Migachev, A.N.; Galin, R.R.; Kulagin, K.A.; Trefilov, P.M.; Onisimov, R.O.; Goloburdin, N.V. Algorithm for Multi-drone Path Planning and Coverage of Agricultural Fields. In Agriculture Digitalization and Organic Production; Smart Innovation, Systems and Technologies; Springer: Berlin/Heidelberg, Germany, 2022; Chapter 25; pp. 299–310.
Ahmed, N.; Pawase, C.J.; Chang, K. Distributed 3-D Path Planning for Multi-UAVs with Full Area Surveillance Based on Particle Swarm Optimization. Appl. Sci. 2021, 11, 3417.
Berger, J.; Lo, N. An innovative multi-agent search-and-rescue path-planning approach. Comput. Oper. Res. 2015, 53, 24–31.
Nagasawa, R.; Mas, E.; Moya, L.; Koshimura, S. Model-based analysis of multi-UAV path planning for surveying postdisaster building damage. Sci. Rep. 2021, 11, 18588.
Pereira, T.; Moreira, A.P.G.M.; Veloso, M. Multi-Robot Planning for Perception of Multiple Regions of Interest. In ROBOT 2017: Third Iberian Robotics Conference; Advances in Intelligent Systems and Computing; Springer: Berlin/Heidelberg, Germany, 2018; Chapter 23; pp. 275–286.
Tian, S.; Li, Y.; Kang, Y.; Xia, J. Multi-robot path planning in wireless sensor networks based on jump mechanism PSO and safety gap obstacle avoidance. Future Gener. Comput. Syst. 2021, 118, 37–47.
Ravankar, A.; Ravankar, A.A.; Kobayashi, Y.; Emaru, T. Symbiotic Navigation in Multi-Robot Systems with Remote Obstacle Knowledge Sharing. Sensors 2017, 17, 1581.
Li, H.; Zhao, T.; Dian, S. Prioritized planning algorithm for multi-robot collision avoidance based on artificial untraversable vertex. Appl. Intell. 2021, 52, 429–451.
Cruz, D.L.; Yu, W. Path planning of multi-agent systems in unknown environment with neural kernel smoothing and reinforcement learning. Neurocomputing 2017, 233, 34–42.
Kyprianou, G.; Doitsidis, L.; Chatzichristofis, S.A. Towards the Achievement of Path Planning with Multi-robot Systems in Dynamic Environments. J. Intell. Robot. Syst. 2021, 104, 15.
Liu, Y.; Jiang, C.; Zhang, X.; Mourelatos, Z.P.; Barthlow, D.; Gorsich, D.; Singh, A.; Hu, Z. Reliability-Based Multivehicle Path Planning Under Uncertainty Using a Bio-Inspired Approach. J. Mech. Des. 2022, 144, 091701.
Shi, W.; He, Z.; Tang, W.; Liu, W.; Ma, Z. Path Planning of Multi-Robot Systems With Boolean Specifications Based on Simulated Annealing. IEEE Robot. Autom. Lett. 2022, 7, 6091–6098.
Han, S.D.; Rodriguez, E.J.; Yu, J. SEAR: A Polynomial-Time Multi-Robot Path Planning Algorithm with Expected Constant-Factor Optimality Guarantee. In Proceedings of the 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Madrid, Spain, 1–5 October 2018; pp. 1–9.
MahmoudZadeh, S.; Abbasi, A.; Yazdani, A.; Wang, H.; Liu, Y. Uninterrupted path planning system for Multi-USV sampling mission in a cluttered ocean environment. Ocean. Eng. 2022, 254, 111328.
Cai, W.; Zhang, M.; Zheng, Y.R. Task Assignment and Path Planning for Multiple Autonomous Underwater Vehicles Using 3D Dubins Curves (dagger). Sensors 2017, 17, 1607.
Lurz, H.; Recker, T.; Raatz, A. Spline-based Path Planning and Reconfiguration for Rigid Multi-Robot Formations. Procedia CIRP 2022, 106, 174–179.
Kapoutsis, A.C.; Chatzichristofis, S.A.; Doitsidis, L.; de Sousa, J.B.; Pinto, J.; Braga, J.; Kosmatopoulos, E.B. Real-time adaptive multi-robot exploration with application to underwater map construction. Auton. Robot. 2015, 40, 987–1015.
Yu, J.; Rus, D. An Effective Algorithmic Framework for Near Optimal Multi-robot Path Planning. In Robotics Research; Springer Proceedings in Advanced Robotics; Springer: Berlin/Heidelberg, Germany, 2018; Chapter 30; pp. 495–511.
Öztürk, S.; Kuzucuoğlu, A.E. Optimal bid valuation using path finding for multi-robot task allocation. J. Intell. Manuf. 2014, 26, 1049–1062.
Regev, T.; Indelman, V. Decentralized multi-robot belief space planning in unknown environments via identification and efficient re-evaluation of impacted paths. Auton. Robot. 2017, 42, 691–713.
Veeramani, S.; Muthuswamy, S. Hybrid type multi-robot path planning of a serial manipulator and SwarmItFIX robots in sheet metal milling process. Complex Intell. Syst. 2021, 8, 2937–2954.
Gul, F.; Mir, I.; Abualigah, L.; Sumari, P.; Forestiero, A. A Consolidated Review of Path Planning and Optimization Techniques: Technical Perspectives and Future Directions. Electronics 2021, 10, 2250.
Patle, B.K.; Babu, L.G.; Pandey, A.; Parhi, D.R.K.; Jagadeesh, A. A review: On path planning strategies for navigation of mobile robot. Def. Technol. 2019, 15, 582–606.
Sanchez-Ibanez, J.R.; Perez-Del-Pulgar, C.J.; Garcia-Cerezo, A. Path Planning for Autonomous Mobile Robots: A Review. Sensors 2021, 21, 7898.
Zhang, H.Y.; Lin, W.M.; Chen, A.X. Path Planning for the Mobile Robot: A Review. Symmetry 2018, 10, 450.
Chen, Y.; Yu, J.; Su, X.; Luo, G. Path Planning for Multi-UAV Formation. J. Intell. Robot. Syst. 2014, 77, 229–246.
Chen, H.; Wang, Q.; Yu, M.; Cao, J.; Sun, J. Path Planning for Multi-robot Systems in Intelligent Warehouse. In Internet and Distributed Computing Systems; Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Germany, 2018; Chapter 13; pp. 148–159.
Nazarahari, M.; Khanmirza, E.; Doostie, S. Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm. Expert Syst. Appl. 2019, 115, 106–120.
Wang, X.; Sahin, A.; Bhattacharya, S. Coordination-free Multi-robot Path Planning for Congestion Reduction Using Topological Reasoning. arXiv 2022.
Wang, B.; Zhou, K.; Qu, J. Research on Multi-robot Local Path Planning Based on Improved Artificial Potential Field Method. In Proceedings of the Fifth Euro-China Conference on Intelligent Data Analysis and Applications, Xian, China, 12–14 October 2018; Advances in Intelligent Systems and Computing. Springer: Berlin/Heidelberg, Germany, 2019. Chapter 77. pp. 684–690.
Zhao, T.; Li, H.; Dian, S. Multi-robot path planning based on improved artificial potential field and fuzzy inference system. J. Intell. Fuzzy Syst. 2020, 39, 7621–7637.
He, C.; Wan, Y.; Gu, Y.; Lewis, F.L. Integral Reinforcement Learning-Based Multi-Robot Minimum Time-Energy Path Planning Subject to Collision Avoidance and Unknown Environmental Disturbances. IEEE Control. Syst. Lett. 2021, 5, 983–988.
Xue, J.; Kong, X.; Dong, B.; Xu, M. Multi-Agent Path Planning based on MPC and DDPG. arXiv 2021.
Turki, E.; Al-Rawi, H. Multi-Robot Path-Planning Problem for a Heavy Traffic Control Application: A Survey. Int. J. Adv. Comput. Sci. Appl. 2016, 7, 179–188.
Solovey, K.; Salzman, O.; Halperin, D. Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning. Int. J. Robot. Res. 2016, 35, 501–513.
Zheng, H.; Yuan, J. An Integrated Mission Planning Framework for Sensor Allocation and Path Planning of Heterogeneous Multi-UAV Systems. Sensors 2021, 21, 3557.
Yuan, Z.; Yang, Z.; Lv, L.; Shi, Y. A Bi-Level Path Planning Algorithm for Multi-AGV Routing Problem. Electronics 2020, 9, 1351.
Sun, X.; Liu, Y.; Yao, W.; Qi, N. Triple-stage path prediction algorithm for real-time mission planning of multi-UAV. Electron. Lett. 2015, 51, 1490–1492.
Singh, A.K. Fault-Detection on Multi-Robot Path Planning. Int. J. Adv. Res. Comput. Sci. 2017, 8, 539–543.
Wang, Z.; Zlatanova, S. Multi-agent based path planning for first responders among moving obstacles. Comput. Environ. Urban Syst. 2016, 56, 48–58.
Zagradjanin, N.; Pamucar, D.; Jovanovic, K. Cloud-Based Multi-Robot Path Planning in Complex and Crowded Environment with Multi-Criteria Decision Making using Full Consistency Method. Symmetry 2019, 11, 1241.
Serpen, G.; Dou, C. Automated robotic parking systems: Real-time, concurrent and multi-robot path planning in dynamic environments. Appl. Intell. 2014, 42, 231–251.
Salerno, M.; E-Martín, Y.; Fuentetaja, R.; Gragera, A.; Pozanco, A.; Borrajo, D. Train Route Planning as a Multi-agent Path Finding Problem. In Advances in Artificial Intelligence; Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Germany, 2021; Chapter 23; pp. 237–246.
Bae, J.; Chung, W. Efficient path planning for multiple transportation robots under various loading conditions. Int. J. Adv. Robot. Syst. 2019, 16, 1729881419835110.
Gujarathi, D.; Saha, I. MT*: Multi-Robot Path Planning for Temporal Logic Specifications. arXiv 2021.
Modi, V.; Chen, Y.; Madan, A.; Sueda, S.; Levin, D.I.W. Multi-Agent Path Planning with Asymmetric Interactions In Tight Spaces. arXiv 2022.
Yu, N.N.; Li, T.K.; Wang, B.L.; Yuan, S.P.; Wang, Y. Reliability oriented multi-AGVs online scheduling and path planning problem of automated sorting warehouse system. IOP Conf. Ser. Mater. Sci. Eng. 2021, 1043, 22035.
Luna, M.A.; Ale Isaac, M.S.; Ragab, A.R.; Campoy, P.; Flores Pena, P.; Molina, M. Fast Multi-UAV Path Planning for Optimal Area Coverage in Aerial Sensing Applications. Sensors 2022, 22, 2297.
Kim, H.; Kim, D.; Kim, H.; Shin, J.U.; Myung, H. An extended any-angle path-planning algorithm for maintaining formation of multi-agent jellyfish elimination robot system. Int. J. Control. Autom. Syst. 2016, 14, 598–607.
Mobarez, E.N.; Sarhan, A.; Ashry, M.M. Obstacle avoidance for multi-UAV path planning based on particle swarm optimization. IOP Conf. Ser. Mater. Sci. Eng. 2021, 1172, 12039.
Chen, Z.; Wu, H.; Chen, Y.; Cheng, L.; Zhang, B. Patrol robot path planning in nuclear power plant using an interval multi-objective particle swarm optimization algorithm. Appl. Soft Comput. 2022, 116, 108192.
Chen, Y.; Ren, S.; Chen, Z.; Chen, M.; Wu, H. Path Planning for Vehicle-borne System Consisting of Multi Air–ground Robots. Robotica 2019, 38, 493–511.
Das, P.K.; Behera, H.S.; Das, S.; Tripathy, H.K.; Panigrahi, B.K.; Pradhan, S.K. A hybrid improved PSO-DV algorithm for multi-robot path planning in a clutter environment. Neurocomputing 2016, 207, 735–753.
He, W.; Qi, X.; Liu, L. A novel hybrid particle swarm optimization for multi-UAV cooperate path planning. Appl. Intell. 2021, 51, 7350–7364.
Panda, M.R.; Das, P.; Pradhan, S. Hybridization of IWO and IPSO for mobile robots navigation in a dynamic environment. J. King Saud Univ. Comput. Inf. Sci. 2020, 32, 1020–1033.
Shao, Z.; Yan, F.; Zhou, Z.; Zhu, X. Path Planning for Multi-UAV Formation Rendezvous Based on Distributed Cooperative Particle Swarm Optimization. Appl. Sci. 2019, 9, 2621.
Paikray, H.K.; Das, P.K.; Panda, S. Optimal Multi-robot Path Planning Using Particle Swarm Optimization Algorithm Improved by Sine and Cosine Algorithms. Arab. J. Sci. Eng. 2021, 46, 3357–3381.
Tang, B.; Xiang, K.; Pang, M.; Zhanxia, Z. Multi-robot path planning using an improved self-adaptive particle swarm optimization. Int. J. Adv. Robot. Syst. 2020, 17, 1729881420936154.
Das, P.K.; Behera, H.S.; Panigrahi, B.K. A hybridization of an improved particle swarm optimization and gravitational search algorithm for multi-robot path planning. Swarm Evol. Comput. 2016, 28, 14–28.
Sahu, B.; Kumar Das, P.; Kabat, M.R. Multi-robot cooperation and path planning for stick transporting using improved Q-learning and democratic robotics PSO. J. Comput. Sci. 2022, 60, 101637.
Zhong, M.; Yang, Y.; Dessouky, Y.; Postolache, O. Multi-AGV scheduling for conflict-free path planning in automated container terminals. Comput. Ind. Eng. 2020, 142, 106371.
Saeed, R.A.; Reforgiato Recupero, D.; Remagnino, P. The boundary node method for multi-robot multi-goal path planning problems. Expert Syst. 2021, 38, e12691.
Song, J.; Liu, L.; Liu, Y.; Xi, J.; Zhai, W.; Yang, G. Path Planning for Multi-Vehicle-Assisted Multi-UAVs in Mobile Crowdsensing. Wirel. Commun. Mob. Comput. 2022, 2022, 9778188.
Ru, J.; Yu, S.; Wu, H.; Li, Y.; Wu, C.; Jia, Z.; Xu, H. A Multi-AUV Path Planning System Based on the Omni-Directional Sensing Ability. J. Mar. Sci. Eng. 2021, 9, 806.
Sun, G.; Zhou, R.; Di, B.; Dong, Z.; Wang, Y. A Novel Cooperative Path Planning for Multi-robot Persistent Coverage with Obstacles and Coverage Period Constraints. Sensors 2019, 19, 1994.
Yanes Luis, S.; Peralta, F.; Tapia Córdoba, A.; Rodríguez del Nozal, Á.R.; Toral Marín, S.; Gutiérrez Reina, D. An evolutionary multi-objective path planning of a fleet of ASVs for patrolling water resources. Eng. Appl. Artif. Intell. 2022, 112, 104852.
Sun, R.; Tang, C.; Zheng, J.; Zhou, Y.; Yu, S. Multi-robot Path Planning for Complete Coverage with Genetic Algorithms. In Intelligent Robotics and Applications; Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Germany, 2019; Chapter 29; pp. 349–361.
Xu, M.; Xin, B.; Dou, L.; Gao, G. A Cell Potential and Motion Pattern Driven Multi-robot Coverage Path Planning Algorithm. In Bio-inspired Computing: Theories and Applications; Communications in Computer and Information Science; Springer: Berlin/Heidelberg, Germany, 2020; Chapter 36; pp. 468–483.
Sarkar, R.; Barman, D.; Chowdhury, N. A Cooperative Co-evolutionary Genetic Algorithm for Multi-Robot Path Planning Having Multiple Targets. In Computational Intelligence in Pattern Recognition; Advances in Intelligent Systems and Computing; Springer: Berlin/Heidelberg, Germany, 2020; Chapter 63; pp. 724–740.
Farooq, B.; Bao, J.; Raza, H.; Sun, Y.; Ma, Q. Flow-shop path planning for multi-automated guided vehicles in intelligent textile spinning cyber-physical production systems dynamic environment. J. Manuf. Syst. 2021, 59, 98–116.
Han, Z.; Wang, D.; Liu, F.; Zhao, Z. Multi-AGV path planning with double-path constraints by using an improved genetic algorithm. PLoS ONE 2017, 12, e0181747.
Xu, W. Path Planning for Multi-AGV Systems based on Two-Stage Scheduling. Int. J. Perform. Eng. 2017, 13, 1347–1357.
Huang, H.; Zhuo, T. Multi-model cooperative task assignment and path planning of multiple UCAV formation. Multimed. Tools Appl. 2017, 78, 415–436.
Yi, G.; Feng, Z.; Mei, T.; Li, P.; Jin, W.; Chen, S. Multi-AGVs path planning based on improved ant colony algorithm. J. Supercomput. 2019, 75, 5898–5913.
Liu, J.; Anavatti, S.; Garratt, M.; Abbass, H.A. Modified continuous Ant Colony Optimisation for multiple Unmanned Ground Vehicle path planning. Expert Syst. Appl. 2022, 196, 116605.
Huang, L.; Qu, H.; Ji, P.; Liu, X.; Fan, Z. A novel coordinated path planning method using k-degree smoothing for multi-UAVs. Appl. Soft Comput. 2016, 48, 182–192.
Botteghi, N.; Kamilaris, A.; Sinai, L.; Sirmacek, B. Multi-Agent Path Planning of Robotic Swarms in Agricultural Fields. ISPRS Ann. Photogramm. Remote. Sens. Spat. Inf. Sci. 2020, 1, 361–368.
Zhang, D.; Duan, H. Social-class pigeon-inspired optimization and time stamp segmentation for multi-UAV cooperative path planning. Neurocomputing 2018, 313, 229–246.
Wang, B.H.; Wang, D.B.; Ali, Z.A. A Cauchy mutant pigeon-inspired optimization–based multi-unmanned aerial vehicle path planning method. Meas. Control 2020, 53, 83–92.
Xu, C.; Xu, M.; Yin, C. Optimized multi-UAV cooperative path planning under the complex confrontation environment. Comput. Commun. 2020, 162, 196–203.
Zhou, M.; Wang, Z.; Wang, J.; Dong, Z. A Hybrid Path Planning and Formation Control Strategy of Multi-Robots in a Dynamic Environment. J. Adv. Comput. Intell. Intell. Inform. 2022, 26, 342–354.
Huang, G.; Cai, Y.; Liu, J.; Qi, Y.; Liu, X. A Novel Hybrid Discrete Grey Wolf Optimizer Algorithm for Multi-UAV Path Planning. J. Intell. Robot. Syst. 2021, 103, 49.
Al-Jarrah, R.; Shahzad, A.; Roth, H. Path Planning and Motion Coordination for Multi-Robots System Using Probabilistic Neuro-Fuzzy. IFAC-PapersOnLine 2015, 48, 46–51.
Pandey, A.; Parhi, D.R. Optimum path planning of mobile robot in unknown static and dynamic environments using Fuzzy-Wind Driven Optimization algorithm. Def. Technol. 2017, 13, 47–58.
K, R.; R, B.; Panchu K, P.; M, R. A novel fuzzy and reverse auction-based algorithm for task allocation with optimal path cost in multi-robot systems. Concurr. Comput. Pract. Exp. 2021, 34, e6716.
Zohdi, T.I. The Game of Drones: Rapid agent-based machine-learning models for multi-UAV path planning. Comput. Mech. 2019, 65, 217–228.
Zhu, D.; Liu, Y.; Sun, B. Task Assignment and Path Planning of a Multi-AUV System Based on a Glasius Bio-Inspired Self-Organising Map Algorithm. J. Navig. 2017, 71, 482–496.
Cao, X.; Zhu, D. Multi-AUV task assignment and path planning with ocean current based on biological inspired self-organizing map and velocity synthesis algorithm. Intell. Autom. Soft Comput. 2015, 23, 31–39.
Bae, H.; Kim, G.; Kim, J.; Qian, D.; Lee, S. Multi-Robot Path Planning Method Using Reinforcement Learning. Appl. Sci. 2019, 9, 57.
Zhu, D.; Lv, R.; Cao, X.; Yang, S.X. Multi-AUV Hunting Algorithm Based on Bio-inspired Neural Network in Unknown Environments. Int. J. Adv. Robot. Syst. 2015, 12, 166.
Zhu, D.; Zhou, B.; Yang, S.X. A Novel Algorithm of Multi-AUVs Task Assignment and Path Planning Based on Biologically Inspired Neural Network Map. IEEE Trans. Intell. Veh. 2021, 6, 333–342.
Çetinkaya, M. Multi-Agent Path Planning Using Deep Reinforcement Learning. arXiv 2021.
Hu, H.; Yang, X.; Xiao, S.; Wang, F. Anti-conflict AGV path planning in automated container terminals based on multi-agent reinforcement learning. Int. J. Prod. Res. 2021, ahead-of-print. 1–16.
Li, B.; Liang, H. Multi-Robot Path Planning Method Based on Prior Knowledge and Q-learning Algorithms. J. Physics. Conf. Ser. 2020, 1624, 42008.
Chang, H.; Chen, Y.; Zhang, B.; Doermann, D. Multi-UAV Mobile Edge Computing and Path Planning Platform Based on Reinforcement Learning. IEEE Trans. Emerg. Top. Comput. Intell. 2022, 6, 489–498.
Wang, T.; Zhang, B.; Zhang, M.; Zhang, S.; Guo, D. Multi-UAV Collaborative Path Planning Method Based on Attention Mechanism. Math. Probl. Eng. 2021, 2021, 6964875.
Yang, Y.; Juntao, L.; Lingling, P. Multi-robot path planning based on a deep reinforcement learning DQN algorithm. CAAI Trans. Intell. Technol. 2020, 5, 177–183.
Wen, S.; Wen, Z.; Zhang, D.; Zhang, H.; Wang, T. A multi-robot path-planning algorithm for autonomous navigation using meta-reinforcement learning based on transfer learning. Appl. Soft Comput. 2021, 110, 107605.
Shiri, H.; Seo, H.; Park, J.; Bennis, M. Attention Based Communication and Control for Multi-UAV Path Planning. IEEE Wirel. Commun. Lett. 2022, 11, 1409–1413.
Luviano, D.; Yu, W. Continuous-time path planning for multi-agents with fuzzy reinforcement learning. J. Intell. Fuzzy Syst. 2017, 33, 491–501.

© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.

Upload a video for this entry

Information

Subjects: Computer Science, Artificial Intelligence

Contributors MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :

Shiwei Lin

Ang Liu

Jianguo Wang

Xiaoying Kong

View Times: 695

Update Date: 15 Sep 2022

Table of Contents

Video Upload Options

Confirm