Publications by the same author
plus in the repository
plus in Google Scholar

Bibliografische Daten exportieren
 

A Feasibility Problem Approach For Reachable Set Approximation

URN to cite this document: urn:nbn:de:bvb:703-epub-2087-4

Title data

Jahn, Thomas U.:
A Feasibility Problem Approach For Reachable Set Approximation.
Bayreuth , 2015 . - III, 134 P.
( Doctoral thesis, 2015 , University of Bayreuth, Faculty of Mathematics, Physics and Computer Sciences)

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 another language

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.

Further data

Item Type: Doctoral thesis (No information)
Keywords: reachable set; feasibility problem; interior point method; optimal control; parallel programming; CUDA; DEOS; parallel cholesky; sparse matrix
DDC Subjects: 500 Science > 510 Mathematics
Institutions of the University: Faculties
Faculties > Faculty of Mathematics, Physics und Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematics V (Applied Mathematics)
Profile Fields
Profile Fields > Advanced Fields
Profile Fields > Advanced Fields > Nonlinear Dynamics
Language: English
Originates at UBT: Yes
URN: urn:nbn:de:bvb:703-epub-2087-4
Date Deposited: 03 Jul 2015 07:54
Last Modified: 24 Jul 2015 10:20
URI: https://epub.uni-bayreuth.de/id/eprint/2087

Downloads

Downloads per month over past year