Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution

• URL: http://arxiv.org/abs/2401.00315v2
• Date: Sun, 7 Jan 2024 01:23:49 GMT
• Title: Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution
• Authors: Yifan Su, Rishi Veerapaneni, Jiaoyang Li
• Abstract summary: We introduce a new graphical representation called a Bidirectional Temporal Plan Graph (BTPG) which allows switching orders during execution to avoid unnecessary waiting time. Experimental results show that following BTPGs consistently outperforms following TPGs, reducing unnecessary waits by 8-20%.
• Score: 7.2988406091449605
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Multi-Agent Path Finding (MAPF) problem involves planning collision-free paths for multiple agents in a shared environment. The majority of MAPF solvers rely on the assumption that an agent can arrive at a specific location at a specific timestep. However, real-world execution uncertainties can cause agents to deviate from this assumption, leading to collisions and deadlocks. Prior research solves this problem by having agents follow a Temporal Plan Graph (TPG), enforcing a consistent passing order at every location as defined in the MAPF plan. However, we show that TPGs are overly strict because, in some circumstances, satisfying the passing order requires agents to wait unnecessarily, leading to longer execution time. To overcome this issue, we introduce a new graphical representation called a Bidirectional Temporal Plan Graph (BTPG), which allows switching passing orders during execution to avoid unnecessary waiting time. We design two anytime algorithms for constructing a BTPG: BTPG-na\"ive and BTPG-optimized. Experimental results show that following BTPGs consistently outperforms following TPGs, reducing unnecessary waits by 8-20%.

Related papers

• AlphaZeroES: Direct score maximization outperforms planning loss minimization [61.17702187957206]
  Planning at execution time has been shown to dramatically improve performance for agents in both single-agent and multi-agent settings. A family of approaches to planning at execution time are AlphaZero and its variants, which use Monte Carlo Tree Search together with a neural network that guides the search by predicting state values and action probabilities. We show that, across multiple environments, directly maximizing the episode score outperforms minimizing the planning loss.
  arXiv  Detail & Related papers  (2024-06-12T23:00:59Z)
• 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)
• 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)
• GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
  We propose an efficient shared encoding for all agents and the map without sacrificing accuracy or generalization. We leverage pair-wise relative positional encodings to represent geometric relationships between the agents and the map elements in a heterogeneous spatial graph. Our decoder is also viewpoint agnostic, predicting agent goals on the lane graph to enable diverse and context-aware multimodal prediction.
  arXiv  Detail & Related papers  (2022-11-04T16:10:50Z)
• 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)
• 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)
• 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)
• 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)
• Optimized Directed Roadmap Graph for Multi-Agent Path Finding Using Stochastic Gradient Descent [33.31762612175859]
  We present a novel approach called Optimized Directed Roadmap Graph (ODRM) ODRM is a method to build a directed roadmap graph that allows for collision avoidance in multi-robot navigation. Our experiments show that with ODRM even a simple centralized planner can solve problems with high numbers of agents that other multi-agent planners can not solve.
  arXiv  Detail & Related papers  (2020-03-29T02:18:31Z)

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.