Source-linked AI summary
Symbolic models for nonlinear control systems without stability assumptions
Majid Zamani, Giordano Pola, Manuel Mazo, Paulo Tabuada
TL;DR
Existing symbolic-model techniques either apply only to restrictive system classes or require exact reachable-set computation. This paper constructs finite symbolic models for suitably restricted smooth systems, establishes approximate simulation relations, and supports controller synthesis for complex specifications.
Problem
Existing techniques are limited to restrictive control-system classes or require exact reachable-set computation, which is difficult in general.
Method
The paper constructs finite abstractions by time-discretizing δ-FC control systems restricted to compact state sets using state, input, and timing quantization parameters.
Results
For every nonlinear control system satisfying incremental forward completeness, the constructed symbolic model is alternatingly approximately simulated by, and approximately simulates, the control system.
Takeaways & Limitations
The symbolic models can support controller synthesis for complex specifications, while controller refinement transfers symbolic-model controllers to the original system.
Takeaways & Limitations
The design methodology is limited by the size of the computed abstractions, motivating ongoing work on controller-aware construction and non-uniform quantization.
Abstract
from arXiv · showhide
Finite-state models of control systems were proposed by several researchers as a convenient mechanism to synthesize controllers enforcing complex specifications. Most techniques for the construction of such symbolic models have two main drawbacks: either they can only be applied to restrictive classes of systems, or they require the exact computation of reachable sets. In this paper, we propose a new abstraction technique that is applicable to any smooth control system as long as we are only interested in its behavior in a compact set. Moreover, the exact computation of reachable sets is not required. The effectiveness of the proposed results is illustrated by synthesizing a controller to steer a vehicle.
1. Introduction
The paper develops symbolic abstractions for broader classes of control systems while avoiding exact reachable-set computation. It establishes existence and construction results under incremental forward completeness and illustrates them with vehicle-controller synthesis.
- Motivation: Existing symbolic-abstraction techniques support controller synthesis for complex specifications but often target restrictive system classes or require exact reachable sets.Finite symbolic models reduce controller synthesis to fixed-point computation over finite-state abstractions.
- Contributions: The proposed technique applies to larger classes of control systems and requires neither stability assumptions nor exact reachable-set computation.The method is contrasted with approaches restricted to particular system structures or based on incremental input-to-state stability.
- Contributions: For nonlinear control systems satisfying incremental forward completeness, the paper constructs symbolic models related to the original system through alternating and ordinary approximate simulation.The symbolic model is alternatingly approximately simulated by the control system and approximately simulates it.
- Comparison: The construction can use tighter reachable-set over-approximations, while avoiding the small sampling-time restriction associated with one related abstraction technique.The trade-off is less tight over-approximations of reachable states compared with that approach.
- Illustration: A vehicle example illustrates synthesizing a controller that reaches a target set while avoiding obstacles.The example demonstrates the proposed results on a control task with geometric constraints.
2. Control Systems and Incremental Forward Completeness
This section formalizes control systems and introduces incremental forward completeness, which bounds trajectory divergence using initial-state and input mismatches. It also relates the property to Lyapunov-like functions and continuity of the flow.
- Control-system model: A control system is modeled by a state space, input set, admissible piecewise-continuous inputs, and a continuous locally Lipschitz dynamics map.The Lipschitz condition is imposed on every compact state set uniformly over inputs.
- Control-system model: Trajectories are uniquely determined by initial conditions and inputs because the dynamics assumptions ensure existence and uniqueness.The notation ξ_x^υ(τ) denotes the state reached at time τ from x under input υ.
- Incremental forward completeness: Incremental forward completeness requires forward completeness and bounds the distance between arbitrary trajectories by initial-condition and input mismatch terms.The bound uses comparison functions β and γ belonging to class K∞ in their first argument.
- Incremental forward completeness: Incremental forward completeness implies uniform continuity of the fixed-time flow map with respect to states and input functions.The relevant topologies use the infinity norm on states, the sup norm on inputs, and the product topology.
- Incremental forward completeness: A δ-FC Lyapunov function is sufficient for a control system to be incrementally forward complete, with the associated β and γ functions obtained from the theorem.The theorem connects a Lyapunov-like certificate to the trajectory-growth property required later.
3. Symbolic Models and Approximate Equivalence Notions
The paper represents control systems and symbolic models as transition systems and uses approximate simulation relations to compare them. Alternating simulation additionally handles adversarial nondeterminism and supports controller refinement.
- System representation: A system is represented by states, inputs, a transition relation, an output set, and an output function.These components provide the common formal structure for control systems and symbolic models.
- System representation: Systems may be metric, countable, finite, deterministic, or nondeterministic according to their outputs, state sets, and successor structure.Nondeterministic systems can have multiple successors for the same state and input.
- Approximate relations: Approximate simulation relates states whose outputs differ by at most a specified precision while matching transitions across systems.The relation requires every source state to have a related target state and preserves source transitions through target transitions.
- Approximate relations: Alternating approximate simulation adds input-wise matching that quantifies over every source input and requires corresponding target behavior.This formulation explicitly captures the adversarial nature of nondeterminism.
- Controller transfer: For deterministic systems, approximate simulation and alternating approximate simulation coincide.These relations are useful because controllers designed for symbolic models can be transferred to the original control system.
4. Symbolic Models for δ-FC Control Systems
The paper constructs finite symbolic abstractions for δ-FC control systems restricted to compact state sets, without requiring exact reachable-set computation. These abstractions support approximate simulation relations and controller refinement.
- Time discretization: Time discretization samples a δ-FC control system at intervals of duration τ, with piecewise-constant input curves.The sampled system captures state evolution at times 0, τ, ..., Nτ.
- Quantized abstraction: The abstraction uses quantization parameters τ, η, µ, and θ for sampling time, state quantization, input quantization, and design precision.The construction defines a symbolic system using these parameters and the functions β and γ from the δ-FC bound.
- Existence theorem: Theorem 4.1 constructs an abstraction for any desired precision ε when µ ≤ bµ and η ≤ ε ≤ θ.The result relates δ-FC control systems to symbolic models under these parameter constraints.
- Reachability approximation: The transition relation may use over-approximations of successor sets rather than exact reachable sets.The paper states that any suitable over-approximation of Post_uq(B_ε(xq)) preserves the theorem’s conclusion.
- Finite restriction: Restricting the state space to a compact set D makes the symbolic model SqD(Σ) finite.The finite abstraction captures the behavior of the sampled system within D.
- Controller refinement: A controller synthesized for the finite model SqD(Σ) can be refined to enforce the same specification on the sampled control system.This follows from the approximate alternating simulation relation between the finite abstraction and the sampled system.
5. Example
The vehicle example applies the abstraction to navigation within a bounded state region. With ε = 0.2, the constructed symbolic model yields a controller whose closed-loop trajectory satisfies the stated specification.
- Vehicle model: The vehicle model represents the front and rear wheel pairs by one front wheel and one rear wheel.The state includes position and orientation, while velocity and steering angle are control inputs.
- System properties: The vehicle is not incrementally input-to-state stable, so the methods requiring that assumption cannot be applied.The example therefore illustrates the proposed approach beyond those stability-based results.
- Specification: The objective is to reach W = [9, 9.5] × [0, 0.5], avoid obstacles, and remain indefinitely inside W within D = [0, 10] × [0, 10] × [−π, π].The target and obstacles are indicated in Figure 1.
- Abstraction and synthesis: For ε = 0.2, the authors choose θ = 0.2, η = 0.2, and τ = 0.3 to construct SqD(Σ).The abstraction was computed using Pessoa, and standard game-theoretic algorithms found a controller enforcing the specification.
- Outcome: The closed-loop trajectory from (0.4, 0.4, 0) satisfies the navigation specification.Figure 2 shows the corresponding input-signal evolution.
6. Discussion
The paper concludes that smooth control systems restricted to compact state subsets admit finite symbolic models, while controller synthesis remains applicable to complex specifications. The discussion identifies abstraction size as the main limitation and points to ongoing remedies.
- Any smooth control system restricted to a compact state subset admits a finite symbolic model.
- The resulting symbolic models support controller synthesis for complex specifications expressed in temporal logics or automata on infinite strings.
- The current design limitation is the size of the computed abstractions.
- The authors are investigating integrated controller design and symbolic-model construction, while other work uses non-uniform quantization to address abstraction size.