2021/09/09 by Keisuke Okumura, Xavier Défago, Okumura, Keisuke +1 · 4 citations
Computer Science · #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #Multiagent Systems (cs.MA) #Optimization and Search Problems #Robotic Path Planning Algorithms #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.2109.04264
openalex publication_date 2021/09/09 · openalex created_date 2021/09/13 · openalex updated_date 2026/07/28
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.