Introduction
In the design of autonomous systems, the "reach-avoid" (RAC) problem is a cornerstone: how can we synthesize a controller that steers a system from an initial set of states to a target Goal while strictly avoiding unsafe regions? While Satisfiability Modulo Theories (SMT) solvers have become powerful tools for verification, their application to synthesis often faces scalability and completeness challenges, particularly when dealing with infinite time horizons.
This paper presents a novel SMT-based algorithm that automatically synthesizes controllers for piecewise linear (PWL) systems. Crucially, the algorithm doesn't just output a control law; it simultaneously generates an inductive proof of its correctness, ensuring safety and reachability for an infinite time horizon.
The Limitations of Horizon Unrolling
Traditional SMT-based synthesis methods often rely on "unrolling" system dynamics over a fixed time horizon $k$. This approach suffers from two primary drawbacks:
- Conservatism and False Negatives: Over-approximating dynamics over multiple steps can lead to "blurry" reachable sets, causing the solver to incorrectly conclude that no solution exists (false negatives).
- Lack of Generalization: A sequence of inputs valid for $k$ steps offers no formal guarantee that the system will remain safe or eventually reach the goal beyond that specific window.
Proposed Method: Proof-Carrying Synthesis
The core innovation lies in searching for three interconnected components simultaneously:
- The Control Law ($u$): A mapping from state regions to specific control inputs.
- An Inductive Invariant ($Inv$): A subset of the safe region that the system is guaranteed never to leave once entered.
- A Ranking Function ($V$): A Lyapunov-like function that proves progress toward the goal, preventing the system from entering infinite loops.
The "Must" and "May" Abstraction
To manage the complexity of the reachable state space, the authors employ an iterative abstraction-refinement loop based on two sets of rules:
- Strengthened Rules (May): These use under-approximations of the dynamics. A solution found here is guaranteed to be valid for the actual system.
- Weakened Rules (Must): These use over-approximations. If the solver finds these rules unsatisfiable, it provides a formal proof that no controller of the specified template can exist.
If the solver is inconclusive, the algorithm refines the state-space partitions into smaller cells and re-evaluates, bridging the gap between the "Must" and "May" bounds.
Evaluation: Vehicle Navigation
The algorithm was evaluated on a vehicle navigation problem using a piecewise linear approximation of Dubin’s car dynamics. The state space, including position, velocity, and heading, was partitioned into 768 cells.
Key Results
The prototype implementation, utilizing the CVC4 SMT solver, successfully synthesized controllers for the 4D navigation task. The encoding involved approximately 7,000 constraints and was solved in roughly 10 minutes.
The algorithm's ability to provide a "proof-carrying" controller is a significant step forward for safety-critical applications. By framing the problem within a "robust" RAC context, the authors prove that their method is relatively complete—it will eventually find a solution or prove non-existence for any robust problem instance.
Conclusion and Future Work
This SMT-based framework effectively bridges the gap between formal verification and control synthesis for PWL systems. By avoiding the pitfalls of horizon unrolling and providing formal certificates of correctness, it offers a rigorous path for autonomous system design. Future work aims to scale the approach to higher-dimensional systems and extend the framework to handle fully nonlinear dynamics by decoupling reachability analysis from the synthesis logic.
Summary updated