Research by Jacob Siefert, Ph.D. Student:

Reachable and invariant sets are used to evaluate system performance and ensure constraint satisfaction in safety-critical applications while accounting for the effects of input, disturbance, and parameter uncertainties. For discrete-time systems, reachable sets are calculated by recursion over successor sets. For nonlinear systems, the complexity and nonconvexity of successor sets limit the scalability of existing approaches.

To improve scalability of calculating successor sets for nonlinear systems, this approach builds on our previous method for hybrid systems that leveraged hybrid zonotopes and a novel construct called a state-update set. Hybrid zonotopes can represent nonconvex, potentially disjoint sets efficiently by representing the union of an exponential number of convex sets using only a linear number of variables. Hybrid zonotopes are closed and have efficient identities for fundamental set operations including linear transformations, generalized intersections and Minkowski summations. A state-update set encodes all possible state transitions of a dynamic system. Using the state-update set, our work has developed a successor set identity using set operations that are efficient for hybrid zonotopes. The successor set identity and a visual representation of the identity is shown in Fig. 1. An extension to nonlinear systems is achieved by using an over-approximation of the nonlinear state-update set represented using a hybrid zonotope. In doing so, over-approximations of reachable sets are generated with linear memory complexity growth and computational complexity that scales linearly with the number of states.

To generate an over-approximation of the nonlinear state-update set, theoretical techniques to approximate nonlinear functions using Special Ordered-Set (SOS) approximations and bounds on SOS approximation error are leveraged. Our approach then efficiently converts SOS approximations into a hybrid zonotope. Fig. 2 shows a sinusoid (green), an SOS-approximation (red), and an over-approximation of the sinusoid (blue) represented as a hybrid zonotope.

Fig. 3 shows reachable sets generated for pendulum-like dynamics in closed loop with a saturated feedback controller. Exact trajectories from randomly sampled initial conditions (green) are also plotted. As the reachable set is never significantly removed from sampled trajectories, it is shown that the over-approximation captures the nonlinear dynamics well, without excessive conservatism.

Research by Jacob Siefert, Ph.D. Student:

Reachable and invariant sets are used to evaluate system performance and ensure constraint satisfaction in safety-critical applications while accounting for the effects of input, disturbance, and parameter uncertainties. For discrete-time systems, reachable sets are calculated by recursion of precursor and successor sets.

Problem: For hybrid systems with continuous and discrete dynamics, the complexity and non-convexity of precursor and successor sets limit the scalability of existing approaches. This is demonstrated using a numerical example for a piecewise affine system with only two regions separated by a so-called guard. Using convex approaches at each time step, reachable sets are partitioned along the guard and the appropriate affine dynamics are applied to each region. The guard and reachable sets are plotted in Fig. 1 starting from the set X_o. The number of convex sets for each time step is plotted in Fig. 2. The process of partitioning set results in more than 100 convex sets in only 10 time steps. In general, this process may result in the number of convex growing exponentially with time, significantly limiting the number of time steps over which analysis can be performed.

Method: To improve scalability of calculating successor and precursor sets, our approach combines a novel set representation called the hybrid zonotope with a novel construct called a state-update set. Hybrid zonotopes can represent nonconvex, potentially disjoint sets efficiently by representing the union of an exponential number of convex sets using only a linear number of variables. Hybrid zonotopes are closed and have efficient identities for fundamental set operations including linear transformations, generalized intersections and Minkowski summations. A state-update set encodes all possible state transitions of a dynamic system. Using the state-update set, our work has developed successor and precursor sets identities using set operations that are efficient for hybrid zonotopes. The successor set identity and a visual representation of the identity are shown in Fig. 3.

Results: Numerical results demonstrated the improved scalability of the approach over the state-of-the-art, reducing the memory complexity growth from exponential to linear. One numerical result compared the proposed approach and the state-of the-art for a room heating example with six rooms and two heaters. The room layout, heater on/off logic, and 50 backwards reachable sets from R₅₀ are shown in Fig. 4. The proposed approach took 0.34 seconds to calculate while the state-of-the-art took over 202 seconds, resulting in the proposed approach being nearly 600 times faster. The proposed approach also resulted in a memory complexity 1/60th that of the state-of-the-art.