The Study of Highway for Lifelong Multi-Agent Path Finding
- URL: http://arxiv.org/abs/2304.04217v1
- Date: Sun, 9 Apr 2023 11:21:22 GMT
- Title: The Study of Highway for Lifelong Multi-Agent Path Finding
- Authors: Ming-Feng Li and Min Sun
- Abstract summary: In modern fulfillment warehouses, agents traverse the map to complete endless tasks that arrive on the fly.
The goal of tackling this challenging problem is to find the path for each agent in a finite runtime while maximizing the throughput.
We explore the idea of highways mainly studied for one-shot MAPF, which reduces the complexity of the problem by encouraging agents to move in the same direction.
- Score: 30.329065698451902
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In modern fulfillment warehouses, agents traverse the map to complete endless
tasks that arrive on the fly, which is formulated as a lifelong Multi-Agent
Path Finding (lifelong MAPF) problem. The goal of tackling this challenging
problem is to find the path for each agent in a finite runtime while maximizing
the throughput. However, existing methods encounter exponential growth of
runtime and undesirable phenomena of deadlocks and rerouting as the map size or
agent density grows. To address these challenges in lifelong MAPF, we explore
the idea of highways mainly studied for one-shot MAPF (i.e., finding paths at
once beforehand), which reduces the complexity of the problem by encouraging
agents to move in the same direction. We utilize two methods to incorporate the
highway idea into the lifelong MAPF framework and discuss the properties that
minimize the existing problems of deadlocks and rerouting. The experimental
results demonstrate that the runtime is considerably reduced and the decay of
throughput is gradually insignificant as the map size enlarges under the
settings of the highway. Furthermore, when the density of agents increases, the
phenomena of deadlocks and rerouting are significantly reduced by leveraging
the highway.
Related papers
- Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities [44.292720085661585]
We present our winning approach to the 2023 League of Robot Runners LMAPF competition.
The first challenge is to search for high-quality LMAPF solutions within a limited planning time.
The second challenge is to alleviate myopic congestion and the effect of behaviors in LMAPF algorithms.
The third challenge is to bridge the gaps between the LMAPF models used in the literature and real-world applications.
arXiv Detail & Related papers (2024-04-24T19:37:18Z) - 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) - Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via
Planning and Learning [46.354187895184154]
Multi-agent Pathfinding (MAPF) problem generally asks to find a set of conflict-free paths for a set of agents confined to a graph.
In this work, we investigate the decentralized MAPF setting, when the central controller that posses all the information on the agents' locations and goals is absent.
We focus on the practically important lifelong variant of MAPF, which involves continuously assigning new goals to the agents upon arrival to the previous ones.
arXiv Detail & Related papers (2023-10-02T13:51:32Z) - 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) - Long-HOT: A Modular Hierarchical Approach for Long-Horizon Object
Transport [83.06265788137443]
We address key challenges in long-horizon embodied exploration and navigation by proposing a new object transport task and a novel modular framework for temporally extended navigation.
Our first contribution is the design of a novel Long-HOT environment focused on deep exploration and long-horizon planning.
We propose a modular hierarchical transport policy (HTP) that builds a topological graph of the scene to perform exploration with the help of weighted frontiers.
arXiv Detail & Related papers (2022-10-28T05:30:49Z) - 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) - Road Network Guided Fine-Grained Urban Traffic Flow Inference [108.64631590347352]
Accurate inference of fine-grained traffic flow from coarse-grained one is an emerging yet crucial problem.
We propose a novel Road-Aware Traffic Flow Magnifier (RATFM) that exploits the prior knowledge of road networks.
Our method can generate high-quality fine-grained traffic flow maps.
arXiv Detail & Related papers (2021-09-29T07:51:49Z) - Decentralised Approach for Multi Agent Path Finding [6.599344783327053]
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.
arXiv Detail & Related papers (2021-06-03T18:07:26Z) - Lifelong Multi-Agent Path Finding in Large-Scale Warehouses [26.017429163961328]
Multi-Agent Path Finding (MAPF) is the problem of moving a team of agents to their goal locations without collisions.
We propose a new framework for solving lifelong MAPF by decomposing the problem into a sequence of Windowed MAPF instances.
arXiv Detail & Related papers (2020-05-15T06:07:15Z)
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.