Cooperative Pathfinding (Silver 2005)

---

Paper Link: Cooperative Pathfinding

@inproceedings{silver2005cooperative,
  title={Cooperative pathfinding},
  author={Silver, David},
  booktitle={Proceedings of the aaai conference on artificial intelligence and interactive digital entertainment},
  volume={1},
  number={1},
  pages={117--122},
  year={2005}
}

To start experimenting the code environment, please look at Getting Started file.

---

The paper studies Cooperative Pathfinding, a multi-agent path planning setting where all agents have full knowledge of each other’s planned routes. The target domain is real-time, congested environments (strategic games), where classical replanning-based approaches fail due to bottlenecks, deadlocks, and oscillations.

The work introduces and evaluates three decoupled but cooperative algorithms:

• Cooperative A* (CA*): It searches space-time for a non-colliding route.
• Hierarchical Cooperative A* (HCA*): It uses an abstract heuristic to boost performance.
• Windowed Hierarchical Cooperative A* (WHCA*): It limits the space-time search depth to a dynamic window, spreading computation over the duration of the route.

These are compared against the industry-standard Local Repair A* (LRA*).

---

Baseline Algorithm: Local Repair A* (LRA*)

LRA* works in the following manner:

• Each agent plans independently with A*, ignoring others except for imminent collisions.
• On collision, the agent replans.
• Every time an agent is forced to replan, its agitation level increases.
• Random noise then added to the A* heuristic, proportional to agitation.
• The hope is that randomness helps agents wiggle out of deadlocks or bottlenecks.

LRA* weakness:

• Deadlocks in narrow passages.
• Excessive replanning.
• Cyclic behavior.
• Poor scalability with agent count.

---

Cooperative A* (CA*)

It plans each agent's path in space-time while treating other agents' planned future positions as hard constraints via a reservation table, ensuring collision-free execution, but at high computational cost with strong dependence on agent ordering.

🧩 Key Data Structure: The Reservation Table

The reservation table is a shared structure that records "which spatial locations are occupied at which times".

Formally:

• Each entry is a tuple (x, y, t)
• If a cell is reserved at time t, no other agent may occupy it at t.
• Waiting in place is allowed, but only if the space-time cell is free.

The table is typically sparse and implemented as a hash map.

✍ Planning Procedure

Step 1: Choose an Agent Order

Agents are planned sequentially using a fixed priority ordering:

$A_1 \rightarrow A_2 \rightarrow A_3 \rightarrow \cdots \rightarrow A_n$

Earlier agents constrain later ones.

Step 2: Single-Agent Space-Time A* Search

For agent $A_i$:

• State space: (x, y, t)
• Actions:
  • Move N, E, S, W
  • Wait (stay in place)
• Transition cost: usually 1 per step
• Heuristic: typically Manhattan distance (ignoring time and agents)

During search:

• Any successor (x', y', t+1) that is reserved is forbidden.
• Collisions are avoided by construction.

Step 3: Commit the Path

Once a path is found:

• All (x, y, t) states along the path are inserted into the reservation table.
• These become hard constraints for all later agents.

Step 4: Repeat for all Agents

continue until all agents are planned or a failure occurs.

🛡️ What CA* Guarantees

If CA* finds a path for all agents, then:

• ✅️ No two agents collide (vertex conflict)
• ✅️ Agents follow consistent, non-oscillatory paths
• ✅️ Each agent has a complete, time-indexed plan

However, CA* is not complete in general.

🚧 Fundamental Limitations

1) Sensitivity to Agent Ordering: Because CA* is greedy and sequential

• A poor priority order can make the problem unsolvable
• Early agents may block critical corridors indefinitely

This is a classic weakness of prioritized planning.

2) Computational Cost: The search space is 3D (x, y, t)

• Branching factor increases (including wait actions)
• Time horizon can grow large
• Full paths must be planned before execution

This makes CA* slow for real-time systems.

3) Goal Blocking: Once an agent reaches its goal

• It remains there forever in the reservation table.
• This can block other agents in narrow environments.

CA* has no mechanism for ongoing cooperation after arrival.

👨‍💻 CA* Pseudocode

procedure CA_STAR(map, agents_in_priority_order):
    R ← empty_reservation_table()

    for agent a in agents_in_priority_order do
        path_a ← SPACE_TIME_ASTAR(map, a.start, a.goal, R, heuristic=MANHATTAN)
        if path_a = FAIL then
            return FAIL
        RESERVE_PATH(R, path_a)          // mark (x,y,t) along the path
        a.path ← path_a
    end for

    return {a.path for all agents a}


procedure SPACE_TIME_ASTAR(map, s, g, R, heuristic):
    // state: (x, y, t)
    open ← priority_queue()
    g_cost[(s.x, s.y, 0)] ← 0
    push open with node (s.x, s.y, 0) with f = g_cost + heuristic((x,y), g)

    while open not empty do
        n ← pop_min_f(open)
        if (n.x, n.y) = g then
            return RECONSTRUCT_PATH(n)

        for each action in {N,E,S,W,WAIT} do
            n2 ← successor_state(n, action)     // (x',y',t+1)
            if n2 hits_obstacle(map) then continue
            if RESERVED(R, n2.x, n2.y, n2.t) then continue    // vertex conflict
            if EDGE_CONFLICT(R, n, n2) then continue          // swap conflict (recommended)
            tentative ← g_cost[n] + 1
            if n2 not seen or tentative < g_cost[n2] then
                parent[n2] ← n
                g_cost[n2] ← tentative
                f ← tentative + heuristic((n2.x,n2.y), g)
                push_or_decrease_key(open, n2, f)
        end for
    end while

    return FAIL

🤝🏻 Relationship to Later Algorithms

CA* is the conceptual foundation for:

• Hierarchical Cooperative A* (HCA*)
• Windowed HCA* (WHCA*)
• Modern reservation-table MAPF methods
• Rolling-horizon and execution-aware planners

Later methods keep CA*’s explicit space–time constraints, but:

• Limit planning horizon
• Add replanning
• Allow agents to move after reaching goals
• Reduce sensitivity to priority order

---

Hierarchical Cooperative A* (HCA*)

Hierarchical Cooperative A* (HCA*) is an extension of Cooperative A* (CA*) that reduces computational cost by using a hierarchical, abstraction-based heuristic, while keeping the same cooperative planning framework.

💡 Motivation

CA* plans in full space–time (x, y, t) and is expensive because:

• The search space is large (extra time dimension)
• The heuristic (e.g., Manhattan distance) ignores agent interactions poorly
• Many unnecessary nodes are expanded

HCA* addresses this by giving CA* a much stronger heuristic.

🎯 Core Idea

HCA* uses a hierarchical abstraction of the environment to compute exact distances in a simplified domain, and uses those distances as an admissible heuristic during cooperative space–time search.

Crucially:

• The abstraction removes time
• The abstraction removes other agents
• Only static obstacles remain

👀 Two search spaces

(a) Concrete (Low-Level) Space

Used for actual planning: (x, y, t)

👨‍💻 HCA* Pseudocode

procedure HCA_STAR(map, agents_in_priority_order):
    R ← empty_reservation_table()

    for agent a in agents_in_priority_order do
        // per-agent abstract heuristic cache
        rra ← INIT_RRA_STAR(map_2D_without_agents, a.goal, a.start)

        path_a ← SPACE_TIME_ASTAR(map, a.start, a.goal, R,
                                  heuristic = (pos)->ABSTRACT_DIST(rra, pos))
        if path_a = FAIL then
            return FAIL
        RESERVE_PATH(R, path_a)
        a.path ← path_a
    end for

    return {a.path for all agents a}


procedure INIT_RRA_STAR(map2D, goal, origin):
    // Reverse A* from goal; can be resumed to compute dist(node→goal)
    rra.open ← PQ(); rra.closed ← set()
    set g(goal)=0
    push rra.open goal with f = g(goal) + MANHATTAN(goal, origin)
    rra.goal ← goal; rra.origin ← origin; rra.map2D ← map2D
    return rra


procedure ABSTRACT_DIST(rra, node_xy):
    if node_xy in rra.closed then
        return g(node_xy)   // already optimal distance to goal
    RESUME_RRA_UNTIL(rra, node_xy)
    if node_xy in rra.closed then return g(node_xy)
    return +∞


procedure RESUME_RRA_UNTIL(rra, target_xy):
    while rra.open not empty do
        p ← pop_min_f(rra.open)
        add p to rra.closed
        if p = target_xy then return
        for each neighbor q of p in 4-neighborhood do
            if q blocked in rra.map2D then continue
            tentative ← g(p) + 1
            if q not in rra.open and q not in rra.closed then
                set g(q)=tentative
                f(q)=g(q)+MANHATTAN(q, rra.origin)
                push rra.open q
            else if q in rra.open and tentative < g(q) then
                update g(q), decrease_key in rra.open
        end for
    end while

---

Windowed Hierarchical Cooperative A* (WHCA*)

👨‍💻 WHCA* Pseudocode

procedure WHCA_STAR(map, agents, window_size w, replan_every k):
    // Typical choice in the paper: replan when halfway through window ⇒ k = w/2
    R ← empty_reservation_table()

    // Each agent keeps its own RRA* cache across windows (reuse)
    for each agent a do
        a.rra ← INIT_RRA_STAR(map_2D_without_agents, a.goal, a.start)
        a.plan ← empty
    end for

    t_global ← 0
    while not all agents finished (or for each simulation tick) do

        // Option A: plan for all agents each cycle; Option B: stagger planning
        for each agent a in some scheduling order do
            // compute partial plan of length w in space-time (relative time 0..w)
            partial ← WINDOWED_SPACE_TIME_ASTAR(map, a.pos, a.goal, R, w,
                                                heuristic=(pos)->ABSTRACT_DIST(a.rra, pos))

            if partial = FAIL then
                return FAIL

            // Reserve only within the window horizon
            RESERVE_PATH_WINDOW(R, a.id, partial, t_global, w)

            a.plan ← partial
        end for

        // Execute k steps, then slide window
        for step = 1..k do
            for each agent a do
                a.pos ← EXECUTE_NEXT_ACTION(a.plan)
            end for
            t_global ← t_global + 1
            ADVANCE_RESERVATIONS_TIME(R)  // optional housekeeping
        end for
    end while

    return SUCCESS


procedure WINDOWED_SPACE_TIME_ASTAR(map, s_xy, g_xy, R, w, heuristic):
    // state: (x, y, τ) where τ is time offset inside window: 0..w
    // Terminal rule at depth w: connect to goal with cost=abstract_dist
    open ← PQ()
    start_state ← (s_xy.x, s_xy.y, 0)
    g_cost[start_state] ← 0
    push open start_state with f = 0 + heuristic(s_xy)

    while open not empty do
        n ← pop_min_f(open)

        if n.τ = w then
            // reached window boundary: terminate and score using abstract distance
            return RECONSTRUCT_PARTIAL_PATH(n)

        for each action in {N,E,S,W,WAIT} do
            n2 ← successor(n, action)   // (x',y',τ+1)
            if n2 hits_obstacle(map) then continue
            if RESERVED(R, n2.x, n2.y, absolute_time = current_global_time + n2.τ) then continue
            if EDGE_CONFLICT(R, n, n2, absolute_time) then continue

            step_cost ← 1
            tentative ← g_cost[n] + step_cost

            // f uses heuristic normally, but implicitly WHCA* treats depth=w as terminal
            f ← tentative + heuristic((n2.x, n2.y))

            if n2 not seen or tentative < g_cost[n2] then
                parent[n2] ← n
                g_cost[n2] ← tentative
                push_or_decrease_key(open, n2, f)
        end for
    end while

    return FAIL