Vertex Conflict

A Vertex Conflict is formally defined as a tuple (a_i, a_j, v, t), where agents a_i and a_j are both planned to occupy the same vertex v at the same timestep t. This is the most basic spatial conflict in discrete MAPF formulations. The conflict represents a hard constraint that must be resolved for a plan to be executable, typically by imposing a constraint on one agent to be elsewhere at time t, often via waiting or detouring.

Vertex conflicts are detected by comparing the space-time trajectories of all agent pairs. Efficient algorithms use data structures like a Conflict Avoidance Table (CAT) to store reservations (v, t) for each agent. A lookup in this table for a planned move reveals an imminent conflict. In Conflict-Based Search (CBS), detecting a vertex conflict is the primary trigger for splitting the search tree and imposing new constraints on the conflicting agents.

Resolving a vertex conflict forces a change to at least one agent's plan. Common resolution methods include:

• Temporal Delay: One agent waits at its previous vertex for one or more timesteps.
• Spatial Detour: One agent takes an alternative route around the contested vertex.
• Priority Assignment: In Priority Planning, the lower-priority agent must always yield, treating the higher-priority agent's path as a moving obstacle. The choice of strategy directly impacts solution optimality metrics like Sum of Costs or Makespan.

Vertex conflicts are one of three primary conflict types in MAPF. It's essential to distinguish them:

• Edge Conflict: Two agents traverse the same edge in opposite directions simultaneously (a_i, a_j, u, v, t). This is logically equivalent to a vertex conflict on the edge.
• Cardinal Conflict: A severe vertex conflict where any resolution necessarily increases the sum of costs for both agents, representing a fundamental bottleneck.
• Following Conflict: A softer constraint where one agent occupies a vertex immediately after another, which may be acceptable or require a k-robust separation.

The frequency and nature of vertex conflicts are primary drivers of computational complexity and plan efficiency. A high density of conflicts leads to:

• Exponential growth of the search tree in optimal algorithms like CBS.
• Increased Sum of Costs (SOC) due to added wait actions or longer detours.
• Longer Makespan as agents wait for shared resources. Algorithms often aim to minimize the number of conflicts or prioritize resolving cardinal conflicts first to guide the search more effectively.

Vertex conflicts are inherently modeled in a discrete space-time framework. The environment is represented as a graph G=(V,E), and time is discretized. An agent's path is a sequence of vertices paired with timesteps: [(v_0, 0), (v_1, 1), ...]. This representation allows for clear conflict definition. In continuous or kinodynamic planning, the analogous concept is a simultaneous occupancy of the same geometric region, which is more complex to detect and resolve.

An Edge Conflict occurs when two agents are planned to traverse the same graph edge in opposite directions during the same time step. This is distinct from a Vertex Conflict, which involves simultaneous occupancy of a node.

• Detection: Algorithms check for pairs of agents where one moves from vertex A to B while another moves from B to A at the same time.
• Resolution: Common strategies include imposing a precedence constraint (forcing one agent to wait) or rerouting one agent via an alternative path.

Conflict-Based Search (CBS) is a two-level, optimal algorithm for solving MAPF problems. It directly identifies and resolves Vertex and Edge Conflicts.

• High-Level: Searches a constraint tree. Each node contains a set of constraints (e.g., "Agent 1 cannot be at vertex V at time T") and a solution that respects them.
• Low-Level: Plans individual paths for each agent using a fast single-agent planner (like A*), adhering to the current constraints.
• Process: When a conflict (vertex or edge) is found in a solution, the algorithm branches, adding a constraint for each agent involved to resolve it.

A Conflict Avoidance Table (CAT) is a core data structure used to efficiently detect Vertex and Edge Conflicts during planning. It stores the space-time reservations of all currently planned agent paths.

• Function: For a candidate move (agent, vertex, time), the planner queries the CAT to see if that space-time cell is already occupied or an edge is already being traversed.
• Implementation: Often implemented as a hash map or a 3D array (agent, location, time).
• Usage: Central to algorithms like CBS, ICTS, and Windowed Hierarchical Cooperative A (WHCA)** for fast conflict checking without pairwise agent comparisons.

A Cardinal Conflict is the most severe type of conflict in optimal MAPF. It occurs when two agents have a Vertex or Edge Conflict, and resolving it by making one agent wait inevitably increases the sum of costs (SOC) for the overall solution.

• Implication: The presence of a cardinal conflict means the current cost bound for the solution must be increased to find a conflict-free plan.
• Detection: Algorithms like Conflict-Based Search (CBS) classify conflicts as cardinal, semi-cardinal, or non-cardinal to guide the search more intelligently, focusing effort on conflicts that force a cost increase.

A Multi-Value Decision Diagram (MDD) is a compact, layered graph that encodes all possible optimal paths for a single agent from its start to its goal within a specific cost bound (e.g., shortest path length).

• Structure: Each layer corresponds to a timestep. Nodes in a layer represent vertices the agent could occupy at that time while still reaching its goal optimally.
• Use in Conflict Detection: MDDs are powerful for identifying Vertex Conflicts. A conflict exists at vertex V at time T if that vertex appears in the MDDs of two different agents at the same layer T.
• Use in Conflict Resolution: Algorithms like ICTS use MDDs to explore combinations of agent paths efficiently.

k-Robust Planning is a robustness strategy that enforces a temporal buffer of at least k timesteps between agents at any location, going beyond merely avoiding Vertex Conflicts.

• Purpose: Provides a safety margin against timing uncertainties, execution delays, or sudden stops in real-world systems.
• Effect on Vertex Conflicts: A k-robust plan inherently avoids standard vertex conflicts (where k=0). For k>0, it prevents agents from occupying the same vertex even at different times if the separation is less than k. This is sometimes called a k-vertex conflict.
• Trade-off: Increases path costs (makespan, SOC) but significantly improves plan executability and safety.