SCRAMPPI: Efficient Contingency Planning for Mobile Robot Navigation via Hamilton-Jacobi Reachability

1. Problem Statement

Autonomous robots often operate under a "nominal" plan to reach a goal while minimizing cost. However, in dynamic or adversarial environments, robots must be prepared for mission-aborting scenarios (e.g., sensor failure, low battery, or adversarial interception).

• The Challenge: Unlike simple obstacle avoidance (stopping or local detouring), contingency planning requires the robot to maintain a guaranteed, dynamically feasible path to a specific safe set (e.g., a charging station or shelter) from every point along its nominal trajectory.
• The Difficulty: This is a "liveness" constraint, not just a safety constraint. It requires verifying that for every state $x$ on the planned path, there exists a control policy to reach a target set $S$ within a time horizon $T_c$ while avoiding obstacles $O$.
• Limitations of Existing Methods:
  • Sampling-based approaches (e.g., Contingency-MPPI): These verify feasibility by running nested planners. They suffer from an asymmetry: finding a path proves feasibility, but failing to find one does not prove infeasibility (it could just be a sampling failure). They are also computationally expensive.
  • Standard HJ Reachability: While Hamilton-Jacobi (HJ) methods provide exact certificates, they are traditionally too computationally heavy for online use and have mostly been applied to obstacle avoidance rather than reach-avoid problems with specific safe sets.

2. Methodology: SCRAMPPI

The authors propose SCRAMPPI (Safe Contingency Reach-Avoid MPPI), a framework that integrates HJ reachability analysis into the Model Predictive Path Integral (MPPI) controller.

A. Formalization as a Reach-Avoid Problem

The contingency requirement is formalized as a Reach-Avoid problem:

• Target Set ($T$): The union of all designated safe sets ($S$).
• Constraint Set ($O$): The set of obstacles (derived from the occupancy grid).
• Value Function ($V(x)$): Computed backward in time using the Hamilton-Jacobi variational inequality.
  • $V(x) \leq 0$: Indicates state $x$ is contingency-feasible (a safe path exists).
  • $V(x) > 0$: Indicates state $x$ is infeasible (no safe path exists within the horizon).
  • The gradient $\nabla V$ provides the optimal control policy to drive the system to the safe set.

B. Online Computation & Safety Margin

• GPU Acceleration: The value function is computed online over the robot's occupancy grid using a GPU-accelerated solver (based on JAX). It is only recomputed when the map changes significantly, making it efficient for real-time operation.
• Pessimistic Assumption: Unknown cells are treated as occupied. As the robot senses more, the obstacle set shrinks, and the feasible set $C = \{x | V(x) \leq 0\}$ grows monotonically.
• Safety Margin ($\delta$): To account for discretization errors and zero-order hold execution, the system enforces a stricter condition $V(x) < -\delta$ to ensure the certificate holds in the real world.

C. Integration with MPPI via Resampling

SCRAMPPI modifies the standard MPPI algorithm to enforce the hard constraint $V(x) \leq 0$ without wasting samples:

1. Multimodal Resampling-Based Rollouts (RBR): Instead of rejecting trajectories that violate the safety constraint (which wastes computation), the algorithm "rewires" unsafe samples at each timestep to the state of a surviving safe trajectory within the same homotopy group.
2. Group-Local Resampling: To prevent "mode collapse" (where all samples converge to a single easy path), resampling is restricted within groups of samples initialized from different ancillary controllers (different topological paths). This preserves diversity in exploration.
3. Control Selection Hierarchy:
   • If the MPPI weighted mean satisfies $V(x) < -\delta$, it is executed.
   • If not, the planner selects the first control from the lowest-cost trajectory that satisfies the constraint.
   • Fallback: If no safe trajectory exists, the robot immediately switches to the HJ optimal controller $u^* = \arg \min \nabla V \cdot f(x,u)$, which is guaranteed to reach the safe set.

3. Key Contributions

1. Formal Certificate: The first method to provide a mathematically exact certificate for contingency feasibility to a designated safe set, replacing probabilistic sampling checks with the sub-zero level set of the HJ value function.
2. Efficient Integration: A novel algorithm that integrates the HJ value function into MPPI using multimodal resampling, ensuring hard constraint satisfaction while maintaining high sampling efficiency and trajectory diversity.
3. Real-Time Performance: Demonstrated that HJ reachability can be computed online (approx. 43ms for a 400x160x60 grid) on a GPU, enabling real-time replanning as the environment is revealed.

4. Experimental Results

The authors evaluated SCRAMPPI in simulation (unicycle robot) and on hardware (AgileX Scout Mini) in adversarial evasion tasks.

• Success Rate & Safety:
  • SCRAMPPI: Achieved 100% success rate and 0% unsafe states across 100 random environments. It maintained valid contingency plans at all times.
  • Contingency-MPPI (C-MPPI): Even with 1,000 inner samples, it achieved only 84% success and 98.5% valid contingency rates, failing to guarantee feasibility due to sampling ambiguity.
• Efficiency:
  • Computation: SCRAMPPI's planning time was comparable to vanilla MPPI (~44ms total, including HJ recomputation). In contrast, C-MPPI-1000 took ~126ms and scaled poorly with horizon length.
  • Memory: SCRAMPPI used 33.6 MB of VRAM, whereas C-MPPI-1000 used 1159.7 MB (a 34x reduction).
• Hardware Validation: On a physical robot in an adversarial scenario, SCRAMPPI successfully navigated to a goal while maintaining a backup path to an occluded safe zone. When a contingency was triggered, the robot seamlessly switched to the HJ controller and reached the safe zone.

5. Significance

SCRAMPPI represents a significant advancement in safe autonomous navigation by bridging the gap between theoretical guarantees (HJ reachability) and practical efficiency (sampling-based control).

• Reliability: It eliminates the "false negative" problem of sampling-based methods, ensuring that if a plan is accepted, a safe recovery path definitely exists.
• Scalability: By leveraging GPU acceleration and smart resampling, it makes exact reachability analysis feasible for online mobile robot control, a task previously considered too computationally expensive.
• Adversarial Robustness: The framework is particularly suited for high-stakes scenarios (search-and-rescue, military, inspection) where mission failure due to a lack of a backup plan is unacceptable.

Limitations & Future Work: The current grid-based HJ solver scales exponentially with state dimension, limiting it to low-dimensional systems (3-4 states). Future work aims to extend this to higher dimensions using learned value function approximations (e.g., DeepReach) and to handle dynamic obstacles.