AtsushiSakai/PythonRobotics · error · Exception

No path found

Error message

No path found

What it means

Thrown by SpaceTimeAStar.plan when the open set is exhausted before the goal is reached: no time-expanded path exists that avoids dynamic obstacles (and reservations) within the grid's time limit. It signals an unsolvable or over-constrained planning query.

Source

Thrown at PathPlanning/TimeBasedPathPlanning/SpaceTimeAStar.py:68

                path_walker: Node = expanded_node
                while True:
                    path.append(path_walker)
                    if path_walker.parent_index == -1:
                        break
                    path_walker = expanded_list[path_walker.parent_index]

                # reverse path so it goes start -> goal
                path.reverse()
                return NodePath(path, len(expanded_set))

            expanded_idx = len(expanded_list)
            expanded_list.append(expanded_node)
            expanded_set.add(expanded_node)

            for child in SpaceTimeAStar.generate_successors(grid, goal, expanded_node, expanded_idx, verbose, expanded_set):
                heapq.heappush(open_set, child)

        raise Exception("No path found")

    """
    Generate possible successors of the provided `parent_node`
    """
    @staticmethod
    def generate_successors(
        grid: Grid, goal: Position, parent_node: Node, parent_node_idx: int, verbose: bool, expanded_set: set[Node]
    ) -> Generator[Node, None, None]:
        diffs = [
            Position(0, 0),
            Position(1, 0),
            Position(-1, 0),
            Position(0, 1),
            Position(0, -1),
        ]
        for diff in diffs:
            new_pos = parent_node.position + diff
            new_node = Node(

View on GitHub (pinned to 1fe4fb980f)

Solutions

1. Increase the grid's time_limit so the search has enough timesteps
2. Lower obstacle density or change the arrangement so a route exists
3. Check start/goal validity and that they are not permanently obstructed
4. Catch the exception and treat it as an 'unreachable' result (skip/wait the agent)

Example fix

# before
path = SpaceTimeAStar.plan(grid, start, goal)

# after
try:
    path = SpaceTimeAStar.plan(grid, start, goal)
except Exception as e:
    if 'No path found' in str(e):
        path = None  # agent cannot reach goal under current constraints
    else:
        raise

assert grid.time_limit > abs(start.x - goal.x) + abs(start.y - goal.y), "time_limit too short for any path"

try:
    path = SpaceTimeAStar.plan(grid, start, goal)
except Exception as e:
    if str(e) == 'No path found':
        path = None  # unreachable under current constraints
    else:
        raise

When it happens

Trigger: Calling SpaceTimeAStar.plan(grid, start, goal) where every candidate route is blocked by dynamic obstacles or reserved cells, or where the grid's time_limit is shorter than any feasible path length.

Common situations: High obstacle density or adversarial arrangements; small time_limit relative to grid size; multi-agent runs where earlier reservations block the later agent; invalid/out-of-bounds goal positions.

Related errors

• No path found
• Number of obstacles is greater than grid size!
• Agent index cannot be 0
• Agent {agent_index} tried to reserve a position already rese
• Path position not found for time {i}.

AI-assisted analysis of AtsushiSakai/PythonRobotics@1fe4fb980f (2026-08-28). Data as JSON: /api/errors/7e23409c279c0398. Report an issue: GitHub.