Ein Java-Applet zur Simulation verteilter Robotersysteme

Um das Applet zu starten, bitte den Start-Button anklicken!


Index

Theorie

[DE:Mithilfe des Applets lassen sich autonom und asynchron gesteuerte, punktförmige Roboter mit beschränkter Sicht simulieren, deren Aufgabe darin besteht, sich in einem Punkt der Ebene zu Versammeln. Die Roboter können untereinander nicht kommunizieren und nur die Roboter in ihrer Umgebung sehen, die sich innerhalb des Umkreis ihres beschränkten Sichtradius befinden. Die Roboter können nicht wahrnehmen, ob an einer Position ein einzelner oder mehrere Roboter stehen. Damit können sie auch nicht feststellen, ob an ihrer eigenen Position weitere Roboter stehen oder nicht.]

[DE:Flocchini et al. haben dazu in dem Paper mit dem Titel Gathering of asynchronous mobile robots with limited visibility einen Algorithmus vorgestellt, der es Robotern mit diesen Beschränkungen ermöglicht, sich in einem einzigen Punkt der Ebene zu versammeln. Voraussetzung dafür ist, dass die Roboter einen gemeinsamen minimalen Sichtradius besitzen, und außerdem ein zusammenhängender Distanzgraph existiert. Der Distanzgraph setzt sich zusammen aus der Menge der Knoten V, die der Menge der Roboterpositionen entspricht, und der Menge der Kanten E mit (p, q) ist eine Kante gdw. die Distanz zwischen zwei Roboterpositionen p und q kleiner oder gleich dem gemeinsamen minimalen Sichtradius aller Roboterpositionen aus V ist. Ist der Distanzgraph also anfangs zusammenhängend, so können sich alle Roboter in einem einzigen Punkt der Ebene versammeln. Ist der Distanzgraph nicht zusammenhängend, so können sich zumindest die Roboter in jeder Zusammenhangskomponente in jeweils einem Punkt der Ebene versammeln. Besitzen einige Roboter kleinere Sichtradien als andere, dann ist die Terminierung des Algorithmus nicht mehr sichergestellt.]

APPLET

[DE:Mithilfe des Applets ist es möglich, verschiedene vordefinierte Szenerien auszuwählen, zu verändern oder komplett neu zu erstellen. Es lassen sich dazu sowohl neue Roboterpositionen einfügen, als auch bestehende verschieben oder entfernen. Außerdem lassen sich die Sichtradien der Roboter einzelnen Roboter verändern.]

Bedienung

[DE:In der Zeichenfläche können neue Roboterpositionen mit einem Linksklick hinzugefügt und mit einem Rechtsklick auf eine vorhandene Roboterposition entfernt werden. Mit gedrückter linker Maustaste können vorhandene Roboterpositionen verschoben werden. Mit gedrückter rechter Maustaste oder durch Drehen des Mausrades kann der Sichtradius eines Roboters verändert werden. Die punktförmigen Roboter werden als kleine Kreise dargestellt, die von ihrem Sichtkreis umschlossen werden. Der Sichtkreis wird grün gezeichnet, wenn der Roboter mindestens einen weiteren Roboter sehen kann und ansonsten rot. Der Roboter kann weitere Roboter sehen, die sich innerhalb seines Sichtkreises und nicht an derselben Position wie er selber befinden.]

[DE:Im rechten Teil des Applets können aus der Szene-Auswahlbox Szenen mit vordefinierten Roboterpositionen ausgewählt werden. Die Anzahl der darin platzierten Roboter und deren gemeinsamer Sichtradius können in den darunter positionierten Elementen eingestellt werden. Für bestehende und neue Roboter können unterschiedliche Sichtradien eingestellt werden, jedoch ist dann nicht mehr sichergestellt, dass sich auch alle Roboter in einem einzigen Punkt der Ebene versammeln. Generell können sich alle Roboter dann versammeln, wenn sie den gleichen minimalen Sichtradius und einen zusammenhängenden Distanzgraphen besitzen.]

[DE:Im rechten Teil des Applets kann eingestellt werden, ob die Roboter als Threads gestartet werden und damit autonom und asynchron, unabhängig vom Hauptprogramm laufen sollen oder ob sie in einer Schleife des Hauptprogramms seriell den Zyklus ihres Versammlungsalgorithmus durchführen. Werden die Roboter als Threads gestartet und ausgeführt, so besteht die Abbruchbedingung darin, dass kein Roboter mehr einen anderen sieht. Diese Abbruchbedingung wird unter Umständen nie erfüllbar, wenn einige Roboter unterschiedliche Sichtradien besitzen. Werden die Roboter nicht als Threads gestartet, so besteht die Abbruchbedingung der Schleife des Hauptprogramms darin, dass sich kein Roboter nach Durchlaufen seines Zyklus bewegt hat.]

[DE:Die Berechnung der Roboterbewegungen wird mit dem Knopf "Compute movements" gestartet. Während der Berechnung wird die bisherige Gesamtanzahl berechneter Schritte im Schrittpanel unterhalb der Zeichenfläche angezeigt. Die andauernde Berechnung kann abgebrochen werden indem derselbe Knopf nochmal gedrückt wird, bevor die Berechnung beendet ist. Die Berechnung aller Roboterbewegungen kann unter Umständen sehr lange dauern, vor allem bei sehr vielen unterschiedlichen Roboterpositionen und fein abgestuften Bewegung ("smooth movements" aktiviert). Ist die Berechnung beendet oder abgrebrochen worden, dann werden die bisher berechneten Einzelschritte der Roboterbewegungen hintereinander als Animation angezeigt.]

[DE:Am unteren Rand des Applets unterhalb der Zeichenfläche, befindet sich das Schrittpanel. Mit Hilfe des Schrittpanels können die berechneten Schritte einzeln angewählt und die dazugehörigen Roboterpositionen in der Zeichenfläche angezeigt werden. Zur Anwahl der einzelnen Schritte befinden sich unten links vier Steuerungsknöpfe für (von links nach rechts) 1. Schritt, vorheriger Schritt, nächster Schritt und letzter Schritt. Rechts daneben befindet sich der Steuerungsknopf für den Start und den Stop einer Animation aller berechneten Schritte. Rechts daneben befindet sich die Anzeige der Nummer des aktuellen Schrittes und der Gesamtzahl aller berechneten Schritte. Daneben befindet sich ein Rollbalken, über den die einzelnen Schritte angewählt werden können und der die Position innerhalb der Liste aller berechneten und gespeicherten Schritte anzeigt.]


Autor: Sebastian Gerhards[gerhards@informatik.uni-bonn.de]