TY - GEN
T1 - Conflict-Based Search and Improvement Strategies for Solving a New Lexicographic Bi-Objective Multi-Agent Path Finding Problem
AU - Li, Siyi
AU - Li, Xingyang
AU - Zhou, Mengchu
AU - Zhao, Ziyan
AU - Liu, Shixin
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - Multi-Agent Path Finding (MAPF) is an important problem with a variety of applications. Its aim is to find collision-free paths for agents having separate start and goal positions. This work proposes a new lexicographic bi-objective MAPF considering different task types, where agents are divided into two kinds to perform critical and acritical tasks. This is common in practical intelligent warehousing scenarios where a critical/acritical-task-performing agent (called c-agent and a-agent, respectively) may represent a full-load/no-load one or the one conducting urgent/non-urgent tasks. The primary objective is to minimize the sum-of-costs of c-agents, while the secondary objective is to minimize the sum-of-costs of a-agents. Two MAPF algorithms are modified to fit and solve the concerned problem for the first time. Moreover, four improvement strategies are embedded to the proposed algorithms and proved to be effective in solving MAPF problems with different task types.
AB - Multi-Agent Path Finding (MAPF) is an important problem with a variety of applications. Its aim is to find collision-free paths for agents having separate start and goal positions. This work proposes a new lexicographic bi-objective MAPF considering different task types, where agents are divided into two kinds to perform critical and acritical tasks. This is common in practical intelligent warehousing scenarios where a critical/acritical-task-performing agent (called c-agent and a-agent, respectively) may represent a full-load/no-load one or the one conducting urgent/non-urgent tasks. The primary objective is to minimize the sum-of-costs of c-agents, while the secondary objective is to minimize the sum-of-costs of a-agents. Two MAPF algorithms are modified to fit and solve the concerned problem for the first time. Moreover, four improvement strategies are embedded to the proposed algorithms and proved to be effective in solving MAPF problems with different task types.
KW - Multi-agent path finding
KW - conflict-based search
KW - improvement strategies
KW - lexicographic bi-objective optimization
UR - http://www.scopus.com/inward/record.url?scp=85142721818&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85142721818&partnerID=8YFLogxK
U2 - 10.1109/SMC53654.2022.9945343
DO - 10.1109/SMC53654.2022.9945343
M3 - Conference contribution
AN - SCOPUS:85142721818
T3 - Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
SP - 1862
EP - 1867
BT - 2022 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2022 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2022 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2022
Y2 - 9 October 2022 through 12 October 2022
ER -