Walk, stop, count, and swap: Decentralized multi-Agent path finding with theoretical guarantees

Hanlin Wang*, Michael Rubenstein

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

For multi-Agent path finding (MAPF) problems, finding the optimal solution has been shown to be NP-Complete. Here we present WSCaS (Walk, Stop, Count, and Swap), a decentralized multi-Agent path-finding algorithm that can provide theoretical completeness and optimality guarantees. That is, WSCaS is able to deliver a worst case \mathbf {\mathcal {O}(1)}-Approximate distance-optimal solution to MAPF instances on square grids without narrow passages. Moreover, the algorithm's cost is independent of the swarm's size with respect to computation complexity, memory complexity, as well as communication complexity, therefore the algorithm can scale well with the number of agents in practice. The algorithm is executed on 1024 simulated agents as well as 100 physical robots, the results show that the WSCaS is robust to real-world non-idealitys.

Original languageEnglish (US)
Article number8962201
Pages (from-to)1119-1126
Number of pages8
JournalIEEE Robotics and Automation Letters
Volume5
Issue number2
DOIs
StatePublished - Apr 2020

Keywords

  • Path planning for multiple mobile robots or agents
  • distributed robot systems
  • swarms

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Biomedical Engineering
  • Human-Computer Interaction
  • Mechanical Engineering
  • Computer Vision and Pattern Recognition
  • Computer Science Applications
  • Control and Optimization
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Walk, stop, count, and swap: Decentralized multi-Agent path finding with theoretical guarantees'. Together they form a unique fingerprint.

  • Cite this