SpaceTimeAStar
- class w9_pathfinding.mapf.SpaceTimeAStar
A space-time A* planner for dynamic pathfinding.
The planner computes collision-free paths for a single agent in environments with known dynamic obstacles.
- Parameters:
env (Environment) – The environment in which to search for paths.
- find_path(start, goal, max_length=100, reservation_table=None)
Finds an optimal path from start to goal, constrained by a maximum path length.
Guarantees persistent goal safety: once the agent reaches the goal, it can remain there indefinitely without future collisions.
Note: There may exist a lower-cost path with a length greater than max_length. This function only considers paths of length ≤ max_length.
- Parameters:
start (node) – The starting node.
goal (node) – The goal node.
max_length (int, default=100) – Maximum allowed path length (number of time steps).
reservation_table (ReservationTable, optional) – Dynamic obstacles.
- Returns:
path – A list of nodes representing the path. Returns an empty list if no valid path is found.
- Return type:
list[node]
- find_path_with_depth_limit(start, goal, search_depth=100, stay_at_goal=True, reservation_table=None)
Performs A* search with a limited planning depth, returning partial paths when needed.
This function explores the space-time environment up to search_depth time steps. If a full path to the goal is found within that depth, it is returned. Otherwise, a partial path is returned.
This method is particularly useful in scenarios where the environment may change in the near future — for example, in WHCA*-like algorithms or rolling-horizon planning — where computing the full path is unnecessary or even wasteful.
- Parameters:
start (node) – The starting node.
goal (node) – The goal node.
search_depth (int, default=100) – Maximum number of time steps the planner is allowed to search
stay_at_goal (bool, default=True) – If True, ensures safety at the goal for all future steps.
reservation_table (ReservationTable, optional) – Dynamic obstacles.
- Returns:
path – A list of nodes representing the path. Returns an empty list if no valid path is found.
- Return type:
list[node]
- find_path_with_exact_length(start, goal, length, reservation_table=None)
Finds an optimal collision-free path from start to goal with an exact number of steps.
It is useful for tightly synchronized planning where arrival time is fixed.
The agent is assumed to disappear immediately upon reaching the goal; no further collision checks are performed at the goal after arrival.
- Parameters:
start (node) – The starting node.
goal (node) – The goal node.
length (int) – Required number of time steps for the path
reservation_table (ReservationTable, optional) – Dynamic obstacles.
- Returns:
path – A list of nodes representing the path. Returns an empty list if no valid path is found.
- Return type:
list[node]
- find_path_with_length_limit(start, goal, max_length, stay_at_goal=True, reservation_table=None)
Finds an optimal path from start to goal, constrained by a maximum path length.
Note: There may exist a lower-cost path with a length greater than max_length This function only considers paths of length ≤ max_length.
- Parameters:
start (node) – The starting node.
goal (node) – The goal node.
max_length (int) – Maximum number of time steps (path length) allowed
stay_at_goal (bool, default=True) – If True, the agent must remain safely at the goal after arrival. If False, the agent disappears upon reaching the goal.
reservation_table (ReservationTable, optional) – Dynamic obstacles.
- Returns:
path – A list of nodes representing the path. Returns an empty list if no valid path is found.
- Return type:
list[node]