Robust Multi-Agent Pickup and Delivery with Delays
- URL: http://arxiv.org/abs/2303.17422v1
- Date: Thu, 30 Mar 2023 14:42:41 GMT
- Title: Robust Multi-Agent Pickup and Delivery with Delays
- Authors: Giacomo Lodigiani, Nicola Basilico, Francesco Amigoni
- Abstract summary: 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.
- Score: 5.287544737925232
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Multi-Agent Pickup and Delivery (MAPD) is the problem of computing
collision-free paths for a group of agents such that they can safely reach
delivery locations from pickup ones. These locations are provided at runtime,
making MAPD a combination between classical Multi-Agent Path Finding (MAPF) and
online task assignment. Current algorithms for MAPD do not consider many of the
practical issues encountered in real applications: real agents often do not
follow the planned paths perfectly, and may be subject to delays and failures.
In this paper, we study the problem of MAPD with delays, and we present two
solution approaches that provide robustness guarantees by planning paths that
limit the effects of imperfect execution. In particular, we introduce two
algorithms, k-TP and p-TP, both based on a decentralized algorithm typically
used to solve MAPD, Token Passing (TP), which offer deterministic and
probabilistic guarantees, respectively. Experimentally, we compare our
algorithms against a version of TP enriched with online replanning. k-TP and
p-TP provide robust solutions, significantly reducing the number of replans
caused by delays, with little or no increase in solution cost and running time.
Related papers
- Learning Logic Specifications for Policy Guidance in POMDPs: an
Inductive Logic Programming Approach [57.788675205519986]
We learn high-quality traces from POMDP executions generated by any solver.
We exploit data- and time-efficient Indu Logic Programming (ILP) to generate interpretable belief-based policy specifications.
We show that learneds expressed in Answer Set Programming (ASP) yield performance superior to neural networks and similar to optimal handcrafted task-specifics within lower computational time.
arXiv Detail & Related papers (2024-02-29T15:36:01Z) - 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) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs)
This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models.
In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
arXiv Detail & Related papers (2023-07-01T18:35:21Z) - An Efficient Approach to the Online Multi-Agent Path Finding Problem by
Using Sustainable Information [10.367412630626834]
Multi-agent path finding (MAPF) is the problem of moving agents to the goal without collision.
We propose a three-level approach to solve online MAPF utilizing sustainable information.
Our algorithm can be 1.48 times faster than SOTA on average under different agent number settings.
arXiv Detail & Related papers (2023-01-11T13:04:35Z) - 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) - Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
Entanglement routing establishes remote entanglement connection between two arbitrary nodes.
We propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (SD) pairs in quantum networks.
arXiv Detail & Related papers (2021-11-15T14:07:22Z) - 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) - Symmetry Breaking for k-Robust Multi-Agent Path Finding [30.645303869311366]
k-Robust Conflict-BasedSearch (k-CBS) is an algorithm that produces coordinated and collision-free plan that is robust for up to k delays.
We introduce a variety of pairwise symmetry breaking constraints, specific to k-robust planning, that can efficiently find compatible and optimal paths for pairs of conflicting agents.
arXiv Detail & Related papers (2021-02-17T11:09:33Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
Security-constrained optimal power flow (SCOPF) is fundamental in power systems.
Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs.
This paper proposes a novel approach that combines deep learning and robust optimization techniques.
arXiv Detail & Related papers (2020-07-14T12:38:21Z) - 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.