TY - GEN
T1 - Computing maximizer trajectories of affine dynamics for reachability
AU - Frehse, Goran
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/2/8
Y1 - 2015/2/8
N2 - Computing an overapproximation of the reachable set of states of a continuous or hybrid system is a challenging problem. The use of overapproximations based on a set of template directions has led to scalable algorithms. When the approximation is too conservative, it can be refined by adding more template directions. Synthesizing suitable directions is possible but costly without tight underapproximations to guide the refinement. Suitable underapproximations can be constructed from the trajectories of states that are maximal in the template directions, which we call maximizers. In this paper, we propose algorithms to compute maximizer trajectories for dynamical systems with affine dynamics and nondeterministic inputs. Our computations are based solely on solving ODEs and, assuming the initial condition is a polytope, solving linear programs. Highly optimized commercial tools are available for both tasks, with corresponding performance and numerical robustness, which may help pave the way towards industrial applications of reachability analysis. Since maximizer trajectories represent actual executions of the system, or parts thereof, they can be used as counterexamples and provide additional feedback and insight to the user.
AB - Computing an overapproximation of the reachable set of states of a continuous or hybrid system is a challenging problem. The use of overapproximations based on a set of template directions has led to scalable algorithms. When the approximation is too conservative, it can be refined by adding more template directions. Synthesizing suitable directions is possible but costly without tight underapproximations to guide the refinement. Suitable underapproximations can be constructed from the trajectories of states that are maximal in the template directions, which we call maximizers. In this paper, we propose algorithms to compute maximizer trajectories for dynamical systems with affine dynamics and nondeterministic inputs. Our computations are based solely on solving ODEs and, assuming the initial condition is a polytope, solving linear programs. Highly optimized commercial tools are available for both tasks, with corresponding performance and numerical robustness, which may help pave the way towards industrial applications of reachability analysis. Since maximizer trajectories represent actual executions of the system, or parts thereof, they can be used as counterexamples and provide additional feedback and insight to the user.
KW - Approximation algorithms
KW - Context
KW - Heuristic algorithms
KW - Optimal control
KW - Support vector machines
KW - Switches
KW - Trajectory
UR - https://www.scopus.com/pages/publications/84962016588
U2 - 10.1109/CDC.2015.7403397
DO - 10.1109/CDC.2015.7403397
M3 - Conference contribution
AN - SCOPUS:84962016588
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 7454
EP - 7461
BT - 54rd IEEE Conference on Decision and Control,CDC 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 54th IEEE Conference on Decision and Control, CDC 2015
Y2 - 15 December 2015 through 18 December 2015
ER -