PaperlayerView exact revision on arXiv

Source-linked AI summary

Online, Reachability-Aware, Sampling-Based Motion Planning

Brendan Gould, Zhiyuan Zhang, Panagiotis Tsiotras, Samuel Coogan

arXiv:2609.09073v1cs.ROcs.SYeess.SY

TL;DR

Sampling-based MPC is flexible, but standard approaches lack deterministic safety guarantees for safety-critical navigation. This work computes interval-based reachable-set overapproximations online; it reduced simulation crash frequency by over 99.1% under the stated exclusion and completed 35 hardware laps without collision.

  • Problem

    Standard sampling-based MPC lacks safety constraints, and approaches that mitigate failure probability do not provide deterministic safety guarantees for safety-critical systems.

    Source: §I · p. 1

  • Method

    The controller computes guaranteed reachable-set overapproximations online using fast interval-based reachability.

    Source: §I · p. 1, §V · p. 7

  • Results

    Excluding unrecoverable initializations, reachability reduced crash frequency by over 99.1%; against, it achieved the same safety criteria at 0.98 m/s, a 6% speed penalty from 1.04 m/s.

    Source: B. Simulations · p. 6, C. Comparison · p. 6

  • Takeaways & Limitations

    The hardware experiment completed 35 consecutive laps without collision, supporting the controller’s applicability to the real world.

    Source: D. Experiment · p. 7

    Finite sampling and conservative over-approximation can leave the controller without a certified safe sequence, and the receding-horizon method lacks recursive feasibility beyond its prediction horizon.

    Source: D. Limitations · p. 4

Abstract

from arXiv · show

Sampling-Based Model-Predictive Control (MPC) algorithms are a flexible class of controllers used for navigation on a wide range of robotic systems. Historically, such approaches have lacked hard safety guarantees, a shortcoming which we remedy in this work by computing guaranteed reachable-set overapproximations online with a fast, interval-based pipeline. We show that our method achieves similar performance to a state-of-the-art reachability-based planner without the need for the expensive pre-computation step, and can be scaled to systems that are infeasible using existing approaches. Finally, we demonstrate that our technique reduces safety violations by over 99% in a racing simulation and successfully controls a model racecar on real hardware experiments without crashes.

I. INTRODUCTION

The introduction motivates safety guarantees for flexible sampling-based MPC, then presents online interval-based reachability as a way to provide them without expensive precomputation. The problem statement formalizes safety under bounded disturbances and the choice of desirable controls among safe ones.

I. INTRODUCTION

  • Standard MPPI lacks safety constraints, while cost penalties and sampling-distribution changes mitigate failure probability without deterministic guarantees.Safety filters are another approach, but designing control barrier functions for practical systems can be non-obvious and interventions can affect performance counter-intuitively.Source: §I · p. 1
  • Prior HJ reachability guarantees safety under bounded disturbances, but requires a precomputed value function on a state-space grid and assumes the system and environment are known.The PDE precomputation becomes infeasible as state dimension grows.Source: §I · p. 1
  • The proposed controller uses fast interval-based reachability online to provide a guarantee similar to without expensive precomputation.The paper also proposes a reachable-set-aware sampling controller and reports similar results to without precomputation.Source: §I · p. 1

A. Notation

  • The notation defines intervals using an element-wise partial order, applies min and max component-wise, and distinguishes continuous- and discrete-time signals.For a continuous-time function, p(·) denotes the whole function and p(c) its value; square brackets denote discrete-time signals.Source: A. Notation · pp. 1–2

II. PROBLEM STATEMENT

  • Problem 1 seeks a control that keeps trajectories in the safe set for T under every bounded disturbance, or verifies that no such control exists.The safety function h defines the safe states; for collision avoidance, h(x) ≥ 0 denotes no collision.Source: §II · p. 2
  • Problem 2 selects an optimal control from the safe controls using a cost functional to express which states and actions are desirable.Source: §II · p. 2

III. METHODOLOGY

The methodology section moves from the established reachability technique to a sampling-based planner, then combines them in a controller with a safety guarantee and discusses remaining challenges.

III-A

  • Section III-A summarizes the established reachability technique used in the work.Source: §III · p. 2

III-B

  • Section III-B introduces a sampling-based motion planner.Source: §III · p. 2

III-C

  • Section III-C combines the preceding ideas in the proposed controller, Algorithm 2, and its safety guarantee, Theorem 1.Source: §III · p. 2

III-D

  • Section III-D describes remaining opportunities for addressing Problems 1–2.Source: §III · p. 2

A. Interval Reachability

The method uses interval arithmetic and an embedding system to compute efficient, conservative overapproximations of reachable trajectories under bounded disturbances. Its interval trajectories are guaranteed to contain the original system’s trajectories.

A. Interval Reachability

  • Inclusion functions bound dynamics over state intervals, but may be conservative and are not unique.They need only contain the dynamics’ outputs for inputs in the specified intervals.Source: A. Interval Reachability · p. 2
  • Checking expansion on interval faces reduces conservatism compared with bounding dynamics over the entire state interval.A trajectory leaving an interval must first pass through one of its faces.Source: A. Interval Reachability · pp. 2–3
  • Embedding-system trajectories form time-varying interval sets that contain original-system trajectories under bounded disturbances.Their bounds can be computed at approximately 2× the cost of an original-system trajectory.Source: A. Interval Reachability · pp. 2–3
  • The embedding system’s inclusion function can be computed automatically by immrax for dynamics composed from its primitive mathematical operations.The paper applies immrax to a 6D dynamic bicycle model and describes heuristics for operations that are expensive to extend to intervals.Source: A. Interval Reachability · p. 3

B. Trajectory-Based Motion Planning

The planner uses a receding-horizon sampling loop to evaluate candidate control sequences through nominal trajectories. It rejects predicted unsafe trajectories, scores the remaining candidates, and warm-starts the next loop from the selected control.

B. Trajectory-Based Motion Planning

  • At each planning step, the method samples candidate controls from a Gaussian centered on a reference sequence and uses piecewise-constant policies over a uniform time grid.The horizon is T = M∆ut for M segments of duration ∆ut.Source: B. Trajectory-Based Motion Planning · p. 3
  • Candidate controls are rolled out with zero disturbance; predicted unsafe trajectories are checked, and the remaining trajectories are evaluated by the cost functional.Controls are smoothed and clipped for low-level tracking.Source: B. Trajectory-Based Motion Planning · p. 3
  • The selected control’s differences are saved as the reference for warm-starting the next control loop.The approach follows a receding-horizon, sampling-based paradigm inspired by prior work,,.Source: B. Trajectory-Based Motion Planning · p. 3

C. Reachability-Aware Motion Planning

The reachability-aware planner replaces nominal rollouts with embedding-system trajectories that overapproximate states under bounded disturbances. It selects among sampled controls only after checking their robust safety, while interval trajectories also support cost evaluation.

C. Reachability-Aware Motion Planning

  • The planner uses embedding-system trajectories for sampled controls to overapproximate reachable states under disturbances and check robust safety.This replaces the nominal-trajectory safety check, which considers only the disturbance-free trajectory.Source: C. Reachability-Aware Motion Planning · p. 3
  • Theorem 1 guarantees that a verified safe control can be applied without a disturbance causing a safety violation.This permits selecting the best sampled signal that is safe, rather than averaging over disturbances as in MPPI.Source: C. Reachability-Aware Motion Planning · p. 4
  • The reachable-set planner is formed by substituting reachable-set safety and cost criteria into the sampling planner.The resulting logic is given in Algorithm 2.Source: C. Reachability-Aware Motion Planning · p. 4
  • The immrax implementation uses GPU parallelization to process sampled control sequences simultaneously for real-time performance.The remark identifies modern GPU parallelization as critical to Algorithm 2’s real-time performance.Source: C. Reachability-Aware Motion Planning · p. 4
  • The hardware experiments use precise OptiTrack state measurements; observation error could instead be represented by initializing the embedding system with an interval.That interval would contain the true state with high confidence.Source: C. Reachability-Aware Motion Planning · p. 4

D. Limitations

The safety guarantee is limited by finite sampling, the receding horizon, numerical integration and timestep discretization, and the assumed disturbance model.

D. Limitations

  • Finite sampling and conservative reachable-set overapproximation can leave the planner without a proven-safe control even when one exists.The receding-horizon method also lacks a recursive-feasibility guarantee for states whose safety violations occur after horizon T.Source: D. Limitations · p. 4
  • Poor numerical integration can hide unsafe trajectories, while coarse timestep discretization can miss brief unsafe periods.In that case, an unsafe trajectory might be falsely considered safe.Source: D. Limitations · p. 4
  • The safety set may be inaccurate if actual disturbances exceed their modeled bounds or affect the dynamics differently than assumed.The method requires a reasonable disturbance bound and model of how disturbances enter the dynamics.Source: D. Limitations · p. 4

IV. NUMERICAL SIMULATIONS AND EXPERIMENTS

The section evaluates Algorithm 2 in simulation and on real-world hardware, moving from vehicle dynamics and planning objectives to benchmarking and a physical racecar demonstration.

  • The evaluation covers vehicle dynamics and planning objectives, simulation benchmarks and robustness, comparison with a state-of-the-art reachability-aware planner, and a physical 1/28th-scale racecar demonstration.Source: §IV · p. 4

A. Vehicle Dynamics and Objective

The test system uses a dynamic bicycle model with bounded disturbances, and evaluates safety and performance in Frenet coordinates relative to a reference raceline. Planning assumes access to track geometry over the prediction horizon.

  • The racecar is modeled with dynamic bicycle states, steering and acceleration inputs, and Pacejka tire-slip forces.Source: A. Vehicle Dynamics and Objective · p. 5
  • Bounded adversarial disturbances represent uncertainty in lateral velocity and heading, while a kinematic bicycle model replaces the dynamic model below a longitudinal-speed threshold to avoid singular slip-force calculations.Source: A. Vehicle Dynamics and Objective · p. 5
  • Safety and performance are expressed in Frenet coordinates, with running costs favoring raceline tracking and progress and a terminal cost rewarding progress along the track.Source: A. Vehicle Dynamics and Objective · p. 5
  • The planner assumes access to the approaching raceline, track boundaries, and desired speed over the horizon; experiments use fixed environments where this information is readily available.Source: A. Vehicle Dynamics and Objective · p. 5
  • For interval states, the implementation approximates track-geometry conversion by checking trajectories from the four position-plane vertices and collecting their results.The authors report this as a computational-speed choice and say that collision-free vertex trajectories strongly indicate the safety check will pass.Source: A. Vehicle Dynamics and Objective · p. 6

B. Simulations

In simulation, the reachability-aware controller substantially reduced crashes relative to the trajectory-only baseline and was more robust to disturbance and cost-weight variation. Most remaining crashes occurred in initial states where no safe control was sampled.

  • The comparison used 540 runs per controller across 30 initial states, 9 cost-weight combinations, and 2 disturbance signals, with early termination for crashes or stalls.Source: B. Simulations · p. 6
  • 141 baseline crashes fell to 26 with reachability; excluding 25 crashes from precarious starts with no sampled safe control, crash frequency fell by over 99.1%.The authors suspect the remaining crash was caused by failure to guarantee recursive feasibility.Source: B. Simulations · p. 6
  • Algorithm 2's success rate was largely independent of disturbance realization and cost weights, and its disturbance-robust safety considerations coincided with universally faster lap times.Source: B. Simulations · p. 6

C. Comparison

Against the state-of-the-art reachability-enabled planner, the method maintained the same collision-prevention criterion with a reported speed penalty, while avoiding expensive value-function precomputation. The prior approach's overhead made application to the paper's 6D vehicle model difficult.

  • The comparison reports similar performance and safety without precomputation, with the proposed method scalable to larger system dimensions.Source: C. Comparison · p. 6
  • The method prevented all collisions in the replicated racecar task and averaged 0.98 m/s versus the baseline's 1.04 m/s, a 6% speed penalty.The HJ planner's value function filters rollouts for sample efficiency, but requires dense-grid computation and storage.Source: C. Comparison · p. 6
  • The prior HJ method's precomputation took over 115 hours and used 2.4 GB for the 6D vehicle; coarse-grid interpolation imprecision led its controller to crash before finishing the three-lap trial.Source: C. Comparison · p. 6

D. Experiment

The hardware experiment ran Algorithm 2 at nearly 60 Hz and completed over 35 consecutive laps without collision. The conclusion presents online interval reachable sets as a way to guarantee safety over a receding horizon.

D. Experiment

  • The controller sampled 1,024 control signals and predicted 30 integration steps of 0.02 seconds per sample each control loop.Experiments used the palm-sized Buzzracer platform, with inputs broadcast over a local area network.Source: D. Experiment · p. 6
  • Table I summarizes a 1,080-run sweep by sweep variable and reachable-set-filter setting, reporting race completions and mean lap times for successful runs.Overall cells aggregate 540 runs; cells for disturbance direction, centering weight, and velocity scale aggregate 270, 180, and 180 runs, respectively.Source: Table I · p. 7
  • Over 35 consecutive laps were completed without collision on the real vehicle, with the control loop running at nearly 60 Hz.The authors say these results validate the disturbance structure and Algorithm 2 for real-world use.Source: D. Experiment · pp. 6–7

V. CONCLUSION

  • The conclusion describes fast, interval-based online reachable sets as enabling safety guarantees over a receding horizon for sampling-based MPC.Future work could add a backup policy for cases where no certifiably safe control is sampled, or address dynamic environments and adaptive control.Source: §V · p. 7
Loading 2609.09073v1…