Geometric and Algorithmic Techniques for Design and Verification of Hybrid Control Systems
Michael S. Branicky, Steven M. LaValle · 2005
ion methods An approach that has proven significant in analyzing complicated systems is to collapse large systems into smaller ones, by abstracting away some of the details. The use of abstraction makes it possible to ignore inessential system behavior and use nondeterministic models for the system’s dynamics; this enables reasoning about the global system behavior. Central to this approach is the notion of simulation relations, by which the abstracted system is said to be a simulation of the original system if it can reproduce all of its behaviors. Various abstraction techniques, all of whose soundness is based on the theory of abstract interpretation [39], have been found useful for verifying discrete state systems. Some representative examples of abstraction techniques for finite-state systems include the cone of influence reduction, data abstraction, and predicate abstraction methods. The cone of influence reduction [36, 37] attempts to decrease the size of the system under consideration by focusing on the variables of the system that appear in the specification. Data abstraction [42] involves mapping the actual data values in the system to a small set of abstract data values, thereby reducing the number of different cases to consider in verification. Finally, in predicate abstraction [57] states are grouped according to the collection of the fixed, finite set of predicates they satisfy, and then a small quotient automaton is automatically constructed of a possibly-infinite state system. The extension of such methodologies to infinite-state systems often relies on the concept of bisimulation, which is a finite-state Quotient Transition System that is equivalent to the original system for the purposes of verification. In other words, the whole state space is partitioned into classes of states that are equivalent for the problem at hand. To find a bisimulation, a finite partition of the state space is constructed and subsequently refined until its equivalence with the original system is established. However, this procedure is guaranteed to terminate only for very limited classes of hybrid systems, for which reachability problems are proven decidable [61, 96]. Approximate quotient transition systems have been introduced to allow the analysis and verification of more general systems [35]. Even though the worst-case complexity of such approaches is typically disappointing, it may be possible to identify classes of practical systems which are amenable to algorithmic analysis. Other successful techniques for analyzing hybrid systems are not based on constructing a finite quotient transition system, but rather rely on the propagation of constraints that encode conservative approximations of reachable sets. These constraints are usually linear or quadratic, resulting in polyhedral [3, 41, 60, 63] or ellipsoidal [14, 69] reachable sets. In general, such techniques only provide semi-decidable procedures for reachability. In other words, if the given set of states is reachable, then the algorithm will terminate with the right answer; otherwise, it might fail to terminate. These procedures are semi-decidable, not because the underlying reachability problem is necessarily undecidable, but because of the way they try to solve the problem. Hence, it is possible that the analysis methods may fail to terminate, even though the reachability problem itself is decidable. Compositional reasoning In compositional reasoning, one decomposes the overall problem of verification of a complex system into a sequence of smaller problems, aiming at the analysis of the properties of sub-components of the system. The properties of the system as a whole are then inferred through a composition of these “local” properties. For example, hierarchical or modular decompositions are attractive from a conceptual point of view, and provide the means for simplifying the control synthesis problem for very complex systems. As a matter of fact, systems based on such decomposition have been developed, and in general perform satisfactorily, even though guarantees on their behavior are not available. Correspondingly, a hierarchical or modular approach in the verification process is attractive, since it allows the