ResumableSpaceTimeDijkstra

class w9_pathfinding.mapf.ResumableSpaceTimeDijkstra

Space-time version of Resumable Dijkstra’s algorithm.

This class performs a single-source Dijkstra traversal in a time-expanded graph starting from (start_node, 0). It supports dynamic obstacles via a ReservationTable, and allows querying shortest-path distances and paths to nodes at specific times.

Unlike standard Dijkstra’s algorithm, results are cached and reused efficiently for multiple distance/path queries without re-running the full search.

It guarantees to find the optimal path in any environment.

The search only considers states (node, t) where t <= time_horizon.

Parameters:

  • env (Environment) – The environment in which to search for paths.

  • start_node (node) – The source node. The search starts from (start_node, 0).

  • reservation_table (ReservationTable, optional) – Dynamic obstacles.

  • time_horizon (int, default=100) – Maximum time step considered by the search. States with time greater than time_horizon are not explored.

Raises:

ValueError – If start_node is not a valid node in the environment.

distance(node, time=None)

Get the shortest-path cost from (start_node, 0) to the given node.

Parameters:

  • node (node) – The target node.

  • time (int, optional) – The arrival time. If provided, returns the cost to reach (node, time). If None, returns the minimum cost to reach the node at any time t <= time_horizon.

Returns:

The minimum cost from (start_node, 0) to the target. Returns float(‘inf’) if the node is unreachable.

Return type:

float

Raises:

ValueError – If node is not a valid node in the environment.

find_path(node, time=None)

Find the optimal path from (start_node, 0) to the given node.

Parameters:

  • node (node) – The target node.

  • time (int, optional) – The arrival time. If provided, returns a path that reaches (node, time). If None, returns the optimal path reaching the node at any time t <= time_horizon.

Returns:

A list of nodes representing the optimal path. If a path is found, the list starts with start_node and ends with node. Returns an empty list if the node is unreachable.

Return type:

list[node]

Raises:

ValueError – If node is not a valid node in the environment.

start_node

The current start node for the search.

This is the node from which all paths and distances are computed, starting at time t = 0.

You can get or set this property. Setting a new start node will reset internal state and rerun Dijkstra’s algorithm in the next query.