Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution
Keywords:Unlabeled Multi-agent Pathfinding, Target Assignment, Online Planning
AbstractReal-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.
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. https://doi.org/10.1609/icaps.v32i1.19810