Conflict-Based Search and Improvement Strategies for Solving a New Lexicographic Bi-Objective Multi-Agent Path Finding Problem

Siyi Li, Xingyang Li, Mengchu Zhou, Ziyan Zhao, Shixin Liu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2022 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2022 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1862-1867
Number of pages6
ISBN (Electronic)9781665452588
DOIs
StatePublished - 2022
Event2022 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2022 - Prague, Czech Republic
Duration: Oct 9 2022Oct 12 2022

Publication series

NameConference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
Volume2022-October
ISSN (Print)1062-922X

Conference

Conference2022 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2022
Country/TerritoryCzech Republic
CityPrague
Period10/9/2210/12/22

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Human-Computer Interaction

Keywords

  • Multi-agent path finding
  • conflict-based search
  • improvement strategies
  • lexicographic bi-objective optimization

Fingerprint

Dive into the research topics of 'Conflict-Based Search and Improvement Strategies for Solving a New Lexicographic Bi-Objective Multi-Agent Path Finding Problem'. Together they form a unique fingerprint.

Cite this