Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions

• URL: http://arxiv.org/abs/2103.04516v1
• Date: Mon, 8 Mar 2021 02:34:17 GMT
• Title: Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions
• Authors: Zhongqiang Ren, Sivakumar Rathinam and Howie Choset
• Abstract summary: Multi-agent path finding (MAPF) determines an ensemble of collision-free paths for multiple agents between their respective start and goal locations. This article presents a natural generalization of MAPF with asynchronous actions where agents do not necessarily start and stop concurrently.
• Score: 10.354181009277623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-agent path finding (MAPF) determines an ensemble of collision-free paths for multiple agents between their respective start and goal locations. Among the available MAPF planners for workspaces modeled as a graph, A*-based approaches have been widely investigated and have demonstrated their efficiency in numerous scenarios. However, almost all of these A*-based approaches assume that each agent executes an action concurrently in that all agents start and stop together. This article presents a natural generalization of MAPF with asynchronous actions where agents do not necessarily start and stop concurrently. The main contribution of the work is a proposed approach called Loosely Synchronized Search (LSS) that extends A*-based MAPF planners to handle asynchronous actions. We show LSS is complete and finds an optimal solution if one exists. We also combine LSS with other existing MAPF methods that aims to trade-off optimality for computational efficiency. Extensive numerical results are presented to corroborate the performance of the proposed approaches. Finally, we also verify the applicability of our method in the Robotarium, a remotely accessible swarm robotics research platform.

Related papers

• Multi-Agent Sampling: Scaling Inference Compute for Data Synthesis with Tree Search-Based Agentic Collaboration [81.45763823762682]
  This work aims to bridge the gap by investigating the problem of data synthesis through multi-agent sampling. We introduce Tree Search-based Orchestrated Agents(TOA), where the workflow evolves iteratively during the sequential sampling process. Our experiments on alignment, machine translation, and mathematical reasoning demonstrate that multi-agent sampling significantly outperforms single-agent sampling as inference compute scales.
  arXiv  Detail & Related papers  (2024-12-22T15:16:44Z)
• Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions [5.5233853454863615]
  Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations. Although many MAPF algorithms can handle up to thousands of agents, they usually rely on the assumption that each action of the agent takes a time unit. This paper develops new planners that lie on the other end of the spectrum, trading off solution quality for scalability.
  arXiv  Detail & Related papers  (2024-12-16T11:36:24Z)
• MALT: Improving Reasoning with Multi-Agent LLM Training [64.13803241218886]
  We present a first step toward "Multi-agent LLM training" (MALT) on reasoning problems. Our approach employs a sequential multi-agent setup with heterogeneous LLMs assigned specialized roles. We evaluate our approach across MATH, GSM8k, and CQA, where MALT on Llama 3.1 8B models achieves relative improvements of 14.14%, 7.12%, and 9.40% respectively.
  arXiv  Detail & Related papers  (2024-12-02T19:30:36Z)
• Cooperative Reward Shaping for Multi-Agent Pathfinding [4.244426154524592]
  The primary objective of Multi-Agent Pathfinding (MAPF) is to plan efficient and conflict-free paths for all agents. Traditional multi-agent path planning algorithms struggle to achieve efficient distributed path planning for multiple agents. This letter introduces a unique reward shaping technique based on Independent Q-Learning (IQL)
  arXiv  Detail & Related papers  (2024-07-15T02:44:41Z)
• MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem [5.580214316179672]
  The MG-MAPF problem requires each agent to visit pre-assigned multiple goal points at least once without conflict. We propose the Multi-Goal Conflict-Based Search (MGCBS), which is based on Decoupling the goal Safe interval visiting order search and the Single-agent pathfinding. Our method can consistently obtain optimal results and execute up to 7 times faster than the state-of-the-art method in our evaluation.
  arXiv  Detail & Related papers  (2024-04-30T12:49:54Z)
• 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)
• 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)
• 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)
• 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)

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.