Safe and Dynamically-Feasible Motion Planning Using Control Lyapunov and Barrier Functions
Pol Mestres, Carlos Nieto-Granda, Jorge Cortes
AI summary
Problem
Existing sampling-based planners often generate waypoints that low-level CLF-CBF controllers cannot safely track, while methods that ensure compatibility typically rely on computationally expensive trajectory simulations or boundary value problem solvers that compromise efficiency and formal safety guarantees.
Approach
The authors propose C-CLF-CBF-RRT, which verifies CLF-CBF compatibility at each planning step using tractable optimization to ensure generated paths can be robustly executed by a safe controller, completely bypassing trajectory simulation and boundary value problem solvers.
Key results
- Formulation of CLF-CBF compatibility verification as a tractable optimization problem
- Reduction to quadratically constrained quadratic programming for linear systems with polytopic or ellipsoidal obstacles
- Formal proof of probabilistic completeness for the C-CLF-CBF-RRT algorithm
- Validation in simulation and hardware showing safe, stable execution with improved average runtime
Why it matters
Provides a computationally efficient and formally safe bridge between high-level sampling planners and low-level safety controllers for deployment in safety-critical robotic systems.
Abstract
This article considers the problem of designing mo- tion planning algorithms for control-affine systems that generate collision-free paths from an initial to a final destination and can be executed using safe and dynamically feasible controllers. We introduce the compatible control lyapunov function control barrier function rapidly exploring random tree (C-CLF-CBF-RRT) al- gorithm, which produces paths with such properties and leverages rapidly exploring random trees (RRTs), control Lyapunov func- tions (CLFs), and control barrier functions (CBFs). For linear sys- tems with polytopic and ellipsoidal constraints, C-CLF-CBF-RRT requires solving a quadratically constrained quadratic program at every iteration of the algorithm, which can be done efficiently. We prove the probabilistic completeness of C-CLF-CBF-RRT and showcaseitsperformanceinsimulationandhardwareexperiments.