Reachable set over-approximation for nonlinear systems using piecewise barrier tubes

H. Kong, E. Bartocci, T.A. Henzinger, in:, Springer, 2018, pp. 449–467.

Download
OA 5.59 MB

Conference Paper | Published | English
Department
Series Title
LNCS
Abstract
We address the problem of analyzing the reachable set of a polynomial nonlinear continuous system by over-approximating the flowpipe of its dynamics. The common approach to tackle this problem is to perform a numerical integration over a given time horizon based on Taylor expansion and interval arithmetic. However, this method results to be very conservative when there is a large difference in speed between trajectories as time progresses. In this paper, we propose to use combinations of barrier functions, which we call piecewise barrier tube (PBT), to over-approximate flowpipe. The basic idea of PBT is that for each segment of a flowpipe, a coarse box which is big enough to contain the segment is constructed using sampled simulation and then in the box we compute by linear programming a set of barrier functions (called barrier tube or BT for short) which work together to form a tube surrounding the flowpipe. The benefit of using PBT is that (1) BT is independent of time and hence can avoid being stretched and deformed by time; and (2) a small number of BTs can form a tight over-approximation for the flowpipe, which means that the computation required to decide whether the BTs intersect the unsafe set can be reduced significantly. We implemented a prototype called PBTS in C++. Experiments on some benchmark systems show that our approach is effective.
Publishing Year
Date Published
2018-07-18
Acknowledgement
Austrian Science Fund FWF: S11402-N23, S11405-N23, Z211-N32
Volume
10981
Page
449 - 467
Conference
CAV: Computer Aided Verification
Conference Location
Oxford, United Kingdom
Conference Date
2018-07-14 – 2018-07-17
IST-REx-ID

Cite this

Kong H, Bartocci E, Henzinger TA. Reachable set over-approximation for nonlinear systems using piecewise barrier tubes. In: Vol 10981. Springer; 2018:449-467. doi:10.1007/978-3-319-96145-3_24
Kong, H., Bartocci, E., & Henzinger, T. A. (2018). Reachable set over-approximation for nonlinear systems using piecewise barrier tubes (Vol. 10981, pp. 449–467). Presented at the CAV: Computer Aided Verification, Oxford, United Kingdom: Springer. https://doi.org/10.1007/978-3-319-96145-3_24
Kong, Hui, Ezio Bartocci, and Thomas A Henzinger. “Reachable Set Over-Approximation for Nonlinear Systems Using Piecewise Barrier Tubes,” 10981:449–67. Springer, 2018. https://doi.org/10.1007/978-3-319-96145-3_24.
H. Kong, E. Bartocci, and T. A. Henzinger, “Reachable set over-approximation for nonlinear systems using piecewise barrier tubes,” presented at the CAV: Computer Aided Verification, Oxford, United Kingdom, 2018, vol. 10981, pp. 449–467.
Kong H, Bartocci E, Henzinger TA. 2018. Reachable set over-approximation for nonlinear systems using piecewise barrier tubes. CAV: Computer Aided Verification, LNCS, vol. 10981. 449–467.
Kong, Hui, et al. Reachable Set Over-Approximation for Nonlinear Systems Using Piecewise Barrier Tubes. Vol. 10981, Springer, 2018, pp. 449–67, doi:10.1007/978-3-319-96145-3_24.
All files available under the following license(s):
Creative Commons License:
CC-BYCreative Commons Attribution 4.0 International Public License (CC-BY 4.0)
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded
2018-12-17T15:57:06Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar