AtsushiSakai/PythonRobotics · error · Exception

No path found

Error message

No path found

What it means

Thrown by SafeIntervalPathPlanner.plan when the open set is exhausted without reaching the goal: no sequence of safe-interval transitions exists from start to goal under the current dynamic obstacles and reservations. This is the standard 'unsolvable instance' signal for the planner.

Source

Thrown at PathPlanning/TimeBasedPathPlanning/SafeInterval.py:96

                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_list))

            expanded_idx = len(expanded_list)
            expanded_list.append(expanded_node)
            entry_time_and_node = EntryTimeAndInterval(expanded_node.time, expanded_node.interval)
            add_entry_to_visited_intervals_array(entry_time_and_node, visited_intervals, expanded_node)

            for child in SafeIntervalPathPlanner.generate_successors(grid, goal, expanded_node, expanded_idx, safe_intervals, visited_intervals):
                heapq.heappush(open_set, child)

        raise Exception("No path found")

    """
    Generate list of possible successors of the provided `parent_node` that are worth expanding
    """
    @staticmethod
    def generate_successors(
        grid: Grid, goal: Position, parent_node: SIPPNode, parent_node_idx: int, intervals: np.ndarray, visited_intervals: np.ndarray
    ) -> list[SIPPNode]:
        new_nodes = []
        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

View on GitHub (pinned to 1fe4fb980f)

Solutions

1. Increase the grid's time_limit so a feasible arrival time exists
2. Reduce num_obstacles or change obstacle_arrangement so a safe route exists
3. Verify start/goal are valid, in-bounds cells not permanently occupied by obstacles
4. Wrap plan() in try/except and report 'unreachable goal' to the caller instead of crashing

Example fix

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

# after
try:
    path = SafeIntervalPathPlanner.plan(grid, start, goal)
except Exception as e:
    if 'No path found' in str(e):
        path = None  # handle unreachable goal
    else:
        raise

# sanity check before planning: goal reachable in principle within time limit
assert grid.time_limit > abs(start.x - goal.x) + abs(start.y - goal.y), "time_limit too short for any path"

try:
    path = planner.plan(grid, start, goal)
except Exception as e:
    if str(e) == 'No path found':
        path = None  # treat as unreachable; relax constraints or skip agent
    else:
        raise

When it happens

Trigger: Calling SafeInterval.plan(grid, start, goal) where the goal (or all routes to it) is permanently blocked by obstacle trajectories or reserved cells, or the time_limit of the grid is too short to reach the goal.

Common situations: Dense obstacle arrangements (e.g. NARROW_CORRIDOR with moving blockers); a grid time_limit smaller than the shortest path length; goal cell occupied by an obstacle at all safe intervals; previously reserved agent paths walling off the goal.

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/34c75e0a1920dfa4. Report an issue: GitHub.