Solving simultaneous target assignment and path planning efficiently with time-independent execution

DOI10.1016/J.ARTINT.2023.103946MaRDI QIDQ6108766zbMATH OpenOpenAlexFDO

Authors K. Okumura, Xavier Défago

Publication date 26 July 2023

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.04264

zbMATH Keywords

multi-robot coordinationonline planningtarget assignmentunlabeled multi-agent pathfinding

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Artificial intelligence for robotics (68T40) Agent technology and artificial intelligence (68T42)

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.

Recommendations

• Analyzing the multiple-target-multiple-agent scenario using optimal assignment algorithms
• scientific article; zbMATH DE number 5959974
• Safe multi-agent pathfinding with time uncertainty
• Robust multi-agent path finding and executing
• Multi-agent Path Finding Modulo Theory with Continuous Movements and the Sum of Costs Objective

Cites work

• A note on two problems in connexion with graphs
• A survey of heuristics for the weighted matching problem
• A survey of multi-agent formation control
• Conflict-based search for optimal multi-agent pathfinding
• scientific article; zbMATH DE number 5959974 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• scientific article; zbMATH DE number 3399279 (Why is no real title available?)
• Introduction to Distributed Self-Stabilizing Algorithms
• Lexicographic bottleneck problems
• Maximal Flow Through a Network
• Multi-color pebble motion on graphs
• Network flows. Theory, algorithms, and applications.
• Priority inheritance with backtracking for iterative multi-agent path finding
• Push and rotate: a complete multi-agent pathfinding algorithm
• Reconfigurations in Graphs and Grids

Cited in

(2)

• scientific article; zbMATH DE number 7295087 (Why is no real title available?)
• A scalable multi-robot goal assignment algorithm for minimizing mission time followed by total movement cost

This page was built for publication: Solving simultaneous target assignment and path planning efficiently with time-independent execution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6108766)