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

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
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}
}
Important Related Work
Contact
ko393 [at] cl.cam.ac.uk