SCRAMPPI: Efficient Contingency Planning for Mobile Robot Navigation via Hamilton-Jacobi Reachability
This work addresses the problem of safe contingency planning for autonomous robots, ensuring mission resilience without relaxing safety constraints.
The paper introduces SCRAMPPI, a method for mobile robot navigation that ensures a feasible contingency plan to a safe set exists from any point along the nominal trajectory. By integrating Hamilton-Jacobi reachability analysis with a sampling-based planner (MPPI), it guarantees hard safety constraints while improving sampling efficiency, demonstrated in real-time on a mobile robot in an adversarial evasion task.
Autonomous robots commonly aim to complete a nominal behavior while minimizing a cost; this leaves them vulnerable to failure or unplanned scenarios, where a backup or contingency plan to a safe set is needed to avoid a total mission failure. This is formalized as a trajectory optimization problem over the nominal cost with a safety constraint: from any point along the nominal plan, a feasible trajectory to a designated safe set must exist. Previous methods either relax this hard constraint, or use an expensive sampling-based strategy to optimize for this constraint. Instead, we formalize this requirement as a reach-avoid problem and leverage Hamilton-Jacobi (HJ) reachability analysis to certify contingency feasibility. By computing the value function of our safe-set's backward reachable set online as the environment is revealed and integrating it with a sampling based planner (MPPI) via resampling based rollouts, we guarantee satisfaction of the hard constraint while greatly increasing sampling efficiency. Finally, we present simulated and hardware experiments demonstrating our algorithm generating nominal and contingency plans in real time on a mobile robot in an adversarial evasion task.