Algebraic Proofs of Path Disconnectedness using Time-Dependent Barrier Functions
| Autor: | Henrion, Didier, Miller, Jared, Din, Mohab Safey El |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Two subsets of a given set are path-disconnected if they lie in different connected components of the larger set. Verification of path-disconnectedness is essential in proving the infeasibility of motion planning and trajectory optimization algorithms. We formulate path-disconnectedness as the infeasibility of a single-integrator control task to move between an initial set and a target set in a sufficiently long time horizon. This control-infeasibility task is certified through the generation of a time-dependent barrier function that separates the initial and final sets. The existence of a time-dependent barrier function is a necessary and sufficient condition for path-disconnectedness under compactness conditions. Numerically, the search for a polynomial barrier function is formulated using the moment-sum-of-squares hierarchy of semidefinite programs. The barrier function proves path-disconnectedness at a sufficiently large polynomial degree. The computational complexity of these semidefinite programs can be reduced by elimination of the control variables. Disconnectedness proofs are synthesized for example systems. Comment: 17 pages, 2 tables, 3 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|