Smart abstraction based on iterative ellipsoidal covering

Jungers, Raphaël M. [UCL] Calbert, Julien [UCL] Neves Egidio, Lucas [UCL] et al.

Classic abstraction-based techniques consist of discretizing both the input space and the state space and in general, this discretization is done with hyperrectangles. One problem with discretizing the input space is that one needs a growth-bound on the error between the actual state and the quantized state which is used to take into account the discretization error. This yields an over-approximation of the image set of a cell, which increases the level of nondeterminism in the symbolic system. Instead, we propose to build an abstraction based on an ellipsoidal covering of the state space, a finite set of local affine controllers, and a lazy/iterative construction of the abstraction. One benefit of this approach is the fact that the state and input spaces need not be discretized and the symbolic-input space is reduced to a finite set of controllers. Moreover, when ellipsoidal cells and affine controllers are considered, it is possible to compute an optimal controller via the solution of a semi-definite program (SDP). Another advantage is that the covering is computed smartly and even designed with the help of classic controller design techniques, unlike classical ones, which use an a priori defined, suboptimal, and prone to the curse of dimensionality, grinding approach.