Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks

• URL: http://arxiv.org/abs/2201.06014v2
• Date: Wed, 19 Jan 2022 02:44:05 GMT
• Title: Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks
• Authors: Tomoki Yamauchi, Yuki Miyashita and Toshiharu Sugawara
• Abstract summary: We propose a deadlock avoidance method called standby-based deadlock avoidance (SBDA) SBDA uses standby nodes determined in real-time using the articulation-point-finding algorithm. We demonstrated that our proposed method outperforms a conventional approach.
• Score: 2.3204178451683264
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The multi-agent pickup and delivery (MAPD) problem, in which multiple agents iteratively carry materials without collisions, has received significant attention. However, many conventional MAPD algorithms assume a specifically designed grid-like environment, such as an automated warehouse. Therefore, they have many pickup and delivery locations where agents can stay for a lengthy period, as well as plentiful detours to avoid collisions owing to the freedom of movement in a grid. By contrast, because a maze-like environment such as a search-and-rescue or construction site has fewer pickup/delivery locations and their numbers may be unbalanced, many agents concentrate on such locations resulting in inefficient operations, often becoming stuck or deadlocked. Thus, to improve the transportation efficiency even in a maze-like restricted environment, we propose a deadlock avoidance method, called standby-based deadlock avoidance (SBDA). SBDA uses standby nodes determined in real-time using the articulation-point-finding algorithm, and the agent is guaranteed to stay there for a finite amount of time. We demonstrated that our proposed method outperforms a conventional approach. We also analyzed how the parameters used for selecting standby nodes affect the performance.

Related papers

• Adversarial Schrödinger Bridge Matching [66.39774923893103]
  Iterative Markovian Fitting (IMF) procedure alternates between Markovian and reciprocal projections of continuous-time processes. We propose a novel Discrete-time IMF (D-IMF) procedure in which learning of processes is replaced by learning just a few transition probabilities in discrete time. We show that our D-IMF procedure can provide the same quality of unpaired domain translation as the IMF, using only several generation steps instead of hundreds.
  arXiv  Detail & Related papers  (2024-05-23T11:29:33Z)
• Accelerating Search-Based Planning for Multi-Robot Manipulation by Leveraging Online-Generated Experiences [20.879194337982803]
  Multi-Agent Path-Finding (MAPF) algorithms have shown promise in discrete 2D domains, providing rigorous guarantees. We propose an approach for accelerating conflict-based search algorithms by leveraging their repetitive and incremental nature.
  arXiv  Detail & Related papers  (2024-03-29T20:31:07Z)
• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  We consider a setting in which $N$ agents aim to speedup a common Approximation problem by acting in parallel and communicating with a central server. To mitigate the effect of delays and stragglers, we propose textttDASA, a Delay-Adaptive algorithm for multi-agent Approximation.
  arXiv  Detail & Related papers  (2024-03-25T22:49:56Z)
• Terraforming -- Environment Manipulation during Disruptions for Multi-Agent Pickup and Delivery [11.034208232337749]
  In automated warehouses, teams of mobile robots fulfill the packaging process by transferring inventory pods to designated workstations while navigating narrow aisles formed by tightly packed pods. This problem is typically modeled as a Multi-Agent Pickup and Delivery (MAPD) problem, which is then solved by repeatedly planning collision-free paths for agents on a fixed graph. Existing approaches make the limiting assumption that agents are only allowed to move pods that correspond to their current task, while considering the other pods as stationary obstacles (even though all pods are movable). This behavior can result in unnecessarily long paths which could otherwise be avoided by opening additional corridors via pod manipulation
  arXiv  Detail & Related papers  (2023-05-19T08:19:24Z)
• 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)
• Reinforcement Learning with a Terminator [80.34572413850186]
  We learn the parameters of the TerMDP and leverage the structure of the estimation problem to provide state-wise confidence bounds. We use these to construct a provably-efficient algorithm, which accounts for termination, and bound its regret.
  arXiv  Detail & Related papers  (2022-05-30T18:40:28Z)
• Deadlock-Free Method for Multi-Agent Pickup and Delivery Problem Using Priority Inheritance with Temporary Priority [2.064612766965483]
  This paper proposes a control method for the multi-agent pickup and delivery problem (MAPD problem) by extending the priority inheritance with backtracking (PIBT) method. PIBT is only applicable to environments that are modeled as a bi-connected area, and if it contains dead-ends, such as tree-shaped paths, PIBT may cause deadlocks. Our proposed method enables MAPD tasks to be performed in environments with some tree-shaped paths without deadlock while preserving the PIBT feature.
  arXiv  Detail & Related papers  (2022-05-25T05:45: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)
• A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
  We consider multiple Automated Guided Vehicles (AGVs) navigating a common workspace to fulfill various intralogistics tasks. One approach is to construct an Action Dependency Graph (ADG) which encodes the ordering of AGVs as they proceed along their routes. If the workspace is shared by dynamic obstacles such as humans or third party robots, AGVs can experience large delays. We present an online method to repeatedly modify acyclic ADG to minimize route completion times of each AGV.
  arXiv  Detail & Related papers  (2020-10-11T14:39:50Z)
• Stochastic bandits with arm-dependent delays [102.63128271054741]
  We propose a simple but efficient UCB-based algorithm called the PatientBandits. We provide both problems-dependent and problems-independent bounds on the regret as well as performance lower bounds.
  arXiv  Detail & Related papers  (2020-06-18T12:13:58Z)
• 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.