Beyond pairwise reasoning in Multi-Agent Path Finding

Bojie Shen; Zhe Chen; Jiaoyang Li; Muhammad Aamir Cheema; Daniel D. Harabor; Peter J. Stuckey

doi:10.1609/icaps.v33i1.27217

Beyond pairwise reasoning in Multi-Agent Path Finding

Bojie Shen, Zhe Chen, Jiaoyang Li, Muhammad Aamir Cheema, Daniel D. Harabor, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

3 Citations (Scopus)

Abstract

In Multi-Agent Path Finding (MAPF), we are asked to plan collision-free paths for teams of moving agents. Among the leading methods for optimal MAPF is Conflict-Based Search (CBS), an algorithmic family which has received intense attention in recent years and for which large advancements in efficiency and effectiveness have been reported. Yet all of the recent CBS gains come from reasoning over pairs of agents only. In this paper, we show how to further improve CBS by reasoning about more than two agents at the same time. Our new cluster reasoning techniques allow us to generate stronger bounds for CBS and to identify more bypasses (alternative cost-equivalent paths), which reduce the number of nodes in the CBS conflict tree.

Original language	English
Title of host publication	Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling 2023
Editors	Sven Koenig, Roni Stern, Mauro Vallati
Place of Publication	Palo Alto CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	384-392
Number of pages	9
Volume	33
Edition	1
ISBN (Electronic)	9781577358817
DOIs	https://doi.org/10.1609/icaps.v33i1.27217
Publication status	Published - 2023
Event	International Conference on Automated Planning and Scheduling 2023 - Prague, Czechia Duration: 8 Jul 2023 → 13 Jul 2023 Conference number: 33rd https://ojs.aaai.org/index.php/ICAPS/issue/view/562 https://icaps23.icaps-conference.org/ (Website)

Conference

Conference	International Conference on Automated Planning and Scheduling 2023
Abbreviated title	ICAPS 2023
Country/Territory	Czechia
City	Prague
Period	8/07/23 → 13/07/23
Internet address	https://ojs.aaai.org/index.php/ICAPS/issue/view/562 https://icaps23.icaps-conference.org/ (Website)

Keywords

Heuristic search
Multi-agent
distributed planning

Access to Document

10.1609/icaps.v33i1.27217

Cite this

Shen, B., Chen, Z., Li, J., Cheema, M. A., Harabor, D. D., & Stuckey, P. J. (2023). Beyond pairwise reasoning in Multi-Agent Path Finding. In S. Koenig, R. Stern, & M. Vallati (Eds.), Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling 2023 (1 ed., Vol. 33, pp. 384-392). Association for the Advancement of Artificial Intelligence (AAAI). https://doi.org/10.1609/icaps.v33i1.27217

Shen, Bojie ; Chen, Zhe ; Li, Jiaoyang et al. / Beyond pairwise reasoning in Multi-Agent Path Finding. Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling 2023. editor / Sven Koenig ; Roni Stern ; Mauro Vallati. Vol. 33 1. ed. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2023. pp. 384-392

@inproceedings{0140db8d56694883a7792e7940d1a2bc,

title = "Beyond pairwise reasoning in Multi-Agent Path Finding",

abstract = "In Multi-Agent Path Finding (MAPF), we are asked to plan collision-free paths for teams of moving agents. Among the leading methods for optimal MAPF is Conflict-Based Search (CBS), an algorithmic family which has received intense attention in recent years and for which large advancements in efficiency and effectiveness have been reported. Yet all of the recent CBS gains come from reasoning over pairs of agents only. In this paper, we show how to further improve CBS by reasoning about more than two agents at the same time. Our new cluster reasoning techniques allow us to generate stronger bounds for CBS and to identify more bypasses (alternative cost-equivalent paths), which reduce the number of nodes in the CBS conflict tree.",

keywords = "Heuristic search, Multi-agent, distributed planning",

author = "Bojie Shen and Zhe Chen and Jiaoyang Li and Cheema, {Muhammad Aamir} and Harabor, {Daniel D.} and Stuckey, {Peter J.}",

note = "Funding Information: This research was partially supported by the Australian Research Council under grants FT180100140, DP190100013, DP200100025, DP230100081 and also by a gift from Amazon. Publisher Copyright: Copyright {\textcopyright} 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; International Conference on Automated Planning and Scheduling 2023, ICAPS 2023 ; Conference date: 08-07-2023 Through 13-07-2023",

year = "2023",

doi = "10.1609/icaps.v33i1.27217",

language = "English",

volume = "33",

pages = "384--392",

editor = "Sven Koenig and Roni Stern and Mauro Vallati",

booktitle = "Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling 2023",

publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

address = "United States of America",

edition = "1",

url = "https://ojs.aaai.org/index.php/ICAPS/issue/view/562, https://icaps23.icaps-conference.org/",

}

Shen, B, Chen, Z, Li, J, Cheema, MA , Harabor, DD & Stuckey, PJ 2023, Beyond pairwise reasoning in Multi-Agent Path Finding. in S Koenig, R Stern & M Vallati (eds), Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling 2023. 1 edn, vol. 33, Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 384-392, International Conference on Automated Planning and Scheduling 2023, Prague, Czechia, 8/07/23. https://doi.org/10.1609/icaps.v33i1.27217

Beyond pairwise reasoning in Multi-Agent Path Finding. / Shen, Bojie; Chen, Zhe; Li, Jiaoyang et al.
Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling 2023. ed. / Sven Koenig; Roni Stern; Mauro Vallati. Vol. 33 1. ed. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI), 2023. p. 384-392.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Beyond pairwise reasoning in Multi-Agent Path Finding

AU - Shen, Bojie

AU - Chen, Zhe

AU - Li, Jiaoyang

AU - Cheema, Muhammad Aamir

AU - Harabor, Daniel D.

AU - Stuckey, Peter J.

N1 - Conference code: 33rd

PY - 2023

Y1 - 2023

N2 - In Multi-Agent Path Finding (MAPF), we are asked to plan collision-free paths for teams of moving agents. Among the leading methods for optimal MAPF is Conflict-Based Search (CBS), an algorithmic family which has received intense attention in recent years and for which large advancements in efficiency and effectiveness have been reported. Yet all of the recent CBS gains come from reasoning over pairs of agents only. In this paper, we show how to further improve CBS by reasoning about more than two agents at the same time. Our new cluster reasoning techniques allow us to generate stronger bounds for CBS and to identify more bypasses (alternative cost-equivalent paths), which reduce the number of nodes in the CBS conflict tree.

AB - In Multi-Agent Path Finding (MAPF), we are asked to plan collision-free paths for teams of moving agents. Among the leading methods for optimal MAPF is Conflict-Based Search (CBS), an algorithmic family which has received intense attention in recent years and for which large advancements in efficiency and effectiveness have been reported. Yet all of the recent CBS gains come from reasoning over pairs of agents only. In this paper, we show how to further improve CBS by reasoning about more than two agents at the same time. Our new cluster reasoning techniques allow us to generate stronger bounds for CBS and to identify more bypasses (alternative cost-equivalent paths), which reduce the number of nodes in the CBS conflict tree.

KW - Heuristic search

KW - Multi-agent

KW - distributed planning

UR - http://www.scopus.com/inward/record.url?scp=85162124731&partnerID=8YFLogxK

U2 - 10.1609/icaps.v33i1.27217

DO - 10.1609/icaps.v33i1.27217

M3 - Conference Paper

AN - SCOPUS:85162124731

VL - 33

SP - 384

EP - 392

BT - Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling 2023

A2 - Koenig, Sven

A2 - Stern, Roni

A2 - Vallati, Mauro

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Palo Alto CA USA

T2 - International Conference on Automated Planning and Scheduling 2023

Y2 - 8 July 2023 through 13 July 2023

ER -

Shen B, Chen Z, Li J, Cheema MA , Harabor DD , Stuckey PJ. Beyond pairwise reasoning in Multi-Agent Path Finding. In Koenig S, Stern R, Vallati M, editors, Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling 2023. 1 ed. Vol. 33. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2023. p. 384-392 doi: 10.1609/icaps.v33i1.27217

Beyond pairwise reasoning in Multi-Agent Path Finding

Abstract

Conference

Keywords

Access to Document

Other files and links

Driving Towards Greener and Safer Roads using Big Spatiotemporal Data

Improved Constraint Reasoning for Robust Multi-agent Path Planning

Personalised Public Transport

Cite this

Beyond pairwise reasoning in Multi-Agent Path Finding

Abstract

Conference

Keywords

Access to Document

Other files and links

Projects

Driving Towards Greener and Safer Roads using Big Spatiotemporal Data

Improved Constraint Reasoning for Robust Multi-agent Path Planning

Personalised Public Transport

Cite this