Computing Funnels Using Numerical Optimization Based Falsifiers
This work addresses the challenge of scaling funnel computations to high dimensions for domains such as robotics, though it appears incremental as it builds on existing falsification and optimization techniques.
The paper tackles the problem of computing funnels along trajectories of ordinary differential equations, which generalizes single trajectory behavior to sets for applications like robot motion planning, and presents an algorithm based on falsification and numerical optimization that computes accurate funnel estimates more efficiently than sum-of-squares programming methods.
In this paper, we present an~algorithm that computes funnels along trajectories of systems of ordinary differential equations. A funnel is a time-varying set of states containing the given trajectory, for which the evolution from within the set at any given time stays in the funnel. Hence it generalizes the behavior of single trajectories to sets around them, which is an important task, for example, in robot motion planning. In contrast to approaches based on sum-of-squares programming, which poorly scale to high dimensions, our approach is based on falsification and tackles the funnel computation task directly, through numerical optimization. This approach computes accurate funnel estimates far more efficiently and leaves formal verification to the end, outside all funnel size optimization loops.