Conflict Avoidance Table (CAT)

The CAT's fundamental unit is the space-time cell, a tuple (vertex, time) or (edge, time). Each agent's planned path is decomposed into a sequence of these cells. The table stores which agent has reserved each specific cell, creating a global schedule. This explicit temporal dimension is what distinguishes it from a simple occupancy map and allows for predictive conflict detection before execution begins.

• Example: Agent A's path from (1,1) to (1,2) creates reservations for ((1,1), t=0), (edge((1,1)->(1,2)), t=0), and ((1,2), t=1).

The primary function of a CAT is to provide O(1) or O(log n) lookup to determine if a proposed space-time cell is already occupied. Before committing an agent's path to the global plan, the planner queries the CAT for each cell along the proposed trajectory. A conflict is flagged if a cell is already reserved by another agent. This centralized check is the mechanism that enforces the non-collision constraint fundamental to MAPF, preventing both vertex conflicts (same location, same time) and edge conflicts (same edge, opposite directions, same time).

Optimal MAPF algorithms like Conflict-Based Search (CBS) and Increasing Cost Tree Search (ICTS) rely heavily on a CAT. In CBS, the high-level search node uses a CAT to validate the joint plan. When a conflict is found, it generates constraints (e.g., "Agent A cannot be at vertex V at time T"), and the low-level planner must find a new path for the affected agent that respects all constraints, which is verified against the updated CAT. The CAT is the single source of truth for constraint validation.

For large-scale or lifelong MAPF problems, suboptimal algorithms use the CAT to ensure feasibility, not optimality. Windowed Hierarchical Cooperative A (WHCA)** uses a CAT (often called a reservation table) to plan paths for agents within a short rolling time window. The CAT prevents collisions within that window, after which paths are replanned. This balances coordination with scalability. Similarly, algorithms using Priority Planning treat the CAT as a dynamic obstacle map for lower-priority agents.

A CAT is a proactive, centralized planning tool, fundamentally different from reactive, distributed collision avoidance methods like Optimal Reciprocal Collision Avoidance (ORCA) or Velocity Obstacles (VO).

• CAT (Planning): Operates before movement. Creates a deterministic, conflict-free schedule. Requires a central coordinator.
• ORCA (Reactive): Operates during movement. Agents sense neighbors and continuously adjust velocities. Is decentralized and handles unforeseen dynamic obstacles.

Hybrid systems often use a CAT for high-level schedule and ORCA for low-level, real-time deviation correction.

Efficient implementation is critical for performance. Common structures include:

• Hash Tables: Mapping (vertex, time) keys to agent IDs for O(1) average lookup/insertion.
• 2D Arrays: For discrete grids, a 3D array [time][x][y] can store agent IDs, offering O(1) access but high memory cost for long horizons.
• Interval-based Structures: Safe Interval Path Planning (SIPP) conceptually uses a CAT that stores intervals of time when a vertex is safe, reducing the temporal dimension's granularity.

The choice impacts the scalability of the overall MAPF solver, especially for problems with a long makespan or large number of agents.

The overarching computational problem of finding collision-free paths for multiple agents from start to goal locations in a shared environment. A Conflict Avoidance Table (CAT) is a key data structure used by many MAPF algorithms to efficiently store agent reservations and detect vertex conflicts and edge conflicts during the search process.

A leading optimal MAPF algorithm that uses a Conflict Avoidance Table (CAT) at its core. CBS operates on two levels:

• High-level: Searches a constraint tree, where each node contains a set of path constraints and a solution.
• Low-level: Plans individual agent paths using a CAT to respect all constraints and avoid conflicts with other agents' planned paths in the current node. Conflicts found via the CAT are used to generate new constraints, branching the search.

A scalable, suboptimal MAPF algorithm that relies heavily on a reservation table (a CAT). WHCA* plans paths for each agent within a short planning window.

• The CAT reserves space-time cells for the planned segment.
• Agents replan periodically as the window advances.
• This approach avoids the complexity of full horizon planning, enabling real-time coordination for large fleets, though it sacrifices global optimality guarantees.

A compact data structure encoding all possible optimal paths for a single agent within a given cost bound. In advanced MAPF algorithms like CBS, MDDs are used in conjunction with a Conflict Avoidance Table (CAT).

• The MDD for an agent shows all states (location, time) it can occupy in an optimal path.
• The CAT records the specific path chosen for that agent.
• Cross-referencing MDDs allows for sophisticated conflict analysis and more informed constraint generation, improving search efficiency.

A path planning algorithm that extends A* search to include time as an explicit dimension. It searches in a state space of (location, time).

• A Conflict Avoidance Table (CAT) is the natural data structure for tracking reservations in this space-time domain.
• When planning an agent's path, Space-Time A* queries the CAT to ensure no planned (x, y, t) cell is already occupied, preventing vertex conflicts.
• This makes it a fundamental low-level planner for many centralized MAPF algorithms.

A planning strategy that enforces a temporal buffer between agents to account for execution delays and uncertainty. It modifies the rules for a Conflict Avoidance Table (CAT).

• Instead of reserving only the exact time step t for a location, an agent reserves from t to t+k.
• This prevents other agents from planning to use the same location within that k-step window.
• While it reduces spatial efficiency, k-robust planning significantly increases the likelihood that planned paths will remain collision-free during real-world execution.