Decentralised Approach for Multi Agent Path Finding

2021-06-03 · Shyni Thomas, M. Narasimha Murty

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.

📄 PDF Abstract BibTeX arXiv:2106.05188

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-Agent Path FindingScheduling

Methods 이 논문이 사용한 방법론

AWARE We propose to theoretically and empirically examine the effect of incorporating weighting schemes into walk-aggregating GNNs. To this end, we propose a simple, interpretable, and…

Karma Mechanisms for Decentralised, Cooperative Multi Agent Path Finding

2026-04-09 · Kevin Riehl, Julius Schlapbach, Anastasios Kouvelas, Michail A. Makridis arxiv

Multi-Agent Path Finding (MAPF) is a fundamental coordination problem in large-scale robotic and cyber-physical systems, where multiple agents must compute conflict-free trajectories with limited computational and commun…

Multi-Agent Common Knowledge Reinforcement Learning

2018-10-27 · NeurIPS 2019 12 · Christian A. Schroeder de Witt, Jakob N. Foerster, Gregory Farquhar, Philip H. S. Torr 외

Cooperative multi-agent reinforcement learning often requires decentralised policies, which severely limit the agents' ability to coordinate their behaviour. In this paper, we show that common knowledge between agents al…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+2

Decentralised Multi-Demic Evolutionary Approach to the Dynamic Multi-Agent Travelling Salesman Problem

2019-06-13 · Thomas E. Kent, Arthur G. Richards

The Travelling Salesman and its variations are some of the most well known NP hard optimisation problems. This paper looks to use both centralised and decentralised implementations of Evolutionary Algorithms (EA) to solv…

Evolutionary Algorithms

Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning

2020-03-19 · Tabish Rashid, Mikayel Samvelyan, Christian Schroeder de Witt, Gregory Farquhar 외

In many real-world settings, a team of agents must coordinate its behaviour while acting in a decentralised fashion. At the same time, it is often possible to train the agents in a centralised fashion where global state …

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+3

Multiagent Model-based Credit Assignment for Continuous Control

2021-12-27 · Dongge Han, Chris Xiaoxuan Lu, Tomasz Michalak, Michael Wooldridge

Deep reinforcement learning (RL) has recently shown great promise in robotic continuous control tasks. Nevertheless, prior research in this vein center around the centralized learning setting that largely relies on the c…

continuous-control Continuous Control Deep Reinforcement Learning model+4