Bypass Conflict

A Bypass Conflict occurs when an agent's path can be locally modified to 'go around' another agent without increasing its individual path cost. In CBS, the algorithm detects a conflict (e.g., a vertex or edge conflict) and instead of branching by imposing a constraint that forces one agent to avoid the spatio-temporal cell, it finds an alternative, equal-cost path for one agent that resolves the conflict. This is implemented by checking if a new path for the conflicting agent exists with the same cost (g-value) as its current path but without the specific conflict. If found, the node in the CBS constraint tree is updated with this new path instead of generating child nodes with constraints, keeping the search tree narrower.

The primary function of identifying a bypass is to prune the search space of the CBS algorithm. CBS's runtime is heavily dependent on the size of its high-level constraint tree. Each unresolved conflict typically causes an exponential branch. A bypass allows the algorithm to resolve the conflict without branching, updating the current node in place. This can lead to dramatic reductions in the number of nodes expanded, especially in dense, complex environments where many conflicts are superficial and can be sidestepped with minimal effort. It directly combats the combinatorial explosion inherent in multi-agent planning.

A correctly implemented bypass mechanism preserves the optimality guarantees of CBS. Since the new path for the agent has an identical cost to the old one, the sum of costs (SOC) for the entire solution remains unchanged at that node. The search continues from a node with the same cost but a resolved conflict. This is in contrast to suboptimal algorithms that might use similar 'replanning' techniques but allow cost increases. The bypass is a strictly improving operation: it finds a solution of equal cost while reducing conflict, moving the search closer to a viable, optimal joint plan.

Bypass conflicts sit on a spectrum of conflict severity within CBS:

• Cardinal Conflict: The most severe. Resolving it forces an increase in the sum of costs (SOC), as all resolutions require at least one agent to take a longer path.
• Semi-Cardinal Conflict: Resolving it increases the cost for one agent but not the overall SOC (if another agent's cost can decrease).
• Bypass Conflict: The least severe. Resolution does not increase any agent's individual cost. It is a 'free' resolution. Efficient CBS implementations classify conflicts upon detection to apply the most effective resolution strategy, prioritizing bypass identification to avoid unnecessary branching.

Detecting a bypass requires a local replanning step for the conflicting agent. When a conflict is found at time t at vertex v, the algorithm temporarily constrains the agent from being at v at t and calls its low-level planner (e.g., A*) to find a new path from its start to its goal. The critical check is whether the cost of this new path is equal to the cost of the agent's current path in the CBS node. If costs are equal, a bypass exists and the node is updated. This detection adds computational overhead per conflict, but this cost is almost always outweighed by the reduction in tree size.

The use of bypass conflicts is a key optimization in modern, performant CBS variants (e.g., CBS with Bypassing). Its impact is twofold:

• Solution Quality: Maintains optimality (minimum sum of costs).
• Scalability: Can significantly improve the number of agents a CBS-based planner can handle within a practical time frame. By avoiding branch generation for bypassable conflicts, the algorithm can solve denser problems. In warehouse robotics simulations, implementations using bypassing have demonstrated solve-time reductions of over 50% for problems with 20+ agents, compared to vanilla CBS.

Conflict-Based Search (CBS) is the foundational two-level optimal algorithm where Bypass Conflict is deployed. At the high level, a constraint tree is searched. At the low level, individual agents are replanned with constraints. A Bypass Conflict is a specialized resolution applied when a new path for an agent has the same cost as its old path but avoids a conflict, allowing the search to progress without increasing the solution cost.

• High-Level: Searches a binary tree of constraints.
• Low-Level: Fast, single-agent planners like A*.
• Bypass Role: A pruning technique within the constraint tree search.

A Cardinal Conflict is the most severe type of conflict in MAPF, representing the direct opposite of a Bypass Conflict. Resolving a cardinal conflict by making one agent wait unavoidably increases the sum of costs (SOC) for the solution. This forces the CBS algorithm to explore alternative constraint branches, directly impacting optimality. Understanding the conflict hierarchy is key:

• Cardinal: Unavoidable cost increase.
• Semi-Cardinal: Cost increase for one agent only.
• Non-Cardinal: No cost increase (where Bypass applies).

A Multi-Value Decision Diagram (MDD) is a compact data structure that encodes all possible optimal paths for a single agent within a given cost bound. In advanced CBS implementations, MDDs are used to detect Bypass Conflicts efficiently. By comparing the MDDs of conflicting agents, the algorithm can instantly see if an alternative, equal-cost path exists that avoids the collision, enabling the bypass without expensive replanning.

• Represents all shortest paths.
• Enables fast bypass identification.
• Key for algorithms like ICBS (Improved CBS).

Sum of Costs (SOC) is the primary optimality metric for MAPF, calculated as the total number of time steps or distance traveled by all agents. The Bypass Conflict strategy is explicitly designed to preserve the SOC. By finding an alternative path of identical length, it resolves a conflict without inflating this metric. Other common metrics include:

• Makespan: Total time until the last agent finishes.
• Flowtime: Synonym for SOC.
• Bypass Impact: SOC remains unchanged.

WHCA* is a popular, scalable, but suboptimal algorithm that contrasts with the optimal, CBS-based approach using Bypass. It plans paths for all agents within a short time window using a shared reservation table. It lacks systematic conflict resolution like bypass; instead, it relies on replanning and reservations.

• Approach: Decentralized, window-based.
• Trade-off: Speed for optimality.
• Vs. Bypass: No guarantee of finding equal-cost alternative paths.

Safe Interval Path Planning (SIPP) is a single-agent algorithm for dynamic environments where obstacles move. It is often used as the low-level planner in CBS. SIPP groups time into 'safe intervals' where a location is continuously free. When CBS triggers a replan for a bypass, SIPP can efficiently find a new, cost-equivalent path within the agent's safe intervals, making it a practical engine for enabling the bypass strategy.

• Core Concept: Plan through safe time intervals.
• Role in CBS: Low-level planner.
• Bypass Support: Efficiently finds temporal alternatives.