💻 computer science

StochSIPP: Safe Interval Path Planning in Stochastic Dynamic Environments

StochSIPP is an exact contingent planner that combines Safe Interval Path Planning (SIPP) with bounded AND/OR search to generate optimal, collision-free policies for navigating temporal roadmaps with uncertain, locally revealed blockages, effectively reducing arrival times and solving scenarios where conservative fixed-path planners fail.

Original authors: Ajith Kemisetti, Shahaf S. Shperberg, Yoonchang Sung

Published 2026-08-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ajith Kemisetti, Shahaf S. Shperberg, Yoonchang Sung

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the captain of a spaceship navigating a dense, shifting asteroid field. You have a map, but it's not a static picture; it's a live feed of probabilities. Some asteroids might be solid rocks, others might be ghostly illusions that vanish if you get close enough. In the world of robotics, this is the challenge of Safe Navigation. Robots need to move through spaces filled with moving things—like people in a warehouse or cars on a street—without crashing. The tricky part is that these moving things are unpredictable. If a robot guesses wrong and moves into a space that suddenly becomes blocked, it crashes. If it guesses too conservatively and waits forever for a path to clear, it never gets anywhere.

To solve this, scientists use a concept called Safe Interval Path Planning (SIPP). Think of SIPP as a robot's way of saying, "I know this hallway is safe for the next 5 seconds, so I'll sprint through it." It breaks time into chunks where the path is guaranteed clear. But what happens when the robot isn't sure if the hallway will stay clear? What if there's a 50% chance a door is locked and a 50% chance it's open, and the robot can only find out by walking up to the door? This is where the paper steps in, tackling the messy reality of planning when the future is a roll of the dice, but the robot still needs to get to its destination without getting smashed.

Enter StochSIPP, a new "smart planner" designed by researchers Ajith Kemisetti, Shahaf S. Shperberg, and Yoonchang Sung. You can think of StochSIPP as a master chess player who doesn't just plan one move ahead, but plans for every possible way the game could unfold. Unlike older methods that either guess the most likely future and hope for the best (which often leads to crashes) or assume the worst-case scenario for everything (which makes the robot stand still like a statue), StochSIPP plays a game of "What If?" before it even moves.

Here's how it works in plain English: Imagine you are trying to cross a river with several bridges. Some bridges are definitely open, some are definitely broken, and some are "maybe" bridges—you won't know if they are safe until you get to the bank and look. A traditional robot might pick the shortest bridge, run toward it, and if it turns out to be broken, it crashes or has to turn around. A super-cautious robot might refuse to cross any "maybe" bridge, even if it's the only way across.

StochSIPP is different. It creates a contingent policy, which is like a "Choose Your Own Adventure" book for the robot. Before it takes a single step, it calculates a plan that says: "If I see the first bridge is open, I'll run across it. But if I see it's blocked, I'll immediately switch to the second bridge." It doesn't just pick one path; it picks a strategy that covers all the possible outcomes it might see. It uses a clever trick called macro-actions, which are like "super-steps." Instead of planning every tiny footstep, the robot plans a "sprint to the next observation point." It asks, "If I sprint here, what will I see? If I see X, I'll do Y. If I see Z, I'll do W."

The paper proves that this method is mathematically safe. If the robot follows the plan and the sensors work correctly, it will never crash. It's like having a safety net that catches you no matter which branch of the "Choose Your Own Adventure" you end up on. The researchers also showed that this method is optimal, meaning it finds the fastest way to get to the goal on average, provided the probability guesses are correct.

In their experiments, the team tested StochSIPP on fifty different warehouse-like maps with moving obstacles. They compared it to other robots using different strategies. The results were impressive:

Safety: StochSIPP was 100% successful in reaching the goal without crashing, matching the safety record of the most cautious robots.
Speed: It was significantly faster than those cautious robots, arriving 7% to 31% sooner on average.
The "Gated" Test: In some scenarios, every path had a "gate" that might be locked. The cautious robots simply gave up and returned "no plan" because they couldn't be 100% sure the gate would open. StochSIPP, however, figured out a way to navigate these gates by planning for both the "open" and "locked" possibilities, successfully reaching the goal every time.

However, the paper also points out a limitation. While StochSIPP is a genius at handling a few uncertain things at once, it gets overwhelmed if there are too many. When the researchers tested it with six or more uncertain "gates" appearing at the same time, the time it took to calculate the plan grew explosively, jumping from a fraction of a second to nearly 40 seconds for just one extra uncertain gate. This suggests that while StochSIPP is a powerful tool for complex but manageable environments, it might need help (or a different approach) for situations with a massive amount of simultaneous uncertainty.

In short, StochSIPP teaches robots to be brave but smart. It shows them that they don't have to guess the future perfectly to move safely; they just need to have a backup plan for every possibility. It's the difference between a robot that freezes in fear of the unknown and one that confidently navigates the chaos, ready to pivot the moment the world changes.

Technical Summary: StochSIPP

Problem Formulation

The paper addresses the problem of safe navigation for autonomous robots in dynamic environments where obstacle motion is uncertain. Unlike traditional approaches that plan for a single nominal trajectory or react after collisions occur, StochSIPP operates under a specific input model: a predictor supplies fixed temporal safety probabilities for specific roadmap edges and vertices over time.

The core challenge is that obstacle statuses (safe or blocked) are not known globally in advance but are revealed locally as the robot executes its plan. The robot must decide on a contingent policy—a set of rules specifying which motion to execute after every possible local observation—rather than a single fixed path. The objective is to minimize the expected arrival time at the goal while guaranteeing collision-free execution, provided the underlying probabilistic model and sensing assumptions hold.

The problem generalizes the Canadian Traveler Problem (CTP) by introducing time-indexed uncertainty. Unlike static CTP, temporal uncertainty couples route choice, arrival time, waiting, and future information; reaching a vertex at different times can yield different feasible motions and observation opportunities. The authors establish that deciding the optimal expected cost for this problem is PSPACE-hard.

Methodology

StochSIPP is an exact contingent planner that combines Safe Interval Path Planning (SIPP) with bounded AND/OR search over a cached action–observation graph.

1. Macro-Action Abstraction

To avoid explicit time expansion (which would be computationally intractable), the algorithm uses SIPP to generate certified-safe macro-actions. A macro-action is a scheduled sequence of primitive motions that:

Starts at the current state.
Terminates either at the goal or at the next point where a new local observation becomes available.
Is guaranteed to be collision-free under the current information state (i.e., all intervals used are either deterministically safe or have been observed as safe).

This abstraction allows the planner to treat a sequence of primitive steps as a single decision unit, preserving the "lossless" nature of the search without expanding every timestep.

2. Finite Action–Observation Graph

The search space is modeled as a finite, acyclic graph:

OR Nodes: Represent decision states $(q, t, y)$ , where $q$ is the vertex, $t$ is the time, and $y$ is the partial assignment of observed statuses.
AND Nodes: Represent the outcomes of a macro-action. Since the robot senses new statuses upon reaching the endpoint of a macro-action, an AND node branches into all possible observation outcomes $\omega$ , weighted by their probabilities.

3. Bounded Exact Search

The algorithm employs a best-first search strategy (similar to CAO*) to find the optimal policy:

Admissible Bounds: It utilizes two SIPP-based relaxations to bound the search:
- Optimistic Bound ( $h_{opt}$ ): Assumes all uncertain intervals are safe. This provides a lower bound on the expected arrival time.
- Robust Bound ( $h_{rob}$ ): Assumes all uncertain intervals are blocked (except those with probability 1). This provides an upper bound and serves as a witness for a feasible, collision-free policy.
Pruning: Actions are pruned if their estimated cost exceeds the current best feasible upper bound ( $B(s)$ ).
Solving: A node is marked "solved" when the optimal action is identified and its value is confirmed to be equal to the lower bound, ensuring the policy is optimal for the given finite roadmap and horizon.

4. Execution

The resulting policy is executed without online replanning. The robot senses at the start, follows the arc corresponding to the observation, executes the stored macro-action schedule, senses again at the endpoint, and repeats until the goal is reached. Safety is guaranteed if the sensing is exact, the timing is followed, and the probability-one intervals are truly safe.

Key Contributions

Finite Model and Abstraction: The paper defines a finite model of independent interval-status variables and introduces a lossless SIPP macro-action abstraction. This enables exact contingent search without explicit time expansion, generalizing CTP to temporal roadmaps.
Theoretical Guarantees: The authors derive admissible SIPP lower and upper bounds, sound pruning rules, and conditions for collision-free execution. They prove that the algorithm is expected-cost optimal for the finite roadmap under independent probabilities and that the resulting policy is provably collision-free under exact sensing and timing assumptions.
Empirical Evaluation: The paper evaluates the value of contingent planning against fixed-path baselines. It demonstrates that observing uncertain gates before route selection significantly reduces arrival times compared to conservative fixed-path planners, while maintaining 100% success rates where risk-taking fixed-path planners fail.

Experimental Results

Experiments were conducted on 50 controlled warehouse-like maps and in Gazebo simulations.

Performance vs. Fixed Paths: StochSIPP matched the 100% success rate of conservative fixed-path baselines (e.g., $1.0\text{-}A^*$ ) but reduced the mean arrival time by 7% to 31% (averaging 17%).
Handling Uncertainty: In scenarios where all routes contained uncertain gates, conservative baselines often returned no plan at all. StochSIPP successfully navigated these by disambiguating gates sequentially.
Risk vs. Reward: Risk-taking baselines (e.g., $0.5\text{-}A^*$ ) achieved shorter arrival times but failed in approximately 50% of trials due to collisions or halting. StochSIPP avoided these failures while still outperforming conservative planners.
Scalability: The study revealed that the search effort grows rapidly as the number of simultaneously ambiguous statuses increases. While the algorithm solved small instances efficiently, the number of expansions and nodes grew exponentially (e.g., from 29 nodes for 2 ambiguous statuses to over 1 million for 6), highlighting the complexity of joint-outcome branching.

Significance and Claims

The paper claims that StochSIPP provides a provably safe and expected-cost optimal solution for navigation in stochastic dynamic environments where obstacle statuses are revealed locally.

Safety: The policy is guaranteed to be collision-free if the model assumptions (independent intervals, exact sensing, planned timing) are met.
Optimality: It minimizes expected arrival time within the defined roadmap and horizon, provided the input probabilities are correct and independent.
Practical Value: The experiments demonstrate that contingent planning offers a superior trade-off between safety and efficiency compared to both overly conservative fixed-path planners and risky reactive strategies.

The authors explicitly note that the guarantees are specific to the supplied finite roadmap and independent interval model. They do not claim global optimality in continuous configuration spaces, nor do they claim optimality if the input probabilities are incorrect or if statuses are correlated in ways not captured by the model. Future work is identified as extending the approach to correlated uncertainty and developing approximate methods for large joint observation spaces.