Multi Robot Intruder Search

Abstract

The aim of this work is the development and analysis of methods and algorithms to allow a multi robot system to cooperatively search a closed, 2-dimensional environment for a human intruder. The underlying problem corresponds to the game-theoretic concept of a classical pursuit evasion game, whereas the focus is set to the generation of plans for the group of pursuers.<br /> While the main aspect of of this work lies in the field of probabilistic robotics, concepts and ideas are incorporated from differential game theory, algorithmic geometry and graph theory. The probabilistic basis allows the integration of sensor error as well as nondeterministic robot motion. The main contributions of this work can be divided into three major parts: <br /> The first part deals with the development and implementation of probabilistic human models. Depending on the specific behavior of an intruder, ranging from uncooperative to unaware, different classes of intruders are identified. Models are proposed for two of these classes. For the case of a clever and uncooperative intruder who actively evades detection, we propose a model based on the concept of contamination. The second class corresponds to a person who is unaware of the pursuit. We show that simple Markov models, which are often proposed in literature, are not suited for modeling realistic human motion and develop advanced Markov models, which conform to random waypoint motion models. <br /> The second part, which is also the most extensive part of this work, deals with the problem of finding an uncooperative and clever intruder. A solution is presented, which projects the problem on a graph structure, which is then searched by a highly optimized A* planner. The solution for the corresponding graph problem is afterwards projected back to the original search space and can be executed by the robotic pursuers. By means of the models proposed in the first part, the performance and correctness of the method is shown. We present experiments in simulation as on real robots to show the practicability and efficiency of the method.<br /> The third part deals with the problem of finding an intruder who is unaware of the search. Based on the advanced Markov model previously discussed, a greedy algorithm is proposed, which aims at maximizing the probability to find the intruder in the near future. Experimental results for this method are shown and comparisons to simpler methods are given.

<strong>Mehrroboter-Eindringlings-Suche</strong><br /> Ziel dieser Arbeit ist die Entwicklung und Analyse von Methoden und Algorithmen, die einem kooperativen Mehrrobotersystem erlauben nach einem Eindringling in einer zweidimensionalen, geschlossenen Umgebung zu suchen. Das dem zugrunde liegende Problem entspricht dem spieltheoretischen Konzept eines Suche und Ausweichen Spieles (pursuit evasion game), wobei der Fokus auf der Generierung von Plänen für die Verfolger liegt. <br /> Der Hauptaspekt dieser Arbeit liegt dabei im Feld der probabilistischen Robotik, wobei Konzepte und Ideen aus dem Gebiet der differentiellen Spieltheorie, der algorithmischen Geometrie und der Graph Theorie verwendet werden. Die probabilistische Modellierung erlaubt dabei die Integration von Sensorfehlern wie auch nichtdeterministische Roboter-Bewegung.<br /> Die Arbeit gliedert sich in drei Hauptteile:<br /> Der erste Teil beschäftigt sich mit dem Entwurf und der Implementierung von probabilistischen Modellen für menschliche Bewegung. Abhängig vom angenommenen Verhalten eines Eindringlings, von aktiv ausweichend bis zu ignorant, werden verschiedene Klassen von menschlichem Verhalten unterschieden. Für zwei dieser Klassen stellen wir Modelle auf: Für den Fall einer intelligenten und aktiv ausweichenden Person, generieren wir ein Modell basierend auf dem Konzept von Kontamination. Das zweite Modell entspricht einem Eindringling, der sich der Suche nach ihm nicht bewusst ist. Wir zeigen, dass einfache Markov-Modelle, wie sie in der Vergangenheit oft vorgeschlagen worden sind, ungeeignet sind, um realistische Bewegung zu abzubilden und entwickeln entsprechend erweiterte Markov-Modelle für eine realistischere Modellierung. <br /> Der zweite Teil der Arbeit beschäftigt sich mit der Frage, wie man einen intelligente und aktiv ausweichenden Eindringling aufspüren kann. Die vorgestellte Lösung basiert auf der Projektion des Problems auf einen Graphen, der anschließend von einem hoch optimierten A*-Planungsalgorithmus durchsucht werden kann. Diese Lösung kann anschließend auf den ursprünglichen Raum rückprojeziert werden und kann als direkter Plan von den verfolgenden Robotern ausgeführt werden. Mittels der Modelle aus dem ersten Teil wird die Korrektheit und Effizienz der Lösung gezeigt. <br /> Der letzte Teil befasst sich mit der Frage, wie ein Eindringling gefunden werden kann, der sich neutral zur Suche verhält. Basierend auf den erweiterten Markov-Modellen aus dem ersten Teil, wird eine Lösung durch gierige Suche präsentiert, die die Wahrscheinlichkeit eine Person im nächsten Zeitschritt aufzuspüren, maximiert. Wie im zweiten Teil werden Experimente diskutiert und diese mit der Proformanz simplerer Methoden verglichen.