Set-based reachability analysis is used extensively in fields such as robotics in the context of, e.g., motion planning and the formal verification of cyber-physical systems. In order to properly model such systems, various set representations have been used throughout the literature. For certain computational tasks, one needs to be able to sample random points within such set representations. This thesis will introduce two approaches, the Ball Walk Algorithm and the Billiard Walk Algorithm, which are both so-called Markov Chain Monte Carlo methods that allow one to generate random samples within a convex set. In addition, the distribution of these samples can be shown to converge to the uniform distribution. The set representation we will focus our efforts on are spectrahedral shadows, which can be seen as the solution sets of positive semi-definite constraints. As a possible application, this thesis will also present two probabilistic solutions to the containment problem for spectrahedral shadows, using uniform random sampling algorithms.     «

Set-based reachability analysis is used extensively in fields such as robotics in the context of, e.g., motion planning and the formal verification of cyber-physical systems. In order to properly model such systems, various set representations have been used throughout the literature. For certain computational tasks, one needs to be able to sample random points within such set representations. This thesis will introduce two approaches, the Ball Walk Algorithm and the Billiard Walk Algorithm, whi...     »

Die mengenbasierte Erreichbarkeitsanalyse wird in Bereichen wie Robotik häufig im Zusammenhang mit z. B. Bewegungsplanung und der formalen Verifizierung cyber-physischer Systeme eingesetzt. Um solche Systeme richtig modellieren zu können, wurden in der Literatur verschiedene Mengendarstellungen eingeführt. Für bestimmte Rechenaufgaben muss man in der Lage sein, Punkte zufällig innerhalb solcher Mengendarstellungen wählen zu können. Diese Arbeit stellt zwei Algorithmen vor, den Ball Walk Algorithm und den Billiard Walk Algorithm, die beide sogenannte Markov-Chain-Monte-Carlo-Methoden sind, mit denen man zufällige Stichproben innerhalb einer konvexen Menge erzeugen kann. Darüber hinaus kann gezeigt werden, dass die Verteilung dieser Stichproben zur Gleichverteilung konvergiert. Die Mengendarstellung, auf die wir uns konzentrieren werden, sind spektrahedrale Schatten, die als Lösungsmengen von Optimierungsproblemen mit positiv semidefiniten Beschränkungen angesehen werden können. Als mögliche Anwendung wird diese Arbeit auch zwei probabilistische Lösungen für das Containment-Problem für spektrahedrale Schatten unter Verwendung von Uniform Sampling Algorithmen vorstellen.     «

Die mengenbasierte Erreichbarkeitsanalyse wird in Bereichen wie Robotik häufig im Zusammenhang mit z. B. Bewegungsplanung und der formalen Verifizierung cyber-physischer Systeme eingesetzt. Um solche Systeme richtig modellieren zu können, wurden in der Literatur verschiedene Mengendarstellungen eingeführt. Für bestimmte Rechenaufgaben muss man in der Lage sein, Punkte zufällig innerhalb solcher Mengendarstellungen wählen zu können. Diese Arbeit stellt zwei Algorithmen vor, den Ball Walk Algorith...     »