Efficient Multi Agent Path Finding with turn actions

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

Current approaches for real-world Multi-Agent Path Finding (MAPF) usually start with a simplified MAPF model and modify the resulting plans so they are kinematically feasible. We investigate one such problem, called MAPF with turn actions (MAPFT), and show that ignoring the kinematic constraints significantly increases solution cost. A first modification of the popular Conflict-Based Search algorithm to MAPFT yields significantly better plans but comes at the cost of substantial decreases in scalability. We then introduce several techniques that can improve the performance of CBS for MAPFT, including stronger and generalised versions of existing symmetry-breaking constraints and a novel pruning technique that eliminates redundant branches in the CBS constraint tree. Experimental results on six popular MAPF domains show convincing improvements for CBS success rate and substantial reductions in node expansions and runtime.

Original languageEnglish
Title of host publicationSixteenth International Symposium on Combinatorial Search 2023
EditorsRoman Barták, Wheeler Ruml, Oren Salzman
Place of PublicationWashington DC USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages119-127
Number of pages9
ISBN (Electronic)139781577358824
DOIs
Publication statusPublished - 2023
EventInternational Symposium on Combinatorial Search 2023 - Prague, Czechia
Duration: 14 Jul 202316 Jul 2023
Conference number: 16th
https://ojs.aaai.org/index.php/SOCS/issue/view/565 (Proceedings)
https://socs23.search-conference.org/ (Website)

Publication series

NameThe International Symposium on Combinatorial Search
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number1
Volume16
ISSN (Print)2832-9171
ISSN (Electronic)2832-9163

Conference

ConferenceInternational Symposium on Combinatorial Search 2023
Abbreviated titleSoCS 2023
Country/TerritoryCzechia
CityPrague
Period14/07/2316/07/23
Internet address

Keywords

  • Bounding And Pruning Techniques
  • Constraint Search
  • Symmetry Handling
  • Search In Robotics

Cite this