Computation of discrete abstractions of arbitrary memory span for nonlinear sampled systems

Gunther Reißig.
Computation of discrete abstractions of arbitrary memory span for nonlinear sampled systems.
Proc. 12th Intl. Conf. Hybrid Systems: Computation and Control (HSCC), San Francisco, U.S.A., April 13-15, 2009, vol. 5469 of Lect. N. Computer Science, pp. 306-320, R. Majumdar and P. Tabuada, eds., Springer, 2009.

Full text. (Definitive publication; restricted access.)
Full text. (Accepted version; free access.)

Abstract:
In this paper, we present a new method for computing discrete abstractions of arbitrary memory span for nonlinear sampled systems with quantized output. In our method, abstractions are represented by collections of conservative approximations of reachable sets by polyhedra, which in turn are represented by collections of half-spaces. Important features of our approach are that half-spaces are shared among polyhedra, and that the determination of each half-space requires the solution of a single initial value problem in an ordinary differential equation over a single sampling interval only. Apart from these numerical integrations, the only nontrivial operation to be performed repeatedly is to decide whether a given polyhedron is empty. In particular, in contrast to previous approaches, there are no intermediate bloating steps, and convex hulls are never computed. Our method heavily relies on convexity of reachable sets and applies to any sufficiently smooth system if either the sampling period, or the system of level sets of the quantizer can be chosen freely. In particular, it is not required that the system to be abstracted have any stability properties.

BibTeX entry:

@InProceedings{Reissig11C,
 author = {Gunther Rei{\ss}ig},
 title = {Computation of discrete abstractions of arbitrary memory span for nonlinear sampled systems},
 booktitle = {Proc. 12th Intl. Conf. Hybrid Systems: Computation and Control (HSCC), San Francisco, U.S.A., April 13-15, 2009},
 pages = {306-320},
 year = 2009,
 editor = {R. Majumdar and P. Tabuada},
 volume = 5469,
 publisher = {Springer},
 series = {Lect. Notes Computer Science},
 doi = {10.1007/978-3-642-00602-9_22}
}

Impressum und Haftungsausschluß