Planning over MAPF Agent Dependencies via Multi-Dependency PIBT

• URL: http://arxiv.org/abs/2603.23405v1
• Date: Tue, 24 Mar 2026 16:38:12 GMT
• Title: Planning over MAPF Agent Dependencies via Multi-Dependency PIBT
• Abstract summary: Multi-Agent Path Finding (MAPF) algorithms must plan for hundreds to thousands of agents in congested environments within a second.<n>PIBT is a popular algorithm capable of effectively planning in such situations.<n>We propose Multi-Dependency PIBT (MD-PIBT) that searches over agent dependencies.
• Score: 26.73382486796029
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Modern Multi-Agent Path Finding (MAPF) algorithms must plan for hundreds to thousands of agents in congested environments within a second, requiring highly efficient algorithms. Priority Inheritance with Backtracking (PIBT) is a popular algorithm capable of effectively planning in such situations. However, PIBT is constrained by its rule-based planning procedure and lacks generality because it restricts its search to paths that conflict with at most one other agent. This limitation also applies to Enhanced PIBT (EPIBT), a recent extension of PIBT. In this paper, we describe a new perspective on solving MAPF by planning over agent dependencies. Taking inspiration from PIBT's priority inheritance logic, we define the concept of agent dependencies and propose Multi-Dependency PIBT (MD-PIBT) that searches over agent dependencies. MD-PIBT is a general framework where specific parameterizations can reproduce PIBT and EPIBT. At the same time, alternative configurations yield novel planning strategies that are not expressible by PIBT or EPIBT. Our experiments demonstrate that MD-PIBT effectively plans for as many as 10,000 homogeneous agents under various kinodynamic constraints, including pebble motion, rotation motion, and differential drive robots with speed and acceleration limits. We perform thorough evaluations on different variants of MAPF and find that MD-PIBT is particularly effective in MAPF with large agents.

Related papers

• Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation [49.86232017439639]
  We introduce Multi-Output Augmented Behavioral Cloning (MA-BC)<n>MA-BC partitions divergent expert data while pooling state-action pairs where no behavior conflict is observed.<n>We establish a novel lower bound for multi-objective imitation learning, demonstrating that MA-BC is minimax optimal.
  arXiv  Detail & Related papers  (2026-05-12T11:49:08Z)
• Bridging Planning and Execution: Multi-Agent Path Finding Under Real-World Deadlines [9.228609005424348]
  We propose REMAP, an execution-informed MAPF planning framework for time-sensitive applications.<n>Our framework integrates the proposed ExecTimeNet to accurately estimate execution time based on planned paths.<n>Experiments show that REMAP achieves up to 20% improvement in solution quality over baseline methods.
  arXiv  Detail & Related papers  (2025-11-26T20:08:52Z)
• WinkTPG: An Execution Framework for Multi-Agent Path Finding Using Temporal Reasoning [7.2069924323665235]
  Planning collision-free paths for a large group of agents is a challenging problem with numerous real-world applications.<n>We propose kinodynamic Temporal Plan Graph Planning (kTPG), a multi-agent speed optimization algorithm that efficiently refines a MAPF plan into a kinodynamically feasible plan.<n>Building on kTPG, we propose Windowed kTPG (WinkTPG), a MAPF execution framework that incrementally refines MAPF plans using a window-based mechanism.
  arXiv  Detail & Related papers  (2025-08-02T21:33:08Z)
• Budget Allocation Policies for Real-Time Multi-Agent Path Finding [11.050047263054985]
  Real-Time MAPF embodies a realistic MAPF setup in which planning and execution are interleaved.<n>Existing solutions to RT-MAPF iteratively call windowed versions of MAPF algorithms in every planning period.<n>We explore different policies for allocating the planning budget in windowed versions of standard MAPF algorithms.
  arXiv  Detail & Related papers  (2025-07-22T08:32:55Z)
• PGPO: Enhancing Agent Reasoning via Pseudocode-style Planning Guided Preference Optimization [58.465778756331574]
  We propose a pseudocode-style Planning Guided Preference Optimization method called PGPO for effective agent learning.<n>With two planning-oriented rewards, PGPO further enhances LLM agents' ability to generate high-quality P-code Plans.<n>Experiments show that PGPO achieves superior performance on representative agent benchmarks and outperforms the current leading baselines.
  arXiv  Detail & Related papers  (2025-06-02T09:35:07Z)
• Lightweight and Effective Preference Construction in PIBT for Large-Scale Multi-Agent Pathfinding [10.174848090916669]
  This paper studies two simple yet effective techniques for tiebreaking in PIBT.<n>The first technique allows an agent to intelligently dodge another, taking into account whether each action will hinder the progress of the next timestep.<n>The second technique is to learn, through multiple PIBT runs, how an action causes regret in others and to use this information to minimise regret collectively.
  arXiv  Detail & Related papers  (2025-05-19T02:12:29Z)
• 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)
• 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)
• 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)
• 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)
• Exploiting Submodular Value Functions For Scaling Up Active Perception [60.81276437097671]
  In active perception tasks, agent aims to select sensory actions that reduce uncertainty about one or more hidden variables. Partially observable Markov decision processes (POMDPs) provide a natural model for such problems. As the number of sensors available to the agent grows, the computational cost of POMDP planning grows exponentially.
  arXiv  Detail & Related papers  (2020-09-21T09:11:36Z)

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.