Conflict-Based Search for Connected Multi-Agent Path Finding

• URL: http://arxiv.org/abs/2006.03280v1
• Date: Fri, 5 Jun 2020 08:02:36 GMT
• Title: Conflict-Based Search for Connected Multi-Agent Path Finding
• Authors: Arthur Queffelec and Ocan Sankur and Fran\c{c}ois Schwarzentruber
• Abstract summary: 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.
• Score: 6.18778092044887
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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. We study optimizations, and give experimental results in which we compare our algorithms with the literature.

Related papers

• 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)
• PSDiff: Diffusion Model for Person Search with Iterative and Collaborative Refinement [59.6260680005195]
  We present a novel Person Search framework based on the Diffusion model, PSDiff. PSDiff formulates the person search as a dual denoising process from noisy boxes and ReID embeddings to ground truths. Following the new paradigm, we further design a new Collaborative Denoising Layer (CDL) to optimize detection and ReID sub-tasks in an iterative and collaborative way.
  arXiv  Detail & Related papers  (2023-09-20T08:16: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)
• Adversarial Search and Tracking with Multiagent Reinforcement Learning in Sparsely Observable Environment [7.195547595036644]
  We study a search and tracking (S&T) problem where a team of dynamic search agents must collaborate to track an adversarial, evasive agent. This problem is challenging for both model-based searching and reinforcement learning (RL) methods since the adversary exhibits reactionary and deceptive evasive behaviors in a large space leading to sparse detections for the search agents. We propose a novel Multi-Agent RL (MARL) framework that leverages the estimated adversary location from our learnable filtering model.
  arXiv  Detail & Related papers  (2023-06-20T05:31:13Z)
• PS-ARM: An End-to-End Attention-aware Relation Mixer Network for Person Search [56.02761592710612]
  We propose a novel attention-aware relation mixer (ARM) for module person search. Our ARM module is native and does not rely on fine-grained supervision or topological assumptions. Our PS-ARM achieves state-of-the-art performance on both datasets.
  arXiv  Detail & Related papers  (2022-10-07T10:04:12Z)
• Multi-agent Deep Covering Skill Discovery [50.812414209206054]
  We propose Multi-agent Deep Covering Option Discovery, which constructs the multi-agent options through minimizing the expected cover time of the multiple agents' joint state space. Also, we propose a novel framework to adopt the multi-agent options in the MARL process. We show that the proposed algorithm can effectively capture the agent interactions with the attention mechanism, successfully identify multi-agent options, and significantly outperforms prior works using single-agent options or no options.
  arXiv  Detail & Related papers  (2022-10-07T00:40:59Z)
• Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding [25.11387753357413]
  We study the multi-goal task assignment and path finding (MG-TAPF) problem from theoretical and algorithmic perspectives. Theoretically, we prove that the MG-TAPF problem is NP-hard to solve optimally. We present algorithms that build upon algorithmic techniques for the multi-agent path finding problem and solve the MG-TAPF problem optimally and bounded-suboptimally.
  arXiv  Detail & Related papers  (2022-08-02T03:17:29Z)
• 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)
• Cooperative Exploration for Multi-Agent Deep Reinforcement Learning [127.4746863307944]
  We propose cooperative multi-agent exploration (CMAE) for deep reinforcement learning. The goal is selected from multiple projected state spaces via a normalized entropy-based technique. We demonstrate that CMAE consistently outperforms baselines on various tasks.
  arXiv  Detail & Related papers  (2021-07-23T20:06:32Z)
• 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)

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.