Ellipsoidal approximations of reachable sets for linear games

Verification of safety properties for continuous, discrete, and hybrid systems requires computation of the reachable sets of states for such systems. It is of great interest to develop efficient and scalable numerical algorithms for computation and representation of this reachable set. In this paper, we compute reachable sets for linear differential games, in which one player (the “control”) tries to keep the state of the system outside of a given unsafe subset of the state space; and the second player (the “disturbance”) tries to push the system into this subset. We model this unsafe set, the input set, and the disturbance set as ellipsoids, and we derive conditions under which the reachable set at each time t is an ellipsoid. We give an integral form equation whose solution represents this ellipsoid, and we present special cases in which this ellipsoid may be computed analytically. We conclude with a set of examples