⚡ electrical engineering

Provably Safe Motion Planning Under Unknown Disturbances

This paper presents a provably safe, probabilistically complete sampling-based motion planning algorithm for robotic systems with unknown disturbance distributions that utilizes data-driven Wasserstein ambiguity tubes and a bandit-based validity checker to efficiently generate safe trajectories in cluttered environments while minimizing conservatism.

Original authors: Ibon Gracia, Qi Heng Ho, Luca Laurenti, Morteza Lahijanian

Published 2026-05-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ibon Gracia, Qi Heng Ho, Luca Laurenti, Morteza Lahijanian

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

The Big Picture: Planning a Path in the Fog

Imagine you are trying to guide a robot through a crowded room filled with furniture (obstacles) to reach a specific spot (the goal). In a perfect world, you would know exactly how the robot moves. But in reality, the robot is like a drunk sailor: it gets pushed around by unpredictable gusts of wind (unknown disturbances) and its motors aren't perfect.

The problem is that we don't know exactly how strong the wind is or what pattern it follows. We only have a logbook of where the robot went in the past.

The Goal: Create a plan that guarantees the robot won't crash, even if the wind behaves in the worst possible way, without needing to know the exact rules of the wind.

The Core Innovation: The "Wasserstein Ambiguity Tube"

The authors invented a clever way to handle this uncertainty. Instead of guessing the wind's pattern, they use the robot's past logs to draw a "safety tube" around the robot's path.

Think of this Ambiguity Tube like a protective bubble or a hula hoop that surrounds the robot's expected path.

The Bubble: It's not a single line; it's a thick, fuzzy tube.
The Guarantee: The authors mathematically prove that if the robot stays inside this tube, it is safe.
The Magic: They don't assume the wind is "Gaussian" (a standard bell curve) or "bounded" (staying within a fixed box). They let the data from the robot's past trips define the shape and size of the tube. If the robot usually drifts left, the tube gets bigger on the left.

How They Make It Practical (The "Sawtooth" Trick)

Building a perfect, tight bubble for every single moment in time is computationally expensive, like trying to draw a new, perfect bubble for every inch the robot moves.

The authors realized they don't need a new bubble for every second.

The Strategy: They build a few "anchor bubbles" at specific times (like checkpoints on a race track).
The Inference: For the times in between, they use the robot's physics (how it moves) to mathematically "stretch" the bubble from the last checkpoint.
The Result: This creates a "sawtooth" pattern (like the teeth of a saw) where the tube is tight at the checkpoints and slightly wider in between, but always safe. This saves a massive amount of computer power.

The "Lazy" vs. "Bandit" Checkers

Once they have the tube, they need to check if a proposed path is safe. They developed three ways to do this, like different security guards checking a visitor:

The Strict Guard (Exact Check): This guard measures every single atom of the robot's potential path against the obstacles. It's 100% accurate but very slow.
The Lazy Guard (Fast Check): This guard just looks at the general shape. "If the whole bubble fits in the hallway, you're good." It's super fast but sometimes says "No" to paths that are actually safe (too conservative).
The Bandit Guard (The Smart Hybrid): This is the paper's star invention. It acts like a slot machine or a smart traffic light.
- It starts with the Lazy Guard. If the path looks obviously safe, it lets the robot through instantly.
- If the path looks risky (close to a wall), it flips a coin (based on a smart algorithm) to decide whether to call in the Strict Guard for a detailed check.
- Why it's cool: It learns as it goes. If a certain area of the room is usually tricky, it starts calling the Strict Guard more often there. If an area is easy, it sticks to the Lazy Guard. This makes the planning incredibly fast without sacrificing safety.

The "Dimension Reduction" Trick

The paper also tackles a problem where robots have many moving parts (like a drone with position, speed, angle, etc.). Checking safety for all 8 dimensions at once is like trying to solve a puzzle with 1,000 pieces.

The authors realized that for avoiding walls, you only really care about the robot's position (2 dimensions), not its speed or angle.

The Analogy: Imagine checking if a car will hit a wall. You only need to look at the car's front bumper (2D), not the color of the paint or the temperature of the engine (other dimensions).
The Solution: They project the complex, high-dimensional problem down into simple, low-dimensional tubes. This makes the math much faster and allows the robot to plan in complex environments without getting overwhelmed.

The Results: What They Found

The authors tested their method (called WDR-X) against other state-of-the-art methods in simulated environments:

Cluttered Rooms: In rooms packed with obstacles, their method found paths that others missed because the others were too scared (conservative) to enter narrow gaps.
Unknown Wind: When the wind didn't follow a standard pattern (non-Gaussian), their method still worked perfectly, while other methods failed because they relied on wrong assumptions about the wind.
Speed: Thanks to the "Bandit" checker and the "Dimension Reduction," their method was often 1.5 to 3 times faster than the next best method, especially in difficult scenarios.

Summary

This paper gives robots a new way to "drive" through the unknown. Instead of guessing the rules of the road, they use past experience to draw a safe, mathematical "bubble" around the path. They use a smart, adaptive system to check if that bubble fits through the cracks, allowing robots to move faster and safer in messy, unpredictable real-world environments.

Problem Statement
This paper addresses the challenge of motion planning for robotic systems subject to random disturbances with unknown distributions. Traditional sampling-based planners often assume deterministic models or rely on strong distributional assumptions (e.g., Gaussian noise) and bounded disturbance models. These approaches frequently result in overly conservative plans that fail in cluttered environments or require unrealistic knowledge of the disturbance distribution. The authors formulate the problem as generating a motion plan for linear (or feedback-linearizable) systems that satisfies chance constraints for collision avoidance and goal reachability with high confidence, despite the distributions of the initial state and process noise being unknown. The system must operate within state and control constraints in workspaces containing arbitrary-shaped obstacles.

Methodology
The proposed approach, termed WDR-X (Wasserstein Distributionally Robust-X), is a sampling-based motion planning framework that integrates data-driven uncertainty quantification with tree-based search. The methodology proceeds in two main phases:

Ambiguity Tube Construction (Offline):
Instead of assuming a specific noise distribution, the algorithm learns a Wasserstein ambiguity tube from a set of $N$ i.i.d. trajectory samples. This tube is a sequence of ambiguity sets (Wasserstein balls) that, with a user-defined confidence level, contains the true state distribution at every time step.
- Error Dynamics: The authors decouple the planning problem from the uncertainty propagation by analyzing the error dynamics relative to a reference trajectory. They prove that the ambiguity set for the state can be derived from the ambiguity set of the error and the reference state.
- Infinite Horizon: Unlike previous methods where ambiguity bounds grow unboundedly over time, this approach constructs a tube of infinite temporal length with finite confidence. It achieves this by learning data-driven ambiguity sets at specific time steps and deriving the sets for intermediate steps using system dynamics, resulting in a "sawtooth" radius profile that remains bounded.
- Lower-Dimensional Decomposition: To address the curse of dimensionality, the framework leverages lower-dimensional ambiguity tubes. By projecting the state distribution onto subspaces relevant to specific constraints (e.g., workspace position for obstacles, control effort for limits), the method significantly reduces sample complexity and computational cost while maintaining safety guarantees.
Probabilistically Complete Planning (Online):
The planner grows a sampling-based tree (e.g., RRT) over the nominal (deterministic) reference trajectories.
- Validity Checking: At each node, the algorithm checks if the state satisfies the chance constraints. This is done by evaluating the worst-case collision probability over the learned ambiguity set.
- Efficient Checkers: The paper introduces three validity-checking strategies:
  - Exact Checker: An optimization-free algorithm based on probability mass transport that computes the exact worst-case collision probability for discrete distributions.
  - Lazy Checker: A faster, more conservative method using pre-computed confidence tubes (balls) that avoids detailed mass transport calculations.
  - Bandit-Based Checker: A hybrid approach that adaptively selects between the exact and lazy checkers using a multi-armed bandit framework. This balances efficiency and conservatism, particularly in complex environments like narrow passages.

Key Contributions
The paper makes the following specific contributions:

Algorithm: A sampling-based motion planning algorithm for linear systems with unknown additive disturbances that utilizes trajectory observation data.
Theoretical Guarantees: Proofs of soundness and probabilistic completeness for the planner under relaxed assumptions regarding disturbance distributions.
Ambiguity Propagation: New theoretical results on the propagation of distributional ambiguity, specifically showing that ambiguity propagation decouples from planning for linear systems, allowing for a single offline-learned tube.
Tighter Bounds: A tighter characterization of the size of data-driven ambiguity sets defined by the 1-Wasserstein distance compared to existing literature, utilizing one-sided McDiarmid inequalities and moment information.
Validity Checking: Three validity-checking methods that trade off efficiency and conservativeness, all less conservative than existing work, unified by a multi-armed bandit scheme that adaptively selects the appropriate checker.
Dimensionality Reduction: A formalization of using multiple lower-dimensional ambiguity tubes to reduce data and computational requirements without sacrificing safety.

Experimental Results
The authors evaluated the approach on two systems: a 4-D linear system and an 8-D drone system navigating 2D workspaces.

Baselines: The method was compared against moment-based distributionally robust approaches (TS and Risk-Assigned) and other Wasserstein-based variants (Particle, Confidence, Hybrid).
Performance:
- In cluttered and narrow-passage environments, the proposed Bandit-WDR-RRT significantly outperformed moment-based baselines, which failed to find paths due to excessive conservatism. For instance, in a narrow passage with non-Gaussian noise, the baselines achieved 0–9% success rates, while Bandit-WDR-RRT achieved up to 100%.
- The Bandit-based checker demonstrated the best balance, matching or exceeding the success rates of other variants while being 1.5–3 times faster than the Hybrid approach.
- The lower-dimensional approach successfully enabled planning for the 8-D drone system by learning separate tubes for position and control constraints, demonstrating scalability.
Safety: Monte Carlo simulations confirmed that the generated plans achieved 99–100% success rates in avoiding collisions, validating the soundness of the ambiguity tube constraints.

Significance
The paper claims that its primary significance lies in providing a provably safe and scalable motion planning framework for systems with unknown disturbance distributions. By leveraging Wasserstein ambiguity sets and data-driven learning, the approach avoids the geometric over-approximations inherent in moment-based methods and the distributional assumptions of Gaussian-based methods. The ability to handle arbitrary-shaped obstacles and non-convex constraints without sacrificing probabilistic completeness makes the method suitable for complex, real-world robotic applications where safety is critical and disturbance models are uncertain. The introduction of the bandit-based validity checker further enhances practical utility by dynamically managing the trade-off between computational speed and solution conservatism.