Batched A and space-time A¶

Two searches share one idea: on a unit-cost grid, the set of states at cost t is exactly the t-th wavefront, so expanding a whole frontier per sweep visits states in the same optimal order a serial A or Dijkstra would — with every cell of the frontier processed in parallel. "A" here names the problem semantics (optimal paths, Hart, Nilsson and Raphael 1968), not a serial open list.

`batched_astar`¶

Optimal single-agent paths for many (start, goal) queries at once: one batched BFS from the goals (which doubles as a reusable heuristic table), then an O(path length) gradient descent per query on the host. Returns cost-optimal paths, None for unreachable queries.

`space_time_astar`¶

The constrained low-level search of MAPF (Silver 2005, Cooperative pathfinding, AIIDE): states are (cell, time) pairs, waiting is a legal move, and a ReservationTable supplies

vertex constraints — cell v occupied at time t;
edge constraints — encoded as arrived_from[t, v]: because at most one agent arrives anywhere per timestep, a single integer per (t, cell) rules out every swap.

Each timestep is one masked dilation of the reachable set — five candidate predecessors per cell (4 moves + wait), checked against the table — implemented as array shifts on the CPU and as one kernel launch per timestep on CUDA, with the table resident on the device.

The settle rule matches pymapf: an agent may finish on its goal only after the last vertex reservation touching it, so a returned path can be extended by waiting forever.

Bounded horizon¶

The search enumerates timesteps up to a horizon bound and is complete only within it — a dense table over (horizon, cells) is the price of making constraint checks O(1) array lookups for the whole frontier at once. The default bound is generous for the instance sizes this library targets and is a constructor parameter everywhere it matters.

Batched shortest paths and constrained space-time search.

Two searches live here, both realized as frontier-parallel wavefronts:

:func:batched_astar — optimal single-agent paths for many (start, goal) queries at once. On a 4-connected grid with unit edge costs, A (Hart, Nilsson and Raphael 1968) and Dijkstra return the same paths; the wavefront expands exactly the cost-t band per sweep, so the batched flood fill is* the optimal search, with the entire batch advanced by every sweep. Paths are then extracted by gradient descent on the distance maps — O(path length) host work.
:func:space_time_astar — the constrained low-level search of MAPF (Silver 2005): states are (cell, t) pairs, wait moves are allowed, and vertex/edge reservations from a :class:~cuplan.reservations.ReservationTable are honoured. Since every edge costs one timestep, the set of states reachable at time t is exactly the cost-t band, so one masked dilation per timestep enumerates the search space in optimal order — every cell in parallel on the CUDA backend.

Both return cost-optimal paths (given the horizon bound, for the constrained search). "A*" names the problem semantics, not a serial open list: with unit costs the wavefront explores in the same optimal order without one.

batched_astar ¶

batched_astar(grid, starts, goals, backend='auto')

Solve many single-agent shortest-path queries in one batch.

Parameters:

Name	Type	Description	Default
`grid`	`Grid`	the occupancy grid.	required
`starts`	`ndarray`	`(n, 2)` start cells.	required
`goals`	`ndarray`	`(n, 2)` goal cells.	required
`backend`	`Backend`	`"auto"`, `"cpu"` or `"cuda"`.	`'auto'`

Returns:

Type	Description
`list[Path \| None]`	A list of `n` paths (lists of cells, start to goal inclusive),
`list[Path \| None]`	with `None` where the goal is unreachable from the start.
`list[Path \| None]`	Each returned path is cost-optimal.

Source code in cuplan/astar.py

def batched_astar(
    grid: Grid,
    starts: np.ndarray,
    goals: np.ndarray,
    backend: Backend = "auto",
) -> list[Path | None]:
    """Solve many single-agent shortest-path queries in one batch.

    Args:
        grid: the occupancy grid.
        starts: ``(n, 2)`` start cells.
        goals: ``(n, 2)`` goal cells.
        backend: ``"auto"``, ``"cpu"`` or ``"cuda"``.

    Returns:
        A list of ``n`` paths (lists of cells, start to goal inclusive),
        with ``None`` where the goal is unreachable from the start.
        Each returned path is cost-optimal.
    """
    starts = np.atleast_2d(np.asarray(starts, dtype=np.int32))
    goals = np.atleast_2d(np.asarray(goals, dtype=np.int32))
    if starts.shape != goals.shape:
        raise ValueError("starts and goals must have the same shape")
    # One BFS per goal: dist[i] is the exact cost-to-go for query i,
    # which doubles as the heuristic table other solvers reuse.
    dist = distance_maps(grid, goals, backend=backend)
    return [
        _descend(grid, dist[i], tuple(starts[i]), tuple(goals[i]))
        for i in range(len(starts))
    ]

space_time_astar ¶

space_time_astar(grid, start, goal, table=None, horizon=None, backend='auto')

Find a minimal-time path from start to goal under reservations.

Waiting in place is a legal move. The agent may only settle on the goal after the last vertex reservation touching it, so a path is returned only when the agent can stay once it arrives — the same settle rule as pymapf's space-time A*.