Multi-Goal Multi-Agent Pickup and Delivery

• URL: http://arxiv.org/abs/2208.01223v1
• Date: Tue, 2 Aug 2022 03:20:59 GMT
• Title: Multi-Goal Multi-Agent Pickup and Delivery
• Authors: Qinghong Xu, Jiaoyang Li, Sven Koenig, Hang Ma
• Abstract summary: We consider the Multi-Agent Pickup-and-Delivery (MAPD) problem, where agents constantly engage with new tasks and need to plan collision-free paths to execute them. We propose two variants of an algorithm that assigns a sequence of tasks to each agent using the anytime algorithm Large Neighborhood Search (LNS) and plans paths using the Multi-Agent Path Finding (MAPF) algorithm Priority-Based Search (PBS) LNS-PBS is complete for well-formed MAPD instances, a realistic subclass of MAPD instances, and empirically more effective than the existing complete MAPD algorithm CENTRAL. LN
• Score: 25.11387753357413
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we consider the Multi-Agent Pickup-and-Delivery (MAPD) problem, where agents constantly engage with new tasks and need to plan collision-free paths to execute them. To execute a task, an agent needs to visit a pair of goal locations, consisting of a pickup location and a delivery location. We propose two variants of an algorithm that assigns a sequence of tasks to each agent using the anytime algorithm Large Neighborhood Search (LNS) and plans paths using the Multi-Agent Path Finding (MAPF) algorithm Priority-Based Search (PBS). LNS-PBS is complete for well-formed MAPD instances, a realistic subclass of MAPD instances, and empirically more effective than the existing complete MAPD algorithm CENTRAL. LNS-wPBS provides no completeness guarantee but is empirically more efficient and stable than LNS-PBS. It scales to thousands of agents and thousands of tasks in a large warehouse and is empirically more effective than the existing scalable MAPD algorithm HBH+MLA*. LNS-PBS and LNS-wPBS also apply to a more general variant of MAPD, namely the Multi-Goal MAPD (MG-MAPD) problem, where tasks can have different numbers of goal locations.

Related papers

• 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)
• Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search [30.364955687049292]
  State-of-the-art anytime MAPF is based on Large Neighborhood Search (LNS) We propose Bandit-based Adaptive LArge Neighborhood search Combined with Exploration (BALANCE) We empirically demonstrate cost improvements of at least 50% compared to state-of-the-art anytime MAPF in large-scale scenarios.
  arXiv  Detail & Related papers  (2023-12-28T01:24:42Z)
• 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)
• Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement in Large-Scale Warehouses [6.852682268049646]
  We introduce a new problem formulation, Double-Deck Multi-Agent Pickup and Delivery (DD-MAPD), which models the multi-robot shelf rearrangement problem in automated warehouses. We propose MAPF-DECOMP, an algorithmic framework that decomposes a DD-MAPD instance into a MAPF instance for coordinating shelf trajectories and a subsequent MAPD instance for computing paths for agents. Our experimental results demonstrate the efficiency and effectiveness of MAPF-DECOMP, with the ability to compute high-quality solutions for large-scale instances with over one thousand shelves and hundreds of agents in just minutes of runtime.
  arXiv  Detail & Related papers  (2023-04-27T16:26:05Z)
• Robust Multi-Agent Pickup and Delivery with Delays [5.287544737925232]
  Multi-Agent Pickup and Delivery (MAPD) is the problem of computing collision-free paths for a group of agents. Current algorithms for MAPD do not consider many of the practical issues encountered in real applications. We present two solution approaches that provide robustness guarantees by planning paths that limit the effects of imperfect execution.
  arXiv  Detail & Related papers  (2023-03-30T14:42:41Z)
• 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 Multi-Agent Path Finding for Precedence Constrained Planning Tasks [0.7742297876120561]
  We consider an extension to this problem, Precedence Constrained Multi-Agent Path Finding (PC-MAPF) We propose a novel algorithm, Precedence Constrained Conflict Based Search (PC-CBS), which finds makespan-optimal solutions for this class of problems. We benchmark the performance of this algorithm over various warehouse assembly, and multi-agent pickup and delivery tasks, and use it to evaluate the sub-optimality of a recently proposed efficient baseline.
  arXiv  Detail & Related papers  (2022-02-08T07:26:45Z)
• 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)
• The Surprising Effectiveness of MAPPO in Cooperative, Multi-Agent Games [67.47961797770249]
  Multi-Agent PPO (MAPPO) is a multi-agent PPO variant which adopts a centralized value function. We show that MAPPO achieves performance comparable to the state-of-the-art in three popular multi-agent testbeds.
  arXiv  Detail & Related papers  (2021-03-02T18:59:56Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

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.