Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution
This addresses real-time coordination challenges in multi-agent systems like robot swarms, offering incremental improvements in scalability and robustness for practical applications.
The paper tackles the combined problem of target assignment and path planning for multiple agents (unlabeled-MAPF) by proposing TSWAP, a sub-optimal complete algorithm that handles both offline and online scenarios, achieving near-optimal solutions with orders of magnitude runtime reduction in offline tests and demonstrating delay tolerance in real-robot demos.
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.