Überdeckungsstrategien (Covering) in polygonalen Szenen

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


Index


Das Applet

Dieses Applet implementiert eine Simulationsumgebung für Strategien zur Exploration (aka Covering) polygonaler Umgebungen. Strategien dieser Art werden beim Entwurf von Serviceroboter, z.B. zum Staub saugen oder Rasen mähen benötigt. Zugrundegelegt werden daher einfache, kostengünstige Roboter, die insbesondere ohne teures Sichtsystem auskommen müssen und nur mit Tastsensoren ausgestattet sind. Weiterhin stehen dem Roboter nur begrenzte Kapazitäten (Rechenleistung, Speicher und Energie) zur Verfügung.

Wir gehen davon aus, dass die Umgebung dem Roboter zu Beginn nicht bekannt ist, wir haben also mit online strategien zu tun.

Als Beispiel dient die Strategie Eine Beispiel-Strategie, die weiter unten kurz beschrieben wird.


Benutzung

Das Applet besitzt zwei Haupt-Ansichten, die über das Menü Windows in der Menüleiste angnewählt werden können: Den Polygon-Explorer, der beim Start des Applets erscheint, sowie den Polygon-Editor, mit dem sich die vorgegebene Umgebung für die Exploration verändern läßt.

Polygon-Editor

Canvas

In der Editor Ansicht läßt sich im Wesentlichen auf der Canvas zeichnen, in dem mit der linken Maustaste einzelne Punkte gesetzt werden, die per Hand verbunden werden können oder die Maus wird bei gedrückter linker Taste bewegt. Dabei werden bei Richtungsänderungen automatisch Eckpunkte in die so gezogene Linie eingefügt. Um eine Umgebung mit Hindernissen zu zeichnen muss mit den Hindernissen begonnen werden, die dann von einem äußeren Polygon umschlossen werden, da das Zeichnen von Polygonen in bereits geschlossene Polygone nicht erlaubt ist. Ein Rechtsklick auf der Canvas öffnet ein Popup Menü mit weiteren Editiermöglichkeiten wie Löschen, Verschieben, Kopieren, Skalieren, Rotieren und Scheren.

Mouse

Die Maus wird wie oben beschrieben im Editor benutzt um auf der Canvas zu zeichnen. Mit der linken Maustaste können außerdem Punkte, Liniensegmente oder ganze Polygone durch angeklickt halten und bewegen der Maus verschoben werden. Das PopupMenü, das mit der rechten Maustaste geöffnet wird beinhaltet weitere Möglichkeiten ( wie Löschen, Verschieben, Kopieren, Skalieren, Rotieren und Scheren ), bereits gezeichnete Teile der Umgebung zu verändern.

Panel

Außer dem bereits beschriebenen ScrollPanel, in das die Canvas eingebettet ist und dem dazu gehörigen ZoomPanel, beinhaltet das Editor-Fenster noch eine untere Reihe von Panels, die die Editierfunktionen beeinflussen. Am häufigsten werden dabei die 4 Buttons ganz rechts zur Verwendung kommen ( Clear Scene, Open Scene, Erase Single Points, Erase Open Polygons ) mit denen die ganze Szene, einzelne Punkte, das umgebende Polygon sowie offenen Polygone selektiv gelöscht werden können. Daneben kann ein Gitter Grid zur Größenorientierung beim Zeichnen mit variablem Gitterabstand eingeschaltet werden. Die beiden Optionen des Segment Drag unterscheiden beim Verschieben eines Segmentes, ob die ursprünglichen Endpunkte des Segments dort verbleiben und Zusätzliche an der neuen Position eingefügt werden ( New Vertices ), oder nur diese Neuen Endpunkte verbleiben ( Original Vertices ). Für den End Point Drag ergeben sich die selben Optionen als Pencil Mode und Move Point.

Polygon-Explorer

Canvas

In der Explorer Ansicht ist die Canvas mit den gleichen Scroll- und Zoom-Funktionen ausgestattet wie in der Editor Ansicht, es fehlen natürlich alle Zeichen-Features, da hier nur die Wirkungsweise der Strategien beobachtet werden soll.

Zu sehen ist beim Start des Applet ein einfaches Polygon als vorgegebene Explorationsumgebung und ein schwarzes +, das den Nullpunkt des Bild-Koordinatensystems zur Orientierung kennzeichnet. Der Roboter wird erst nach der Wahl einer Strategie sichtbar, da diese seine Form und andere Parameter bestimmen kann.

Mouse

Die Maus dient im Explorer nur zum Aufrufen eines Popup-Menüs per rechter Maustaste. Dessen Funktion beschränkt sich bisher auf das setzen der Roboterposition : Bei Wahl von Set Robot Position wird der Referenzpunkt des Roboters auf die Koordinaten gesetzt, die beim Ausruf des Menüs aus den Cursor-Koordinaten gespeichert wurden. Die Funktionalität kann leicht erweitert werden. ( Siehe Klassen-Struktur )

Panel

Status Panel

Im Status-Panel werden während einer Exploration die von der Strategie bereit gestellten Status-Informationen angezeigt. Als Parameter wurden hier die prozentual bearbeitete Fläche und die Länge des bisher zurückgelegten Pfades ausgewählt, da diese zur Bewertung der Güte einer Staubsauger-Strategie geeignet erschienen. ( Zur Bereitstellung der Daten und Darstellung zusätzlicher Information siehe auch StratHandler )

Strategy Panel

Hier wird die angewendete Strategie gewählt. Die entsprechenden Parameter werden von jeder Strategie(-Klasse) selbst verwaltet und die Eingabe über einen separat erscheinenden Frame realisiert. Die entsprechenden Methoden und Klassen sind vorgefertigt und werden je nach Bedarf der Strategie angepasst. ( Zum Einfügen neuer Strategien siehe auch Klassen-Struktur, Implementierung neuer Strategien )

Control Panel

Die 6 selbsterklärenden Buttons werden durch enstprechende step-, undo-step- und redo-step-Methoden der Strategien realisiert. ( Die Radio-Buttons all und step sind als Erweiterungen des Undo- und Redo- Buttons zu sehen. ) Die Buttons können je nach Vorgabe der Strategie ganz oder zeitweise von außen enabled oder disabled werden. ( Zu Anforderungen an Strategien siehe auch Klassen-Struktur, Implementierung neuer Strategien )

Robot Editor

Der Button Robot Editor in der rechten Unteren Ecke der Explorer Ansicht dient dem Öffnen einer kleineren, einfachen Version des Polygon-Editors zum Design der äußeren Form des Roboters. Mit der rechten Maustaste erreicht man das gleiche Popup-Menü wie in der Editor Ansicht. Die restlichen Optionen beschränken sich jedoch auf das Löschen der gesamten Scene mit Clear, da ein Roboter nur aus einem Polygon bestehen soll, sowie dem Setzen des Roboters, also dem Übertragen des Polygons in die dargestellte Szene und die gewählte Strategie mit Set. Diese Option funktioniert nur bei vorgewählter Strategie. ( Siehe auch Klassen-Struktur ) Mit Scaling kann das aktuelle Polygon herunter skaliert werden. In der Menüleiste können unter Forms verschiedene vordefinierte Polygone ausgewählt werden und mit Quit wird unter File der Editor verlassen, wobei das letzte Polygon bis zum Neustart des Applets vorhanden bleibt ( also bei einem erneuten Aufruf des Editors wieder erscheint ).

Klassen Struktur

Die wichtigsten Klassen des Applets werden hier kurz beschrieben :

CRApplet.java

Außer dem Start und der Initialisierung aller Bedienelemente ( Frame, Panels ) obliegt der Hauptklasse des Applets die Verteilung von Informationen als ActionListener per ActionEvents unter den Klassen, die keine engeren Verbindungen - beispielsweise als gegenseitige Listener - unterhalten.

CRFrame.java

Der MainFrame des Applets übernimmt das grobe Layout des Applets, das weiter durch die einzelnen schon im Applet initialisierten Panels verfeinert wird. ( Siehe oben unter Panels ) Hier wird außerden die Auswahl von Editor- oder Explorer-Ansicht mit den notwendigen Layout-Änderungen ermöglicht.

CRRobot.java

CRRobot ist abgeleitet von anja.polyrobot.robots.ConvexRobot, einem Roboter, der als Grundfläche ( _shape ) ein beliebiges (!) Polygon2 ( anja.geom ) verwaltet. Hinzugekommen ist hier die Erzeugung vordefinierter Polygone und die Verwaltung von Mittelpunkt ( _center ) und einem Referenzpunkt für Drehungen ( _nose ), die Drehung selbst, sowie eine Methode zur Spiegelung der Grundfläche am Koordinatenursprung, die für Minkowski-Summen-Bildung zur Bewegungsplanung benötigt wird.

StratHandler.java

Der StratHandler stellt das Bindeglied zwischen der Darstellung in der Explorer Ansicht und der Strategie dar. Als abgeleitete Klasse von anja.swinggui.polygon.Polygon2SceneWorker verwaltet der StratHandler die Szene und erlaubt es die Robotergrundfläche, sowie Pfad und bearbeitete Fläche darin einzuzeichnen ( get-/setRobot([Polygon2]), get-/setArea([HolePolygon2]), addTo-/RemoveFrom-/getPath([Polygon2]) sowie zugehörige paint- und graphische reset- Methoden ). Die Auswahl der Strategie führt zur Instanzierung der gewählten Strategie in einem eigenen Thread in der Instanz des StratHandlers ( initStrat(), run-/stop-/resetStrat(), usw. ). Diese wiederum wird bei der Initialisierung des Applets einmal erzeugt . Um den Zugriff auf Statusinformationen und den einzelnen step-Methoden ( Siehe oben unter Strategy Panel, Control Panel ) zu gewährleisten, müssen alle von StratHandler verwalteten Strategien von Strat.java abgeleitet sein. Damit der StratHandler auf ( abgeschlossene ) Aktionen der Strategie reagieren kann, sollte er bei der Strategie als ActionListener registriert sein ( actionPerformed ). Auch das Popup-Menü ( siehe Mouse ) wird hier behandelt ( siehe dazu auch buildPopupMenü ), sowie das editieren der Roboter-Grundfläche.

Strat.java

Strat.java stellt die Basisklasse für alle Strategien dar, deren abstrakte Funktionen ( sowie die run()-Methode ) zur korrekten Funktion des StratHandlers überschrieben werden müssen.

StratConsts.java

In StratConsts.java werden alle Strategien mit einer eindeutigen ID registriert. Diese kann mittels getNameByID() mit einem vordefinierten String als Namen für Menüs etc. identifiziert werden. Auch andere klassenübergreifend genutzte Konstanten ( für Listener usw.) werden praktischerweise hier hinterlegt.

Implementierung neuer Strategien

Die wesentlichen Punkte bei der Implementierung neuer Strategien wurden bereits bei der Vorstellung der wichtigsten Klassen erwähnt. Eine neue Strategie-Klasse wird demzufolge von Strat.java abgeleitet und mit einer neuen ID in StratConsts.java versehen. Zusätzlich muss sie - bisher noch "von Hand" - an zwei Orten registriert werden : Alle übrigen Anpassungen der Strategie-Klasse an das Framework sind automatisch mit der Implementierung der abstrakten Methoden in Strat.java gegeben :

Zusätzlich zu dieser knappen Dokumentation empfehlen sich die Kommentare im Source-Code zu einzelnen Methoden oder ganzen Klassen. Das wichtigste Konzept zur Implementierung neuer Strategien für dieses Framework ist neben den obigen Hinweisen das java-typische EventHandling mittels aller Arten von Listenern, die die Kommunikation zwischen Klassen bestreiten.


Eine Beispiel-Strategie

Die bisher implementierte Cleaner-Strategie ist eine einfache randomisierte Strategie, die aus einem vorgegebenen Winkelbereich einen Zufallswinkel auswählt, in dem der Roboter von dem nächsten getroffenen Hindernis "reflektiert".

Um der Ausdehnung des Roboters ( im Gegensatz zum punktförmigen Roboter ) Rechnung zu tragen, wird der Auftreffpunkt auf ein Hindernis nicht an den Polygonen der Szene selbst berechnet, sondern im Raum der freien Konfigurationen. Dieser wird mit Hilfe der Minkowski-Summe aus den Hindernis-Polygonen und dem am Koordinatenursprung gespiegelten Roboter gewonnen ( siehe Skript Bewegungsplanung ).

Der "Reflektionswinkel" w ist initial zufällig aus dem Intervall [0, 2PI], und stammt danach entsprechend der gewählten Angle Range r und dem letzten Auftreffwinkel a auf einem Hindernis aus dem Intervall [ a-r, a+r ]. Mittels Fix Angle kann w auch auf r fest gesetzt werden.

Der Pfad von den aktuellen zu den mit Winkel w bestimmten nächsten Koordination kann direkt ( Straight ) oder im Zick-Zack ( X (zig-zag) ) verlaufen, wobei im letzteren Fall noch Breite und Abstand der x-Bewegung eingestellt werden können. Die Darstellung des Pfades kann außerdem als Gesamtfläche ( Area ) oder als aneinanderliegende Polygone ( Trace ) erfolgen.

Die Grundfläche des Roboters kann aus vordefinierten Formen ausgewälht werden ( inklusive der letzten im Editor bearbeiteten ) oder direkt im Robot Editor gezeichnet und ebenfalls größenskaliert werden. Außerdem wird mit Turn Robot zwischem einem rein reflektierenden Roboter, der sich in alle Richtungen bewegen kann und einem Roboter, der sich nach "Fahrtrichtung" ausrichtet, unterschieden.

Die einzustellende Safe Distance gibt an wie groß der Sicherheitsabstand zur Wand sein soll.
( Einrichtung von IKEA ? - 5-10%. Einrichtung antik - 100% ;-)

Autor: Birgit Engels