Conflict Graph Heuristics for Multi-Agent Path Finding

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 28 papers17 conceptsfrozen 2026-10-04

In Multi-Agent Path Finding (MAPF), the goal is to move a fleet of agents from their starts to their goals without collisions. The state-of-the-art approach for optimal solving is Conflict-Based Search (CBS). CBS works on two levels: a "low-level" that finds individual paths and a "high-level" that resolves collisions by adding constraints (e.g., "Agent A cannot be at location X at time T").

However, CBS often suffers from an exponential explosion in the high-level search tree. The search becomes blind when it cannot distinguish between a "simple" conflict that is easily bypassed and a "bottleneck" conflict that forces a massive detour. To solve this, researchers have turned to graph theory—specifically the Edge-Weighted Minimum Vertex Cover—to build powerful heuristics that "see" the cost of future resolutions before they happen.

The Geometry of Dependency

The core insight developed by Jiaoyang Li, Ariel Felner, and their colleagues is that conflicts are rarely isolated. If Agent A and Agent B collide, resolving that conflict will necessarily increase the path cost of at least one of them.

In Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search, the authors propose modeling these interactions as a Dependency Graph (DG). In this graph:

  • Each node represents an agent.
  • An edge exists between two nodes if their current paths conflict.

If we have a conflict between Agent A and Agent B, we know that at least one of them must be constrained to a different path. If that constraint forces a cost increase, we can assign a weight to that edge representing the minimum additional cost required to make that specific pair conflict-free.

From Conflicts to Vertex Covers

To find a global lower bound on how much the total cost must increase, we cannot simply sum the weights of all edges. If Agent A conflicts with both Agent B and Agent C, a single detour by Agent A might resolve both conflicts simultaneously. Summing the costs would over-count and break the "admissibility" of the heuristic (a requirement for finding the optimal solution).

The solution is the Edge-Weighted Minimum Vertex Cover (EWMVC). A vertex cover is a set of vertices such that every edge in the graph is incident to at least one vertex in the set. By solving for the minimum weight vertex cover on the dependency graph, we find the smallest possible cost increase that accounts for every known conflict.

As shown in Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search: Preliminary Results, this approach provides a much tighter lower bound for the high-level search, reducing node expansions by up to 50 times.

Identifying Cardinal Conflicts

While heuristics help estimate the cost, the search still needs to decide which conflict to resolve first. Eli Boyarski, Daniel Harabor, and others introduced the concept of $f$-cardinal conflicts in F-Cardinal Conflicts in Conflict-Based Search.

An $f$-cardinal conflict is one where any resolution is guaranteed to increase the total estimated cost ($f$-value) of the resulting search nodes. By using the conflict graph to simulate the impact of a resolution, the algorithm can prioritize these high-impact conflicts. This structural analysis of the conflict graph allows the solver to prune the search space aggressively, as detailed in f-Aware Conflict Prioritization & Improved Heuristics For Conflict-Based Search.

Scaling to Physical Robots and Real-Time Delays

The utility of conflict graph heuristics extends beyond point-mass agents on grids. In Multi-Agent Path Finding for Large Agents, Jiaoyang Li and Sven Koenig applied these techniques to Large Agents (LA-MAPF)—robots with physical volume that can block multiple cells. In these dense environments, conflicts are more frequent and dependencies more complex, making the EWMVC heuristic even more critical for tractability.

More recently, the framework has been adapted for Temporal Plan Graphs, which handle real-world uncertainty. When a robot is delayed, the system must reschedule others to avoid new collisions. He Jiang and Muhan Lin demonstrate in Speedup Techniques for Switchable Temporal Plan Graph Optimization that modeling "switchable edges" (decisions about which agent goes first) as a weighted dependency graph allows for real-time rescheduling of hundreds of agents.

By treating agent interactions as a structured graph problem rather than a series of isolated collisions, these researchers have transformed MAPF from a theoretical curiosity into a robust tool for industrial robotics.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 8 papers
  2. Version 1 · 2026-10-04 · 8 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_vertex_cover_cost_estimation_1e57bd62,
  title = {vertex cover cost estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/vertex-cover-cost-estimation/rdr_1e57bd62aa5f470e8db95b92c1292926},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_conflict_graph_heuristics_for_multi_agen_1e57bd62_v1,
  title = {Conflict Graph Heuristics for Multi-Agent Path Finding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/conflict-graph-heuristics-for-multi-agent-path-finding/rdr_1e57bd62aa5f470e8db95b92c1292926/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}