Windowed Hierarchical Cooperative A* (WHCA*)

WHCA* does not plan complete paths to the goal. Instead, it plans only a short segment—typically 5 to 15 timesteps into the future—known as the planning window. Agents execute this segment and then replan from their new position. This rolling horizon approach allows the algorithm to adapt to dynamic changes and new agent insertions in real-time, but it sacrifices global optimality for local feasibility.

The core coordination mechanism is a centralized Conflict Avoidance Table (CAT). This data structure stores space-time reservations—records of which agent plans to occupy which (x, y, t) cell. When an agent plans its windowed path using A*, it queries the CAT to avoid cells already reserved by other agents. This enforces hard constraints that prevent vertex conflicts (same location, same time) and edge conflicts (swapping positions).

WHCA* is a decoupled algorithm, meaning it plans for each agent independently rather than in the exponential joint state space. The hierarchy has two levels:

• High Level: Assigns a fixed priority order to agents (often static).
• Low Level: Each agent, in priority order, runs a space-time A* search for its window, respecting reservations from higher-priority agents. This structure makes computation scalable to hundreds of agents, as search complexity grows linearly with the number of agents, not exponentially.

WHCA* is bounded suboptimal; it does not guarantee the shortest sum-of-costs or makespan. Suboptimality arises from three sources:

1. Fixed Priority Ordering: Lower-priority agents are treated as moving obstacles, which can lead to detours.
2. Limited Lookahead: The short window cannot anticipate conflicts far in the future.
3. Myopic Replanning: Replanning at each step can lead to oscillatory or inefficient global behavior. The trade-off is extreme scalability, often solving problems with 100+ agents in milliseconds where optimal algorithms fail.

WHCA* is practically deployed in environments where density is moderate and dynamic changes are frequent. Classic examples include:

• Autonomous Mobile Robot (AMR) fleets in fulfillment centers, where new pick tasks are constantly assigned.
• Dynamic obstacle avoidance with human workers or manual vehicles entering the workspace.
• Online Lifelong MAPF (LMAPF) scenarios, where agents receive new goals immediately upon completing old ones. The algorithm's fast replanning cycle (e.g., every 100ms) is ideal for these operational conditions.

Despite its strengths, WHCA* has known failure modes that system architects must mitigate:

• Deadlocks: Agents can cyclically block each other, especially in narrow corridors, because the short window cannot plan around complex interdependencies.
• Starvation: Low-priority agents can be perpetually delayed by a stream of higher-priority agents.
• Window Size Sensitivity: Performance is highly sensitive to the chosen window length. Too short leads to myopia; too long reduces the benefit of replanning and increases computation.
• Priority Assignment: A poor static priority ordering can drastically reduce overall throughput. Adaptive or dynamic priority schemes are often layered on top.

WHCA* is a cornerstone algorithm for coordinating fleets of Autonomous Mobile Robots (AMRs) in distribution centers. It enables dozens of robots to navigate shared aisles, pick stations, and charging docks without deadlock.

• Dynamic Replanning: The periodic replanning window allows robots to adapt to new orders, blocked pathways, or priority overrides in near real-time.
• Scalability: By planning for a short horizon (e.g., 5-10 seconds) and using a hierarchical approach, WHCA* can manage 50-100+ agents where optimal algorithms like CBS or MAA* become computationally intractable.
• Use Case: A major e-commerce fulfillment center uses WHCA* to coordinate a mixed fleet of item-picking AMRs and larger pallet-transport robots, reducing travel time by ~22% compared to older, zone-based routing.

In port automation, Automated Guided Vehicles (AGVs) transport shipping containers between ships, cranes, and storage yards. WHCA* provides the necessary collision-free path planning in this highly structured but dynamic grid environment.

• Spatial-Temporal Reservations: The algorithm's reservation table prevents conflicts at critical intersections and under crane gantries, where collisions are catastrophic.
• Handling Priorities: The hierarchical framework can incorporate dynamic priorities, allowing urgent export containers to bypass standard traffic flows.
• Integration: WHCA* acts as the core planner within a larger Spatial-Temporal Scheduling system that also manages crane operations and yard stacking, minimizing vessel turnaround time.

For service robots delivering meals, linens, or lab samples in semi-structured environments like hospitals, WHCA* balances efficiency with robust safety.

• Human-Shared Spaces: The short planning window and frequent replanning allow robots to react to unpredictable human movement in corridors and elevator lobbies.
• Decentralized Execution: Each robot can run its own WHCA* instance, sharing only its reserved space-time cells (via the Conflict Avoidance Table) with a central coordinator, reducing communication overhead.
• Example: A hospital deployment uses WHCA*-based robots for pharmacy deliveries. The system dynamically reroutes around closed corridors for cleaning or emergency traffic, maintaining >99% on-time delivery without requiring full global replans.

WHCA* is widely used in real-time strategy games and massive multi-agent simulations where rendering believable group movement for hundreds of units is critical.

• Performance: The algorithm's suboptimal but fast solutions are perfectly suited for 60 FPS game loops, where visual plausibility trumps mathematical optimality.
• Natural-looking Flow: The windowed approach creates fluid, adaptive crowd movement as units continuously replan around each other, avoiding the rigid, pre-computed paths that look robotic.
• Application: Game engines use WHCA* variants for large-scale battle scenes, civilian crowd simulations, and any scenario requiring Lifelong MAPF (LMAPF) where agents receive new goals continuously.

In flexible, cellular manufacturing systems, autonomous carts transport components between workstations. WHCA* coordinates these carts in a tightly coupled, just-in-time environment.

• JIT Synchronization: Paths are planned within time windows that align with station cycle times, ensuring a component arrives precisely when a workstation is ready.
• Deadlock Prevention: The reservation table mechanism inherently prevents gridlock in confined spaces like assembly cell entry points, a common failure mode for simpler algorithms.
• System Benefit: Enables rapid reconfiguration of production lines. When a workstation is moved, the WHCA* planner's graph is updated, and carts automatically adapt their routing without reprogramming.

For synchronized aerial drone displays involving hundreds of UAVs, WHCA* provides the foundational coordination layer for generating safe, collision-free trajectories.

• 3D Space-Time Planning: The algorithm extends naturally to 3D grids, reserving airspace cubes (x, y, z, t) to prevent mid-air collisions during complex maneuvers.
• Robustness to Timing Errors: The concept of k-Robust Planning can be integrated with WHCA* by inflating reservations, providing a buffer for minor motor or timing variances between drones.
• Surveillance Adaptation: In perimeter monitoring or search missions, drones use WHCA* to dynamically partition airspace and patrol sectors, replanning as threats are identified or battery levels drop, linking to Battery-Aware Scheduling.

Multi-Agent Path Finding (MAPF) is the foundational computational problem of planning collision-free paths for multiple agents from their start positions to their goal positions in a shared environment. It is the core problem that WHCA* is designed to solve.

• Centralized vs. Decoupled: Algorithms are categorized as centralized (planning in the joint state space of all agents) or decoupled (planning for agents individually with coordination).
• Optimality Criteria: Solutions are typically evaluated on metrics like Makespan (total completion time) or Sum of Costs (SOC) (total distance traveled).
• Complexity: Finding optimal paths is NP-hard, leading to the development of scalable, suboptimal algorithms like WHCA*.

Conflict-Based Search (CBS) is a leading optimal, centralized MAPF algorithm. It operates on two levels: a high-level constraint tree and low-level path planners for individual agents.

• Constraint Resolution: When a conflict (e.g., two agents occupying the same space-time) is found, CBS branches by imposing constraints on the involved agents and replans their paths.
• Optimality Guarantee: It systematically explores constraint combinations until it finds a conflict-free solution with minimal cost.
• Contrast with WHCA*: Unlike CBS, WHCA* is a decoupled, suboptimal, and windowed algorithm designed for scalability in lifelong planning scenarios, sacrificing optimality for real-time performance.

A Conflict Avoidance Table (CAT) is a core data structure used by WHCA* and other MAPF algorithms to enable efficient coordination. It is essentially a space-time reservation table.

• Function: The CAT records which agent has reserved a specific grid cell at a specific future time step.
• Fast Conflict Detection: During planning, an agent's proposed path is checked against the CAT to detect vertex conflicts (same cell, same time) and edge conflicts (swapping positions).
• Hierarchical Use in WHCA*: In WHCA*, agents plan using a local CAT that only contains reservations within the current planning window, enabling decoupled and parallel planning.

Lifelong MAPF (LMAPF) is a dynamic variant of the path finding problem where agents continuously execute and receive new tasks, making it a persistent, online planning challenge. This is the primary operational context for WHCA*.

• Continuous Operation: Agents are never "done"; upon reaching a goal, they are immediately assigned a new one.
• Requires Replanning: The environment and agent objectives are constantly changing, necessitating algorithms that can replan efficiently.
• WHCA's Fit*: WHCA* is explicitly designed for LMAPF. Its windowed approach (planning only a short segment ahead) and periodic replanning cycle are ideal for this never-ending, dynamic problem.

Space-Time A* is a fundamental path planning algorithm that extends the classic A* search to include time as an explicit dimension. It is the low-level planner used within the WHCA* framework.

• Node Representation: Each search node is a tuple (x, y, t) representing a location at a specific time step.
• Collision Checking: Paths are planned directly in a 3D space-time grid, allowing the algorithm to avoid reservations in the Conflict Avoidance Table (CAT) by treating them as blocked cells.
• Role in WHCA*: Each agent in WHCA* uses Space-Time A* to find an optimal path from its current position to its sub-goal within the current fixed-duration planning window, respecting the shared CAT.

Bounded Suboptimal Search refers to a class of algorithms that sacrifice guaranteed optimality for significant gains in speed or scalability, with a provable bound on solution cost. WHCA* falls into this category.

• Weighted A*: A common technique where the heuristic is multiplied by a weight (w > 1), speeding up the search but potentially returning a path with cost no worse than w * optimal_cost.
• Trade-off: This is a critical engineering trade-off in real-world systems where a feasible solution now is more valuable than an optimal solution later.
• WHCA's Suboptimality*: WHCA*'s suboptimality arises from its decoupled nature (agents plan independently per window) and its use of a limited planning horizon, which can lead to myopic decisions.