Abstract | ||
---|---|---|
We address the problem of analyzing the reachable set of a polynomial nonlinear continuous system by over-approximating the flow-pipe 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. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1007/978-3-319-96145-3_24 | COMPUTER AIDED VERIFICATION (CAV 2018), PT I |
Field | DocType | Volume |
Nonlinear system,Polynomial,Computer science,Numerical integration,Algorithm,Linear programming,Interval arithmetic,Piecewise,Computation,Taylor series | Conference | 10981 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.36 |
References | Authors | |
27 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hui Kong | 1 | 14 | 3.03 |
Ezio Bartocci | 2 | 733 | 57.55 |
Thomas A. Henzinger | 3 | 14827 | 1317.51 |