Cardinal Conflict

A Cardinal Conflict is a conflict between two agents where resolving it by making one agent wait unavoidably increases the Sum of Costs (SOC). This is its defining property: the conflict is on the critical path of both agents' optimal individual plans. Resolving it forces at least one agent to take a longer path, directly increasing the total cost of the joint solution. It is the most computationally expensive conflict type for algorithms like Conflict-Based Search (CBS) to resolve, as it forces a branching decision with a guaranteed cost increase.

Cardinal Conflicts are distinguished from less severe conflict types based on their impact on the Sum of Costs (SOC).

• Cardinal Conflict: Increases the SOC regardless of which agent is constrained to wait. Example: Two agents meet head-on in a narrow corridor where the only alternative path is significantly longer.
• Semi-Cardinal Conflict: Increases the SOC for only one of the two possible resolutions (e.g., constraining Agent A increases cost, but constraining Agent B does not).
• Non-Cardinal Conflict: Can be resolved without increasing the SOC for either agent, often via a Bypass where an agent takes a different but equal-cost path. This hierarchy is used by CBS and its variants to prioritize conflict resolution, tackling cardinal conflicts first.

Algorithms detect cardinality by analyzing the agents' Multi-Value Decision Diagrams (MDDs). An MDD compactly encodes all optimal paths for a single agent within a given cost bound. For a conflict at vertex v at time t:

1. Query if Agent A has alternative optimal paths that avoid v at t.
2. Query the same for Agent B. A conflict is cardinal only if neither agent has an alternative optimal path avoiding the spatio-temporal cell. If both have alternatives, it's non-cardinal. If only one has an alternative, it's semi-cardinal. This MDD analysis provides a formal, computable criterion for conflict classification.

In the Conflict-Based Search (CBS) algorithm, cardinal conflicts drive the most significant expansions of the Constraint Tree (CT). When CBS encounters a conflict:

1. It classifies it as cardinal, semi-cardinal, or non-cardinal.
2. Cardinal conflicts are prioritized for branching because they guarantee an increase in the cost of both child nodes in the CT. Resolving them early prunes large sections of the search space that cannot contain a better solution.
3. Advanced CBS variants like CBS with Prioritizing Conflicts (PC) use this classification to make more informed branching decisions, significantly improving search efficiency over vanilla CBS, which treats all conflicts equally.

The presence of a cardinal conflict is a direct indicator of a fundamental trade-off required for a jointly optimal solution. It proves that the current lower bound (often the sum of individual optimal path costs) is unattainable. Resolving a cardinal conflict establishes a new, higher lower bound for that branch of the search. Consequently, the number and nature of cardinal conflicts in a MAPF instance are strong predictors of problem difficulty and the minimum possible Sum of Costs (SOC). Instances with many cardinal conflicts are inherently harder for optimal solvers.

Consider a narrow warehouse aisle that is only one cell wide. Agent 1's optimal path goes from West to East down the entire aisle. Agent 2's optimal path goes from East to West down the same aisle. They have a vertex conflict for every cell in the aisle at successive times.

• Analysis: Neither agent has an alternative optimal path. To avoid the conflict, one agent must exit the aisle, travel around a long block of shelves, and re-enter, adding many steps to its path.
• Result: This is a cardinal conflict. Any feasible joint solution will have a SOC greater than the sum of each agent's individual shortest path. The conflict represents the core scheduling bottleneck for that section of the warehouse floor.

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

• Detection: Check agent reservations in a Conflict Avoidance Table (CAT).
• Resolution: Typically resolved by adding a constraint that prevents one agent from being at that vertex at that time, forcing it to wait or take an alternative route.

An Edge Conflict (or swapping conflict) occurs when two agents are planned to traverse the same graph edge in opposite directions during the same timestep.

• Cause: Models a physical collision if agents attempt to pass each other in a narrow corridor.
• Importance: Must be explicitly prevented in many MAPF formulations, as simply avoiding vertex conflicts does not guarantee edge conflict avoidance.

Sum of Costs (SOC), also called Flowtime, is the primary optimality metric for MAPF. It is calculated as the sum of the path lengths (or travel times) for all individual agents from their start to their goal.

• Formula: SOC = Σ (finish_time_i - start_time_i) for all agents i.
• Relation to Cardinal Conflict: A Cardinal Conflict is defined by the property that any resolution unavoidably increases the SOC. Minimizing SOC is the objective of optimal MAPF solvers like CBS and ICTS.

Makespan is a key MAPF performance metric defined as the total time from the start of execution until the last agent reaches its goal.

• Focus: Measures overall completion time rather than cumulative agent effort.
• Trade-off: Solutions with optimal Makespan may have a higher SOC, and vice-versa. A Cardinal Conflict directly impacts SOC but may not affect Makespan if the delaying agent is not the last to finish.

Conflict-Based Search (CBS) is a leading optimal algorithm for MAPF that explicitly discovers and resolves conflicts like Cardinal Conflicts.

• High-level: Searches a tree of constraints.
• Low-level: Plans individual agent paths under those constraints.
• Cardinal Conflict Handling: When CBS identifies a Cardinal Conflict, it must branch on constraints for both involved agents, as delaying either one increases the total cost. This leads to significant search tree expansion.

A Bypass Conflict is a favorable type of conflict where an agent can resolve it by taking a slightly different, alternative path without increasing its own path cost.

• Contrast with Cardinal Conflict: The opposite of a Cardinal Conflict. Resolving a Bypass Conflict does not increase the Sum of Costs.
• Algorithm Benefit: In CBS, finding a bypass allows the algorithm to avoid creating a new constraint node, keeping the search tree shallow and improving performance.