Vertex Cover Heuristics for Conflict Based Search

18 concepts8 papers1 proposal

Multi-Agent Path Finding (MAPF) requires routing a fleet of agents to their respective destinations without collisions. One of the leading frameworks for solving this optimally is Conflict-Based Search (CBS). CBS operates at two levels: a low-level search that finds optimal paths for individual agents, and a high-level search that resolves collisions by branching and imposing spatio-temporal constraints (e.g., "Agent A cannot occupy cell $X$ at time $T$").

Historically, the high-level search in CBS was "blind." It lacked an admissible heuristic to estimate the remaining cost required to resolve all agent conflicts, forcing it to explore the search space in a manner akin to an uninformed breadth-first search. To transform CBS into an efficient, informed A-style search, researchers needed a way to mathematically bound the future cost of resolving overlapping collisions. The breakthrough came from mapping agent interactions to a classic graph-theoretic problem: the Minimum Vertex Cover*.

Mapping Conflicts to Graph Vertex Covers

To understand why this mapping works, consider the fundamental nature of a conflict. If Agent A and Agent B collide under their current optimal paths, any valid solution must force at least one of them to deviate. Forcing an agent to deviate typically introduces a delay or a detour, increasing the total solution cost.

As introduced by [Jiaoyang Li 0001] et al. in Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding, we can formalize these relationships by constructing a conflict graph. In this graph:

  • Vertices represent individual agents.
  • Edges represent unavoidable conflicts between pairs of agents' optimal paths.

To achieve a conflict-free state, the high-level search must apply constraints to at least one agent in every conflicting pair. In graph theory, selecting a subset of vertices such that every edge is incident to at least one selected vertex is known as a Vertex Cover.

Because each vertex in the cover represents an agent that must change its path—and each path change increases the total cost by at least 1—the size of the Minimum Vertex Cover (MVC) provides a guaranteed, admissible lower bound on the additional cost required to resolve all current conflicts.

Accounting for Cost Severity via Edge Weights

While counting binary conflicts via the MVC provides a valid lower bound, it treats all collisions as equal. In reality, a conflict in an open space might be resolved by an agent waiting for a single time step (a cost increase of +1), whereas a conflict inside a narrow corridor might force an agent into a massive detour (a cost increase of +10).

To capture this discrepancy, [Jiaoyang Li] et al. proposed the Weighted Dependency Graph (WDG) framework in Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search: Preliminary Results and Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search. Instead of assuming a uniform cost of 1 for every edge, the authors introduced a localized sub-problem cost calculation. For every conflicting pair of agents, the algorithm solves a mini two-agent pathfinding problem to determine the exact minimum cost increase required to make that specific pair completely conflict-free.

These calculated costs are then assigned as weights to the edges of the dependency graph. The problem of estimating the total search cost then evolves from a simple MVC into an Edge-Weighted Minimum Vertex Cover (EWMVC) problem.

Why the Vertex Cover Abstraction Works

The core elegance of the EWMVC formulation lies in its ability to handle overlapping dependencies without overestimating or underestimating costs.

Imagine a scenario with three agents where Agent B conflicts with both Agent A and Agent C. Suppose the localized sub-problem determines that resolving the A-B conflict costs 2, and resolving the B-C conflict costs 3.

  (A) -- 2 -- (B) -- 3 -- (C)

If we simply added these costs together, our heuristic estimate would be 5. However, if altering Agent B's path by a detour of cost 4 happens to resolve both conflicts simultaneously, then the true minimum cost increase to resolve all conflicts is 4, not 5. Summing the costs would violate admissibility by overestimating the required cost.

The EWMVC mathematically prevents this overestimation. It solves an optimization problem that assigns a cost increase to each vertex (agent) such that for every edge $(u, v)$ with weight $w$, the sum of the costs assigned to vertices $u$ and $v$ is at least $w$. By minimizing the total sum of these vertex values, the EWMVC finds the most efficient global resolution strategy. This ensures that the heuristic remains strictly admissible (it never overestimates the true cost) while remaining as tight as possible.

Broadening the Paradigm

The vertex cover abstraction has proven to be a highly versatile foundation, anchoring several advancements across different facets of multi-agent coordination:

  • Physical Volume (Large Agents): Traditional MAPF treats agents as points. When agents have physical volume, spatial conflicts become significantly more complex. [Jiaoyang Li] et al. demonstrated in Multi-Agent Path Finding for Large Agents that EWMVC heuristics scale effectively to these environments, capturing the severe cost increases associated with maneuvering large physical robots around one another.
  • Conflict Prioritization: Beyond calculating heuristics, the topology of the conflict graph can dictate search strategy. [Eli Boyarski] et al. in F-Cardinal Conflicts in Conflict-Based Search and f-Aware Conflict Prioritization & Improved Heuristics For Conflict-Based Search showed that by simulating the MVC/EWMVC calculation on modified conflict graphs, the search can identify "cardinal conflicts"—those guaranteed to immediately increase the global lower bound ($f$-value) when branched upon. Prioritizing these conflicts dramatically prunes the high-level search tree.
  • Temporal Plan Robustness: The utility of this framework extends beyond initial pathfinding to execution robustness. In Speedup Techniques for Switchable Temporal Plan Graph Optimization, [He Jiang] et al. applied EWMVC to switchable temporal plan graphs, using it to compute tight lower bounds on the unavoidable delays caused by real-world disruptions and unexpected agent stalls.
  • Beyond Pairwise Interactions: In highly dense environments, reasoning about pairs of agents can understate the true cost of multi-agent deadlocks. To push past this limitation, [Bojie Shen] et al. developed techniques in Beyond Pairwise Reasoning in Multi-Agent Path Finding to isolate larger clusters of mutually conflicting agents, solving localized group sub-problems to inject even tighter bounds into the global vertex cover formulation.

Key Foundational Work

Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search: Preliminary Results (2019) — contributed 4 concept elements to this direction.
Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding (2018) — contributed 3 concept elements to this direction.
Multi-Agent Path Finding for Large Agents (2019) — contributed 2 concept elements to this direction.
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 2, frozen text):

@misc{lacuna_vertex_cover_cost_estimation_1e57bd62_v2,
  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/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake