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

Authors

  • Keisuke Okumura Tokyo Institute of Technology
  • Xavier Défago Tokyo Institute of Technology

Keywords:

Unlabeled Multi-agent Pathfinding, Target Assignment, Online Planning

Abstract

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, e.g., pattern formation by robot swarms. This paper studies two aspects of unlabeled-MAPF: (1) offline scenario: solving large instances by centralized approaches with small computation time, and (2) online scenario: executing unlabeled-MAPF despite timing uncertainties of real robots. For this purpose, we propose TSWAP, a novel sub-optimal complete algorithm, which takes an arbitrary initial target assignment 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; providing near-optimal solutions while reducing runtime by orders of magnitude compared to existing approaches. In addition, we present the benefits of Online TSWAP, such as delay tolerance, through real-robot demos.

Downloads

Published

2022-06-13

How to Cite

Okumura, K., & Défago, X. (2022). Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 270-278. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19810