Koordination und Kooperation von Mehrrobotersystemen unter spatialen Nebenbedingungen

Abstract

Schon die Steuerung eines einzelnen Roboters ist komplex und erfordert oft ein intensives Training. Soll ein System aus mehreren Robotern kontrolliert werden, potenziert sich diese Schwierigkeit. Zudem müssen neben dem eigentlichen Ziel, das das Mehrrobotersystem (MRS) verfolgt, häufig zusätzliche Nebenbedingungen eingehalten werden, die mit der eigentlichen Aufgabe nur am Rande zu tun haben. Daher wird in dieser Arbeit ein neues Planungsverfahren vorgestellt, welches, nach Vorgaben des Benutzers und unter Berücksichtigung einer spatialen Nebenbedingung, geeignete Endkonfigurationen und den Weg dorthin vorschlägt.<br /> Diese Arbeit stellt sowohl die theoretischen Grundlagen als auch die praktischen Umsetzungen der koordinierten Navigation unter Nebenbedingung vor. Der Schwerpunkt liegt in der Erstellung sogenannter globaler Mehrroboterpläne. Diese enthalten Zielpunkte für jeden Roboter sowie die Wege zwischen den Zielpunkten. Zur Berechnung der globalen Mehrroboterpläne wird die Umwelt diskretisiert und die Bewegungsmöglichkeiten sowie die Nebenbedingung in je einem Graphen dargestellt. Diese beiden Graphen zeigen, wo die Roboter hinfahren können und wo sie hinfahren dürfen. Durch die graphenbasierte Darstellung der Umgebung und der Nebenbedingung kann dabei weitestgehend von der konkreten Aufgabe des Mehrrobotersystems abstrahiert und somit eine große Gruppe von Nebenbedingungen betrachtet werden. <br /> Mit der Darstellung des globalen Planungsproblems unter spatialen Nebenbedingungen als Graphenproblem werden zwei Algorithmen vorgestellt, die die globale Planung durch-führen können. Der STPlan Algorithmus nutzt die Äquivalenz zwischen der Endkonfiguration und dem Steinerbaum-Problem aus, während der AgentenPlaner an den MPR-Flooding Algorithmus angelehnt ist. Zudem wird eine Variante des AgentenPlaners, der schnelle AgentenPlaner, vorgestellt.<br /> Die Eigenschaften und die Performance des STPlaners sowie des AgentenPlaners und des schnellen AgentenPlaners werden in ausführlichen Simulationen getestet. Dabei dient der STPlaner als Referenzalgorithmus, da er, aufgrund der großen Nähe zu den bekannten Steinerbaum-Heuristiken, die Bewertung des AgentenPlaners und des schnellen AgentenPlaners vereinfacht. Es zeigt sich bei der Auswertung, dass, obwohl die Endkonfigurationen des STPlaners weniger Roboter benötigen als die anderen Algorithmen, die Pläne des AgentenPlaners für eine reale Umsetzung besser geeignet sind. Nach der Betrachtung des Problems in einer statischen Umgebung wird das Verhalten des AgentenPlaners in dynamischen Umgebungen untersucht. Dabei werden zwei Fälle untersucht: im Voraus bekannte Graphen, bei denen während der Planausführung Kanten gelöscht werden, sowie Graphen, die zunächst unbekannt sind und erst erkundet werden müssen. Durch die Übertragung des Planungsverfahrens auf reale Systeme wird zuletzt in zwei beispielhaften Versuchen mit mehreren Robotern gezeigt, dass das Planungsverfahren auch in realen Umgebungen eingesetzt werden kann.