TY - GEN
T1 - Multi-Agent Path Finding for Non-Conflicting Paths
T2 - 42nd Chinese Control Conference, CCC 2023
AU - Hou, Yaodong
AU - Tao, Gang
AU - Zang, Zheng
AU - Kong, Guojie
AU - Gong, Jianwei
N1 - Publisher Copyright:
© 2023 Technical Committee on Control Theory, Chinese Association of Automation.
PY - 2023
Y1 - 2023
N2 - Multi-Agent Path Finding (MAPF) is the problem of finding a set of non-conflicting paths for multiple agents on a graph, which is NP-hard to solve optimally. This paper proposes an infinite speed Conflict-Based Search (IS-CBS) algorithm to solve the MAPF problem when the agents move at different speeds and the edges correspond to roads of varying lengths. In addition, three distinct approaches are introduced to calculate admissible heuristics for IS-CBS: the sum approach which uses the sum of all heuristics as the final heuristic, the Pareto approach which builds a Pareto set and selects nodes from it, and the alternation approach which alternates between heuristics in search iterations. In our experiment, IS-CBS with heuristics outperforms IS-CBS in terms of success rate, runtime, and number of expanded nodes which is reduced by up to a factor of 21.
AB - Multi-Agent Path Finding (MAPF) is the problem of finding a set of non-conflicting paths for multiple agents on a graph, which is NP-hard to solve optimally. This paper proposes an infinite speed Conflict-Based Search (IS-CBS) algorithm to solve the MAPF problem when the agents move at different speeds and the edges correspond to roads of varying lengths. In addition, three distinct approaches are introduced to calculate admissible heuristics for IS-CBS: the sum approach which uses the sum of all heuristics as the final heuristic, the Pareto approach which builds a Pareto set and selects nodes from it, and the alternation approach which alternates between heuristics in search iterations. In our experiment, IS-CBS with heuristics outperforms IS-CBS in terms of success rate, runtime, and number of expanded nodes which is reduced by up to a factor of 21.
KW - Multi-Agent Path Finding
KW - heuristic search
KW - infinite speed Conflict-Based Search
UR - http://www.scopus.com/inward/record.url?scp=85175573794&partnerID=8YFLogxK
U2 - 10.23919/CCC58697.2023.10241096
DO - 10.23919/CCC58697.2023.10241096
M3 - Conference contribution
AN - SCOPUS:85175573794
T3 - Chinese Control Conference, CCC
SP - 5500
EP - 5505
BT - 2023 42nd Chinese Control Conference, CCC 2023
PB - IEEE Computer Society
Y2 - 24 July 2023 through 26 July 2023
ER -