Global Suboptimality Budgeting for Multi-Agent Path Finding

This direction is merged into another direction: multi-agent pathfinding complexity. Its last version stays readable and citable here.

Version 1 of 15 papers17 conceptsfrozen 2026-10-04

In Multi-Agent Path Finding (MAPF), the goal is to move a team of agents to their destinations without collisions. While finding the absolute shortest set of paths is often computationally prohibitive, researchers frequently use bounded-suboptimal algorithms like Enhanced Conflict-Based Search (ECBS). These algorithms guarantee that the total solution cost is no more than a factor $w$ (e.g., 1.1x) of the optimal cost.

However, traditional implementations of these algorithms suffer from a self-imposed restriction: they enforce the suboptimality bound on every agent individually. Recent research has shown that treating this bound as a shared global resource—a concept known as Flex Distribution—drastically improves the efficiency and success rate of pathfinding in crowded environments.

The Problem with Individual Constraints

In standard bounded-suboptimal search, if the global suboptimality factor is $w$, every agent $i$ is restricted to a path cost $c_i \leq w \cdot opt_i$, where $opt_i$ is the shortest possible path for that agent.

As Jiaoyang Li, Daniel Harabor, and Peter J. Stuckey argue in ECBS with Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding, this individual enforcement is unnecessarily rigid. Imagine a narrow corridor where one agent needs to take a long detour to let others pass. If that detour exceeds its personal $w$-bound, the search algorithm will reject the path, even if every other agent is currently on its optimal path and the total system cost is well within the global limit. This forces the high-level search to branch excessively, trying to find complex maneuvers that fit within everyone's tiny individual "slack" budgets.

Sharing the Flex Budget

The core insight of the Flexible ECBS (FECBS) and Flexible EECBS (FEECBS) algorithms, introduced by Jiaoyang Li and Shao-Hung Chan in Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding, is to decouple the global bound from individual agents.

Instead of checking each agent's cost, the algorithm maintains a global suboptimality budget. If Agent A finds a very short path (using 0% slack), the "saved" budget is added to a pool that Agent B can use to take a significantly longer detour (using 20% slack). As long as the sum of all costs $\sum c_i$ remains below $w \cdot \sum opt_i$, the solution remains valid. This flexibility allows the search to resolve collisions by letting specific agents take the "hit" for the team, bypassing the need for intensive search branching in high-conflict areas.

Strategic Allocation and the Greedy Trap

While sharing a budget is powerful, it introduces a new challenge: how should the budget be distributed? In early versions of Flex Distribution, the search was "greedy"—the first agents to encounter conflicts would consume the available slack, potentially leaving nothing for agents processed later in the search.

In New Mechanisms in Flex Distribution for Bounded Suboptimal Multi-Agent Path Finding, Shao-Hung Chan, Thomy Phan, and Sven Koenig identify that this greedy consumption causes search failures in dense environments. If the budget is exhausted early, the algorithm reverts to the same rigid constraints that caused problems in the first place.

To solve this, they proposed smarter allocation mechanisms:

  1. Conflict-Based Prioritization: Instead of a first-come, first-served approach, the budget is allocated based on an agent's current number of collisions. Agents in high-traffic bottlenecks are given more "flex" to find a way out.
  2. Strategic Budget Management: By preventing the search from "overspending" its slack on minor conflicts, the algorithm preserves the budget for the most complex coordination challenges.

By treating suboptimality as a managed global resource rather than a local constraint, these algorithms can scale to much higher agent densities, finding valid paths in crowded warehouses where traditional bounded-suboptimal searches would time out.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_global_suboptimality_budgeting_for_multi_5ff87ae7,
  title = {Global Suboptimality Budgeting for Multi-Agent Path Finding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-suboptimality-budgeting-for-multi-agent-path-finding/rdr_5ff87ae7c4b84f7ea0594e6fb5ac5ee2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_global_suboptimality_budgeting_for_multi_5ff87ae7_v1,
  title = {Global Suboptimality Budgeting for Multi-Agent Path Finding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-suboptimality-budgeting-for-multi-agent-path-finding/rdr_5ff87ae7c4b84f7ea0594e6fb5ac5ee2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}