Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution

Keisuke Okumura
University of Cambridge / National Institute of Advanced Industrial Science and Technology (AIST)
Xavier Défago
Tokyo Institute of Technology

Demo

pattern formation

unlabeled MAPF

robust execution

Overview

Real-time planning for a combined problem of target assignment and path planning for multiple agents, also known as the unlabeled version of multi-agent path finding (MAPF), is crucial for high-level coordination in multi-agent systems, such as pattern formation by robot swarms. This paper studies two aspects of unlabeled-MAPF: (1) offline scenario: solving large instances using centralized approaches with a small computation time, and (2) online scenario: executing unlabeled-MAPF, despite the timing uncertainties real robots face. For this purpose, we propose TSWAP, a novel sub-optimal complete algorithm that takes an arbitrary initial target assignment and then repeats one-timestep path planning with target swapping. TSWAP can adapt to both offline and online scenarios. We empirically demonstrate that offline TSWAP is highly scalable, and provides near-optimal solutions while reducing runtime by orders of magnitude compared with existing approaches. In addition, we present the benefits of online TSWAP, such as delay tolerance, through real-robot demonstrations.

News

  • A toy Python implementation has been released (pytswap) (Aug. 2025) [link]
  • The paper has been accepted to Artificial Intelligence (AIJ)! (May. 2023) [link]
  • Got the ICAPS 2022 Best Student Paper Award! (May. 2022) [link]
  • The paper has been accepted to ICAPS-22! (Jan. 2022) [link]

Video

Slides

Citation

# journal version
@article{okumura2023solving,
  title = {Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution},
  journal = {Artificial Intelligence},
  pages = {103946},
  year = {2023},
  issn = {0004-3702},
  doi = {https://doi.org/10.1016/j.artint.2023.103946},
  author = {Keisuke Okumura and Xavier Défago}
}


# conference version
@inproceedings{okumura2022solving,
  title={Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution},
  author={Okumura, Keisuke and D{\'e}fago, Xavier},
  booktitle={Proceedings of the International Conference on Automated Planning and Scheduling},
  volume={32},
  pages={270--278},
  year={2022}
}

Contact

ko393 [at] cl.cam.ac.uk