Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search

• URL: http://arxiv.org/abs/2012.06005v1
• Date: Thu, 10 Dec 2020 22:44:35 GMT
• Title: Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search
• Authors: Taoan Huang, Bistra Dilkina, Sven Koenig
• Abstract summary: Conflict-Based Search (CBS) is a state-of-the-art algorithm for path finding. We propose a machine-learning framework for conflict selection that observes the decisions made by the oracle. Our method significantly improves the success rates, the search tree sizes and runtimes over the current state-of-the-art CBS solver.
• Score: 35.71926950656326
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Conflict-Based Search (CBS) is a state-of-the-art algorithm for multi-agent path finding. At the high level, CBS repeatedly detects conflicts and resolves one of them by splitting the current problem into two subproblems. Previous work chooses the conflict to resolve by categorizing the conflict into three classes and always picking a conflict from the highest-priority class. In this work, we propose an oracle for conflict selection that results in smaller search tree sizes than the one used in previous work. However, the computation of the oracle is slow. Thus, we propose a machine-learning framework for conflict selection that observes the decisions made by the oracle and learns a conflict-selection strategy represented by a linear ranking function that imitates the oracle's decisions accurately and quickly. Experiments on benchmark maps indicate that our method significantly improves the success rates, the search tree sizes and runtimes over the current state-of-the-art CBS solver.

Related papers

• AdaCAD: Adaptively Decoding to Balance Conflicts between Contextual and Parametric Knowledge [57.66282463340297]
  Knowledge conflict arises from discrepancies between information in the context of a large language model (LLM) and the knowledge stored in its parameters. We propose a fine-grained, instance-level approach called AdaCAD, which dynamically infers the weight of adjustment based on the degree of conflict.
  arXiv  Detail & Related papers  (2024-09-11T16:35:18Z)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  Multi-armed bandits are a sequential-decision-making framework, where, at each interaction step, the learner selects an arm and observes a reward. We consider the scenario in which the learner has access to a set of mediators, each of which selects the arms on the agent's behalf according to a and possibly unknown policy. We propose a sequential decision-making strategy for discovering the best arm under the assumption that the mediators' policies are known to the learner.
  arXiv  Detail & Related papers  (2023-08-29T18:18:21Z)
• 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)
• Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree [9.518757918128799]
  Combined Target-Assignment and Path-Finding problem (TAPF) requires simultaneously assigning targets to agents. Conflict-Based Search with Target Assignment (CBS-TA) is a leading approach to address TAPF. We show that, in theory, ITA-CBS is guaranteed to find an optimal solution and, in practice, is computationally efficient.
  arXiv  Detail & Related papers  (2023-07-02T20:52:16Z)
• Subdimensional Expansion Using Attention-Based Learning For Multi-Agent Path Finding [9.2127262112464]
  Multi-Agent Path Finding (MAPF) finds conflict-free paths for multiple agents from their respective start to goal locations. We develop a novel multi-agent planner called LM* by integrating this learning-based single-agent planner with M*. Our results show that for both "seen" and "unseen" maps, in comparison with M*, LM* has fewer conflicts to be resolved and thus, runs faster and enjoys higher success rates.
  arXiv  Detail & Related papers  (2021-09-29T20:01:04Z)
• A Deep Dive into Conflict Generating Decisions [3.222802562733787]
  We use Conflict Driven Clause Learning to solve Satisfiability (SAT) problems. We show that CDCL learns clauses from conflicts, a technique that allows a solver to prune its search space. We develop Common Reason Variable Reduction (CRVR) as a new decision strategy that reduces the selection priority of some variables from the learned clauses of mc decisions.
  arXiv  Detail & Related papers  (2021-05-10T18:17:52Z)
• Resolving Head-On Conflicts for Multi-Agent Path Finding with Conflict-Based Search [0.0]
  Conflict-Based Search (CBS) is a popular framework for solving the Multi-Agent Path Finding problem. This paper introduces a new technique, namely the head-on technique that finds out such conflicts. Experimental results show that the head-on technique improves the state-of-the-art MAPF solver CBSH.
  arXiv  Detail & Related papers  (2020-07-07T15:52:45Z)
• Conflict-Based Search for Connected Multi-Agent Path Finding [6.18778092044887]
  We study a variant of the multi-agent path finding problem (MAPF) in which agents are required to remain connected to each other and to a designated base. This problem has applications in search and rescue missions where the entire execution must be monitored by a human operator. We re-visit the conflict-based search algorithm known for MAPF, and define a variant where conflicts arise from disconnections rather than collisions.
  arXiv  Detail & Related papers  (2020-06-05T08:02:36Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)
• Fast Template Matching and Update for Video Object Tracking and Segmentation [56.465510428878]
  The main task we aim to tackle is the multi-instance semi-supervised video object segmentation across a sequence of frames. The challenges lie in the selection of the matching method to predict the result as well as to decide whether to update the target template. We propose a novel approach which utilizes reinforcement learning to make these two decisions at the same time.
  arXiv  Detail & Related papers  (2020-04-16T08:58:45Z)

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.