A Feasibility Problem Approach For Reachable Set Approximation

Titelangaben

Jahn, Thomas U.:
A Feasibility Problem Approach For Reachable Set Approximation.
Bayreuth , 2015 . - III, 134 S.
( Dissertation, 2015 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Abstract

Reachability and controllability analysis for dynamic control systems are powerful tools for numerous applications like trajectory prediction, system verification, collision avoidance or control strategy validation. The computation of reachable sets (and controllability sets) is a central part of this analysis.

In this work we advance an algorithm for approximating reachable sets which is originally based on optimally controlled problems with distance functions as objectives. It was initially described 2009 by Baier and Gerdts. The advanced approach works without minimizing objective functions and is based on pure feasibility problems. Many of these feasibility problems are solved in parallel to check the reachability of discrete grid points of a reachable set which is approximated via an equidistant grid discretization.

We use the concept of interior point methods to develop an algorithm for solving many feasibility problems synchronously. Through a suitable problem definition we achieve a sparse linear algebra structure within the interior point method which is utilized to speed up the algorithm significantly. The whole algorithm design aims for an efficient execution on parallel CPU hardware and SIMD architecture as well.

As an application example we use the new algorithm to compute the controllability set of a satellite docking maneuver (DEOS mission). With a 13-dimensional state vector and 6-dimensional control vector this system of ordinary differential equations is quite challenging in the context of reachable sets and serves as a nice benchmark.

Abstract in weiterer Sprache

Erreichbarkeits- und Kontrollierbarkeits-Analysis sind starke Tools für zahlreiche Anwendungen, wie der Prädiktion von Trajektorien, Systemverifikation, Vermeidung von Kollisionen und der Wahl der richtigen Kontrollstrategie. Ein zentraler Teil dieser Analysis ist die Berechnung von Erreichbarkeits- und Kontrollierbarkeitsmengen.

In dieser Arbeit entwickeln wir einen Algorithmus zur Approximation von Erreichbarkeitsmengen weiter. Dieser basiert ursprünglich auf Optimalsteuerungsproblemen mit Distanzfunktionen als Zielfunktionen und wurde erstmals 2009 von Baier und Gerdts beschrieben. Beim weiterentwickelten Ansatz ist es nicht mehr nötig, Zielfunktionen zu minimieren. Stattdessen wird lediglich noch überprüft, ob ein diskreter Gitterpunkt einer mithilfe eines äquidistanten Gitters approximierten Erreichbarkeitsmenge erreicht werden kann. Diese Überprüfung findet parallel auf vielen Gitterpunkten gleichzeitig statt.Um die Lösbarkeit eines Optimalsteuerungsproblems zu ermitteln, wird das Konzept der Innere-Punkte-Verfahren verwendet und im Speziellen modifiziert, um viele dieser Lösbarkeitsprobleme simultan zu behandeln. Durch eine geeignete Formulierung des Optimalsteuerungsproblems wird erreicht, dass die lineare Algebra innerhalb des Innere-Punkte-Verfahrens auf dünn besetzten Matrizen mit immer gleichen Strukturen basiert. Diese Strukturen
werden ausgenutzt, um die effiziente Ausführung sowohl auf paralleler CPU-Hardware, als auch auf SIMD-Architektur zu ermöglichen und die Geschwindigkeit des Algorithmus somit deutlich zu beschleunigen.

Als Anwendungsbeispiel wird die Kontrollierbarkeitsmenge während des Andockmanövers eines Satelliten berechnet (DEOS Mission). Aufgrund des 13-dimensionalen Zustands- und 6-dimensionalen Kontroll-Vektors des damit verbundenen gewöhnlichen Differenzialgleichungssystems ist die Berechnung der Kontrollierbarkeitsmenge eine echte Herausforderung.