Decentralised Approach for Multi Agent Path Finding
- URL: http://arxiv.org/abs/2106.05188v1
- Date: Thu, 3 Jun 2021 18:07:26 GMT
- Title: Decentralised Approach for Multi Agent Path Finding
- Authors: Shyni Thomas, M. Narasimha Murty
- Abstract summary: Multi Agent Path Finding (MAPF) requires identification of conflict free paths for spatially-extended agents.
These find application in real world problems like Convoy Movement Problem, Train Scheduling etc.
Our proposed approach, Decentralised Multi Agent Path Finding (DeMAPF), handles MAPF as a sequence of pathplanning and allocation problems.
- Score: 6.599344783327053
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Multi Agent Path Finding (MAPF) requires identification of conflict free
paths for agents which could be point-sized or with dimensions. In this paper,
we propose an approach for MAPF for spatially-extended agents. These find
application in real world problems like Convoy Movement Problem, Train
Scheduling etc. Our proposed approach, Decentralised Multi Agent Path Finding
(DeMAPF), handles MAPF as a sequence of pathplanning and allocation problems
which are solved by two sets of agents Travellers and Routers respectively,
over multiple iterations. The approach being decentralised allows an agent to
solve the problem pertinent to itself, without being aware of other agents in
the same set. This allows the agents to be executed on independent machines,
thereby leading to scalability to handle large sized problems. We prove, by
comparison with other distributed approaches, that the approach leads to a
faster convergence to a conflict-free solution, which may be suboptimal, with
lesser memory requirement.
Related papers
- Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
We present the first optimal any-angle multi-agent pathfinding algorithm.
Our planner is based on the Continuous Conflict-based Search (CCBS) algorithm and an optimal any-angle variant of the Safe Interval Path Planning (TO-AA-SIPP)
We adapt two techniques from classical MAPF to the any-angle setting, namely Disjoint Splitting and Multi-Constraints.
arXiv Detail & Related papers (2024-04-25T07:41:47Z) - 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) - 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) - MADiff: Offline Multi-agent Learning with Diffusion Models [79.18130544233794]
Diffusion model (DM) recently achieved huge success in various scenarios including offline reinforcement learning.
We propose MADiff, a novel generative multi-agent learning framework to tackle this problem.
Our experiments show the superior performance of MADiff compared to baseline algorithms in a wide range of multi-agent learning tasks.
arXiv Detail & Related papers (2023-05-27T02:14:09Z) - 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) - Multi-Agent Terraforming: Efficient Multi-Agent Path Finding via
Environment Manipulation [12.401344261399613]
Multi-agent pathfinding is concerned with planning collision-free paths for a team of agents from their start to goal locations in an environment cluttered with obstacles.
We introduce a new extension of MAPF, which we call Terraforming MAPF (tMAPF), where some agents are responsible for moving obstacles to clear the way for other agents.
We present extensions of two state-of-the-art algorithms, CBS and PBS, in order to tackle tMAPF, and demonstrate that they can consistently outperform the best solution possible under a static-obstacle setting.
arXiv Detail & Related papers (2022-03-20T12:18:35Z) - 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) - MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal
Sequencing and Path Finding [10.354181009277623]
In multi-agent applications such as surveillance and logistics, fleets of mobile agents are often expected to coordinate and safely visit a large number of goal locations.
In this article, we introduce a new algorithm called MS* which computes an optimal solution for this multi-agent problem.
Numerical results show that our new algorithm can solve the multi-agent problem with 20 agents and 50 goals in a minute of CPU time on a standard laptop.
arXiv Detail & Related papers (2021-03-18T01:57:35Z) - F2A2: Flexible Fully-decentralized Approximate Actor-critic for
Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
Decentralized multi-agent reinforcement learning algorithms are sometimes unpractical in complicated applications.
We propose a flexible fully decentralized actor-critic MARL framework, which can handle large-scale general cooperative multi-agent setting.
Our framework can achieve scalability and stability for large-scale environment and reduce information transmission.
arXiv Detail & Related papers (2020-04-17T14:56:29Z)
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.