Conflict-Based Search for Explainable Multi-Agent Path Finding
- URL: http://arxiv.org/abs/2202.09930v1
- Date: Sun, 20 Feb 2022 23:13:14 GMT
- Title: Conflict-Based Search for Explainable Multi-Agent Path Finding
- Authors: Justin Kottinger, Shaull Almagor, Morteza Lahijanian
- Abstract summary: In safety-critical applications, a human supervisor may want to verify that the plan is indeed collision-free.
MAPF problem asks for a set of non-colliding paths that admits a short-enough explanation.
Traditional MAPF algorithms are not equipped to directly handle explainable-MAPF.
We adapt Conflict Based Search (CBS), a well-studied algorithm for MAPF, to handle explainable MAPF.
- Score: 7.734726150561088
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the Multi-Agent Path Finding (MAPF) problem, the goal is to find
non-colliding paths for agents in an environment, such that each agent reaches
its goal from its initial location. In safety-critical applications, a human
supervisor may want to verify that the plan is indeed collision-free. To this
end, a recent work introduces a notion of explainability for MAPF based on a
visualization of the plan as a short sequence of images representing time
segments, where in each time segment the trajectories of the agents are
disjoint. Then, the explainable MAPF problem asks for a set of non-colliding
paths that admits a short-enough explanation. Explainable MAPF adds a new
difficulty to MAPF, in that it is NP-hard with respect to the size of the
environment, and not just the number of agents. Thus, traditional MAPF
algorithms are not equipped to directly handle explainable-MAPF. In this work,
we adapt Conflict Based Search (CBS), a well-studied algorithm for MAPF, to
handle explainable MAPF. We show how to add explainability constraints on top
of the standard CBS tree and its underlying A* search. We examine the
usefulness of this approach and, in particular, the tradeoff between planning
time and explainability.
Related papers
- MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale [46.35418789518417]
Multi-agent pathfinding is a challenging computational problem that typically requires to find collision-free paths for multiple agents in a shared environment.
We have created a foundation model for the MAPF problems called MAPF-GPT.
Using imitation learning, we have trained a policy on a set of sub-optimal expert trajectories that can generate actions in conditions of partial observability.
We show that MAPF-GPT notably outperforms the current best-performing learnable-MAPF solvers on a diverse range of problem instances.
arXiv Detail & Related papers (2024-08-29T12:55:10Z) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations.
Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential.
We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
arXiv Detail & Related papers (2024-01-30T14:26:04Z) - Decentralized Monte Carlo Tree Search for Partially Observable
Multi-agent Pathfinding [49.730902939565986]
Multi-Agent Pathfinding problem involves finding a set of conflict-free paths for a group of agents confined to a graph.
In this study, we focus on the decentralized MAPF setting, where the agents may observe the other agents only locally.
We propose a decentralized multi-agent Monte Carlo Tree Search (MCTS) method for MAPF tasks.
arXiv Detail & Related papers (2023-12-26T06:57:22Z) - Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via
Planning and Learning [46.354187895184154]
Multi-agent Pathfinding (MAPF) problem generally asks to find a set of conflict-free paths for a set of agents confined to a graph.
In this work, we investigate the decentralized MAPF setting, when the central controller that posses all the information on the agents' locations and goals is absent.
We focus on the practically important lifelong variant of MAPF, which involves continuously assigning new goals to the agents upon arrival to the previous ones.
arXiv Detail & Related papers (2023-10-02T13:51:32Z) - Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding [29.76466191644455]
Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics that asks us to compute collision-free paths for a team of agents.
We propose a new approach for MAPF where agents are guided to their destination by following congestion-avoiding paths.
We evaluate the idea in two large-scale settings: one-shot MAPF, where each agent has a single destination, and lifelong MAPF, where agents are continuously assigned new destinations.
arXiv Detail & Related papers (2023-08-22T07:17:39Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding.
Specifically, we use individual paths to assist the agents with the the goal-reaching behavior.
We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
arXiv Detail & Related papers (2023-07-25T12:33:53Z) - LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding [5.025654873456756]
We propose a novel complete algorithm for multi-agent pathfinding (MAPF) called lazy constraints addition search for MAPF (LaCAM)
LaCAM uses a two-level search to find solutions quickly, even with hundreds of agents or more.
Our experiments reveal that LaCAM is comparable to or outperforms state-of-the-art sub-optimal MAPF algorithms in a variety of scenarios.
arXiv Detail & Related papers (2022-11-24T06:27:18Z) - POGEMA: Partially Observable Grid Environment for Multiple Agents [64.88759709443819]
POGEMA is a sandbox for challenging partially observable multi-agent pathfinding (PO-MAPF) problems.
It can be tailored to a variety of PO-MAPF, which can serve as an excellent testing ground for planning and learning methods.
arXiv Detail & Related papers (2022-06-22T09:39:50Z) - Leveraging Experience in Lifelong Multi-Agent Pathfinding [12.401344261399613]
In Lifelong Multi-Agent Path Finding (L-MAPF) a team of agents performs a stream of tasks while avoiding collisions with one another.
We introduce a new RHCR-inspired approach called exRHCR, which exploits experience in its constituent MAPF queries.
ExRHCR solves L-MAPF up to 25% faster than RHCR, and allows to increase throughput for given task streams by as much as 3%-16%.
arXiv Detail & Related papers (2022-02-09T10:41:35Z) - Compilation-based Solvers for Multi-Agent Path Finding: a Survey,
Discussion, and Future Opportunities [7.766921168069532]
We show the lessons learned from past developments and current trends in the topic and discuss its wider impact.
Two major approaches to optimal MAPF solving include (1) dedicated search-based methods, which solve MAPF directly, and (2) compilation-based methods that reduce a MAPF instance to an instance in a different well established formalism.
arXiv Detail & Related papers (2021-04-23T20:13:12Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.