TY - JOUR
T1 - A decoupling method for solving the multi-agent path finding problem
AU - Liao, Bin
AU - Zhu, Shenrui
AU - Hua, Yi
AU - Wan, Fangyi
AU - Qing, Xinlin
N1 - Publisher Copyright:
© 2023, The Author(s).
PY - 2023/12
Y1 - 2023/12
N2 - Many existing multi-agent path finding (MAPF) solvers focus on completeness, speed, or optimization. However, completeness and rapidity are usually in conflict with each other, which makes these algorithms far from satisfactory in practical applications. Motivated by this realistic requirement, we propose an efficient decoupling method to accelerate the solution of large MAPF problems. First, we define the concept of ‘non-essential vertex’-vertices which are not needed to solve a MAPF problem, and a scheme to identify them. Then, a decoupling scheme based on ‘non-essential vertex’ is proposed, which will assign higher priorities to agents whose goal positions are non-essential vertices and lower priorities to agents whose start positions are non-essential vertices. That is, invoking our decoupling algorithm can decouple any given MAPF problem into three subproblems while maintaining the completeness of the solution. All three sub-MAPF problems can be solved sequentially by a complete solver (e.g., CBS or EECBS, etc.), and two of them can also be solved by a prioritized planning algorithm. We have conducted several experiments in different workspaces, and the statistical results show that the proposed decoupling method significantly improves the speed and success rate of existing MAPF solvers with almost no degradation in solution quality when solving problems with high agent density. In addition, the solving efficiency can be further improved if the prioritized planning algorithm is invoked to solve the first and third sub-MAPF problems.
AB - Many existing multi-agent path finding (MAPF) solvers focus on completeness, speed, or optimization. However, completeness and rapidity are usually in conflict with each other, which makes these algorithms far from satisfactory in practical applications. Motivated by this realistic requirement, we propose an efficient decoupling method to accelerate the solution of large MAPF problems. First, we define the concept of ‘non-essential vertex’-vertices which are not needed to solve a MAPF problem, and a scheme to identify them. Then, a decoupling scheme based on ‘non-essential vertex’ is proposed, which will assign higher priorities to agents whose goal positions are non-essential vertices and lower priorities to agents whose start positions are non-essential vertices. That is, invoking our decoupling algorithm can decouple any given MAPF problem into three subproblems while maintaining the completeness of the solution. All three sub-MAPF problems can be solved sequentially by a complete solver (e.g., CBS or EECBS, etc.), and two of them can also be solved by a prioritized planning algorithm. We have conducted several experiments in different workspaces, and the statistical results show that the proposed decoupling method significantly improves the speed and success rate of existing MAPF solvers with almost no degradation in solution quality when solving problems with high agent density. In addition, the solving efficiency can be further improved if the prioritized planning algorithm is invoked to solve the first and third sub-MAPF problems.
KW - Collision avoidance
KW - Multi-agent path finding
KW - Multi-agent systems
KW - Path planning for multiple mobile robots or agents
UR - http://www.scopus.com/inward/record.url?scp=85160634256&partnerID=8YFLogxK
U2 - 10.1007/s40747-023-01088-2
DO - 10.1007/s40747-023-01088-2
M3 - 文章
AN - SCOPUS:85160634256
SN - 2199-4536
VL - 9
SP - 6767
EP - 6780
JO - Complex and Intelligent Systems
JF - Complex and Intelligent Systems
IS - 6
ER -