Multi-Agent Path Finding with Temporal Jump Point Search

Shuli Hu; Daniel Damir Harabor; Graeme Gange; Peter J. Stuckey; Nathan R. Sturtevant

doi:10.1609/icaps.v32i1.19798

Multi-Agent Path Finding with Temporal Jump Point Search

Shuli Hu, Daniel Damir Harabor, Graeme Gange, Peter J. Stuckey, Nathan R. Sturtevant

Department of Data Science & AI

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

Abstract

Temporal Jump Point Search (JPST) is a recently introduced algorithm for grid-optimal pathfinding among dynamic temporal obstacles. In this work we consider JPST as a low-level planner in Multi-Agent Path Finding (MAPF). We investigate how the canonical ordering of JPST can negatively impact MAPF performance and we consider several strategies which allow us to overcome these limitations. Experiments show our new CBS/JPST approach can substantially improve on CBS/SIPP, a contemporary and leading method from the area.

Original language	English
Title of host publication	Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling
Editors	Akshat Kumar, Sylvie Thiébaux, Pradeep Varakantham, William Yeoh
Place of Publication	Palo Alto CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	169-173
Number of pages	5
ISBN (Electronic)	9781577358749
DOIs	https://doi.org/10.1609/icaps.v32i1.19798
Publication status	Published - 2022
Event	International Conference on Automated Planning and Scheduling 2022 - Online, Singapore Duration: 13 Jun 2022 → 24 Jun 2022 Conference number: 32nd https://icaps22.icaps-conference.org (Website) https://ojs.aaai.org/index.php/ICAPS/issue/view/505 (Proceedings)

Publication series

Name	Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Number	1
Volume	32
ISSN (Print)	2334-0835
ISSN (Electronic)	2334-0843

Conference

Conference	International Conference on Automated Planning and Scheduling 2022
Abbreviated title	ICAPS 2022
Country/Territory	Singapore
Period	13/06/22 → 24/06/22
Internet address	https://icaps22.icaps-conference.org (Website) https://ojs.aaai.org/index.php/ICAPS/issue/view/505 (Proceedings)

Keywords

Multi-Agent Path Finding
Jump Point Search
Temporal Obstacles
Conflict-Based Search

Access to Document

10.1609/icaps.v32i1.19798

408475924-oaFinal published version, 2.02 MB

1 Finished
1 Active

Personalised Public Transport
Harabor, D. (Primary Chief Investigator (PCI)), Moser, I. (Chief Investigator (CI)) & Ronald, N. (Chief Investigator (CI))
24/06/19 → 31/12/25
Project: Research
Improved Constraint Reasoning for Robust Multi-agent Path Planning
Stuckey, P. (Primary Chief Investigator (PCI)), Harabor, D. (Chief Investigator (CI)), Le Bodic, P. (Chief Investigator (CI)), Gange, G. (Chief Investigator (CI)) & Koenig, S. (Partner Investigator (PI))
1/01/20 → 31/12/24
Project: Research

Cite this

Hu, S., Harabor, D. D., Gange, G., Stuckey, P. J., & Sturtevant, N. R. (2022). Multi-Agent Path Finding with Temporal Jump Point Search. In A. Kumar, S. Thiébaux, P. Varakantham, & W. Yeoh (Eds.), Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (pp. 169-173). (Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling; Vol. 32, No. 1). Association for the Advancement of Artificial Intelligence (AAAI). https://doi.org/10.1609/icaps.v32i1.19798

Hu, Shuli ; Harabor, Daniel Damir ; Gange, Graeme et al. / Multi-Agent Path Finding with Temporal Jump Point Search. Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling. editor / Akshat Kumar ; Sylvie Thiébaux ; Pradeep Varakantham ; William Yeoh. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2022. pp. 169-173 (Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling; 1).

@inproceedings{71e32694a6ee4cad9c81010a3d1b8662,

title = "Multi-Agent Path Finding with Temporal Jump Point Search",

abstract = "Temporal Jump Point Search (JPST) is a recently introduced algorithm for grid-optimal pathfinding among dynamic temporal obstacles. In this work we consider JPST as a low-level planner in Multi-Agent Path Finding (MAPF). We investigate how the canonical ordering of JPST can negatively impact MAPF performance and we consider several strategies which allow us to overcome these limitations. Experiments show our new CBS/JPST approach can substantially improve on CBS/SIPP, a contemporary and leading method from the area.",

keywords = "Multi-Agent Path Finding, Jump Point Search, Temporal Obstacles, Conflict-Based Search",

author = "Shuli Hu and Harabor, {Daniel Damir} and Graeme Gange and Stuckey, {Peter J.} and Sturtevant, {Nathan R.}",

year = "2022",

doi = "10.1609/icaps.v32i1.19798",

language = "English",

series = "Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling",

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

number = "1",

pages = "169--173",

editor = "Akshat Kumar and Sylvie Thi{\'e}baux and Pradeep Varakantham and William Yeoh",

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

address = "United States of America",

note = "International Conference on Automated Planning and Scheduling 2022, ICAPS 2022 ; Conference date: 13-06-2022 Through 24-06-2022",

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

}

Hu, S, Harabor, DD, Gange, G, Stuckey, PJ & Sturtevant, NR 2022, Multi-Agent Path Finding with Temporal Jump Point Search. in A Kumar, S Thiébaux, P Varakantham & W Yeoh (eds), Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling. Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling, no. 1, vol. 32, Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 169-173, International Conference on Automated Planning and Scheduling 2022, Singapore, 13/06/22. https://doi.org/10.1609/icaps.v32i1.19798

Multi-Agent Path Finding with Temporal Jump Point Search. / Hu, Shuli; Harabor, Daniel Damir; Gange, Graeme et al.
Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling. ed. / Akshat Kumar; Sylvie Thiébaux; Pradeep Varakantham; William Yeoh. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI), 2022. p. 169-173 (Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling; Vol. 32, No. 1).

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

TY - GEN

T1 - Multi-Agent Path Finding with Temporal Jump Point Search

AU - Hu, Shuli

AU - Harabor, Daniel Damir

AU - Gange, Graeme

AU - Stuckey, Peter J.

AU - Sturtevant, Nathan R.

N1 - Conference code: 32nd

PY - 2022

Y1 - 2022

N2 - Temporal Jump Point Search (JPST) is a recently introduced algorithm for grid-optimal pathfinding among dynamic temporal obstacles. In this work we consider JPST as a low-level planner in Multi-Agent Path Finding (MAPF). We investigate how the canonical ordering of JPST can negatively impact MAPF performance and we consider several strategies which allow us to overcome these limitations. Experiments show our new CBS/JPST approach can substantially improve on CBS/SIPP, a contemporary and leading method from the area.

AB - Temporal Jump Point Search (JPST) is a recently introduced algorithm for grid-optimal pathfinding among dynamic temporal obstacles. In this work we consider JPST as a low-level planner in Multi-Agent Path Finding (MAPF). We investigate how the canonical ordering of JPST can negatively impact MAPF performance and we consider several strategies which allow us to overcome these limitations. Experiments show our new CBS/JPST approach can substantially improve on CBS/SIPP, a contemporary and leading method from the area.

KW - Multi-Agent Path Finding

KW - Jump Point Search

KW - Temporal Obstacles

KW - Conflict-Based Search

U2 - 10.1609/icaps.v32i1.19798

DO - 10.1609/icaps.v32i1.19798

M3 - Conference Paper

T3 - Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling

SP - 169

EP - 173

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

A2 - Kumar, Akshat

A2 - Thiébaux, Sylvie

A2 - Varakantham, Pradeep

A2 - Yeoh, William

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

CY - Palo Alto CA USA

T2 - International Conference on Automated Planning and Scheduling 2022

Y2 - 13 June 2022 through 24 June 2022

ER -

Hu S, Harabor DD, Gange G, Stuckey PJ, Sturtevant NR. Multi-Agent Path Finding with Temporal Jump Point Search. In Kumar A, Thiébaux S, Varakantham P, Yeoh W, editors, Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2022. p. 169-173. (Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling; 1). doi: 10.1609/icaps.v32i1.19798

Multi-Agent Path Finding with Temporal Jump Point Search

Abstract

Publication series

Conference

Keywords

Access to Document

Projects

Personalised Public Transport

Improved Constraint Reasoning for Robust Multi-agent Path Planning

Cite this