Edge Conflict

An Edge Conflict is formally defined as a tuple (a_i, a_j, v, u, t) where agents a_i and a_j are planned to move from vertices v->u and u->v, respectively, at the same time step t. This represents a direct, head-on collision on a bidirectional path segment. Unlike a Vertex Conflict (occupying the same node), an edge conflict involves agents in transit, making it a dynamic and often more complex constraint to resolve within the space-time planning domain.

In optimal algorithms like Conflict-Based Search (CBS), an edge conflict is resolved by imposing constraints that prevent the collision. The solver creates two child nodes:

• Constraint for Agent A: (a_i, v, u, t) – Agent a_i cannot be at u at time t having come from v.
• Constraint for Agent B: (a_j, u, v, t) – Agent a_j cannot be at v at time t having come from u. Each agent's path is then replanned independently under its new constraint, typically forcing one agent to wait or take an alternative route, which may increase the Sum of Costs (SOC) or Makespan.

Edge conflicts are detected by querying a Conflict Avoidance Table (CAT) or by checking pairs of agent paths in the space-time domain. Efficient detection is crucial for performance. Algorithms like Space-Time A* and Safe Interval Path Planning (SIPP) inherently avoid these conflicts during search by treating planned agent trajectories as dynamic obstacles. In Priority Planning schemes, lower-priority agents treat the planned paths of higher-priority agents as occupied edges in the time-expanded graph.

Edge conflicts are a primary driver of computational complexity in MAPF. Resolving them often requires increasing path costs. A Cardinal Conflict is a severe case where resolving the edge conflict unavoidably increases the global cost. The need to resolve multiple interdependent edge conflicts can lead to exponential growth in the search tree for optimal solvers. This makes edge conflicts a key consideration for choosing between optimal, bounded-suboptimal, and complete but non-optimal algorithms like Push and Swap.

In physical systems, an edge conflict maps to a head-on collision on a narrow corridor, aisle, or lane. Resolution must account for kinodynamic constraints like turning radius, acceleration, and physical size. In velocity-based reactive methods like Optimal Reciprocal Collision Avoidance (ORCA), an edge conflict corresponds to a reciprocal velocity obstacle where the set of permissible velocities for each agent is mutually constrained. Real-world deployment often adds a k-robust temporal buffer (e.g., a 2-timestep separation) to edge reservations to account for execution uncertainty.

It is essential to differentiate an Edge Conflict from other common MAPF conflicts:

• Vertex Conflict: Two agents occupy the same node at the same time.
• Following Conflict: An agent moves into a node just vacated by another; often permitted unless specific 'swapping' is disallowed.
• Bypass Conflict: A potential conflict resolved by a local detour without cost increase. Edge conflicts are symmetric and often require more significant replanning than vertex conflicts, as simply waiting at the source node for one timestep does not resolve it—the agents would still attempt to cross simultaneously in the next step.

A Vertex Conflict occurs when two agents are planned to occupy the same graph node or location at the same timestep. This is the most fundamental spatial conflict in MAPF.

• Detection: Algorithms check for identical (location, time) tuples in agent plans.
• Resolution: Typically resolved by forcing one agent to wait at its previous node or by finding an alternative route.
• Relation to Edge Conflict: While an edge conflict involves simultaneous traversal, a vertex conflict is about simultaneous occupancy. A severe edge conflict can manifest as two sequential vertex conflicts.

A Cardinal Conflict is the most severe type of conflict in optimal MAPF. It occurs when any feasible resolution (e.g., making one agent wait) inevitably increases the sum of costs (SOC) for the involved agents.

• Optimality Impact: The presence of a cardinal conflict means the current cost bound for the joint plan cannot be maintained; the optimal solution cost must increase.
• Identification: Conflict-Based Search (CBS) algorithms classify conflicts by analyzing the MDDs (Multi-Value Decision Diagrams) of the conflicting agents.
• Severity: Cardinal > Semi-Cardinal > Non-Cardinal. Resolving an edge conflict may create a cardinal conflict if no cost-preserving bypass exists.

A Conflict Avoidance Table (CAT) is a core data structure used by many MAPF algorithms to efficiently detect vertex and edge conflicts. It stores the space-time reservations of all planned agent paths.

• Function: For a given (vertex, time) or (edge, time), the CAT returns which agent has reserved it. A query for an edge checks for reservations in both directions.
• Implementation: Often implemented as a hash map or a 3D array (x, y, t).
• Usage: Algorithms like Space-Time A* and WHCA* query the CAT during search to prune collision-prone branches, enabling real-time conflict detection for edge conflicts.

A Bypass is a conflict resolution strategy where an agent's path is locally modified to go around another agent without increasing its path cost, thus avoiding the need to impose a constraint that would raise the total solution cost.

• Application to Edge Conflicts: For an edge conflict (A, B, e, t), the algorithm may search for an alternative 2- or 3-step path for agent A that avoids edge e at time t while keeping the same path length.
• Optimality: Successfully finding a bypass allows the algorithm to maintain the current cost bound. It is a key optimization in advanced CBS variants.
• Limitation: Not always possible, especially in dense or highly constrained environments.

k-Robust Planning is a robustness strategy that enforces a minimum temporal separation of k timesteps between agents at any location or edge. It provides a buffer against execution timing errors.

• Preventing Edge Conflicts: A k-robust plan with k>=1 inherently prevents standard edge conflicts, as agents cannot be scheduled on the same edge in consecutive timesteps.
• Trade-off: Increases makespan (total completion time) and can reduce overall fleet throughput.
• Use Case: Critical in real-world systems where agents have imperfect control and synchronization, common in heterogeneous fleets with mixed manual and automated vehicles.

ORCA is a distributed, reactive velocity-based algorithm for continuous collision avoidance. It is a decentralized alternative to centralized MAPF planning.

• Mechanism: Each agent independently computes a set of permissible velocities (ORCA half-planes) that guarantee collision avoidance for a given time window, assuming other agents reciprocate.
• Relation to Edge Conflicts: ORCA operates in continuous space and time, preventing the physical manifestation of edge conflicts by adjusting velocities in real-time, rather than avoiding them in a discrete plan.
• Application: Often used as a low-level execution layer beneath a high-level MAPF planner (like one that solves edge conflicts) to handle dynamic deviations.