Resolving Head-On Conflicts for Multi-Agent Path Finding with Conflict-Based Search

• URL: http://arxiv.org/abs/2007.03575v1
• Date: Tue, 7 Jul 2020 15:52:45 GMT
• Title: Resolving Head-On Conflicts for Multi-Agent Path Finding with Conflict-Based Search
• Authors: Lun Yang
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Conflict-Based Search (CBS) is a popular framework for solving the Multi-Agent Path Finding problem. Some of the conflicts incur a foreseeable conflict in one or both of the children nodes when splitting on them. This paper introduces a new technique, namely the head-on technique that finds out such conflicts, so they can be processed more efficiently by resolving the conflict with the potential conflict all together in one split. The proposed technique applies to all CBS-based solvers. Experimental results show that the head-on technique improves the state-of-the-art MAPF solver CBSH.

Related papers

• ECon: On the Detection and Resolution of Evidence Conflicts [56.89209046429291]
  The rise of large language models (LLMs) has significantly influenced the quality of information in decision-making systems. This study introduces a method for generating diverse, validated evidence conflicts to simulate real-world misinformation scenarios.
  arXiv  Detail & Related papers  (2024-10-05T07:41:17Z)
• Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
  We present a novel algorithm, SMART, for the problem based on a hybridization of three innovative techniques. Two of these techniques are based on dynamic programming, where we show a powerful connection between the coalitions selected for evaluation and the performance of the algorithms. Our techniques bring a new way of approaching the problem and a new level of precision to the field.
  arXiv  Detail & Related papers  (2024-07-22T23:24:03Z)
• Rehearsal: Simulating Conflict to Teach Conflict Resolution [54.32934135393982]
  Rehearsal is a system that allows users to rehearse conflicts with a believable simulated interlocutor. Users can utilize Rehearsal to practice handling a variety of predefined conflict scenarios. Rehearsal uses IRP to generate utterances grounded in conflict resolution theory.
  arXiv  Detail & Related papers  (2023-09-21T17:59:20Z)
• Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning [59.14935871979047]
  This work presents solutions to the Traveling Salesperson Problem with precedence constraints (TSPPC) using Deep Reinforcement Learning (DRL) Common to these approaches is the use of graph models based on multi-head attention layers.
  arXiv  Detail & Related papers  (2022-07-04T14:31:47Z)
• 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)
• Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search [35.71926950656326]
  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.
  arXiv  Detail & Related papers  (2020-12-10T22:44:35Z)
• End-to-End Learning and Intervention in Games [60.41921763076017]
  We provide a unified framework for learning and intervention in games. We propose two approaches, respectively based on explicit and implicit differentiation. The analytical results are validated using several real-world problems.
  arXiv  Detail & Related papers  (2020-10-26T18:39:32Z)
• Dynamic Multi-Agent Path Finding based on Conflict Resolution using Answer Set Programming [0.0]
  We introduce a new method to solve D-MAPF based on conflict-resolution. The idea is, when a set of new agents joins the team and there are conflicts, instead of replanning for the whole team, to replan only for a minimal subset of agents whose plans conflict with each other.
  arXiv  Detail & Related papers  (2020-09-22T00:50:35Z)
• 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)
• Joint Wasserstein Distribution Matching [89.86721884036021]
  Joint distribution matching (JDM) problem, which aims to learn bidirectional mappings to match joint distributions of two domains, occurs in many machine learning and computer vision applications. We propose to address JDM problem by minimizing the Wasserstein distance of the joint distributions in two domains. We then propose an important theorem to reduce the intractable problem into a simple optimization problem, and develop a novel method to solve it.
  arXiv  Detail & Related papers  (2020-03-01T03:39:00Z)

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.