Home

Entwicklerhandbuch - Heinz Nixdorf Institut

1. b c d e c d A A KEN gt A AEA e f g h f g h Sei der triangleTreshold 5 c kann nicht entfernt werden da er mehr als ein Kind enth lt d kann nicht ersetzt werden da a nachher 4 5 gt triangleTreshold Dreiecke enthalten w rde b erf llt alle Kriterien und kann daher entfernt werden Abbildung 45 Beispiel f r compressTreeStructure 5 Mache die Boundingboxen so klein wie m glich Dies dient dazu das Fru stumculling zu verbessern Je passgenauer die Boundingbox desto selte ner kommt es vor dass beim Frustumculling ein Octreeknoten im Frustum liegt obwohl sein Inhalt nicht sichtbar ist Traversiere dazu rekursiv und bottom up den gesamten Baum Setze Gr e und Positionen der BoundingBoxen eines Octreeknotens so dass die Gr e minimal ist aber dennoch s mtliche in diesem Knoten gespeicherten Drei ecke sowie die Boundingboxen aller Kinder noch hinein passen Ein wichtiger Spezialfall liegt vor wenn ein Knoten einen Stein enth lt Dann darf die Boundingbox nur verkleinert aber nicht verschoben werden Grund siehe Punkt 2 Illustration siehe Abbildung 46 Der Parameter shrinkBoundingBoxes bestimmt ob diese Optimierung ausgef hrt werden soll oder nicht links Ausgangssituation ein Dreieck ein Stein mit Durchmesser 1 und die BoundingBox mit Durchmesser 2 mittig Schrumpfen ohne Verschiebung dies ist die korrekte Situation der Stei
2. i Subject Coo en a al A Il gt Kernel H MainControl i E Datenhaltung Terrain2D Robots visitedPaths i i i i Terrain3D GroundObjects Selection i i i ExplorationQuadtrees N P Abbildung 33 Grobarchitektur der Visualisierung sualisierung die f r die User Interaktionen und f r die konkrete Visualisierung der Simulation verantwortlich sind b eine Reihe Datenstrukturen insbeson dere f r die visualisierungsseitige Speicherung der Map und der Roboter und c einige weitere Hilfsklassen All diese werden im n chsten Abschnitt 5 2 de tailreicher beschrieben Als wichtiges Entwurfskonzept ist in der Architektur das Observer Pattern vgl GHJV95 zu finden Konkret implementiert wurde es in Klassen Subject und Observer sowie allen Unterklassen der Observer Klasse Mittels dieses Patterns wird daf r gesorgt da die Aktionen der Simulation in der Visualisierung ein fach und effizient publik gemacht werden 5 2 Wichtige Klassen In diesem Abschnitt werfen wir einen detaillierteren Blick auf das Innere des Visualisierungsmoduls Dabei stellen wir dar 1 wie die Abl ufe innerhalb der Visualisierung aussehen 2 wie die Datenhaltung aussieht 3 was die konkrete Ansicht auf die Simulation leistet 4 wie Features wie Detailansicht Anzeige der explorierten Karte und der abgelaufenen Wege einz
3. Abbildung 9 Quadtree mit Nachbarschaftsbeziehung nach Zellteilung e QNode diese enth lt Kinderknoten NW NE SW SE alle vom Typ QNo de Position im Gel nde Informationen ber Seitenl nge Hindernisei genschaft Koordinate e RegionQuadtree diese enth lt einen Wurzelknoten vom Typ QNode und Methoden zum Parsen einer XML Gel ndedatei in die Datenstruktur e StaticObjects diese Unterklasse von RegionQuadtree erweitert diesen um den Bereichsanfrage Algorithmus 3 3 2 PRQuadtree f r Speicherung der Sch tze Es befinden sich auf der Karte nicht nur Hindernisse sondern auch andere Ob jekte wie z B Sch tze oder Flags Die Hindernisse sind statisch d h sie werden zur Laufzeit nicht mehr ver ndert Die Sch tze und Flags dagegen sind dyna misch d h Sch tze k nnen von den Robotern abgebaut werden Flags k nnen an jeder Position abgesetzt werden Daher ist es sinnvoll die Sch tze und Flags getrennt von den Hindernissen zu bearbeiten Sch tze und Flags werden zu dynamischen Objekten zusammengefasst Diese werden in einem PRQuadtree gespeichert Eine Liste w re in diesem Fall als Datenstruktur nicht sinnvoll weil sie im schlimmsten Fall komplett durchlaufen werden m sste Beim PRQuadtree wird nur ein Pfad von der Wurzel bis zu einem Knoten durchlaufen Aufbau eines PRQuadtrees Der PRQuadtree unterteilt die Karte rekursiv in vier gleich grose Teilbereiche siehe Abbildung 10 Die Informationen der gesamt
4. Implizit wird auch die Kollisionsvermeidung bzgl Hindernissen eingesetzt um die Ausweichbewegung abzusichern Die Vermeidung bzgl Robotern wird of fensichtlich zweimal aufgerufen Alle anderen Operationen haben konstante Laufzeit S mtliche relevanten Berechnungen finden in hasAction statt Es werden praktisch keine Daten permanent gespeichert Der Speicheraufwand ist daher zu vernachl ssigen Der angesprochene Parameter SidestepTechnique erwartet einen String Es stehen dabei folgende M glichkeiten f r die Ausweichbewegung zur Verf gung e ParallelRight von der aktuellen Position aus parallel zur Mittelsenk rechte nach rechts e ParallelDirected von der aktuellen Position aus parallel zur Mittel senkrechte in die eigentlich angestrebte grobe Richtung e AngularRight von der aktuellen Position aus schr g nach rechts auf die Mittelsenkrechte zu e AngularDirected von der aktuellen Position aus schr g auf die Mittel senkrechte zu in die eigentlich angestrebte grobe Richtung 41 4 3 Taktiken 4 ROBOTER MODUL Alles Ausweichbewegungen stellen nur Heuristiken dar und es ist keineswegs ausgeschlossen dass andere besser w ren Eine Erweiterung dieser Taktik w re daher denkbar In der Praxis hat sich bislang AngularRight als tauglichste Methode erwiesen weswegen dies der Default Wert ist Sie ist exemplarisch in Abb 18 dargestellt Roboter 1 e Roboter 1 de o m N o ja Rob
5. 49 Protokoll beim Verlassen eines Teams 50 Protokoll beim Verlassen eines Teams 51 Zustandsautomat der Strategie SubAreaStrategy 56 Beispiel einer SubArea mit Stripes 0 57 Beispiel zum Ablaufen eines Hindernisses bis zum Rand der SubA TOM nin Hie eG ea ARA eH Se re ner Bh ee ee 57 Beispiel zum Umrunden eines Hindernisses 58 Beispiel zum Verlassen der SubArea und Erkunden von abge trennten Bereichen 2 02 0000 eee eee 58 Zustandsautomat der Strategie TreasuregreedStrategy 61 Zustandsautomat der Worker Strategie 62 Zustamdsautomat von der Transporter Strategie 63 Die Visualisierung gt ia c ss msa sopd e e e 64 Grobarchitektur der Visualisierung 65 Repr sentation der Karte im TerrainQuatree in unterschiedli chen Detailgraden In gr beren Detailgraden werden die Werte der Kinder interpoliert um auch feine Strukturen bei kleinen Zoomstufen angen hert darstellen zu k nnen 69 Resultat des Gel ndezeichnens ohne und mit Interpolation 69 Die Robotertypen Relais Explorer Worker Multirobot und Trans porter von links nach rechte oaa 72 Die Blickrichtung der Kamera 2 2 2 72 97 Abbildungsverzeichnis Abbildungsverzeichnis 38 39 40 41 42 43 44 45 46 47 48 49 50 5l 52 53 54 55 Zusammenh ngende Hindernisstrukturen finde
6. e move List lt Position gt pathNodes float speed Berechnet aus einer gege benen Folge von Positionen eine Folge von Bewegungs Elementaraktionen und f gt diese an die Aktionsliste an e move List lt Position gt pathNodes float speed int index Berechnet aus einer gegebenen Folge von Positionen eine Folge von Bewegungs Elementar aktionen und fiigt diese in die Aktionsliste an die Stelle index in e move Position startPos Position endPos float speed Fiigt eine aus Start und Endposition zu berechnende Folge von Bewegungs Elementaraktionen an die Aktionsliste an e move Position startPos Position endPos float speed int index Fiigt eine aus Start und Endposition zu berechnende Folge von Bewegungs Elementaraktionen in der Aktionsliste vor index in Gibt den Index der ersten Elementaraktion nach den eingefiigten zuriick e workOnObject GroundObjectID objectID int change int numberOf Rounds Fiigt eine sich aus der iibergebenen Anzahl an Runden ergeben de Folge von Bearbeitungs Elementaraktionen an die Aktionsliste an e workOnObject GroundObjectID objectID int change int numberOf Rounds int index F gt eine sich aus der bergebenen Anzahl am Run den ergebende Folge von Bearbeitungs Elementaraktionen in die Aktions liste zwischen index und index 1 e loadObject GroundObjectID objectID int totalAmount int amountPer Round Fuegt eine aus Anzahl insgesamt und pro Runde aufzuhebender Objekte zu berechnende Fo
7. 99
8. Dokumentation Universitat Paderborn Fakult t f r Elektrotechnik Informatik und Mathematik Institut f r Informatik Fachgruppe Algorithmen und Komplexit t Heinz Nixdorf Institut Institut f r Informatik F rstenallee 11 33102 Paderborn Prof Dr math Friedhelm Meyer auf der Heide Raum F1 301 Telefon 49 0 5251 60 6480 Telefax 49 0 5251 60 6482 eMail fmadh upb de Paderborn 01 10 2007 Inhaltsverzeichnis 1 Einf hrung kle Motivation aida e wa a e ee Eee k es eA Vie ere kh ok Stee Besa ah Bee eae Bee fare OL eed ee ke eee ve 1493 Modells 2 0 sn aa Ripe be eR ar aa BSE Be x LA Projektteam u scr 2 oe da era nr ee a Architektur und Komponenten 2 1 Architektur des Gesamtsystems o 2 2 Dimiulabionskermel gt won Poni ne dr A akt a 2 3 Kobhotermodul ro sok un Dr me A euch a ee u 2 4 Visualisierine kaa ww a are Ae i 2er Editon e os e a as ae Sok ete WS ee re we Ee Bee E 2 6 Messsr en occiso 28 au 2 mar ana Simulationskernel Sls Arehntektur sos ua e ek Gut Pe RA ee ek ee eo eS 3 2 Simulationsabwicklung und verwaltung 3 2 1 Multithreading soe s sor mosia ee A ee 9 22 Messages oraria ya aaa Dean 3 2 3 Roboterverwaltung c sos s soca aoe aoa aa aaa 3 3 Datenstrukturen css eii ze us au ke we Aa es 3 3 1 Quadtree f r Speicherung der Map 3 3 2 PRQuadtree f r Speicherung der Sch tze BA RME
9. H ngt eine Ele mentaraktion zum Versenden von Nachrichten an die Liste an sendMessage ArrayList lt Messagelnformation gt messages int index F gt eine Elementaraktion zum Versenden von Nachrichten in die Liste zwi schen index und index 1 ein removeFirst Entfernt die als n chst auszuf hrende Aktion aus der Liste removeLast Entfernt die letzte Aktion aus der Liste removelnterval int from int to Entfernt alle Aktionen im Intervall from to sofern das Intervall existiert removeAll Entfernt alle Aktionen aus der Liste Taktiken ganze Reihe von vordefinierten Taktiken existiert bereits Im folgenden finden sich diese unterteilt in die u eren Klassen in denen sich diese befinden Vor allem f r das Vermeiden von Kollisionen Kapitel 4 3 1 und das Anstreben bestimmter Orte Kapitel 4 3 2 oder Roboter Kapitel 4 3 3 wurden Taktiken implementiert aber auch f r Team Management Kapitel 4 3 4 und die Ener gierverwaltung des Roboters Kapitel 4 3 5 4 3 1 CollisionDetector Die Taktiken der Klasse CollisionDetector implementieren alle das Inter face IMovementTactic und widmen sich der Vermeidung von Kollisionen mit Hindernissen und oder Robotern und der Berechnung von Ausweichbewegun gen Die Methoden der Taktiken erlauben es im Vorhinein zu erkennen ob 40 4 3 Taktiken 4 ROBOTER MODUL eine Bewegung in einer Kollision mit einem Hindernis oder anderen Robotern enden k nnte Die korrekte Benutz
10. Zu Anfang tauchten Probleme beim Rendering auf Das Bild hat beim neu zeich nen geflackert Dies wurde dadurch gel st dass der angezeigte Ausschnitt zuerst als ein Bild im Hintergrund erstellt wird und anschliesend in den Vordergrund geschaltet wird Die Bigmap dient nicht nur dazu Hindernisse und Sch tze anzu zeigen der Benutzer selbst kann neu Hindernisse und Sch tze einf gen indem er auf der Optionspalette einen entsprechenden Zeichenmodus ausw hlt und mit klicken und ziehen der Mouse ber der Bigmap Hindernisse einzeichnet oder l scht 6 1 2 Die Minimap Die Minimap ist ein JPanel welches die gesamte Karte den gesamten Quadtree anzeigt Wegen Renderingproblemen die am Anfang aufgetaucht sind wird die Karte jetzt zuerst als Bild im Hintergrund gezeichnet Das Bild hat dabei die Gr Se der Karte H he x Breite in Pixel Anschliesend wird das Bild ska liert und in den Vordergrund geschaltet W rde man jedes Hindernisse f r sich skalieren und dann zeichnen w rde es zu Darstellungsproblemen kommen Die rechteckigen Hindernisse h tten keine glatten R nder sondern an manchen Stel len Zacken Auser der Anzeige der gesamten Karte liefert die Minimap zus tzliche Informa tionen ber den Ausschnitt der in der Bigmap angezeigt wird Weil mit float Werten und int Werten hantiert wird stimmt der angezeigte Ausschnitt der Bigmap mit der Information in der Minimap nicht immer Es liegen leichte Abweichungen aufgrund der Rundung der
11. rameters in der Methode initDataManagement jeder Strategie ge ndert werden e sendMapRegion int horizontal int vertical List lt RobotID gt receiverIDs Sendet den durch die Parameter definierten Bereich der Karte an die angegebenen Roboter e sendMapRegion int horizontal int vertical RobotID receiverID Sendet den durch die Parameter definierten Bereich der Karte an den angegebe nen Roboter e sendMap List lt RobotID gt receiverIDs Sendet die komplette Karte des Roboters an die angegebenen Roboter e sendMap RobotID receiverID Sendet die komplette Karte des Roboters an den angegebenen Roboter In dieser Schnittstelle existieren weitere Methoden die ebenfals in der Java Dokumentation nachgeschlagen werden k nnen IContainer Data Schnittstelle erm glicht der Strategie auf die Daten des Con tainers zuzugreifen Folgende Methoden stehen zu Verf gung e int getAvailableCapacity bermittelt die aktuell verf gbare Kapazit t des Containers e int get AmountOfTreasureObjects Ermittelt die aktuelle Anzahl an Schatzeinheiten die im Container des Roboters enthalten sind 35 4 2 Strategie und Taktikkonzept 4 ROBOTER MODUL int get AmountOfFlagObjects Ermittelt die aktuelle Anzahl an Flagein heiten des Containers des Roboters Map lt FlagID Object gt getAllFlagContents Gibt eine Kopie der Inhalte aller aufgehobenen Flags zur ck Object getFlagContent FlagID flagID Ermittelt den Inhalt des F
12. tik kann jedoch nicht gew hrleisten dass eins der Relais erreicht wird da deren Position im Allgemeinen nicht bekannt ist Als Ausweichmethode wird in die sem Fall die HomeBase angestrebt Unter der Annahme dass Relais bestimmte Positionen zur Aufrechterhaltung des Kommunikationsnetzwerks beibehalten kann diese Taktik jedoch erfolgversprechend arbeiten Die Taktik liefert solange Bewegungsaktionen bis ein Relais im Funkradius ist oder die HomeBase erreicht wurde Ziel der Bewegungen ist dabei das 45 4 3 Taktiken 4 ROBOTER MODUL nahest vermutete Relais ausgehend von den zuletzt gesehenen Relais Stan dardm ig werden dazu die in den letzten 1000 Runden gesehenen Relais gespei chert Dieser Wert ist durch den Parameter BackUpsOfSeenRelays bei Bedarf ver nderbar Wurde an der Zielposition und auf dem Weg dorthin kein Relais gefunden wird anstattdessen die HomeBase angestrebt was grunds tzlich sinn voll erscheint da diese beim Datenaustausch hilfreich ist Alle Berechnungen haben nur konstante zu vernachl ssigende Laufzeit Der ben tigte Speicher ist nach oben begrenzt durch die Anzahl der Relais und im schlechtesten Fall linear von diesen abh ngig 4 3 4 TeamManagement Die Taktiken im TeamManagement geben den Robotern die M glichkeit un tereinander Teams aufzubauen anderen Teams beizutreten oder auch Teams wieder zu verlassen oder aufzul sen Die Taktiken des Teammanagements ar beiten komplett auf Basis von
13. Main settings Panell sieh Abb 51 e Settings for random function Panel2 sieh Abb 51 e Settings for file function Panel4 sieh Abb 51 e Creating the map Panel3 sieh Abb 51 Das Panel Main settings Hier werden alle grundlegenden Informationen zur Generierung der Karte ab gefragt e Gr sse der Karte als Potenz von 2 die Gr se der Karte ist dann 2 e Anteil von Hindernissen an der gesamten Karte also wieviel von der ge samten Fl che mit Hindernissen bedeckt werden muss e Die Generierungsfunktion Zur Zeit gibt es nur zwei Methoden Zufalls funktion und Dateifunktion Das Panel Settings for random function Diese Methode bietet eine M glichkeit eine Karte durch einf gen von verschie denen Formen zu generieren Zur Zeit gibt es folgende Formen e Quadrat ein Rechteck e Rectangle ein Recheck e Shoe eine Hufeisenform e Tee eine T Form e Ess eine S Form Alle Formen sind standardm ssig ausgew hlt Falls nur bestimmte Formen bei der Generierung benutzt werden m ssen kann man die unn tige Formen abw hlen Zu jeder Form kann man die minimal und maximalm gliche Gr sse ausgew hlen Bei der Generierung der Karte werden dann diese Formen aus dem Bereich mi nimale und maximale Gr ssen per Zufall erzeugt und in die Karte eingef gt Zus tzlich gibt es auch eine M glichkeit den Anteil einer Form an dem Ge samtanteil aller F
14. QuadtreeMonumenter werden zun chst noch positive Z Werte erzeugt histo risch bedingt am Ende werden die Z Werte dann negativ gemacht und bleiben ab da negativ QuadtreeMonumenter Das Modell der Simulation ist auf eine zweidimensio nale Beschreibung des Gel ndes beschr nkt Um dennoch Hindernisse in der 3D Visualisierung nicht flach darzustellen war es unsere Aufgabe aus beliebig geformten Hindernissen eine ansprechende Berglandschaft zu generieren Da die Formen von Hindernissen auch sehr untypisch f r Berge sein k nnen fiel unsere Wahl auf Tafelberge da diese auch bei sehr scharfen Konturen und abstrakten Formen von Hindernissen ein einigerma en realistisches Gesamtbild schaffen Nichtsdestotrotz gibt es ein Flag dass optional die den Generator auf Pyrami den bzw H gelartige Berge setzt Der QuadtreeMonumenter bekommt das Terrain2D bergeben generiert dar aus ein Netz aus Dreiecken und gibt dieses als TerrainData3D zur ck Er er zeugt dabei drei Arten von Hindernissen Steine Schutth gel und Monuments Dabei geht er wie folgt vor 1 bersetze den Quadtree aus Terrain2D in einen MeshQuadtree der eini ge zus tzliche Funktionen Nachbarschaftsuchen Zusammenhangskompo nenten finden u und die M glichkeit Vertexindices zu speichern bietet 2 Trenne 1mx1m Hindernisse aus dem Quadtree heraus und speichere ihre Koordinaten in einer Liste Hieraus werden die Steine 3 Trenne gro e Zusammenhangskompenten ber
15. cheninhalt ist 8 Es soll das Dreieck ausgew hlt werden welches zu der zuf lligen Zahl 4 3 0 8 geh rt Der oberste Kasten zeigt die Sortierung der Dreiecke entsprechend des post order Durchlaufs und mit Gewichtung nach Fl cheninhalt Hier sieht man dass das horizontal linierte Dreieck aus Knoten d ausgew hlt w rde Der Algorithmus ermittelt dies wie folgt Im 1 und 2 Schritt errechnet man anhand der triangles Area Werte der Kinder in welchem Kind das Dreieck liegen muss Im 3 Schritt sieht man an den Werten dass das Dreieck in keinem Kind liegen kann also in d selbst Im 4 Schritt wird dann die Dreiecksliste von d linear nach dem passenden Dreieck durchsucht Abbildung 44 Beispiel f r pullUpSamples 4 Versuche wenig n tzliche Octreeknoten einzusparen Knoten die nur ein Kind haben und wenige Dreiecke beinhalten werden nach M glichkeit eliminiert denn sie machen den Octree un tig gro Im Elternknoten wird dann die Referenz auf diesen Knoten durch sein einziges Kind ersetzt Die Dreiecke des Knotens werden in den Elternknoten verschoben Der Parameter triangleTreshold ist eine Obergrenze f r die Anzahl der Dreiecke die im Elternknoten nach dieser Optimierung enthalten sein d rfen Ist triangleTreshold 0 dann wird diese Optimierung nur dann vorgenommen wenn der Knoten keine Dreiecke enth lt 78 5 3 Preprocessing 5 VISUALISIERUNG a AA
16. dass der aktuelle Zielort erreicht wird wenn er erreichbar ist Es wird versucht auf direktem Weg zur Zielregion zu gelan gen Das hei t das nur horizontal bzw vertikal gegangen wird wenn sich der Roboter bereits auf H he der Zielregion befindet Anderenfalls wird der aheste Eckpunkt der Zielregion angestrebt Hindernisse im Weg des Roboters k nnen dazu f hren dass dieses umlaufen wird Mittels setTarget Position upperLeft Position lowerRight l sst sich der Taktik eine Zielregion zuweisen Genau dann wenn der Roboter sich nicht innerhalb der Grenzen dieser Region befindet wird eine Aktion angeboten um sich zu der Region hinzubewegen Ist eine Region einmal erreicht worden hat der Roboter sie also einmal betreten wird sie als Zielregion gel scht Alle Be rechnungen haben nur konstante zu vernachl ssigende Laufzeit Ebenso werden kaum Daten permanent gespeichert HeadFor UnexploredRegion Die IMovementTactic Taktik HeadForCloseUnexploredRegion dient zum Hin bewegen zu einer nahe gelegenen und aus Sicht des Roboters noch unexplorier ten Region die automatisch berechnet wird Die korrekte Benutzung der Taktik gew hrleistet dass eine unexplorierte Region erreicht wird sofern vorhanden und erreichbar Diese Taktik berechnet aus Griinden des Aufwands nicht die nahestgelegene Re gion stellt aber eine vern nftige Heuristik dar Zu der aktuellen Position wird der Knoten im Quadtree des Roboters ermittelt Innerhalb des Tei
17. die auf der Karte platziert werden werden in einem RegionQuadtree gespeichert Der Quadtree ist folgendermassen aufgebaut Er enth lt einen Wurzelknoten und jeder Vaterknoten bis zu vier Kindsknoten Jeder Blattknoten steht f r ein Hindernis auf der Karte Jeder Knoten steht f r einen Bereich auf der Karte Der Wurzelknoten enth lt die Information der gesamten Karte Abbildung 50 BESA Abbildung 50 Aufbau eines RegionQuadtrees Die Karte l sst sich aufteilen in vier kleinere Bereiche den nordwestlichen nord stlichen s dwestlichen und s d stlichen Bereich Diese Bereiche bilden die Kindknoten des Wurzelknotens dies l sst sich rekursiv weiter verkleinern Ein Knoten enth lt nur dann einen Kindknoten wenn sich in diesem Bereich ein Hindernis befindet Die Karte wird auf diese Weise soweit in Bereiche unterteilt bis ein Bereich so klein wie das kleinste Hindernis ist Befinden sich in allen vier Blattknoten ein Hindernis so wird der Bereich zu dem n chst gr seren zusammengefasst d h Die Blattknoten werden gel scht und der Vaterknoten wird zum Blattknoten dies spart Speicherplatz 86 6 5 Generator 6 EDITOR 6 5 Generator Da viele Strategien eine Menge von Karten brauchen wurde ein Werkzeuge ben tigt das die Generierung von Karten automatisch bernimmt Zu diesem Zweck wurde ein Generator entwickelt der ein Bestandteil des Editors ist und zwei Methoden Random function und File function zur Generierun
18. einzelner Roboter zu speichern und in die Karte zu zeichnen Damit die Speiche rung dieser abgelaufenen Wege findet statt in der Klasse VisitedPaths nicht zu platzbed rftig wird ist dieses Feature nur f r einzelne Roboter implementiert es ist also nicht m glich sich auf Knopfdruck s mtliche abgelaufene Wege anzei gen zu lassen Des weiteren wurde mittels eines simplen Tricks der Speicherbe darf zwar nicht minimiert aber immerhin leistbar gemacht Anstatt jeden ein zelnen Punkt zu speichern den der Roboter besucht hat werden nur diejenigen gespeichert die der Roboter bei einer Richtungs nderung besucht Zwischen diesen Punkten werden dann Linien gezeichnet Diese L sung ist simpel aber praktikabel dennoch gibt es zweifellos geeignetere Speicherungsm glichkeiten die zu implementieren allerdings aus Zeitgr nden nicht m glich war 5 2 6 3D Visualisierung In der 3D Ansicht wird die Szene h bsch aufbereitet damit man auch mal was nett anzusehendes zeigen kann Alle Informationen werden dabei aus den 2D Daten extrahiert und ggf um eine H heninformation erg nzt siehe Abschnitt 5 3 2 Es ist also kein echtes 3D man k nnte es 2 5D nennen Im vorletzten Satz steckt allerdings ein wichtiges Detail es sind schon die X und Y Werte gegeben In der 2D Ansicht gehen positive X Werte nach rechts und positive Y Werte nach unten Die Hindernisse w rden aus dem Bildschirm rauskommen H tten die Hindernisse positive Z Werte
19. teilt sich aus Be nutzersicht in zwei Teile auf Die zwei und die dreidimensionale Visualisierung Die zweidimensionale Visualisierung ist ideal zur Evaluierung von Strategien und Taktiken geeignet der Benutzer kann sich dort viele Details anzeigen las sen beispielsweise den bereits explorierten Teil der Karte Die dreidimensionale Visualisierung bietet eine attraktive Sicht auf die Roboter und die Karte 2 5 Editor Der Editor ist ein unerl licher Teil des Gesamtprojektes Mit diesem Werkzeug kann man komfortabel Karten Roboter und Bodenobjektkonfigurationen er stellen und bearbeiten Daran angebunden ist ein Generator der Karten mittels vieler verschiedener Parameter automatisch generiert oder sie aus Bilddateien ausliest und in ein f r den Simulator lesbares Format transferiert Mehr ber Features und zur Funktionsweise findet sich in Abschnitt 6 2 6 Messgr en Das Me gr en Framework ist ein Analysetool f r das Smartteams Projekt Mittels diesem Framework kann man eine reichhaltige Auswahl an Daten bei spielsweise ber Roboterbewegungen aufzeichnen und sich die Ergebnisse in der Form verschiedenartiger Graphen darstellen lassen Das erm glicht eine umfassende Analyse verwendeter Strategien und Taktiken Dokumentiert ist es in Abschnitt 7 3 SIMULATIONSKERNEL 3 Simulationskernel Dieses Kapitel beschreibt den Simulationskernel Zun chst wird ein kurzer berblick ber die Architektur gegeben im weit
20. Anforderungen an diese Auswahl wie beispielsweise die Notwendigkeit da bei Auswahl eines Roboters die Detailansicht aktualisiert wird werden in diesen Zugriffsopera tionen erf llt Ihre wichtigsten Methoden sind 1 public final synchronized void select Set lt extends Selectable gt selection W hlt Objekte aus M glich sind Objekte die das Interface Selectable implementieren das sind beim aktuellen Stand des Projektes Robot und Groundobject 2 public final synchronized void add Set lt extends Selectable gt selection Die bergebenen Selectables werden der Selektionsliste hinzugef gt 3 public final synchronized void remove Set lt extends Selectable gt selection Die bergebenen Selectables werden aus der Selektionsliste entfernt 4 public final synchronized void reset L scht die gesamte Liste von Selectables Bei all diesen Methoden wird sichergestellt da bei Selektion von Robotern oder Bodenobjekten die Anfragen an den Kernel ber Detailaktualisierung gestartet und bei Deselektion gestoppt wird 68 5 2 Wichtige Klassen 5 VISUALISIERUNG 5 2 3 2D Visualisierung Die 2D Visualisierung besteht im Wesentlichen aus der Map2D und dem Ter rain2D Die Map2D bernimmt dabei das zeichnen des Gel ndes der Roboter und der Bodenobjekte und bietet Funktionen wie Zoomen und Verschieben per Maussteuerung Das Terrain2D ist die zugeh rige Datenhaltungsklasse wel che die Bereichsanfragen auf dem i
21. Kartenausschnitte zusammengetra gen um festzustellen ob die gesamte Karte exploriert wurde Da k nnte man ansetzen und beim mergen der Karten an der Homebase jeweils den Robotertyp mit protokollieren HashMap RobotType robot int prozent Man k nnte dann anhand der RoboterID die Homebase aus der Roboter Datenstruktur her aussuchen und die HashMap jede x te Runde auslesen um die Werte im Ku chendigramm zu aktualisieren Im Prinzip ist jede neue Messgr e mit Erweiterungen in bereits bestehenden Datenstrukturen m glich Optional kann man eigene Datenstrukturen einf hren und v llig unabh ngig von bereits bestehenden Strukturen Daten sammeln Die Datenbeh lter m ssen nur observable sein siehe Abbildung 7 2 um MeasurmentContolGUI regis trieren zu k nnen Explorer 60 MultiRobot 20 Transporter 9 usw 93 8 AUSBLICK OFFENE PUNKTE 8 Ausblick Offene Punkte Die beschriebene Funktionalit t unserer Software wurde zwar umgesetzt doch einige Teile sind immernoch in einem ausbauf higen Zustand wobei hier als Beispiel das Teammanagement dienen k nnte Eine Erweiterungsm glichkeit w rde sich insoweit bieten da statt der bisherigen Zufallsentscheidungen kon krete Heuristiken implementiert werden k nnen Solche Baustellen sollte man en masse finden k nnen Bis jetzt sind unsere Datenstrukturen und die da mit verbundenen Algorithmen in der Lage eine Simulation mit 1000 Robo tern auf Karten
22. Nachrichten Es gibt also keine zentrale Stelle die den Aufbau der Teams organisiert die Roboter organisieren sich vielmehr eigenst ndig untereinander Entsprechend gibt es in jeder Taktik des Team managements auch 2 Methoden sendQueries und processQueries die die Aufgabe der Nachrichtenverarbeitung bernehmen Diese beiden Methoden werden in jeder Runde zuerst aufgerufen falls es Nachrichten zu verarbeiten bzw zu senden gibt Die Klassen Team und TeamConfiguration In diesem Abschnitt sollen nochmal kurz die beiden Klassen erl utert werden die beim TeamManagement eine gro e Rolle spielen die Klassen Team und TeamConfiguration Die Klasse TeamConfiguration umschreibt eine Team konstellation und ist im Grunde nichts weiter als ein 5 Tupel mit Gettern und Settern Bei der Initialisierung des TeamManagements wird die Datei TeamCon fig eml ausgelesen die sich im Verzeichnis resources befindet Daraus wird dann die aktuelle Teamkonfiguration erstellt Die Konfiguration kann nachtr glich jedoch mit der Methode setConfiguration aus der TeamBuildTactic ver ndert werden Die Klasse Team modelliert ein Team In der Klasse sind z B die aktuelle Kon stellation des Teams und auch die gew nschte Konstellation des Teams gespei chert Mit diesen Informationen lassen sich sehr einfach und schnell fehlende Ro botertypen deren Anzahl berechnen In der Klasse wird au erdem der aktuel le Teamanf hrer gespeichert Der Anf hrer h l
23. Punkt Argu ments VM Arguments folgender Eintrag gemacht werden Djava security policy project_loc security policy sonst fliegen Exceptions wegen des RMIs Weiterhin ist es empfehlenswert mehr RAM einzustellen mittels Xmx1G 95 Literatur Literatur Literatur 3D Lighthouse 3D Glsl tutorial http www lighthouse3d com opengl glsl Fis07 Matthias Fischer Vorlesung Algorithmen in der Computergrafik R umliche Datenstrukturen SS 2007 GHJV95 Erich Gamma Richard Helm Ralph Johnson and John Vlissides Design Patterns Addison Wesley Boston MA January 1995 Hol Vic Hollis 3d lens flare with occlusion testing http nehe gamedev net data lessons lesson asp lesson 44 Hun Jason Hunter Jdom http www jdom org KKF 04 Jan Klein Jens Krokowski Matthias Fischer Michael Wand Rolf Wanka and Friedhelm Meyer auf der Heide The randomized sample tree A data structure for interactive walk throughs in externally stored virtual environments PRESENCE 13 6 617 637 December 2004 The MIT Press Mor Mark Morley Frustum culling in opengl http www crownandcutlass com features technicaldetails frustum html Sam90 H Samet Design and Analysis of Spatial Data Structures Addison Wesley 1990 Tha00 Ulrich Thatcher Game Programming Gems chapter Loose Octrees Charles River Media 2000 96 Abbildungsverzeichnis Abbildungsverzeichnis Abbildungsverzeichnis Se A
24. SubAreaEzploredState Abb 24 Hinweis Die Strategie kommt bislang mit zwei wesentlichen Einschr nkungen die Aufgrund des zeitlichen Umfangs nicht mehr implementiert wurden konnten Der Fall dass ein Hindernis nicht ausserhalb der SubArea umgangen werden kann weil es an den Kartenrand grenzt wird nicht behandelt Weiterhin gibt 58 4 4 Strategien 4 ROBOTER MODUL es bislang noch Probleme mit dem korrekten setzen der ObstacleCheckpoints wenn ein Stripe direkt bzw mit Toleranz des Bewegungsradius auf dem Rand eines Hindernisses verl uft 4 4 3 ExplorationGreedStrategy Bei dieser Strategie ist das Ziel die Erkundung der Karte dementsprechend eig net sich diese f r Roboter vom Typ Multirobot oder Explorer Zu Beginn wird eine Richtung zwischen 0 und 359 Grad mit einem Zufallsgenerator erzeugt Es wird im Konstruktor der Klasse eine Bewegungsaktion Elementary Action Move erstellt bei der die Richtung dem generierten Winkel und die Geschwin digkeit der maximal zul ssigen Geschwindigkeit des Roboters entspricht Diese Bewegungsaktion wird in eine Liste der Roboteraktionen ActionList hinzu gef gt Als erstes wird nun berpr ft ob mit der aktuellen Position Richtung und Geschwindigkeit des Roboters der Kartenrand erreicht bzw berschritten wird Falls dies der Fall ist so wird nun in einer while schleife eine neue Richtung generiert und anschlie end berpr ft ob unter Einbehaltung dieser Richtung die Bewegung auf de
25. Texturierung per Shaderprogramm Dazu wird eine Oberfl chentextur anhand der xy Koordinaten von oben auf die Hindernisse projiziert und eine H hentextur anhand der z Koordinate von der Seite an die Hindernisse projiziert Die Shaderprogramme sind in GLSL 3D geschrieben und sind so einfach dass sie keiner Erkl rung bed rfen Kann das Shaderprogramm nicht geladen werden z B weil die Grafikkarte zu alt ist so wird automatisch eine optisch nicht ganz so sch ne Methode von OpenGL verwendet die ohne Shaderprogramme auskommt Fallbackmodus Dieser Fallbackmodus verwendet glTexGen zur Erzeugung der Texturkoordina ten und texturiert nur mit der H hentextur 71 5 2 Wichtige Klassen 5 VISUALISIERUNG Roboter Sch tze und Flags Die Roboter die Sch tze und die Flags liegen als obj Datei vor und werden mit Hilfe des OB JLoaders beim Start der Visua lisierung geladen Da die Roboter aus bis zu 917 Polygonen bestehen wurden zus tzlich zu den Robotern verschiedene Level Of Detail Stufen modelliert die in Abh ngigkeit der Distanz zwischen Roboter und Kamera gew hlt werden Abbildung 36 zeigt die f nf Robotertypen EL gt Abbildung 36 Die Robotertypen Relais Explorer Worker Multirobot und Transporter von links nach rechts Kamera und Userinteraktion Die Klasse CameraAndMouse ist f r alles zust ndig was mit der Position der Kamera in der Szene und deren Beeinflussung durch den Benutzer zu tun hat Zu allererst ist
26. das Pro tokoll RMI vgl 3 4 abgewickelt Messages wie wir sie verstehen behandeln hingegen die generelle logische Information welche wir zur Kommunikation zwi schen Kernel und einem Visualisierungsmodul benutzen Aus dem Message Typ den darin enthaltenen Daten und u U der jeweiligen Nachrichtenprotokollphase wird die jeweilige konkrete Handlung abgeleitet 3 2 Simulationsabwicklung und verwaltung 3 SIMULATIONSKERNEL Folgende Message Typen werden benutzt Messagetyp Bedeutung Richtung ChangeSimulationSpeed Fordert den Kernel auf die iibergebene Mindestrundenzeit zu benutzen In PauseSimulation Fordert den Kernel auf die Simulation zu pausieren In Register Fordert den Kernel auf eine Visualisierung zu registrieren und das Nachrichten protokoll zu initiieren In Unregister Fordert den Kernel auf eine Visualisierung aus der Registrierung zu l schen In Out StartDetailPushing Fordert den Kernel auf Detailinformationen zu bestimmten Objekten zu liefern In StartResumeSimulation Fordert den Kernel auf die Simulation fortzusetzen In StopDetailPushing Fordert den Kernel auf bestimmte Detail informationen nicht mehr zu senden In StopSimulation Fordert den Kernel auf die Simulatin zu beenden In StartExplorationQuadtree Fordert den Kernel auf das bisher Pushing erkundete Gebiet eines Roboters zu bertragen und nach Merges geg erneut zu bertragen In Sen
27. der Homebase enth lt RoboterkonfigurationsGlll Abbildung 49 Aufbaue der RoboterkonfiguratiosnGUI Beim Neuerstellen einer Roboterkonfigarution New Button bet tigen werden alle Zeile aus der Tabelle gel scht und anschlieSend die Zeile die die Informa tionen der Homebase enth lt mit Defaultwerten eingef gt Beim Einf gen einer anderen Roboterkonfiguration zu der aktuellen Add Button bet tigt wird die entsprechende xml Datei ge ffnet die Informa tionen daraus gelesen und entsprechend als Zeilen in die Tabelle eingef gt Die 85 6 4 Datenstruktur 6 EDITOR Eigenschaften der Homebase ndern sich nicht Beim Laden einer Roboterkonfiguration Load Button bet tigt werden alle Zeilen der aktuellen Tabelle komplett gel scht Dann werden alle Informatio nen aus der ausgew hlten xml Datei gelesen und entsprechend als Zeilen in die Tabelle eingef gt Die Eigenschaften der Homebase ndern sich auch wo bei die Position nicht ge ndert werden kann Damit wird verhindert dass die Homebase in einem Hindernis steht Beim Speichern der Roboterkonfiguration Save Button bet tigt wird eine neue xml Datei mit den Daten aus der Tabelle erstellt Die Informationen der Ta belle werden Zeilenweise ausgelesen 6 4 Datenstruktur Der Editor benutzt zwei verschiedene Datenstrukturen 1 Liste Alle Sch tze die auf der Karte platziert werden werden in einer LinkedList gespeichert 2 Quadtree Alle Hindernisse
28. der SubArea treffen kann erreicht sie erneut den Ausgangspunkt A An dieser Stelle existiert in jedem Fall eine gerade Anzahl von ObstacleCheckpoints womit die innen liegenden Segmente des Stripes als exploriert markiert werden k nnen Nun weiss die Strategie dass das Hindernis bekannt ist und kann es direkt umrun den CirculateObstacleState Abb 24 um ab Punkt B den Rest des Stripes zu erkunden Die Frage ist nun was passiert wenn die Strategie den letzten Stripe in der zuvor 57 4 4 Strategien 4 ROBOTER MODUL Abbildung 28 Beispiel zum Verlassen der SubArea und Erkunden von abge trennten Bereichen beschreibenen Weise abgelaufen hat Hier brauchen wir nun die BorderCheck points Wir gehen in diesem Fall immer zum zuletzt gesetzten BorderCheckpoint zur ck Move ToNextBorderCheckpointState Abb 24 In Abbildung 28 ist das Punkt A Von hieraus wird das Hindernis ausserhalb der SubArea umrundet Circulate ObstacleOutsideAreaState Abb 24 bis an Punkt B wieder die SubA rea betreten wird und ein neuer BorderCheckpoint gesetzt werden kann Wie zuvor wird das Hindernis entlanggegangen MoveBackwardAlongObstacleState Abb 24 bis zum Auftreffen auf den n chsten Randpunkt C Nachdem zum Aus gangspunkt B zuriickgekehrt wurde kann mit dem normalen Explorieren die ses Unterabschnittes fortgesetzt werden Dieses Verfahren wird analog fiir den verbleibenden Unterabschnitt angewandt Danach ist die SubArea vollst ndig exploriert
29. einem gewissen Thresh hold default 32m heraus und speichere Sie in einem zweiten Quadtree siehe Abbildung 38 Hieraus werden die Monuments Der briggebliebene Debrisquadtree beschreibt die Schutth gel 4 L se bei beiden Quadtrees die Ecken von Hindernissen auf 0 5mx0 5m auf Unterteile weiterhin solche Randbl tter die die maximal angegebene Randgr e berschreiten solche die mit mehr als einer Seite am Rand liegen und solche von denen mindestens eine Seite nur teilweise am Rand liegt siehe Abbildung 39 74 5 3 Preprocessing 5 VISUALISIERUNG PO y 7 MN y Hit Nicht markiert Markiert Aktiv Noch zu bearbeiten 7 gt Abbildung 38 Zusammenh ngende Hindernisstrukturen finden gt i O Imxim Abbildung 39 Hindernisstrukturen an den Ecken h her aufl sen 5 Balanciere den Quadtree d h sorge durch Unterteilen daf r dass die Gr en zweier benachbarter Bl tter sich nie um mehr als den Faktor zwei unterscheiden siehe Abbildung 40 FA FA gt Abbildung 40 Quadtree balancieren 6 Berechne bei beiden Quadtr
30. ge letzte usere Zeile hinzu f Berechne innere Zellen i Berechne rekursiv usere Zellen mit geringerem Radius g Entferne illegale Positionen Wichtig hierbei ist zu erkennen dass die Annahme ein Roboter befin de sich immer im Mittelpunkt einer Zelle zum Verschieben des eigent lichen Sicht bzw Kommunikations Quadrates f hrt Dadurch kann der Fall entstehen dass Roboter nicht ermittelt werden da sie von vornherein als unerreichbar gelten oder dass zuviele Zellen unn tige Schnittzellen berpr ft werden Eine Performanceerh hung bringt diese Verwaltung lediglich erst ab einer hohen Roboterzahl und einigermasen guten Verteilung ber die gesamte Karte 3 3 Datenstrukturen Um die Karte und die Sch tze auf der Karte mit geringer Platz und Zeitkom plexit t zu speichern w hlten wir jeweils verschiedene Implementationen der Datenstruktur Quadtree vgl Sam90 Diese sind in den folgenden Abschnit ten vorgestellt 3 3 1 Quadtree f r Speicherung der Map Die Anforderungen an die Datenstruktur zur Speicherung der Karte sind die folgenden 1 Es soll ein groses Gel nde im Speicher gehalten werden k nnen also spielt Platzeffizienz eine wichtige Rolle 2 Sie soll die M glichkeit bieten das Gel nde aus einer gegebenen XML Struktur zu parsen 3 Sie mus sehr viele Bereichsanfragen in der Form Welche Hindernisse befinden sich in dem Rechteck R innerhalb kurzer Zeit exakt beantworten k nnen Posi
31. ii es gt eee ee m 15 16 Lis 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 Illustration des Modells 2 2 Coon nn 2 Die Architektur des Gesamtsystems 2 222222 5 Die Architektur des Simulationskernels 22 2 2220 7 Protokoll bei Verf gbarkeit der Karte auf Visualisierungsseite 12 Protokoll bei fehlender Karte auf Visualisierungsseite 13 Beispielaufteilung eines Terrain in Zellen 2 22 2 14 Beispiel f r einen RegionQuadtree 2 22 2 17 Quadtree mit Nachbarschaftsbeziehung vor Zellteilung 18 Quadtree mit Nachbarschaftsbeziehung nach Zellteilung 19 Aufbau eines PRQuadtrees 2 2 2 mn nn 20 Kl ssen bersicht os iaa bd und si herren 20 Aufbau links und Aktionszyklus des Roboters rechts 22 Wesentliche Klassen des Roboter Moduls 23 Vermeidung von Kollisionen mit Hindernissen links und Robo term mechta coria hee ee Ghee th eee CSS we eed 25 Funktionsweise der StaticMap 2 26 DynsmieDstalist x 2 22 2 2223 m Ss Seen ww he 27 UML Klassendiagramm des Taktik Konzeptes 32 SidestepRobotEvasion mit Parameterwert AngularRight l sst Roboter schr g aneinander vorbeigehen 42 Exemplarisches Vorgehen der Taktik WalkAlongBoundaries 43 Protokoll beim Teamaufbau i s s e ze pa art asus 48 Die Auktion bei der Teambildung
32. neue Endung v2d bzw v3d unterscheidet 5 3 1 2D Gel nde Der Einstiegspunkt zum Preprocessing des 2D Gel ndes ist der Konstruktor Terrain2D InputStream regionXml Dieser bekommt die XML Beschreibung parst ein paar Metadaten und ruft dann die Methode fromXML des Terrain Quadtree auf welcher die eigentliche Arbeit erledigt Die Knoten des TerrainQuadtree werden bottom up anhand der XML Baumstruktur erzeugt Als einzige zus tzliche Berechnung muss der Grauwert eines Knotens berechnet werden Dazu wird die schwarze Fl che der Kindsknoten gemessen in Quadtraten der Gr e 1x 1 Meter aufsummiert und durch die gesamte Fl che des Quadtreeknotens geteilt 5 3 2 3D Gel nde Der Einstiegspunkt zum Preprocessing des 3D Gel ndes ist der Konstruktor Terrain3D Terrain2D terrain2d Hier laufen folgende Schritte ab e bernehmen einiger Metadaten aus dem Terrain2D 73 5 3 Preprocessing 5 VISUALISIERUNG e Erzeugung der 3D Hindernisse mittels QuadtreeMonumenter Ausgabe Dreiecke und Steine als TerrainData3D e Konvertierung der TerrainData3D in Listen aus PreprocessingTriangles und PreprocessingStones e Einsortierung dieser Daten in einen Preprocessing TerrainOctree e Konvertierung des PreprocessingTerrainOctree in den speicherplatzopti mierten Terrain Octree Beachte in fast der ganzen Visualisierung ist die Z Komponente der 3D Vektoren lt 0 Grund siehe Abschnitt 5 2 6 3D Visualisierung Genauer im
33. performAction dieser Taktik verwen det wird kann das L schen des Wegs an der Basisstation ggf linerare Lauf zeit in Abh ngigkeit zur L nge des Wegs haben auch abh ngig von Java Implementierung Der Speicherplatzbedarf ist linear abh ngig von der Anzahl ausgef hrter Bewegungsaktionen nach dem letzten Aufladen der Energie 4 4 Strategien Der berwiegende Teil der Strategien ist noch in den Kinderschuhen Da der Fokus der Projektgruppe auf der Fertigstellung des Simulators stand konnte nur in Grenzen die Konzentration auf das Entwickeln elaborierter Strategi en gerichtet werden Die bislang erzielten Ergebnisse werden in den folgenden Teilkapiteln vorgestellt 4 4 1 DividedExplorationStrategy Die DividedExplorationStrategy stellt eine Explorer Strategie zur Explora tion der gesamten Karte dar Die Strategie ist streng taktikbasiert und verfolgt f r jeden Explorer im Groben folgendes Konzept e Die Karte wird imagin r in eine Anzahl an Regionen unterteilt die der Anzahl an Explorern entspricht e Zu Beginn geht der Explorer zu einer durch seine ID eindeutig definierten Region e Diese Region soll von dem Explorer vollst ndig exploriert werden e Er geht dann zu einer von ihm aus nahe gelegenen und entsprechend seinem Wissen noch nicht vollst ndig explorierten Region und hilfrt dort beim Explorieren e Dieser Vorgang setzt sich fort bis alle Regionen exploriert sind 53 4 4 Strategien 4 ROBOTER MODUL H
34. so bek me man ein linksh ndiges Koordinatensystem OpenGL erwartet aber ein rechtsh ndiges Um das nicht zur Laufzeit immer umrechnen zu m ssen haben wir folgende etwas unintuitive aber notwendige Entscheidung getroffen X in 2D entspricht X in 3D Y in 2D entspricht Y in 3D Z in 3D ist negativ Das Rendering ist mit der Map3D in der Visualisierung verankert Die wich tigsten Klassen und Konzepte sind stecken aber in den folgenden Punkten 70 5 2 Wichtige Klassen 5 VISUALISIERUNG Rendering des Gel ndes Im Preprocessing siehe Abschnitt 5 3 2 wird das Gel nde in gr ere Hindernisse Dreiecke und Steine sich wiederholende In stanzen einiger weniger 3D Stein Modelle unterteilt und in einen Octree einsor tiert Zur Laufzeit werden diese Daten aus der Klasse TerrainOctree ausgelesen Diese Klasse ist bewusst nur aus primitiven Datentypen statt Objekten zusam mengesetzt da sich gezeigt hat dass mit Objekten z B ArrayList statt Array oder f r jedes Dreieck ein Objekt o der Speicherbedarf sehr stark ansteigt Genutzt werden diese Daten vom TerrainRenderer Dieser durchl uft den Ter rainOctree in preorder und rendert alle Dreiecke und Steine die in den durchlau fenen Knoten gespeichert sind Da das Gel nde deutlich mehr Dreiecke enth lt als die Grafikkarte zeichnen kann darf nur eine kleine Menge der Dreiecke ge zeichnet werden Daher wird vor dem rekursiven Abstieg in einen Teilbaum berpr ft ob es sich
35. sowohl Nachrichten von Roboter zu Roboter als auch Nachrichten zu einer oder mehrer Visualisierungseinheit en 3 2 1 Multithreading Das Multithreadingkonzept ist ein Schl sselkonzept in unserem Simulations programm Letztlich ist dieses f r eine angemessene Simulationsgeschwindigkeit verantwortlich denn es erlaubt eine vollst ndige Auslastung eines Dual Kern Prozessors Benutzt wird es innerhalb der sequentiellen Abarbeitungsreihenfolge des Ker nels und parallelisiert die gesamten Roboteraktionen Um solch ein System nut zen zu k nnen ist es wichtig in der Ladephase der Simulation die Roboterein heiten entsprechend in in unserem Falle bislang zwei Teilpackete aufzuteilen Diese Zuordnung wird einmalig von der jeweiligen Roboterverwaltung get tigt Hier muss sichergestellt werden dass sich dies nicht mehr ndert ansonsten 3 2 Simulationsabwicklung und verwaltung 3 SIMULATIONSKERNEL k nnen Fehler durch gleichzeitigen Mehrfachzugriff auf eine Datenstruktur auf tretten Bei der Umsetzung wurden Konditionen f r die Threads formuliert um einen verklemmungsfreien und problemlosen Ablauf sicherzustellen Dabei folgen die Arbeitsthreads folgender Kondition if muter 2 then notifyall else if mutex lt 2 then wait Der Hauptthread hingegen aus welchem die Arbeitsthreads immer gestartet werden folgt lediglich der Kondition if mutex lt 2 wait Es ist leicht einzusehen dass hierbei die logische Bedingung ledig
36. vertreten durch einen Quadtree mit 1 3 Millionen Bl ttern zu erm glichen Dennoch k nnen einige Algorithmen sowie einige Datenstrukturen verbessert werden um die Leistungsf higkeit des Simulators zu verbessern Man k nnte zum Beispiel eine Parallelisierung des Systems in Erw gung ziehen um die M glichkeit zu geben die Simulation auf mehrere Rechner zu verteilen oder einzelne Roboter in Threads auszulagern Ein anderer Ansatz ist die Entwick lung und Erprobung von Strategien und Taktiken f r die Roboter wobei dem Benutzer auch ein elegantes Framework zur Verf gung steht Interessant w ren zum Beispiel Algorithmen die in der Lage sind gezielt Hindernisse zu umrun den und das auch ermitteln zu k nnen oder eine Strategie die die vollst ndige Erkundung einer Karte garantieren kann Genauso k nnte man auch versuchen die grafischen Features aus dem 2D ins 3D zu bertragen und es bieten sich fast unendlich viele neue M glichkeiten der Visualisierung von Details der Roboterstrategie zuk nftig geplante Wegpunkte Nachrichtenverkehr Roboter eines Teams Nat rlich er ffnen neue Taktiken und Strategien auch neue M glichkeiten wichtige Daten daraus in den Messgr en zu visualisieren Den Simulator und weitere Informationen erhalten Sie auf der Website http www upb de cs smartteams 94 A PROJEKT IN ECLIPSE EINBINDEN A Projekt in Eclipse einbinden Soll das Projekt aus dem CVS in Eclipse eingebunden werden so si
37. 008 09 statt Sie hatte das Ziel einen Software Simulator f r einen Schwarm von Robotern zu entwickeln In diesem Kapitel wird das Thema zun chst motiviert und danach die Ziele f r das Projekt vorgestellt Darauf aufbauend wird nachfolgend ein formales Modell beschrieben Zuletzt findet sich noch eine Auflistung des Projektteams 1 1 Motivation Stellen wir uns ein Szenario vor in dem ein Team von Explorationsrobotern wir nennen es ein Smart Team sich selbst organisieren muss um ein unbe kanntes Terrain zu erkunden und darin bestimmte Aufgaben zu erledigen Das Thema ist von gro em wissenschaftlichen und wirtschaftlichen Interesse Prak tische Anwendungen sind z B Rettungseins tze in einem schwer zug nglichen Gel nde sowie Expeditionen im Ozean oder auf einem fremden Planeten Zur Entwicklung von lokalen verteilten Algorithmen zu Steuerung des Roboterver haltens kann ein Software Simulator eine gro e Hilfe sein Beim Entwurf eines solchen Simulators gibt es zwei wesentliche Herausforderungen Die erste Her ausforderung ist dass Roboter nur beschr nktes lokales Wissen ber den globa len Status des Systems haben Daher muss der Simulator f r jeden Roboter eine individuaelle abstrahierte Sicht des Terrains anbieten Angenommen in einem Terrain wird jedes Hindernis durch vier 32 bit float Werte x y Koordinate L nge Breite gespeichert Bei 1 Millionen Hindernisen und 1000 Robotern w rde dies bereits ein Datenvolumen von
38. ActionList werden alle einem Ro boter zu Verf gung stehenden Elementaraktionen der Simulation mitgeteilt falls der Roboter beabsichtigt diese auszuf hren Die ActionList ist eine Da tenstruktur die erm glicht Aktionen einzuf gen Aktionen entfernen oder auch gannze Intervalle von Aktionen einf gen bzw entfernen Folgende Methoden werden bereitgestellt e int size Ermittelt die Anzahl an Aktionen in der Liste e boolean isIdle Indiziert ob der Roboter nichts zu tun hat d h die Liste ist leer e ElementaryAction getNextAction Gibt die n chste Elementaraktion ausschliesslich zu Informationszwecken zurueck 38 4 2 Strategie und Taktikkonzept 4 ROBOTER MODUL e List lt ElementaryAction gt getActionInterval int from int to Gibt einen Vektor mit den Elementaraktionen aus dem Intervall von from bis to zurueck falls moeglich Ist ein Teil des Intervalls nicht vorhanden wird nur der vorhandene Bereich zurueckgegeben e appendAction ElementaryAction elemAction Fuegt eine ganz konkrete Elementaraktion hinten an die Aktionsliste an e insertAction ElementaryAction elemAction int index Fuegt eine ganz konkrete Elementaraktion an die Stelle index in der Aktionsliste ein e appendActionList ActionList actionList H ngt die bergebene Action List an die bestehende an e insert ActionList ActionList actionList int index Fuegt die uebergebene ActionList in die bestehende zwischen index und index 1 ein
39. Around mit dem Unterschied dass hier die Hindernisse links herum umkreist werden RandomObstacleEvasion Die Taktik RandomObstacleEvasion dient dem Ausweichen von Hindernissen In der Methode hasAction wird gepr ft ob eine Kollision bevorsteht Wenn ja wird die Methode randomObstacleEvasionManeuver aufgerufen die als Pa rameter die Richtung und Geschwindigkeit des Roboters enth lt Die Methode ermittelt aus 24 Richtungen die zwischen 0 und 345 Grad liegen diejenigen die keine Kollisionen darstellen Aus den G ltigen Richtungen wird nun eine zuf llig gew hlt die dann die die neue Richtung des Roboters darstellt An schlie end wird eine Bewegungsaktion mit der neuen Richtung erzeugt In der 43 4 3 Taktiken 4 ROBOTER MODUL Methode performActon wird die aktuelle Bewegungsaktion durch die neue ersetzt so dass der Roboter jetzt auch die neue Richtung verfolgt Weitere Taktiken im CollisionDetector 4 3 2 HeadForLocations Die Taktiken in HeadForLocations dienen dazu bestimmte Regionen anszu streben Das Anstreben funktioniert grunds tzlich so dass versucht wird den direkten Weg zur Zielregion zu nehmen etwaige Hindernisse im Weg des Ro boter werden mit der integrierten Taktik WalkAlongBoundaries siehe oben umlaufen HeadForRegion HeadForRegion ist eine ITargetMovementTactic Taktik und dient zum Hin bewegen zu einer bestimmten selbst zu definierenden Region Die korrekte Be nutzung der Taktik gew hrleistet
40. BaseState Roboter bewegt sich zu HomeBase e UnloadTreasureState Sch tze abladen Zu Beginn der Simulation befindet sich der Roboter im Zustand Search Tre asureState Dabei wird die Karte erkundet mit dem Ziel Sch tze die bereits von einem Roboter vom Typ Worker oder Multirobot abgearbeitet wurden und zum Abtransport bereit liegen zu finden Falls der Roboter bei der Erkundung der Karte auf solchen Schatz trifft d h in seinem Sichtradius befindet sich ein Schatz wechselt die Strategie in den Zustand WalkToTreasureState So bald die Position des Schatzes erreicht ist wechselt die Strategie in den Zustand LoadTreasureState In diesem Zustand werden nun pro Runde eine bestimmte Menge an Schatzeinheten in den Container des Roboters geladen In jeder neu en Runde wird berpr ft ob der Container bereits voll geladen ist So bald dies der Fall ist wechselt die Strategie in den Zustand WalkToHomeBaseState In 62 4 4 Strategien 4 ROBOTER MODUL diesem Zustand befindet sich der Roboter auf direktem Wege zu der Homebase In jeder Runde wird gepr ft ob die Position der Homebase bereits erreicht ist Falls auf dem Weg Hindernisse auftauchen werden diese mit Hilfe der Taktik WallkAlongBoundaries umgangen und es wird weiterhin die Position der Ho mebase angestrebt So bald die Homebase erreicht ist wechselt die Strategie in den Zustand UnloadTreasureState Nun werden in jeder Runde eine bestimmte Menge an Schatzeinheiten abgeladen Die
41. ERNEL Kernel Visualization Lo _________ Sende InitTerrain Nachricht _ _________ gt Loose sende Terraininitialized _ ____________ Eee a senge dl a rae MA ALA wenn Kernel pausiert sende SimulationPaused _____ a sende SimulationSpeedChanged T P a gt lt SSS lee see ssa Abbildung 4 Protokoll bei Verf gbarkeit der Karte auf Visualisierungsseite 12 3 2 Simulationsabwicklung und verwaltung 3 SIMULATIONSKERNEL Visualization 8 3 5 ln 12 iF 9 3 IB gt 7 ig 10 12 IQ gt Y JE k sende TerrainRequest i de TerrainD I sende TerrainData Pe SSS SSS Tem Pe eS SSS gt sende Terrainlnitialized PAT ee Se ee sungen sende InitScene Tree sun en gt pias wenn Kernel pausiert sende SimulationPaused_____ _ _ gt i i sende SimulationSpeedChanged gt Vv Vv Abbildung 5 Protokoll bei fehlender Karte auf Visualisierungsseite 13 3 2 Simulationsabwicklung und verwaltung 3 SIMULATIONSKERNEL 4 Generierung der RobotInit Nachricht 5 Sicherstellen einer kontinuierlich gleichbleibenden Ordnung der Roboter Um eine einheitliche und somit auch leicht testbare Basis an Grundeigen schaften sicherzustellen wurden diese Aufgaben als abstrakte Oberklasse ab gelegt Somit miissen konkrete Roboterverwaltung
42. Ein Roboter r der austreten will teilt es seinem Anf hrer mit der Nachricht TM_LEAVE mit Frh lt dieser so eine Nachricht best tigt er sie grunds tzlich mit der Nachricht TM ACK LEAVE und nimmt den Roboter aus dem Team raus Der Roboter 49 4 3 Taktiken 4 ROBOTER MODUL r erh lt wiederum die Best tigung und tritt seinerseits aus dem Team aus Der Automat der das Verhalten modelliert ist in Abbildung 22 dargestellt leave ack_leave ack_leave C gt GL ei ack_leave KPY ade leave Abbildung 22 Protokoll beim Verlassen eines Teams ack_leave Der Algorithmus if messagesWaiting processQueries if leaveTeam sendQueries Wie auch bei der TeamBuildTactic schaut auch hier die Taktik zuerst nach ob es Nachrichten gibt die verarbeitet werden m sen wird durch die boole sche Variable messagesWaiting indiziert Ist dies der Fall wird die Methode processQueries aufgerufen Im zweiten Schritt wird berpr ft ob Nachrich ten verschickt werden m ssen Dies ist der Fall wenn die boolesche Variable leaveTeam true ist In dem Fall wird die Methode sendQueries aufgerufen processQueries 1 Gehe alle Nachrichten durch 2 Kommt dabei ein Austritt LEAVE aus dem Team und ich bin der Tea manf hrer schicke eine Best tigung ACK_LEAVE und nimm den Ro boter aus dem Team Bin ich der einzige Roboter dann l5e das Team auf 50 4 3 Taktiken 4 ROBOTER MODUL 3 Kommt eine B
43. Ergebnismenge zur ckgeben Dieser Algorithmus arbeitet sehr effizient Auch bei einer Simulation mit einer groSen Karte und einer hohen Roboteranzahl also einer entsprechend grosen Datenstruktur und sehr vielen Anfragen da die Roboter je nach Strategie nahezu immer mindestens 2 Bereichsanfragen pro Runde machen erh ht sich dementsprechend die Anzahl der Anfragen ist die Berechnungszeit dieses Algo rithmus laut Profiling Ergebnissen in der Gesamtsimulation vernachli ssigbar Dieser Quadtree hat im Gegensatz zu einer normalen Quadtree Implementierung die Eigenschaft das jede Blatt Zelle ber ihre Nachbarzellen informiert ist Dies erm glicht es Algorithmen zur Wegberechnung auf dem Quadtree laufen zu las sen Die Nachbarschaftsbeziehungen werden beim erstellen des Quadtrees berechnet Dabei werden nach einer Zellteilung zuerst die vier neuen Zellen untereinander verbunden bevor alle Nachbarn des Vaterknotens bearbeitet werden und den entsprechenden Kind Knoten zugeordnet werden Nach dieser Operation kennt der Eltern Knoten keine Nachbarn mehr Dies ist eingef hrt worden damit die Gr e des Quadtree nicht berhand nimmt NO ww gt Abbildung 8 Quadtree mit Nachbarschaftsbeziehung vor Zellteilung Im Sourcecode befindet sich die Implementation des RegionQuadtrees im Packa ge de upb smartteam kernel und zwar in den Klassen 18 3 3 Datenstrukturen 3 SIMULATIONSKERNEL
44. Kernel GUI nachgesehen werden 21 4 ROBOTER MODUL World gt Umgebungsdaten k 4 1 V ermitteln 4 Actuators Sensors Aktion Eigene Karte ausf hren aktualisieren Tactics extendable o Strategy exchangeable Nachrichten 4 Ziel und n chste a gt versenden Aktion berechnen Abbildung 12 Aufbau links und Aktionszyklus des Roboters rechts 4 Roboter Modul In diesem Kapitel werden Architektur wesentliche Bausteine Strategie und Taktikkonzept sowie die bislang existierenden Taktiken und Strategien beschrie ben Grunds tzlich basiert der Roboter auf einer unver nderbaren Komponente die mit ihrer Umgebung mittels Aktoren und Sensoren interagiert Dadurch wer den die physikalischen Eingenschaften des Roboters simuliert Eine austausch bare Strategie steuert das Verhalten des Roboters Es hat Zugriff auf ein Da tenmodul indem alle relevanten Daten ber die Umwelt gespeichert werden und auf ein Taktikmodul das eine vordefinierte erweiterbare Menge an Takti ken zur Verf gung stellt Abstrakt betrachtet entspricht dies dem Schaubild in Abb 12 links Durch diese Trennung zwischen der physikalischen Einheit des Roboters und seiner Strategie wird erm glicht zu garantieren dass der Roboter sich niemals inkorrekt verh lt w hrend er seinen Main Loop ausf hrt Dieser zyklische Prozess ist schematisch dargestellt in Abb 12 rechts und wird im folgenden Kapitel ber die Architektur detaillierter abge
45. Menge die pro Runde abgeladen wer den kann ist durch die Gr e der Abladeschaufel definiert Diese Gr e kann in der xml Datei zu den Robotereigenschaften unter BucketPutSize eingestellt werden So bald der Container leer ist wechselt die die Strategie in den Zustand WalkToTreasureState falls beim verlassen der Schatzposition noch transportier barer Schatz vorhanden war Wenn beim verlassen der Schatzposition jedoch die letzten Schatzeinheiten mitgenommen wurden wechselt die Strategie in den Zustand Search TreasureState In Abbildung 31 ist ein Zustandsautomat mit den zugeh rigen Zust nden und berg ngen dargestellt Gehe zu Schatz Verfolge Weg weiterhin Keine Sch tze in Sichtradius Sch tze in Sichtradius nicht leer noch nicht erreicht Erkunde Karte Container leer kein Schatzrest an Schatzposition Erkunde Karte Treasure State Schatz verschwunden Erkunde Karte Schatz erreicht Lade Schatz Container leer und Schatzrest vorhanden Laufe zu Schatz Container nicht voll amp Schatz vorhanden Lade Schatz Container nicht leer Lade Schatz ab Unload Treasure State Homebase erreicht Lade Schatz ab WalkTo Homebase State Homebase nicht erreicht Gehe weiter Abbildung 31 Zustamdsautomat von der Transporter Strategie Container voll kein Schatz vorhanden Gehe zu Homebase 63 5 VISUALISIERUNG 5 Visualisierung In diesem Ka
46. Methoden entwickelt und umgesetzt werden die eine Kommunikation zwischen den Robotern gew hrleisten auch wenn sich diese in grosser Entfernung befin den Das setzt voraus das mobile Relay Stationen an bestimmten Stellen eingef gt werden und Funksignale weiterleiten 3D VISUALISATION Die Bem hungen der Roboter im Gel nde sollen in 3D Grafik den Interessenten vorgestellt werden Es entsteht Bedarf f r eine sch ne Echtzeit Visualisierung All diese Strategien werden nicht zentral koordiniert die Roboter sind selber f r die Organisation verantwortlich Damit das Kommunikationsnetzwerk und die Computer der Roboter nicht mit Daten berlastet werden sollten entwickel te Strategien effizient verteilt und lokal Arbeiten d h mit einer beschr nkten Sicht auf den Zustand des Systems auskommen Die so erarbeiteten L sungen werden nicht unbedingt optimal sein daf r k nnen die Roboter autonom agie ren und k nnen auch im Fall des Ausfalls Ihrer Kollegen weitermachen Es war gefordert ein komplettes System zu erstellen welches sich aus den dar gestellten Komponenten zusammensetzt Es war nicht nur Softwaretechnische Arbeit am System gefordert sondern auch konzeptionelle Mitwirkung an der Entstehung der Strategien MA 4 Treasure Obstacle omg D ES Robot Home ie View Radius vA Comm Radius 1 3 Modell Abbildung 1 Illustration des Modells Die wesentlichen Elemente des Modells sind in Abbildu
47. Mittelsenkrechte zu anderen Robotern heranfahren Dadurch k nnen sich Roboter nicht treffen denn alle halten sich an dieses Prinzip Fiir Roboter mit Abstand maximal doppelt so gro wie die maximale Geschwindigkeit des Robo ters plus 2 mal 12 5 cm wird eine Schnittpunktberechnung der Bewegung mit der Mittelsenkrechte durchgef hrt Vor dem n chsten Schnittpunkt bleibt der Roboter stehen Abb 14 rechts Performance Tests haben untermauert dass die Kollisionsvermeidung nur einen Bruchteil der Berechnungen eines Roboters darstellt in den Tests im Bereich von 1 4 1 3 RobotData und Wegberechnung Im Package RobotData data sind die Daten gekapselt die vom Roboter ben tigt werden um Berechnungen des n chsten Schrittes durchzuf hren W h rend der Evaluierungsphase greift die PhysicalUnit Package physical schrei bend auf die RobotData zu und aktualisiert die statischen und dynamischen Ob jekte sowie die eingegangenen Nachrichten W hrend der Aktionsphase greift die Strategie Package strategy dann auf die RobotData zu und holt sich notwendige Daten um den neuen Schritt zu berechnen Folgende Daten geh ren in die RobotData die StaticMap in der alle stati schen Objekte gespeichert werden in unserem Fall beschr nkt sich das nur auf Hindernisse die DynamicMap in der dynamische Objekte gespeichert werden Roboter und Flags der Container in dem Sch tze und andere Bodenobjekte abgelegt werden k nnen und die MessageMemory
48. Position des Roboters Methoden zur Verf lschung selbiger sind zwar eingerichtet tun bislang aber nichts Die MotionUnit ist f r die Berechnung der neuen Position aus einer Bewe gung und zur Weitergabe selbiger an den Kernel zust ndig Kollisionen mit Hindernissen und Robotern werden verhindert wof r die gew nschte Bewe 24 4 1 Architektur 4 ROBOTER MODUL roboter 3 tar Stop Punkt E Start 2 Start N Sl x i y Sp Stop Punkt Erstes Ziel Ziel Hindernis E Roboter 2 Abbildung 14 Vermeidung von Kollisionen mit Hindernissen links und Robo tern rechts gung ggf verk rzt wird Anschlie end wird die neue Position an die RobotData bergeben um den neuen Explorationszustand der Karte zu berechnen F r die Vermeidung von Kollisionen mit Hindernissen wird gepriift ob die Bewe gung zu nah lt 12 5 cm an einem Hindernis enden wiirde oder eins trifft oder kreuzt Mittels einer Abwandlung des aus der Computergrafik bekannten Cohen Sutherland Algorithmus werden nur fiir relevante F lle Schnittpunkt berechnungen durchgefiihrt Generell werden nur Hindernisse im Sichtradius betrachtet was letztlich der Grund dafiir ist dass der Sichtradius gr fer als die maximale Geschwindigkeit des Roboters sein muss Der Roboter bleibt vor dem n chsten Hindernis stehen Abb 14 links Die Vermeidung von Kollisio nen mit Robotern beruht darauf dass Roboter niemals n her als 12 5 cm an die
49. Schatz erreicht hat So bald die Position des Schatzes erreicht ist wechselt die Strategie in den Zustand WorkTreasureState Ist der Schatz vollst ndig ab gearbeitet wechselt die Strategie in den Zustand Search TreasureState und der Roboter befindet sich erneut auf Schatzsuche Sollte der Roboter w htend er sich im Zustand SearchTreasureState oder WalkToTreasureState befindet auf Hindernisse sto en so werden diese mit Hilfe der Taktik WallkAlongBoundaries berwunden ohne dabei Kollisionen zu verursachen In Abbildung 30 ist der gesamte Ablauf noch mal als Zustandsautomat dargestellt 61 4 4 Strategien 4 ROBOTER MODUL Sch tze in Sichtradius nicht leer Keine Schatze in Sichtradius Gehe zu Schatz Schatz noch nicht erreicht Erkunde Karte Verfolge Weg weiterhin Walk To Treasure State Schatz nicht vorhanden Erkunde Karte Schatz erreicht Schatz abgebaut Baie Schatzab Erkunde Karte State Lo Unbearbeiteter Schatz vorhanden Baue Schatz ab Abbildung 30 Zustandsautomat der Worker Strategie 4 4 6 TransporterStrategy Diese Strategie wurde fiir Roboter vom Typ Transporter oder Multirobot kon zipiert Ein Roboter der diese Strategie benutzt befindet sich zu jeder Zeit in einem der folgenden Zust nde e SearchTreasureState Exploration der Karte Suche nach Sch tzen e WalkToTreasureState Roboter bewegt sich zum gefundenen Schatz e LoadTreasureState Sch tze aufladen e WalkToHome
50. Strategien zu erzeugen und in die Simulation einzubauen 4 2 1 Strategiekonzept In diesem Kapitel wird erl utert wie das Strategiekonzept funktioniert und aufgebaut ist Die Klasse Strategy spielt bei der Entwicklung von Strategien eine zentrale Rolle Es ist eine abstrakte Klasse die bereits Referenzen auf alle n tigen Funktionalit ten enth lt Folgende Schnittstellen werden bereit gestellt e IStaticMapData Zugriff auf die Datenhaltung f r statische Karteninfor mationen des Roboters e IDynamicMapData Zugriff auf die Datenhaltung f r dynamische Karten informationen des Roboters e IMessageData Zugriff auf die Datenhaltung fiir Nachrichten des Robo ters e ContainerData Zugriff auf die Datenhaltung fiir Containerdaten des Ro boters e RobotFeatures Zugriff auf die Eigenschaften des Roboters e TacticManager Zugriff auf die verschiedenen Taktiken e ActionList Zugriff auf die Aktionsliste Die Methoden die diese Schnittstellen anbieten sind in Kapitel 4 2 3 jeweils mit einer Erkl rung zu Funktionalit t aufgelistet M chte man nun eine neue Strate gie implementieren so muss diese von der Klasse Strategy erben Des weiteren muss die abstrakte Methode compute aus der Oberklasse Strategy in der Unterklasse die zu implementierende Strategie Klasse implementiert werden 29 4 2 Strategie und Taktikkonzept 4 ROBOTER MODUL Diese Methode setzt den wesentlichen Strategieablauf um d h das gesamte V
51. Weg zum gefundenen Schatz Sollten dabei Hindernisse im Weg sein 59 4 4 Strategien 4 ROBOTER MODUL so werden diese mit Hilfe der Taktik WallkAlongBoundaries umgangen So bald die Position des Schatzes erreicht ist wird berpr ft ob Schatz Einheiten noch vorhanden sind denn w hrend der Roboter sich auf dem weg zum Schatz be fand h tte ein anderer Roboter den Schatz abbauen und m glicherweise auch abtransportieren k nnen Falls beim Erreichen der Schatzposition kein Schatz mehr vorhanden ist wechselt die Strategie in den Zustand Search TreasureState Falls jedoch Schatz Einheiten noch vorhanden sind wird berpr ft ob abge baute Schatz Einheiten vorhanden sind und wenn ja wird die Menge mit der Container Kapazit t des Roboters verglichen Reichen die bis jetzt abgebau ten Schatz Einheiten noch nicht aus um den Container zu f llen wechselt die Strategie in den Zustand WorkTreasureState um weitere Schatz Einheiten ab zubauen Falls die Abgebauten Einheiten den Container f llen oder die letzten Sch tze abgebaut wurden wechselt die Strategie in den Zustand Load Treasu reState Nun ist der Roboter dabei Sch tze aufzuladen So bald der Container gef llt ist oder die letzten Sch tze aufgeladen wurden wechselt die Strategie in den Zustand WalkToHomeBaseState Der Roboter befindet sich nun auf dem Weg zu Homebase um die Sch tze da zu entladen Sollte der Roboter auf dem Weg zu Homebase auf Hindernisse sto en so werden diese
52. _NACK2_INVITE Das ACK2 dient in diesem Fall als eine Art Best ti gung einer Best tigung Da der einladende Roboter selber genauso Einladun gen empfangen kann und die M glichkeit besteht da er auch eine dieser Einladungen annimmt kann sehr wohl der Fall auftreten da Best tigungen zu einer Finladung ankommen der Roboter allerdings bereits einem anderen Roboter zugesagt hat F r diesen Fall ist die Nachricht NACK2 gedacht Der Automat der das Verhalten modelliert ist in Abbildung 20 dargestellt Der Algorithmus if messagesWaiting processQueries if teamNeeded OR missingTypes sendQueries Im ersten Schritt schaut die Taktik nach ob es Nachrichten gibt die verar beitet werden m ssen Dies ist der Fall falls unter den eingegangenen Nach richten mindestens eine Nachricht existiert die den oben definierten Typen entspricht wird durch die boolesche Variable messagesWaiting indiziert Im zweiten Schritt schaut die Taktik nach ob noch weitere Roboter ben tigt wer den und verschickt in dem Fall neue Einladungen Dabei zeigt die boolesche 47 4 3 Taktiken 4 ROBOTER MODUL invite ackl ack2 nackl ack2 nackl nack2 ack2 nack2 available invite invite ackl ackl invite nackl nack1 ackl nack2 ack2 Abbildung 20 Protokoll beim Teamaufbau invite nackl ackl ack2 nack2 Variable teamNeeded an da ein Team ben tigt wird und die boolesche Varia ble m
53. amte Kartenrand abgegangen werden Das Vorgehen ist zum besseren Verst ndnis exemplarisch in Abb 19 festgehalten In der Methode hasAction wird maximal eine Kollisionserkennung durch geftihrt und zwar nur zu Beginn des Umgehens In performAction wird der Pledge Algorithmus aufgerufen der im schlechten Fall das mehrmaligen Aufru fen der Kollisionserkennung n tig macht Alle anderen Operationen sind lauf zeittechnisch zu vernachl ssigen insbesondere passiert in update praktisch nichts Es werden kaum Daten permanent gespeichert der Aufwand daf r ist daher ebenfalls zu vernachl ssigen OrbitLeftAround und OrbitRight Around OrbitLeftAround und OrbitRightAround sind Taktiken die einen Roboter veranlassen ein Hindernis zu umkreisen Im folgenden wird die Taktik Orbi tRight Around beschrieben Durch den Aufruf der Methode hasAction wird 42 4 3 Taktiken 4 ROBOTER MODUL gew nschte Bewegung gt Ersatzbewegung Abbildung 19 Exemplarisches Vorgehen der Taktik WalkAlongBoundaries ermittelt ob eine Kollision bevor steht oder ein Hindernis bereits umkreist wird Falls der Riichgabewert true liefert kann nun durch den Aufruf der Methode performAction einen neue Bewegungsaktion berechnet werden die um das Hindernis herumfiihrt Die Berechnung wird in der Methode goRight Around durchgef hrt Dabei wird als erstes gepr ft ob die als n chste auszuf hrende Bewegungsaktio
54. apRequest dynamicMapData getHomeBase Wichtig ist dass diese Strategie davon ausgeht dass die Anzahl an Explorern quadratisch ist und funktioniert nur so Dies resultiert aus der Einteilung der Karte in quadratische Regionen Wird eine nicht quadratische Explorer Anzahl gew hlt findet eine Aufteilung entsprechend der n chst gr eren Quadratzahl statt Dar ber hinaus ist das Quadrat einer 2er Potenz 1 4 16 64 sinnvoll da so die einzelnen Regionen Knoten des Quadtrees entsprechen was f r die verwendeten Taktiken zum Teil Vorteile bringt Hinweis Die vollst ndige Exploration einer Region soll eigentlich von dem Ex plorer mit einer aus der SubAreaStrategy siehe 4 4 2 hervorgehenden Taktik umgesetzt werden Dies konnte jedoch noch nicht mehr rechtzeitig eingebaut werden Jedoch ist die Benutzung der Taktik HeadForCloseUnexploredRegion ein behelfsm ig akzeptabler Ersatz da auch sie nat rlich zu Explorations zwecken benutzt werden kann Ein weiteres Problem besteht in gr en Hin dernissen da sie nach Umlaufen nicht als exploriert erkannt werden Hierf r sind jedoch sinnvollererweise Ma nahmen in den festen Teilen des Roboters zu treffen 54 4 4 Strategien 4 ROBOTER MODUL 4 4 2 SubAreaStrategy Die SubAreaStrategy ist eine Strategie um einen rechteckigen Ausschnitt ei ner Karte Subarea vollst ndig zu explorieren Sie ist eine systematische Su che in der Hinsicht dass die einen vordefinierten Weg geht
55. ationsradius nie benutzt wird so macht es Sinn diese Daten nicht in den Datenhaltungsklassen zu speichern useExplorationQuadTree boolean useQuadTree Setzt fest ob der Quad tree der die erkundete Karte eines Roboters repr sentiert verwendet wer den soll Default Wert ist true setBackUpsOfRobotsInViewRadius int backUpsOfRobotsInViewRadius Setzt fest wieviele Runden fr her im Sichtradius befindliche Roboter ge speichert werden sollen Default Wert ist 0 setBackUpsOfRobotsInCommRadius int backUpsOfRobotsInCommRadi us Setzt fest wie viele Runden fr her im Funkradius befindliche Roboter gespeichert werden sollen Default Wert ist 0 setBackUpsOfDynamicObjectsInViewRadius int backUpsOfDynamicOb jectsInViewRadius Setzt fest wieviele Runden fr her im Sichtradius befindliche dynamische Objekte gespeichert werden sollen Default Wert ist 0 saveRobotsInCommRadius boolean saveRobots Setzt fest ob Roboter im Funkradius ermittelt und tempor r gespeichert werden Default Wert ist true saveDynamicObjects boolean saveDynamicObjects Setzt fest ob dyna mische Objekte im Sichtradius ermittelt und tempor r gespeichert wer den Default Wert ist true 37 4 2 Strategie und Taktikkonzept 4 ROBOTER MODUL e saveMessages boolean saveMessages Setzt fest ob Nachrichten empfan gen und gespeichert werden sollen Default Wert ist true e setNumberOfMapRegions int numberOfMapRegions Setzt die Anzahl als solche defi
56. ber die entsprechende Schnittstelle das Ausf hren der Elementaraktion mitgeteilt 23 4 1 Architektur 4 ROBOTER MODUL 4 1 1 RobotControl Die RobotControl ist sozusagen das Zentralnervensystem des Roboters Es ist der Zugriffspunkt von au en auf den Roboter also vom Kernel Hier werden die statischen Eigenschaften eines Roboters in Form einer RobotConfiguration ge speichert und k nnen von den anderen Modulen des Roboters abgefragt werden Weiterhin ist hier der Roboterype definiert also z B Worker oder Explorer Die Initialisierung des Roboters l uft wie folgt ab Eine Instanz eines Roboters kann nur durch die Klasse RobotFactory erzeugt werden Diese sichert zu dass auf den Roboter nur durch das Interface IKernelToRobot zugegriffen werden kann Als erstes wird nun anhand der im Konstruktor bergebenen RobotID der passende Robotertyp erstellt also eine der von RobotType abgeleiteten Klassen instanziiert Beispielsweise w rde f r eine Robot IDWorker die Klasse Worker in stanziiert Nachfolgend wird mit der speziellen Instanz von RobotType gepr ft ob die Einstellungen in der RobotConfiguration alle Kriterien f r diesen spezi ellen Robotertyp erf llen ansonsten wird eine RobotInitException geschmis sen F r einen Worker w re so ein Kriterium z B dass die Werkzeuggr e zum Abbauen von Sch tzen positiv sein muss Zum Schlu werden noch die Klassen Strategy RobotData und PhysicalUnit instanziiert und ihre Assoziationen u
57. berhaupt lohnt diesen zu zeichnen Es gibt 3 Gr nde warum ein Teilbaum verworfen werden kann 1 die BoundingBox des Teilbaums ist weit vom Betrachter weg und so klein dass in ihm enthaltenen Dreiecke vermutlich kaum sichtbar w ren 2 die BoundingBox des Teilbaums ist nicht sichtbar Frustum Clipping 3 das Rendern des Frames berschreitet ein bestimmtes Zeitlimit Zu Punkt 1 Es wird zu jedem Knoten die Gr e seiner BoundingBox und sein Abstand zur NearPlane Zeichenebene ins Verh ltnis gesetzt Wird dabei ein bestimmtes Limit nicht erreicht so wird der komplette Teilbaum verworfen Um gleichzeitig die Bildqualit t so hoch wie m glich zu halten und dennoch eine fl ssige Navigation zu gew hrleisten wird dieses Limit automatisch angepasst je nachdem wie lange das Rendern des Frames gedauert hat Zu Punkt 3 Derzeit ist es so eingestellt dass das Rendern eines Frames nach 200ms angebrochen wird um mindestens 5 FPS zu sicherzustellen Um die St rungen im Bild zu minimieren die durch ein pl tzliches Abbrechen entstehen k nnen werden die Kinder des Knotens in near to far order durchlaufen so dass eher weiter Weg liegende liegende Dinge wegfallen als nahe am Betrachter liegende Texturierung des Gel ndes Shader Da die Grafikkarte bzw der Bus mit dem bertragen der Vertex und Normalendaten schon genug zu tun hat wird auf die bermittlung von Texturkoordinaten verzichtet Statt dessen bernimmt der MonumentShader die
58. bots besteht im wesentlichen aus einem Array s mtlicher Roboter und einigen Methoden auf dieser Liste Die wichtigsten sind hier kurz erl utert 1 public synchronized void init RobotInit robotInit Initialisiert die Roboter anhand der bergebenen RobotInit Nachricht 2 public synchronized Set lt Robot gt getRobotsInRegion Rectangle2D region Gibt die Roboter innerhalb der spezifizierten Region zuriick 3 public synchronized void updateRobots RobotChanges robotChanges Aktualisiert die Roboter anhand der bergebenen Robot Changes Nachricht Die Klasse GroundObjects ist analog aufgebaut Sie besteht in erster Linie aus einer Menge von GroundObject Objekten und einigen Methoden auf dieser Men ge die wichtigsten davon sind 1 public synchronized void init GroundObjectInit groundObjectInit Initialisiert die Bodenobjekte anhand der bergebenen Ground ObjectInit Nachricht 2 public synchronized Set lt Ground bject gt getGround bjectsInRegion Rectangle2D region Gibt die Bodenobjekte innerhalb der spezifizierten Region zur ck 3 public synchronized void updateGround bjects Ground0bjectChanges ground0bjectChanges Aktualisiert die Bodenobjekte anhand der bergebenen Ground Object Changes Nachricht In der Selection Klasse schlie lich werden die Objekte verwaltet die der Benut zer ausgew hlt hat Letztlich stellt sie eine Datenstrukur hnlich einer normalen Liste dar nur sind die Zugriffsoperationen stark modifiziert
59. ca 15 GB nach sich ziehen das durchg ngig im Arbeitsspeicher gehalten werden m sste Moderne Simulatoren sind nicht f hig diese Anforderungen zu erf llen Es werden besonders platzspa rende Datenstrukturen ben tigt die effiziente Anfragen und Aktualisierungen erlauben Die zweite Herausforderung liegt in der M glichkeit Strategien be sonders schnell Entwickeln zu k nnen Rapid Prototyping Dies kann durch die Bereitstellung einer einfachen Schnittstelle zum Einbinden von Strategien realisiert werden die ein einfachs Framework bereitstellt um Routineaufgaben zu erledigen 1 2 Ziele F r das vorangehende Szenario und die Roboter ergaben sich vier prim re Ziele e EXPLORATION Es sollen Methoden zur Exploration von unbekanntem Gel nde entwickelt und implementiert werden Diese sollen gew hrleisten dass das gesamte Gel nde schnell nach Sch tzen durchgesucht wird Dabei sind Hindernisse zu umzugehen e SCHEDULING Es sollen Methoden zur Bearbeitung der Sch tze entwi ckelt und implementiert werden F r das Ausgraben und Transportieren der Sch tze m ssen ensprechend qualifizierte Roboter eingesetzt werden 1 3 Modell 1 EINFUHRUNG ein Bagger ist ja gleichzeitig nicht LKW Das heisst dass Roboter ge recht eingeteilt werden mtissen damit die anliegende Arbeit schnell erle digt ist e COMMUNICATION Damit die Roboter sich effektiv organisieren k nnen muss ein Kommunikationsmedium verf gbar sein Es sollen
60. concrete tactics strategy Transporter BasicMotion 3 z gt O y Q Strategy K RobotControl IRobotFeatures O O O ee _ IDataParameters _ IDynamicMapData gt IContainerData IStaticMapData ye N N 4 SA l amp 9 RobotData PhysicalUnit Message RobotData MotionUnit Memory Parameters Comm Unit Abbildung 13 Wesentliche Klassen des Roboter Moduls DynamicMap Dynamic DataList Region QuadTree zur ckgreifen Die zum Taktikkonzept geh renden Klassen sind hier ausgeblen det und werden im Kapitel 4 2 2 genauer erl utert Das Konzept der Einbindung konkreter Strategien findet sich hingegen in Kapitel 4 2 1 Jede Runde nun ruft der Kernel die Evaluations und die Aktionsphase ber die RobotControl auf In der Evaluationsphase wird die PhysicalUnit dazu beauftragt neue Umgebungsdaten ermitteln und sie in der RobotData zu spei chern Die Aktionsphase beginnt damit dass die RobotControl die Strategie dazu auffordert eine Elementaraktion zu berechnen Die Strategie greift auf die ben tigten Daten zu berechnet ggf neue Ziele und ermittelt die daraus resul tierende n chste Elementaraktion Nebenbei speichert sie zu sendende Nach richten im MessageMemory Die RobotControl gibt die auszuf hrende Aktion weiter an die PhysicalUnit Von dort aus werden die zu sendenden Nachrichten ber die CommunicationUnit verschickt Anschlie end wird dem Kernel
61. dWholeExploration Fordert den Kernel auf das aktuell Quadtree erkundete Gebiet aller Roboter zu bertragen In StopExplorationQuadtree Tilgt eine Beobachtung des erkundeten Pushing Gebiets bergebener Roboter In Terrainlnitialized Benachrichtigt den Kernel dass das Terrain erfolgreich bei der Visualisiserung initialisiert wurde In TerrainRequest Wird aktuell nicht benutzt In Error Wird aktuell nicht benutzt In Out Ping Wird benutzt um die Verbindung zu testen Eine Pong Nachricht ist die Antwort In Out Pong Wird als Antwort auf eine Ping Nachricht geschickt In Out ExplorationQuadtreeUpdate Sollte ein Merge einer unter Beobachtung stehenden Roboters aufgetretten sein so wird diese Nachricht geschickt Out WholeExplorationQuadtree Kapselt den QuadTree aller Roboter Out Tabelle 1 Message Typen Teil 1 10 3 2 Simulationsabwicklung und verwaltung 3 SIMULATIONSKERNEL Messagetyp Bedeutung Richtung InitScene Kapselt Initialisierungsdaten von Robotern und Bodenobjekten Out InitTerrain Kapselt den Namen und den Hashcode des zu verwendenden Terrains Out NewRound Kapselt Daten aller Anderungen der letzten Runde Out GroundObjectDetailUpdate Kapselt Detailinformationen zu einem Bodenobjekt Out RobotDetailUpdate Kapselt Detailinformationen zu einem Roboter Out Robot Defect Sobald ein Roboter ausfallt wird diese Nachricht geschickt Out SimulationPaused Benachrichtigt eine V
62. das die Position und Blickrichtung der Kamera Die Position ist ein einfacher Vektor die Blickrichtung wird durch einen links rechts Winkel und einen hoch runter Winkel angegeben siehe Ab bildung 37 Dies erm glicht eine einfache Manipulation durch die Maus x Z bis 89 y Lay bis 180 bis 180 zu 0 bis 89 Drehung nach links rechts Drehung nach oben unten Abbildung 37 Die Blickrichtung der Kamera Die zweite Aufgabe ist das Bereitstellen aller notwendigen Operationen fiir das Frustum Clipping Immer wenn sich die Position oder Blickrichtung ndert werden die 6 Ebenen gespeichert welche das Frustum beschr nken Anhand dieser kann dann getestet werden ob sich ein W rfel im Frustum befindet Die Implementierung richtet sich exakt nach zwei Tutorials Wor Hol und ist dort ausf hrlich erkl rt Hier w re sicherlich eine Implementierung mit Objekten 3D Vektoren deutlich sch ner zu lesen hat aber zu sp rbaren Geschwin digkeitseinbu en gef hrt 72 5 3 Preprocessing 5 VISUALISIERUNG Die dritte wichtige Aufgabe ist die Userinteraktion Hier sollte eigentlich alles selbsterkl rend bzw durch JavaDoc ausreichend erkl rt sein Einzig zum Tas taturlistener ist noch zu erw hnen dass hierf r ein eigener Thread eigerichtet wurde der regelm ig schaut welche Tasten gedr ckt sind und dementspre chend die Kamera ver ndert Dies war notwendig da die von Java ausgel sten Events beim Halten einer Taste zu la
63. de Aufteilung stellt ein Beispiel dar O 00 15 00 15 1 16 31 00 15 2 33 47 00 15 3 49 63 00 15 4 00 15 16 31 5 16 31 16 31 6 33 47 16 31 7 49 63 16 31 8 00 15 33 47 9 16 31 33 47 10 33 47 33 47 11 49 63 33 47 12 00 15 49 63 13 16 31 49 63 14 33 47 49 63 15 49 63 49 63 Abbildung 6 Beispielaufteilung eines Terrain in Zellen 14 3 2 Simulationsabwicklung und verwaltung 3 SIMULATIONSKERNEL Die Verwaltung selbst benutzt Zellennummern zur Speicherung bei der Berechnung in getRobotsInCommunicationRadius und getRobotsIn View Radius wird hingegen mit Positionen gerechnet hierzu sp ter mehr Die Roboterbewegung ist insoweit angepasst dass bei einer Umsetzung des Roboters nun die entsprechende Zelle in welcher der Roboter sich befunden hat geg angepasst wird Verwaltet wird dies mit einer Hash Map und einem Array wobei ersteres f r die Speicherung von Robotern in einer Zelle und letzteres zur Speicherung der Zelle f r einen Roboter benutzt wird Kommen wir nun zum interessanten Teil der approximativen Berechnung von Robotern im Sicht bzw Kommunikationsradius Folgende Schritte werden hierf r in dieser Reihenfolge get tigt a Bestimmte Quadrat des Radius b berpr fe ob Roboter ber den Rand seiner aktuellen Zelle blicken kann Dabei wird die Position auf den Mittelpunkt der Zelle approximi
64. die eingegangene gesendete und zu sendende Nachrichten speichert Es werden weiterhin 2 Interfaces benutzt Zum einen ist das das Interface IRobotFeatures um an roboterspezifische Daten wie zum Beispiel die ID 25 4 1 Architektur 4 ROBOTER MODUL oder den Energieverbrauch zu kommen Zum anderen ist das das Interface IRobotDataParameters Dar ber hat man die M glichkeit verschiedene Flags zu setzen zum Beispiel das Speichern der Karte ein und auszuschalten Es gibt au erdem noch eine Referenz auf die PhysicalUnit Die StaticMap Mit Hilfe der StaticMap wird der dem Roboter bekannte Bereich der Kar te gespeichert Intern wird als Datenstruktur ein Quadtree benutzt genauer RegionQuadtree Der Quadtree wiederum besteht aus einer Menge von Kno ten RegionQuadtreeNode die entweder mit dem Wert 1 Gebiet ist bekannt oder 0 Gebiet ist nicht bekannt markiert sind Die Menge aller Knoten inner halb des Quadtrees die mit einer 1 markiert sind spiegelt somit das gesamte bekannte Gebiet eines Roboters wider Der Roboter kann nun f r ein belie biges bekanntes Gebiet erfragen welche Hindernisse sich dort befinden Dazu kann der Roboter Anfragen beim Kernel durchf hren und kriegt als Ergebnis die Menge der Hindernisse als Liste bergeben die in dem angefragten Ge biet liegen siehe Abbildung 15 Um sicherzustellen da der Roboter nicht Informationen ber noch nicht bekanntes Gebiet erfragt wird die Anfrage in der PhysicalUni
65. ee ee RA a A Roboter Modul AA Architektur s 224 24 ra a da a ee a G ALL Bobollchtrel i au Bop bak en a doe BR era 4 12 PhysicalUnit p a 4 mah a Ee ee Se Soe a AR a 4 1 3 RobotData und Wegberechnung 4 2 Strategie und Taktikkonzept 2 4 2 1 Strategiekonzept oo sr sead utorak adk kedok 4232 Taktikkonz pt lt seg seana 04 pye e k ee 4 2 3 Schnittstellen f r die Strategieentwicklung AS Taktiken ss scoct eben wa bbw be bee eee ee 4 3 1 CollisionDetector o ss ea samos 4 3 2 HeadForLocations sos so neeesa a ba ka a a aea 4 3 3 HeadForRobots cs aw ssa a u eoe Bee a ah has nike dad TeamManagerient es u cog eae ae Re ee 4 3 5 SecureEnergyManagement a AAS Orate e ua a Gee eo eo a aao a Ee se Bae A a e a 4 4 1 DividedExplorationStrategy 4 4 2 SubAreaStrategy s asaos 520004 4 4 3 ExplorationGreedStrategy ooo a 4 4 4 TreasureGreedStartegy 2 2 a 4 4 5 WorkerStrategy o 520005 4 4 6 TransporterStrategy lt aua ia Visualisierung Dele Architektur 2 0 fea and ee ee eR Er me 5 2 Wichtige Klassen sos siri ect aaoi sa a ee 5 2 1 Anbindung an den Kernel und Ablaufsteuerung 5 2 2 Datenhaltung 22 a soei moa ee sra 5 2 3 2D Visualisierung 2 2 2044 622245 Aue 5 24 Detailansicht s s a 24544406 54440 Soa 2 dee E 5 2 5 Erkundete Karte und abg
66. ees f r alle Eckpunkte der Bl tter die City blockabst nde bis zum Rand des Hindernisses siehe Abbildung 41 Wenn noch nicht vorhanden f ge Vertices mit dem Randabstand als z Wert an den Ecken der Quadtreebl tter ein Die xy Koordinate ergibt sich aus dem Quadtreeblatt Merke dir die Indices der Vertices und speichere sie Speichere sie ebenfalls in den Nachbarn die diese Vertices teilen 7 Berechne f r den Debrisquadtree und den Monumentquadtree mit der zugeh rigen H henfunktion Eingabe Randabstand Ausgabe H he die endg ltige H he der Vertices F ge einen Mittelpunkt in jedes Blatt ein und interpoliere dessen H henwert 8 Berechne Normalen einer Kugel vor und ordne Ihnen Indizes zu 75 5 3 Preprocessing 5 VISUALISIERUNG CCE Abbildung 41 Iterativ Abst nde zum Rand berechnen 9 Erzeuge aus jedem Blatt beider Quadtrees Dreiecke siehe Abbildung 42 die auf die Vertex Indices referenzieren und berechne die zugeh rigen Nor malenindizes H Abbildung 42 Dreiecke generieren 10 Ordne jedem Eintrag aus der Steinliste einen zuf lligen Index zu der auf einen der zehn vorgefertigten stone Objekte verweist PreprocessingTerrainOctree Der Einstiegspunkt zum Einsortieren der Drei ecke und Steine in den Octree die statische Methode preprocessTerrainOctree der Klasse PreprocessingTerrainOctree Dieser bekommt neben den Dr
67. eiecks und Steindaten einige Parameter welche in den folgenden Abs tzen bei ihrem jeweiligen Einsatzpunkt erkl rt werden Dabei wird wie folgt vorgegangen 1 F ge die Dreiecke ein Das ganze funktioniert nach dem Prinzip des Loo se Octree Fis07 Tha00 Grob gesagt die Boundingboxen der Octree Knoten werden in jeder Dimension doppelt so gro wie in einem gew hnlichen Octree sie berlappen sich also Die Tiefe in der ein Dreieck eingef gt wird h ngt damit nur noch von der Gr e seiner Boundingbox ab und die Position im Octree nur vom Mittelpunkt seiner Boundingbox Gro er Vorteil es k nnen keine kleinen Dreiecke mehr oben im Octree h ngen bleiben nur weil sie ung nstig liegen siehe Abbildung 43 Zus tzlich gibt es einen Parameter maxDepth der bestimmt wie tief der Baum maximal werden darf Dieser Parameter ist relativ zu log Breite des Gel ndes zu verstehen d h die wirkliche Maximaltiefe ist log Breite des Gel ndes maxDepth Der Grund so ist z B 0 immer ein sinnvoller Wert un abh ngig von der Kartengr e 2 F ge die Steine ein Die Steine werden grunds tzlich in der Tiefe log Breite des Gel ndes eingef gt Es wird immer rekursiv in den Kindknoten hinabgestiegen in 76 5 3 Preprocessing 5 VISUALISIERUNG Aufgrund seiner Gr e muss das Dreieck in die BoundingBox gestrichelt eines Knotens der Tiefe 2 passen In welchem Knoten dicke Linie das Dreieck landet bes
68. ein Transporter keine Sch tze ausgraben wohl aber welche transportieren Jeder Roboter muss Informationen ber sei ne Umgebung Hindernisse Roboter Sch tze lokal ermitteln und seine eigene abstrakte Repr sentation davon erstellen Geteiltes bzw gemeinsames Wissen kann nur durch den expliziten Austausch von Information ber Kommunikation geschehen Alle Roboter handeln v llig autonom d h jeder Roboter hat eine ei gene Strategie von der sein Verhalten gesteuert wird Das Hauptziel der Roboter als Kollektiv ist die Karte vollst ndig zu explorieren alle Sch tze auszugraben und sie anschliessend zur Basisstation zu bringen Die Roboter k nnen dabei unterschiedliche Teilaufgaben bernehmen je nach Robotertyp und Strategie 1 4 Projektteam Teilnehmer der Projektgruppe e Stephan Arens e Alexander Buss e Helena Deck e Holger Hagedorn e Peter Isaak e Alexander Krieger e Viktor Nesterow e Adrian Ogierman e Jonas Schrieb e Boris Stobbe e Thomas Storm e Henning Wachsmuth 1 4 Projektteam 1 EINF HRUNG Projektleiter Holger Hagedorn Betreuer der AG Meyer auf der Heide e Prof Dr Friedhelm Meyer auf der Heide e Dr Matthias Fischer e Miroslaw Dynia e Jaroslaw Kutylowski 2 ARCHITEKTUR UND KOMPONENTEN 2 Architektur und Komponenten In diesem Abschnitt wird kurz vorgestellt aus welchen einzelnen Modulen das System zusammengesetzt und wofiir diese Teilmodule jeweils verantwortlich sind Eine genauere Ana
69. einzelnen Roboter Da diese Karte nur ein einziges Mal existiert basiert sie auf dem komplet ten Gel nde Einzelne Roboter kennen nur einen eingeschr nkten Teil dieses Gel ndes deshalb m ssen vor der Benutzung diese globalen Daten transfor miert werden um dem Wissen des Roboters zu entsprechen Eine komplette Transformation der Karte ist sehr zeitaufw ndig ist und hat we gen der Bewegungen der Roboter nur einen kurzen G ltigkeitszeitraum Deshalb wird anstelle eines Preprocessing vor der Wegberechnung die Karte on the fly ver ndert Wie sieht diese Ver nderung nun aus Grundlage f r dieses Verfah ren ist der Dijkstra Algorithmus Bevor ein Knoten im Algorithmus abgearbei tet wird wird berpr ft ob dieser Knoten im bekannten Gebiet des Roboters liegt Hierbei gibt es nun drei verschiedene M glichkeiten Die beiden trivialen Varianten das der Knoten komplett bzw garnicht im bekannten Gebiet liegen betrachten wir nicht weiter Was passiert nun falls ein Knoten nur teilweise im bekannten Gebiet liegt In diesem Fall wird der Knoten in kleinere Knoten aufgeteilt basierend auf den Zellgrenzen in der StaticMap Diese berdeckungen werden lokal w hrend der Wegberechnung gespeichert und am Ende wieder freigegeben da diese Knoten sich im Grenzgebiet befinden und sich damit wahrscheinlich bald durch die Explorationstatigkeit ver ndern Nach diesem Algorithmus erhalten wir einen Weg dessen einzelne Knoten den Zellen oder Teilzell
70. eise eingebunden werden Betrachtet man diese Taktiken etwas genauer so stellt man fest dass sie alle in einer hnlichen Weise funktionieren Im Wesentlichen beschr nken sich Taktiken auf zwei Typen Bewegungen und Entscheidungen Beispiele f r Be wegungstaktiken sind das Umrunden eines Hindernisses ein Ausweichman ver beim Auftreffen auf einen anderen Roboter oder die R ckkehr zur Basisstation Entscheidungen k nnen z B sein sich einer Gruppe von Robotern anzuschlies sen oder aber die Erkennung einer Kollision Diese beiden Taktik Arten werden ber verschiedene Interfaces realisiert IDecisionTactic f r Entscheidungen IMovementTactic f r automatische Bewegungen und ITargetMovementTactic f r Bewegungen zu einem bestimmten Ziel Es wurde ein Framework entwickelt welches eine besonders einfache Benutzung f r den Entwickler darstellt Jede Taktik bekommt dabei zun chst einen beson ders aussagekr ftigen Namen der f r die Art der auszuf hrenden Aktion steht Der Entwickler kann dann diese Taktik ber einen Verwalter laden In jeder Runde holt sich die geladene Taktik dann automatisch alle Informationen die sie f r ihre Auf hrung ben tigt Das einzige was der Entwickler nur noch ma 31 4 2 Strategie und Taktikkonzept 4 ROBOTER MODUL chen muss ist die Taktik zu fragen ob sie aktuell ihre Aktion ausf hren kann und sollte dem so sein dann der Taktik mitteilen dass sie die Aktion auch ausf hren soll Dies reduziert die un
71. elaufene Wege 5 2 6 BD Visualisierune secs ph aveam aa Re nen DB PEOPrOC SSIDS e a u ara nc ee ee a 58 1 2D Gel nde y s owe 22 2A ede eg GRE ewe ws 5 3 2 3BD Gel nde o se 2 ke ee en insta de i ae a 530 Ein paar Zahlen ce 24 2 vart ha bee hae 2 Editor 6 1 Architektur s o 2424 8 e888 eee ee ee kA EGE Cee es 6 1 1 Die Biemaps lt 2 eee ano a REO Ee ee ee ee 6 1 2 Die Minimap s e ose 266 ei ee eee Le hed 6 1 3 Die Optionspalette 2 2 En nn 6 1 4 Die Men leiste o e e 6 1 5 Die Statuszeile o 6 2 Sch tzeverwaltung o s c ca sss cs saama e aiaa nn 6 3 Roboterkani uratione s s av eca a ei a ao ASS aei da ie g 64 Datenstruktues ie saag e BORK ew ke 6 0a i ce fy eke ik Br ae eee Bek ea Bl eet e Gol Architektur wu gun ace A pe ce Boe en Bes 6 5 2 Wizard Framework i lt eao ser acana os nenn 6 5 3 Generatorimplementierung Messgr en Tie Einleitung e hac eS sun ana eh ee Fw Eh be hh Be 1 2 Ablauf und Architektur 23a ae ee Be ee ee Bea 5 io Sammeln der Messwerte lt eor 0 2 u wa eek we a a ee us 7 4 Benutzereigene Messgr en 2 2 222 nn Ausblick Offene Punkte Projekt in Eclipse einbinden 1 EINFUHRUNG 1 Einf hrung Die Projektgruppe Smart Teams Local Distributed Strategies for Self Organizing Robotic Exploration Teams fand vom Wintersemester 2007 08 bis zum Wintersemester 2
72. elner Roboter arbeiten 65 5 2 Wichtige Klassen 5 VISUALISIERUNG 5 2 1 Anbindung an den Kernel und Ablaufsteuerung Wie schon in Kapitel 3 2 2 dargestellt kommunizieren Kernel und Visualisie rung ber Nachrichten die ber Java RMI verschickt werden Visualisierungs seitig wird die Kommunikation von der Klasse MainControl abgewickelt Sie ist ein Thread und das Gegenst ck zur Controller Klasse im Kernel damit ist sie f r das visualisierungsseitige Message Handling verantwortlich Sie behandelt einerseits die ankommenden Nachrichten und verarbeitet die in ihnen gekap selten Informationen ber die Simulation andererseits werden hier die von der Visualisierung ausgehenden Nachrichten erstellt und verschickt Da die Anzeige der Visualisierung ausschlie lich von den Nachrichten abh ngt die vom Kernel ankommen ist die MainControl von zentraler Bedeutung Zus tzlich wird in der MainControl die Visualisierung initialisiert die anderen Hauptklassen der Visualisierung werden hier instanziiert Implementiert ist die MainControl Klasse als Zustandsautomat Sie verf gt ber eine Reihe Zust nde die sich je nach Simulationszustand und nach Ver bindungszustand zum Kernel ndern Zustand Beschreibung UNREGISTERED Es besteht keine Verbindung zum Kernel REGISTERED Eine Verbindung zum Kernel ist her gestellt aber es l uft keine Simulati on TERRAIN_REQUESTED Der Kernel hat zum Initialisieren des Gel ndes aufgef
73. en wird durch die Variable messagesWaiting indi ziert und danach werden bei Bedarf Nachrichten rausgeschickt wird durch die Variable disbandTeam indiziert processQueries 1 Gehe alle Nachrichten durch 2 Ist die Nachricht vom Typ DISBAND und der Sender ist mein Tea manf hrer dann schicke ich eine Best tigung und verlasse das Team 3 Wenn die Nachricht eine Best tigung ACK_DISBAND ist und ich der Anf hrer bin dann nehme ich den entsprechenden Roboter aus dem Team Wenn ich der einzige Roboter im Team bin dann l se ich es auf sendQueries 1 Wenn ich der Teamanf hrer bin dann verschicke eine Nachricht DIS BAND an alle Teammitglieder 4 3 5 SecureEnergyManagement Diese Taktik geht auf das Energiekonzept des Roboters ein Die korrekte Benut zung der Taktik gew hrleistet mit einer Ausnahme dass der Roboter rechtzeitig zur HomeBase zur ckkehrt ehe seine Energie verbraucht ist Die Ausnahme be steht in der Kollisionsvermeidung mit Robotern da sich deren H ufigkeit nicht im Vorhinein determinieren l sst Daher beinhalt die Taktik eine einstellbare Anzahl an Schritten die weniger gegangen wird als theoretisch m glich wie Die Taktik zielt darauf ab den Berechnungsaufwand zu minimieren Von der Verwendung der Wegberechnung wurde letztlich abgesehen da bei Ende der Implementierungsarbeiten noch keine korrekte Benutzbarkeit der Wegberech nung in Zusammenhang mit dieser Taktik sichergestellt war Die Vorb
74. en Anzahl an Objekteinheiten int getBucketPutSize Gibt die Gr e der Ablegeschaufel zur ck int getBucketGrabSize Gibt die Gr e der Aufnehmschaufel zur ck Position getStartPosition Gibt die Startposition des Roboters zur ck an der er sich zu Beginn der Simulation befand 36 4 2 Strategie und Taktikkonzept 4 ROBOTER MODUL float get MapBorderLength Gibt die H he und Breite der Karte in Me tern zurtick int getNumberOfRobots Gibt die Anzahl der Roboter an die insgesamt in der aktuellen Simulation vorhanden sind int getNumberOfRobotTypes Gibt die Anzahl der Roboter in der ak tuellen Simulation vorhanden sind zur ck die vom gleichen Typs wie der anfragende Roboter sind int getRound Gibt die Nummer der aktuellen Runde der Simulation an Random getRandom Gibt einen Zufallsgenerator zur ck dessen Seed f r die Simulation setzbar ist IDataParameters Schnittstelle ber die eine Strategie Parameter der Daten haltung setzen kann vor allem um nicht ben tigte Daten nicht speichern oder gar ermitteln zu lassen Dies dient der Verringerung des Speicher und Laufzeit bedarfs Eine Runde in der Simulation besteht aus einer Evaluierungsphase und eine Aktionsphase In der Evaluierungsphase werden die Datenhaltungsklassen aller Roboter aktualisiert damit die Strategie Berechnung bei Bedarf auf diese Daten zugreifen kann Falls man aber zum Beispiel eine Strategie entwickelt in der der Kommunik
75. en Karte werden in dem Wurzelknoten gespei chert Befinden sich mehr als ein dynamisches Objekt in einem der Knoten so wird der Knoten bzw der Teilbereich den der Knoten darstellt in vier kleinere 19 3 3 Datenstrukturen 3 SIMULATIONSKERNEL Abbildung 10 Aufbau eines PRQuadtrees Teilbereiche unterteilt Die Teilbereiche werden mit NW NE SW und SE be zeichnet damit sie unterscheidbar sind Nach der Teilung werden die Bereiche als neu Kindknoten angeh ngt die mindestens ein dynamisches Objekt enthal ten Enth lt der neue Knoten mehr als ein Objekt wird die ganze Prozedur wiederholt es sei denn die maximale Tiefe ist erreicht Alle Blattknoten des PRQuadtrees enthalten mindestens ein dynamisches Objekt Klassen bersicht Folgende Klassen wurden erstellt um die Datenstruktur aufzubauen siehe Abbildung 11 PRQuadtree PRNode DynamicObjects DynamicObject Treasure Flag Abbildung 11 Klassen bersicht Klasse PRQuadtree Erstellt den Quadtree In diesen k nnen Objekte ei negef gt oder gel scht werden und es kann nach einem bestimmten Knoten gesucht werden Klasse DynamicObjects Erbt die Funktionen von der Klasse PRQuadtree und stellt weitere zur Verf gung wie z B das erstellen eines Quadtrees aus einer 20 3 4 RMI 3 SIMULATIONSKERNEL xml Datei Stellt eine weitere Funktion bereit mit der man alle Objekte im Sichtradius eines Roboter
76. en des Quadtree entsprechen Dieser muss noch in richtige Wegpunkte transformiert werden damit die Roboter anhand derer navigieren k nnen Diese Wegpunkte werden jeweils in die Mitte der Strecke gelegt die sich zwei benachbarte Zellen als Grenze teilen Innerhalb der Startzelle und der Zielzelle werden gerade Wege vom Startpunkt bzw Zielpunkt zu dem n chsten 28 4 2 Strategie und Taktikkonzept 4 ROBOTER MODUL Wegpunkt gelegt 4 2 Strategie und Taktikkonzept Eine Strategie bestimmt das Verhalten eines Roboters Sie wird in jeder Ak tionsphase des Roboters aufgerufen um anhand neuer und bestehender Daten ber die Umgebung die Ziele des Roboters zu berechnen und die daf r als n chstes auszuf hrende Elementaraktion zu ermitteln Innerhalb einer Simu lation kann potentiell jeder Roboter eine eigene Strategie verwenden aber es k nnen auch viele Roboter die gleiche Strategie haben oder zumindest eine prin zipiell gleiche und nur durch Parameter unterschiedliche gestaltete Strategie Im folgenden Teilkapitel 4 2 1 wird das Strategiekonzept beschrieben das zen tral f r das Verst ndnis der Benutzung des Simulators aus Entwicklersicht ist Anschlie end wird in Kapitel 4 2 2 das Taktikkonzept erl utert mit dem er reicht werden soll dass immer wiederkehrende Teilstrategien wiederverwend bar zur Verf gung gestellt werden Kapitel 4 2 3 f hrt dann die Schnittstellen auf von denen ein Entwickler Gebrauch machen kann um selbst
77. en sich nur noch bis auf das Initiieren und F llen geg zus tzlich ben tigter Strukturen um die folgenden Elementaraktionen bzw deren Implementierung k mmern 1 getRobotsInCommunicationRadius 2 getRobotsInViewRadius 3 moveRobot Folgende konkrete Roboterverwaltungen existieren im aktuellen System 1 RobotManagementExact Diese Verwaltung stellt die Grundform dar Das eigentliche Bewegen von Robotern also die Implementierung von moveR obot ist lediglich ein einfacher Positionswechsel in einem Array Bei den Bereichsanfragen getRobotsInCommunicationRadius und getRo botsInViewRadius werden alle Roboter sequentiell durchlaufen und ein Positionsabgleich durchgef hrt wobei der Radius durch ein Quadrat mit Breite des Radius approximiert wird Wichtig hierbei ist zu erkennen dass diese L sung sehr einfach aber bei hoher Roboterzahl nicht mehr performant ist 2 RobotManagementCellBased Diese Verwaltung stellt eine Verbesserung der Grundform RobotManagementExact dar Hierbei wird der Radius immernoch durch ein Quadrat approximiert jedoch arbeitet diese Ver waltung mit Hilfe einer Zellenaufteilung um performanter zu sein Hierbei bedeutet Zellenaufteilung nichts weiter als das das Terrain in Schachbrettform in Zellen mit Breite einer Zweierpotenz aufgeteilt wird Die Zellen sind hierbei quadratisch und von einer Breite welche immer eine Zweierpotenz sein muss Letzteres vermeidet Probleme bei der Zel lenaufteilung Folgen
78. ereitung zum Einbau sind im Code jedoch bereits vorhanden zum Teil allerdings aus kommentiert Mittels einer lokalen ActionList wird ein Weg zurck zur HomeBase als Folge von Elementaraktionen gespeichert der der umgekehrten Bewegung des Robo ters entspricht Dies wird in der automatisch aufgerufenen ITactic Methode 52 4 4 Strategien 4 ROBOTER MODUL update sichergestellt Sie vergleicht die aktuelle und vorherige Position und berechnet automatisch den Riickweg daraus Auch wird hier gepriift ob eine bestimmte Bewegung wirklich ausgefiihrt wurde und im negativen Fall die sich ergebende Weg nderung berechnet An der HomeBase angekommen werden dar ber hinaus solange Aufladeaktionen zur Verf gung gestellt bis die Ener gie wieder aufgeladen ist Mittels hasAction kann berpr ft werden ob das Zur ckgehen zur HomeBase aktuell notwendig ist bzw ob Energie aufgeladen werden sollte Ein einzelner Schritt des R ckwegs wird mittels performAction ermittelt und automatisch in die ActionList des Roboters vorne eingef gt Da Energieverwaltung Vorrang vor andere T tigkeiten haben sollte wird dazu ge raten zu Beginn jeder Runde zu pr fen ob das Zur ckgehen zur HomeBase n tig ist Lediglich die Vermeidung von Kollisionen sollte nach Ausf hren einer der von dieser Taktik angebotenen Aktionen noch sichergestellt werden Alle Operationen die f r die Benutzung notwendig sind haben konstante Lauf zeit Wenn nicht die Standard Metode
79. eren Verlauf dann werden Konzepte und Datenstrukturen des Kernels detailliert beschrieben 3 1 Architektur Ein berblick ber die Architektur des Simulationskernels findet sich in Abbil dung 3 Interfaces VisuMessages IKernelTovisurMil IKernelToRobot visuToKernelRhAl IKernelToYisulink Kontrollmodul lt lt Thread gt gt Kernel Controller MessageHandler Datenstrukturen Roboterverwaltung RegionQuadtree PRQuadtree Abbildung 3 Die Architektur des Simulationskernels Daraus ist zu erkennen dass der Hauptteil der Simulation durch das Kon trollmodul verwaltet wird Hier laufen die einzelnen Simulationsschritte ab werden die Nachrichten verwaltet sowohl die Roboternachrichten als auch die RMI Nachrichten zur Visualisierung hier hat die Roboterverwaltung ihren Sitz und vieles mehr Die wichtigsten Klassen dieses Moduls sind Controller und 3 2 Simulationsabwicklung und verwaltung 3 SIMULATIONSKERNEL Kernel sowie MessageHandler und RobotObjects Die Konzepte die in diesem Modul Anwendung finden sind in Abschnitt 3 2 ausf hrlich beschrieben Fiir die Simulation unerlaslich sind des Kernels Datenstrukturen Diese werden in ihrem eigenen Abschnitt 3 3 ausftihrlich behandelt Auch sie sind mit dem Kontrollmodul verbunden Die Interfaces dienen der Kommunikation Die Kommunikation mit dem Ro botermodul l uft dabei ber das Interface IKernelToRobot dieses wird im Kontrollmodul implementiert Die Kommu
80. ergebene Position sich befindet boolean isInMotionRange Position position Liefert true falls die angege bene Position in einer Runde mit maximaler Geschwindigkeit erreichbar ist boolean isOnObstacleInViewRadius Position position Indiziert ob die bergebene Position in einem Hindernis innerhalb des Sichtradius liegt List lt Position gt searchPathInKnownArea Position from Position to Be rechnet einen kurzen nicht unbedingt k rzesten Weg zwischen zwei Po sitionen der komplett innerhalb des vom Roboter gesehenen Gebietes liegt boolean isMapBorderReached Position curPosition float direction float speed Liefert true falls die bergebene Position ausserhalb des Karten randes oder direkt auf dem Kartenrand liegt IDynamicMapData Diese Schnittstelle erm glicht es der Strategie auf dy namische Kartendaten zuzugreifen Zu den dynamischen Kartendaten geh ren Sch tze Flags Wegmarkierungen und Roboter Folgende Methoden werden bereitgestellt Map lt TreasurelD Position gt getTreasuresInViewRadius Ermittelt die aktuellen Sch tze im Sichtradius des Roboters Jede Schatzmine wird da bei durch eine Position und eindeutige Id in einer Map zur ckgegeben Map lt TreasureAtHomelD Position gt get TreasuresAtHomelnViewRadius Ermittelt die aktuellen Sch tze an der Basisstation falls diese im Sicht radius des Roboters liegt Hier handelt es sich um bereits eingesammelte Sch tze int get TreasureTransportableAmo
81. erhalten eines Roboters der die Strategie benutzt wird in dieser Methode beschrieben Uber die oben erw hnte Schnittstellen k nnen s mtliche Informa tionen angefordert werden Die folgenden Stichpunkte sollen als kleines Beispiel dienen wie man Informationen anfordert e this staticMapData getCurrentPosition liefert die aktuelle Position des Roboters in Koordinaten bzgl der x und y Achse e this staticMapData getObstaclesIn ViewRadius liefert Hindernisse im Sicht radius e this dynamicMapData getTreasuresInViewRadius liefert Sch tze im Sicht radius e this messageData getReceivedMessages liefert Empfangene Nachrichten e this containerData getAvailableCapacity Zu Verf gung stehende Container Kapazit t e this robotFeatures getMaxzimumsSpeed Maximale Geschwindigkeit mit der sich der Roboter bewegen darf Anhand der ermittelten Informationen k nnen nun Entscheidungen getroffen werden Sollte die Strategie entscheiden den Roboter zum Punkt x1 yl zu bewegen so muss die geplante Aktion in die ActionList eingef gt werden Die ActionList ist die zentrale Einheit ber die der Roboter Strtategie mit der Au enwelt agiert d h jegliche Art von Aktionen werden in die ActionList eingef gt um in den n chsten Runden von dem Kernel ausgef hrt zu werden Es stehen der Strategie folgende Aktionen zu Verf gung e ElementaryActionMove speed direction Bewegungsaktion in der Ge schwindigkeit und Richtung ange
82. ert 6 Deleting treasures Es werden Sch tze entfernt Daf r werden der Delete Button der Normal Button und der Treasure Button aktiviert 7 Setting the homebase Die Homebase wird platziert Daf r werden der Draw Button der Normal Button und der Homebase Button aktiviert 8 Deleting the homebase Die Homebase wird entfernt Daf r werden der Delete Button der Normal Button und der Homebase Button aktiviert 9 Drawing fast small obstacles Es werden viele kleine Hindernisse bei gedr ckter Mousetaste hintereinander gezeichnet vergleichbar mit einem Stift Daf r werden der Draw Button der Fast Button und der kleine Rechtecke Button aktiviert 10 Deleting fast small obstacles Es werden viele kleine Hindernisse bei gedr ckter Mousetaste hintereinander gel scht vergleichbar mit einem Radiergummi Daf r werden der Draw Button der Fast Button und der kleine Rechtecke Button aktiviert Zus tzlich zu den Buttons befindet sich ein Spinner auf der Optionspalette Der Spinner ist deaktiviert wenn keine Sch tze gezeichnet werden Wenn ein Schatz gezeichnet werden soll wird der Spinner automatisch aktiviert so dass vor dem Zeichnen des Schatzes die Gr Se des Schatzes eingestellt werden kann Der Default Wert liegt bei 100 6 1 4 Die Men leiste Das Men besteht aus vier Untermen s Dem Filemen dem Editmen dem Extrasmen und dem Helpmen Aus dem Filemen heraus kann ein neues Terrain erstellt werden dazu w
83. ert i Falls ja so gehe zu Schritt 3 ii Falls nein so gehe zu Schritt 4 c berpr fe Roboter im Radius innerhalb der Zelle wie bei RobotMa nagementExact d Erstelle zwei Listen i Listel enth llt dabei die useren Zellen d h die Zellen welche vom Radius lediglich geschnitten und nicht g nzlich abgedeckt werden ii Liste2 enth llt dabei die inneren Zellen d h die Zellen welche vom Radius g nzlich abgedeckt werden e Berechne alle inneren und useren Zellen mit dem Algorithmus com puteDirectNeighbors zur NS Fiige Roboter der inneren Zellen direkt zum Resultat hinzu berpr fe Roboter der u eren Zellen wie in RobotManagementE xact 099 Na Algorithmus computeDirectNeighbors a Normalisiere eigene Roboterposition b Berechne Position der oberen linken Ecke des Quadrats i Korrigiere Randfehler falls notwendig Positionen innerhalb einer Zelle werden auf den Zellenmittelpunkt normiert 2Durch die Zellenaufteilung bilden sich Randfehler wie folgt Angenommen wir haben eine Zellenbreite von 16 so geh ren Positionen 0 15 zu der jeweiligen Zelle Jedoch f hrt die Position 15 zu einer Verzerrung des Quadrat Radius des Roboters 15 3 3 Datenstrukturen 3 SIMULATIONSKERNEL c Berechne linke untere und rechte obere Position d Normalisiere alle Eckpositionen e Berechne usere Zellen i F ge erste usere Zeile hinzu ii F ge ersten und letzten Punkt f r weitere Zeilen hinzu iii F
84. ervall die Zufallszahl liegt siehe dazu Abbildung 21 bestes Gebot 0 m _ _ _ _ Gebot von r Gebot von r3 Gebot von rz Gebot von r4 Abbildung 21 Die Auktion bei der Teambildung sendQueries 1 Suche eine Menge R passender Roboter die sich im Kommunikationsra dius befinden 2 Generiere Gebot 3 Versende Einladungen mit Gebot an Roboter aus der Menge R Auch bei den Geboten wird im Moment mit Zufallszahlen gearbeitet Es be steht aber die M glichkeit stattdessen eine Heuristik zu implementieren TeamLeaveTactic Diese Taktik erm glicht einem Roboter ein Team wieder zu verlassen Diese M glichkeit ist nur gegeben wenn der Roboter der austreten will nicht der Anf hrer der Gruppe ist und nat rlich auch Mitglied eines Teams ist F r den Fall da es sich um den Anf hrer handelt gibt es die TeamDisbandTactic die etwas weiter unten erklit wird Die Taktik berpr ft in jeder Runde zuerst ob Nachrichten f r sie eingetroffen sind und im zweiten Schritt schaut sie nach ob ein Austritt aus dem Team bevorsteht Ist dies der Fall wird eine entsprechende Nachricht versendet Die Entscheidung ber einen Austritt basiert momentan noch auf einer Zufallsentscheidung Auch in dieser Taktik l uft der Ablauf nachrichtenbasiert es werden folgende Typen definiert e TM LEAVE e TM ACK LEAVE Das Protokoll funktioniert folgenderma en Es handelt sich hierbei um ein Protokoll mit nur 1 Handshake
85. es Frame works gelegt Da je nach Problemstellung und deren L sung verschiedene Messgr en inner halb unterschiedlicher Strategien interessant sind bietet das Framework die M glichkeit benutzereigene Messgr en zu sammeln und in Diagrammen an zuzeigen Im folgenden Abschnitten werden Einzelheiten zur Implementierung pr sentiert 7 2 Ablauf und Architektur Der Kern des Messgr enframeworks ist die Klasse MeasurmentContolG UI Dort werden die relevanten Daten gesammelt und bei Bedarf angezeigt Die GUI Elemente Tabelle Button usw und deren Reaktionen sind ebenfalls in dieser Klasse untergebracht Die Klasse MeasurmentContolGUI ist ein Obser goer TT MeassurementControlGUI HashMap int RobotID DataBag A HashMap int RobotID DataBag B HashMap int RobotID DataBag C SceneControl update Obsevable class Object data Abbildung 54 Architektur des Messgr en frame works ver den man in observable Klassen registrieren und deregistrieren kann Sobald der Benutzer auf den Messgr en Button in der Kernel GUI klickt wird eine Instanz von MeasurmentContolGUI erzeugt und im Controller registriert Ab diesem Zeitpunkt wird vom Controller die aktuelle Rundenzahl an die In stanz von MeasurmentContolGUI verschickt Die Rundenzahl landet in der update Methode Mit dem Spinner update Intervall in der GUI kann man die H ufigkeit der Aktualisierung festlegen Dabei wird die aktuelle Rundenzah
86. est tigung ber einen Austritt den ich auch verschickt habe dann verlasse das Team sendQueries 1 Wenn ich nicht der Teamanfiihrer bin dann verschicke eine Nachricht LEAVE an den Anfiihrer TeamDisband Tactic Das Benutzen dieser Taktik ist lediglich dem Teamanfiihrer vorbehalten denn wie der Name schon sagt ist sie dazu gedacht bestehende Teams aufzul sen F den korrekten Ablauf wurden folgende Nachrichten definiert e TM DISBAND e TM ACK DISBAND Das Protokoll funktioniert folgenderma en Es handelt sich auch hierbei um ein Protokoll mit nur 1 Handshake Ein Ro boter der auch gleichzeitig Anf hrer eines Teams sein mu teilt allen seinen Teammitgliedern mit da das Team aufgel st werden soll Dies geschieht mit der Nachricht DISBAND Jeder Roboter der eine solche Nachricht von seinem Teamanf hrer erh lt schickt an den Anf hrer eine Best tigung und verl sst das Team Der Automat der das Verhalten modelliert ist in Abbildung 23 dargestellt disband er ack_disband Sa ack_disband ack_disband Abbildung 23 Protokoll beim Verlassen eines Teams disband ack_disband Der Algorithmus ol 4 3 Taktiken 4 ROBOTER MODUL if messagesWaiting processQueries if disbandTeam sendQueries Der grunds tzliche Ablauf ist auch hier genauso wie bei den anderen beiden Taktiken zuerst wird auf eingegangene Nachrichten berpr ft die eventuell verarbeitet werden m ss
87. estergebniss der Simulation mit unterschiedlichen Karten 80 6 EDITOR 6 Editor Die Aufgabe bestand darin eine bersichtliche und benutzerfreundliche Ober fl che zusammen zu stellen die die Erstellung und Bearbeitung von Karten erm glicht 6 1 Architektur In diesem Kapitel wird der Aufbaue der Oberfl che im folgenden GUI engl Graphical User Interface n her erl utert Informationen zur Bedienung des Editors finden Sie im Benutzerhandbuch Men Help Die wesentlichen Kom ponenten der Klasse GUI sind in Abbildung 47 zu sehen Schieberegler Sch tzeverwaltung Roboterkonfiguration Abbildung 47 Grober Aufbau der GUI 6 1 1 Die Bigmap Die Bigmap besteht aus einem JPanel und zwei Schiebereglern eines f r die horizontale und eines f r die vertikale Schieberichtung In der Bigmap wird ein Ausschnitt der Karte in skalierter Form angezeigt Daf r werden nur die Hindernisse aus dem Quadtree ausgelesen und gezeichnet die sich in diesem Sichtbereich befinden Zus tzlich zu den Hindernissen werden auch Sch tze und die Homebase angezeigt Mit Hilfe der Schieberegler l sst es sich auf der Karte navigieren Der Ausschnitt der angezeigt wird ver ndert sich dementsprechend Um eine bessere Orientierung zu erhalten wird zus tzlich in der Statuszeile die Koordinaten der Mouseposition angezeigt und der zusehne 81 6 1 Architektur 6 EDITOR Ausschnitt als gr nes Rechteck in der Minimap
88. fiziert ist Und zwar hat ITactic keine direkte Assoziation zu ITacticHost sondern die abstrakte Klasse ITacticProvider Dies hat folgenden Hinter grund Taktiken k nnen oft sehr hnliche Funktionalit t besitzen was dazu f hren k nnte dass f r verschiedene Taktiken dieselben Methoden implemen tiert werden m ssten Um dies zu vermeiden ist jede Taktik in eine ITacticProvider Klasse gekapselt In diese Klasse stehen nun alle Methoden die die eigentliche Funktionalit t enthalten und die Taktiken greifen lediglich in ihrer spezifischen Art und Weise darauf zu Es gibt dabei zwei M glichkeiten der Implementie rung 1 Hierbei gibt es nur eine in ihrer Funktionalit t alleinstehende Taktik z B vom Typ Entscheidung In diesem Fall wird eine Klasse ConcreteTacticProviderA vom TacticProvider abgeleitet die zus tzlich das Interface IDecisionTactic implementiert Damit ist der Provider auch gleichzeitig Taktik 2 Andererseits kann es aber auch zwei sehr hnliche Taktiken ConcreteTacticB1 und ConcreteTacticB2 geben wovon eine vielleicht nur Entscheidungen trifft und die andere Bewegungen ausf hrt Ihre Funktionalit t kann dann in einem einzigen Provider ConcreteTacticProviderB gekapselt werden ber den Provider kann sich der TacticManager dann mittels der Methode useTactic name String ITactic eine der beinhalteten Taktiken zur ckgeben lassen Damit der Manager aber berhaupt weiss welche Taktiken und zu geh rige Provider es gib
89. float Werte vor 6 1 3 Die Optionspalette Die Optionspalette ist ein JPanel welches mit dem GridBagLayout s mtliche Buttons in eine Ordnung bringt Mit den Buttons k nne verschiedene Kom binationen aktiviert werden Buttons die grau markiert sind sind aktiviert Insgesamt gibt es zehn verschiedene Kombinationen 1 Drawing slowly small obstacles Es werden einzelne kleine rechtecki ge Hindernisse gezeichnet Daf r werden der Draw Button der Normal Button und der kleine Rechtecke Button aktiviert 2 Deleting slowly small obstacles Es werden einzelne kleine rechtecki ge Hindernisse gel scht Daf r werden der Delete Button der Normal Button und der kleine Rechtecke Button aktiviert 3 Drawing big obstacles Es werden grose rechteckige Hindernisse ge zeichnet Dabei wird beim ziehen der Mouse mit gedr ckter Mousetaste die Gr Se des zu zeichnenden Hindernisses festgelegt Daf r werden der Draw Button der Normal Button und der gro e Rechtecke Button ak tiviert 4 Deleting big obstacles Es werden grose rechteckige Hindernisse gel scht Dabei wird beim ziehen der Mouse mit gedr ckter Mousetaste die Gr se 82 6 1 Architektur 6 EDITOR des zu l schenden Bereichs definiert Dafiir werden der Delete Button der Normal Button und der grose Rechtecke Button aktiviert 5 Drawing treasures Es werden Sch tze platziert Daf r werden der Draw Button der Normal Button und der Treasure Button aktivi
90. g einer Karte bietet Der Generator wurde in Form eines Wizards implementiert 6 5 1 Architektur In Abbildung 51 sind die wesentlichen Klassen des Generators dargestellt Er be steht aus 3 Komponenten eigentliche Implementierung des Generators Wizard Framework Package wizard und Hilfsklassen f r Random function Package forms Alle Eingaben die ein Benutzer im Generator eingibt werden in der forms wizard ao WizardPanelDescriptor WizardPanelNotFoundException G ti er ran WizardController Wizard S A drat WizardModel_ WizardPanelDescriptor WizardPanelDescriptor PaneliDescriptor Panel4Descriptor GenerationData JPanel Panel4 Actiontistener JPanel JPanel WizardPanelDescriptor WizardPanelDescriptor Panel2 Panel3 Panel3Descriptor Panel2Descriptor Abbildung 51 Klassen des Generators Klasse GenerationData gesammelt und bei der Generierung einer Karte aus gelesen Die genauen Funktionen jeder einzelnen Panel werden im Kapitel 6 5 3 erkl rt 6 5 2 Wizard Framework F r die Implementierung des Generators wurde ein Framework benutzt dessen Klassen in Abbildung 52 dargestellt sind Das Framework bietet die M glichkeit 87 6 5 Generator 6 EDITOR einen Wizard mit Back Next und Cancel Buttons komfortabel zu erstel len PropertyChangeListenes WindowAdapter Wizard WizardModel Actiontistener WizardController WizardPa
91. geben sind e Elementary ActionSendMessage messages Nachrichtenaktion in der die zu versendenden Nachrichten in Einer Liste angegeben werden e Elementary Action WorkGroundObject groundObjectID change Bearbei tung eines Objektes Schatz oder Flag e Elementary ActionLoadGroundObject amount groundObjectID Aufla den eines Objekts in den Container e Elementary ActionUnloadGroundObject groundObjectID value Entla den von Objekten aus dem Container e ElementaryActionDoNothing Aktion die nichts tut Falls die Strategie in einer Runde keine Aktion in die ActionList einfiigt und die ActionList leer ist so wird eine ElementaryActionDoNothing Aktion automatisch in die ActionList eingefiigt Dies hat Datenstrukturspezifische Griinde 30 4 2 Strategie und Taktikkonzept 4 ROBOTER MODUL Kommen wir zurtick zu Strategie Entwicklung Hat man nun eine Bewegungs aktion festgelegt so ist es nun sehr sinnvoll sicherzustellen dass der Roboter beim Ausf hren dieser Bewegung nicht mit einem Hindernis kollidiert F r solch einen Fall stehen der Strategie eine Auswahl an Taktiken zu Verf gung M chte man z B im Falle einer Kollision die vorher festgelegte Richtung trotzdem bei behalten ist die Taktik WalkAlongBoundaries die richtige daf r Durch walkA longBoundaries hasAction wird die Bewegungsaktion die an erster Stelle in der ActionList steht auf Kollisionen mit Hindernissen untersucht Falls die ge plante Bewegung eine Kollisi
92. gt Add Button eine Ro boterkonfiguration geladen Load Button oder die aktuelle gespeichert werden kann Save Button Der mittlere Bereich enth lt eine Tabelle mit 14 Spalten von denen die erste Spalte nie bearbeitet werden kann sowie alle grauen Zellen Die Tabelle kann beliebig viele Zeilen haben wobei jede Zeile f r einen Robotertyp steht und jede Zelle der Zeile die Eigenschaften f r diesen Robotertyp festlegt Die Zellen der zweiten bis 12 Spalte enthalten alle eine Spinner wobei einige Spinner mit reellen Werten arbeiten und andere nur mit nat rlichen Werten Die Zellen der 13 Spalte enthalten Textfelder in den der Pfad der zu verwendeten Strategie eingetragen ist Die Zellen der letzten Spalten enthalten je einen Button mit dem ein Dialogfeld ge ffnet wird Mit diesem l sst sich die zu verwendete Stra tegie ausw hlen Der Pfad der Strategie wird anschliesend in der 13 Spalte angezeigt Der untere Bereich enth lt wiederum Buttons sechs an der Zahl Mit den ers ten f nf Buttons l sst sich jeweils eine Zeile in die Tabelle einf gen dabei steht jeder Button f r einen Robotertyp Beim Einf gen einer Zeile wird dann auch gleich darauf geachtet dass entsprechenden Zellen grau markiert sind d h nicht bearbeitbar sind da der Robotertyp diese Eigenschaften nicht hat oder nicht ben tigt Der letzte Button dient zum l schen einer Zeile Es kann jede beliebi ge Zeile gel scht werden bis auf die erste die die Informationen
93. handelt 4 1 Architektur In Abb 13 sind die wesentlichen Klassen des Roboters dargestellt Der Roboter besteht prinzipiell aus den vier Komponenten RobotControl PhysicalUnit RobotData und Strategy ber die RobotControl hat der Kernel verwaltenden Zugriff auf den Robo ter Sie initialisiert den Roboter ist f r das Typkonzept zust ndig regelt die Abl ufe im Roboter und speichert die Eigenschaften des Roboters die sie ber IRobotFeatures zur Verf gung stellt Weitere Information in Kapitel 4 1 1 Die PhysicalUnit regelt die Datenermittlung f hrt Elementaraktionen aus und stellt sicher dass sich der Roboter korrekt verh lt genauer beschrieben in Kapi tel 4 1 2 Hier finden sich die die einzigen und zwar physikalischen Schnittstellen in Richtung Kernel In der RobotData findet die Speicherung aller Umgebungs daten statt aufgeteilt in die Bereiche Nachrichten Containerinhalt Parame ter statische und dynamische Daten siehe Kapitel 4 1 3 Die abstrakte Klasse Strategy hat ber diverse Interfaces Zugriff auf die Datenhaltung Diese Inter faces sind Inhalt von Kapitel 4 2 3 Jede konkrete Strategie erbt von Strategy Die Strategie steuert das Verhalten des Roboters sie berechnet Aktionen f r die ActionList kann dabei Hilfsmethoden des BasicMotionComputer siehe Ka pitel 4 2 3 nutzen Au erdem kann sie auf eine beliebige Auswahl von Taktiken 22 4 1 Architektur 4 ROBOTER MODUL MultiRobot Bunch of Any
94. ic implements implements ConcreteTacticProviderA i setTarget target Position l i 1 setTarget upperLeft Position lowerRight Position l l useTactic name String ITactic setTargetPosition robot RobotID l K 1 1 l l I l I l a I 1 I 1 l ConcreteTacticB1 ConcreteTacticB2 I I I I I ConcreteProviderB Abbildung 17 UML Klassendiagramm des Taktik Konzeptes Um dies nun zu konkretisieren betrachten wir das Klassendiagramm in Abbil dung 17 Der TacticManager ist die zentrale Verwaltung aller Taktiken Mit ihm kann tiber die Methoden useXXXTactic name String IXXXTactic ei ne Taktik vom Typ XXX angefordert werden die den Namen name hat Die Riickgabewerte sind alles Vererbungen von dem Interface ITactic dem Basi 32 4 2 Strategie und Taktikkonzept 4 ROBOTER MODUL sinterface fiir alle Taktik Typen Es beinhaltet die zwei fiir den Entwickler wich tigen Methoden um das Vorhandensein einer Aktion abzufragen hasAction boolean und um die Aktion dann auch auszufiihren performAction Die update Methode ist zur Benachrichtigung der Taktik vorgesehen dass sich der Systemzustand ge ndert hat und sie neu berechnen muss ob sie eine Ak tion ausf hren kann Diese Methode wird automatisch aufgerufen von Klassen die das Interface ITacticHost implementieren wie z B die Klasse Strategy Diese Beziehung gen gt dem Observer Pattern GHJV95 wobei dies hier etwas modi
95. inzukommend wird bei dieser Strategie stets versucht die Energie des Ro boters aufrechtzuerhalten Daf r geht der Explorer regelm ig zur HomeBase zur ck um seine Energie aufzuladen An der HomeBase ankommend schickt der Explorer seine Karte an die HomeBase und erfragt bei selbiger den dieser bislang bekannten Gesamt Explorationszustand Kollisionen mit anderen Ro botern und Hindernissen werden von vorneherein vermieden Die jede aufgerufene Methode compute zeigt durch ihren geringen Umfang eindrucksvoll die Vorziige des Taktik Konzepts protected void compute if energyManagement hasAction if tacticToPerform equals energyManagement getName this setCurrentRegion headForRegion this performAction energyManagement else if headForRegion hasAction this performAction headForRegion else if regionExploration hasAction amp amp this isCurrentRegionNotExplored this setCurrentRegion regionExploration if regionExploration hasAction this performAction regionExploration else if headForUnexploredRegion hasAction this performAction headForUnexploredRegion else if headForHomeBase hasAction this performAction headForHomeBase if obstacleCollisionEvasion hasAction this performAction obstacleCollisionEvasion if robotCollisionEvasion hasAction this performAction robotCollisionEvasion if arrivesAtHome messageData sendMap dynamicMapData getHomeBase messageData sendM
96. ird ein Diaolgfeld ge ffnet in dem man die Gr Se der Karte in dem Spinner angeben muss Des Weitern k nnen Terrains und Sch tze aus xml Dateien geladen wer den oder gespeichert Hierbei wird auch jeweils ein Dialogfeld ge ffnet in dem man den entsprechenden Pfad der zuladenden oder speicherten Datei angeben muss Aus dem Editmen k nnen alle Hindernisse von der Karte gel scht werden daf r wird der komplette Quadtree gel scht bis auf den Wurzelknoten Es k nne auch alle Sch tze entfernt werden daf r werden alle Elemente aus der Liste gel scht Es ist auch m glich den Zoomfaktor der Bigmap zu ndern daf r ffnet sich ein Dialogfeld der einen Spinner und zwei Buttons enth lt Beim Speichern des Faktors wird die Ansicht in der Bigmap dementsprechend sofort aktualisiert Aus dem Extrasmen kann der Generator gestartet werden die Gr Se der 83 6 2 Sch tzeverwaltung 6 EDITOR Schatze verwaltet oder eine Roboterkonfiguration erstellt werden Aus dem Helpmenii heraus kann nur die Bedienungsanleitung des Editors ge ffnet werden 6 1 5 Die Statuszeile Die Statuszeile dient zur Orientierung des Benutzers so zeigt sie z B die Koor dinaten der Mouseposition auf der Karte die in der Bigmap dargestellt wird an Des Weiteren weiS der Benutzer wie gros die Karte ist und um welchen Faktor der Ausschnitt der Karte in der Bigmap vergr ert ist 6 2 Sch tzeverwaltung Die Verwaltung der Sch tze geschieht in einem se
97. issingTypes zeigt an ob ein Roboter der in einem Team ist noch weitere Roboter im Team braucht siehe TeamConfiguration processQueries 1 Gehe alle Nachrichten durch und sammle alle Einladungen INVITE und Best tigungen ACK1 von Einladungen in jeweils 2 Listen Die Liste der Einladungen hei e inviteList die Liste mit den Best tigungen hei e ackiList 2 Fiihre eine Auktion durch zwischen der eigenen Einladung und den frem den Einladungen durch und bestimme so das beste Angebot 3 Falls ich selbst die Auktion gewinne dann verschicke an alle Roboter aus ackiList ein ACK2 und an alle Roboter aus inviteList ein NACK1 Wenn ein anderer Roboter gewinnt dann verschicke an ihn ein ACK1 an die restlichen Roboter aus inviteList ein NACK1 und an alle Roboter aus ackiList ein NACK2 Der Ablauf der Auktion wird momentan randomisiert durchgef hrt Um den noch etwas auf die Wichtigkeit des Gebotes das ja bei jedem INVITE mit geschickt wird einzugehen wird folgendes Konzept verwendet Auf einem Zahlenstrahl der L nge 1 wird jedem Roboter ein Teilst ck zugewie sen das genauso lang ist wie der Anteil seines Gebotes in Bezug zur Summe aller Gebote auch des eigenen Beispiel Wir haben einen Roboter r der Einladungen von den Robotern ra r3 r4 be kommen hat Das Gebot eines Roboters r entspreche b Der Roboter w rfelt 48 4 3 Taktiken 4 ROBOTER MODUL danach Der Gewinner h ngt davon ab in welchem Int
98. isualisierung dass die Simulation pausiert wurde Out SimulationSpeedChanged Benachrichtigt eine Visualisierung dass die Simulationgeschwindigkeit ge ndert wurde Out SimulationStopped Benachrichtigt eine Visualisierung dass die Simulation beendet wurde Out SimulationResumed Benachrichtigt eine Visualisierung dass die Simulation fortgesetzt wurde Out TerrainData Wird aktuell nicht benutzt Out Tabelle 2 Message Typen Teil 2 Zu beachten ist hierbei dass lediglich Nachrichten zum Initialisierungspro zess auch an nicht registrierte Visualisierungen versendet werden Alle anderen Nachrichten werden nur an registrierte Visualisierungen versenden einige zu dem noch unter zus tzlichen Restriktionen In Abbildung 4 ist der vorgeschriebene Nachrichtenverkehr zwischen Kernel und Visualisierung bei Vorhandensein der zu benutzenden Karte auf Visua lisierungsseite angezeigt Fin alternativer Ablauf welcher derzeitig leider nur vorbereitet aber nicht g nzlich implementiert ist wird in Abbildung 5 gezeigt 3 2 3 Roboterverwaltung Die Roboterverwaltung ist ein Teil der Datenstrukturen vom Kernel Hier wird alles bez glich Roboter abgewickelt Zu den fundamentalen Aufgaben einer Ro boterverwaltung z hlen 1 Generierung von Robotern 2 Initialisieren und Pflegen von fundamentalen Datenstrukturen 3 Abwicklung des gesamten interroboter Nachrichtenverkehrs 11 3 2 Simulationsabwicklung und verwaltung 3 SIMULATIONSK
99. jectsInViewRadius Zus tzlich werden noch die Hindernisse im Sichtradius in einer eigenen Liste er fa t staticObjectsInViewRadius Diese Listen werden jede Runde w hrend der Evaluierungsphase aktualisiert Schritt i Se Oo Schrittitl ee o 0 Schritt i 2 ee O O Abbildung 16 DynamicDataList Der Container Der Container entspricht einer Art Ladefl che eines Roboters Der Roboter kann diverse dynamische Objekte in seinen Container legen aufgenommene Objekte werden hier gelagert und er kann gelagerte Objekte natiirlich auch wieder entladen Der Container hat eine Kapazit t das hei t da die Menge der Objekte die er fassen kann begrenzt ist Sch tze werden dabei als Integer Werte angesehen Beim Ablegen eines Schat zes wird ein neues Objekt in der Landschaft mit dem gewiinschten Gewicht erstellt Danach wird die Anzahl der Sch tze im Container einfach verringert Entsprechend wird beim Aufladen die Menge der Sch tze im Container um das Gewicht des neuen Schatzes erh ht und das Objekt in der Landschaft ent fernt Bei den Flags ist das ein wenig anders hier wird zwischen Inhalt und Anzahl unterschieden Das Konzept der Anzahl entspricht dem von Sch tzen jedoch hat der Roboter ggf zu Beginn schon eine Reihe von Flags Au erdem kann er ein aufgehobenes Flag mit beliebigem neuen Inhalt wiederverwenden Es wird zwischen der Menge der Sch tze unterschieden die pro Runde aufgeladen und abgeladen
100. l Quadtrees von dessen Elternknoten wird der gr tm gliche noch unexplorierte Knoten ermittelt Existieren mehrere gleich gro e so wird der von der aktuellen Positi on aus nahestgelegene solche Knoten zur ckgegeben Ist einmal eine Zielregion so berechnet worden wird intern die Taktik HeadForRegion verwendet um dorthin zu gelangen Eine Ausnahme tritt auf wenn der Roboter neue Karten information von anderen Robotern empfangen hat In diesem Fall wird erneut eine Zielregion berechnet da sich die explorierten Teile ge ndert haben k nnten 44 4 3 Taktiken 4 ROBOTER MODUL Au erdem wird an der Basisstation ein neues Ziel berechnet wenn der Para meter NewTargetAtHomeBase auf true gesetzt wird Default Wert false Dies kann im Einklang mit der Energieveraltung stehen Die Laufzeit des Findens einer nahegelegenen unexplorierten Zielregion ist li near abh ngig von der Tiefe des Quadtrees also O 1 Sie findet bei Bedarf in hasAction statt Es wird kein relevanter Speicherplatz daf r ben tigt Alle weiteren relevanten Berechnungen entsprechen denen von HeadForRegion 4 3 3 HeadForRobots Die Taktiken in HeadForRobots dienen dazu bestimmte Roboter oder Roboter typen anzustreben Das Anstreben funktioniert grunds tzlich so dass versucht wird den direkten Weg zum Zielroboter zu nehmen etwaige Hindernisse im Weg des Roboter werden mit der integrierten Taktik WalkAlongBoundaries siehe oben umlaufen HeadForHomeBa
101. l modulo update Intervall gerechnet Setzen wir einfachheitshalber das update Intervall auf Das ist mit Flexibilit t gemeint In der Literatur manchmal auch als Listener bezeichnet 91 7 3 Sammeln der Messwerte 7 MESSGR SSEN 10 d h jede zehnte Runde k nnen wir eine Aktion durchf hren Ziel dieser Vorgehensweise ist es jede x te Runde Daten aus den Datenstruk turen herauszuholen und in eigenen Datenbeh ltern DataBags zu speichern um sie bei Bedarf Diagrammen zu bergeben die sie dann anzeigen k nnen Der Zugriff auf die Daten erfolgt ber die Klasse SceneControl Dies hat den Vor teil dass man auf alle Datenstrukturen des Kernels Roboter Gel ndespeicherung dynamische Objektet zugreifen kann Es ist somit auch m glich auf einzelne Roboter und deren Datenbeh lter StandardDetails ExploredMap Elementa ryAction usw zu zugreifen und daraus die relevanten Daten heraus zu ziehen 7 3 Sammeln der Messwerte Wie oben beschrieben k nnen jede x te Runde Daten herausgezogen bearbeitet und in eigenen Datenbeh ltern gespeichert werden Die Daten k nnen je nach Wahl des Diagrammtyps in zwei Beh ltern gespeichert werden 1 DefaultCategoryDataset dataset Ein und zwei Fl chendiagramm 2 DefaultPieDataset pieDataset Kuchendiagramm robot position energy speed and flags Value 545833233 5858 i la ee ES ES m Ene
102. lags mit der bergebenen ID sofern vorhanden removeFlagContent FlagID flagID L scht den Inhalt des Flags mit der bergebenen ID sofern vorhanden removeAllFlagContents L scht den Inhalt aller aufgehobener Flags IRobotFeatures ber diese Schnittstelle k nnen alle wesentlichen Eigen schaften des Roboters ebenso wie Informationen ber die gesamte Simulations situation abgefragt werden In der folgende Auflistung werden diese vorgestellt RobotID getRobotID Gibt die ID des Roboters zur ck RobotType getRobotType Gibt den Typ des Roboters zur ck float getViewRadius Gibt den Sichtradius des Roboters zur ck float getCommunicationRadius Gibt den Kommunikationsradius des Roboters zur ck float getMaximumSpeed Gibt die maximale Geschwindigkeit des Ro boters in Metern pro Runde zur ck int getContainerCapacity Gibt die gesamte Kapaziz t des Containers des Roboters zur ck float getEnergy Gibt die aktuelle Energie des Roboters zur ck float getEnergyConsumption Gibt den Energieverbrauch pro Runde des Roboters in Prozent zur ck float getEnergyLoad Gibt den Wert zur ck den ein Roboter an Energie pro Runde maximal an der Homebase aufladen kann int getToolSize Gibt die Gr e des Werkzeugs des Roboters zur ck Das Werkzeug dient dem Roboter zum Bearbeiten von Objekten vorwiegend also zum Abbauen von Sch tzen Die Gr e des Werkzeugs entspricht der maximal pro Runde bearbeitbar
103. lge von passenden Elementaraktionen an die Aktionsliste an e loadObject GroundObjectID objectID int totalAmount int amountPer Round int index Fiigt eine aus Anzahl insgesamt und pro Runde aufzu hebender Objekte zu berechnende Folge von passenden Elementaraktio nen in der Aktionsliste zwischen index und index 1 ein 39 4 3 Taktiken 4 ROBOTER MODUL 4 3 Eine unloadObject GroundObjectID objectID int totalAmount int amountPer Round Fiigt eine aus Anzahl insgesamt und pro Runde abzulegender Objekte zu berechnende Folge von passenden Elementaktionen an die Ak tionsliste an unloadObject GroundObjectID objectID int totalAmount int amountPer Round int index Fiigt eine aus Anzahl insgesamt und pro Runde abzu legender Objekte zu berechnende Folge von passenden Elementaraktionen in der Aktionsliste zwischen index und index 1 ein unloadObject GroundObjectID objectID IFlagContent content Fiigt ei ne Entladeaktion eines Objektes mit dem bergebenen Inhalt an die Ak tionsliste an F r Sch tze sollte ein int als Anzahl bergeben werden f r Flags ein beliebiger Inhalt unloadObject GroundObjectID objectID IFlagContent content int in dex F gt eine Entladeaktion eines Objektes mit dem bergebenen In halt in die Aktionsliste an die bergebene Stelle ein F r Sch tze sollte ein int als Anzahl bergeben werden f r Flags ein beliebiger Inhalt sendMessage ArrayList lt Messagelnformation gt messages
104. lich vorsieht solange mit der Abarbeitungsreihenfolge zu warten bis alle Arbeitsthreads ihre Aufgabe beendet haben Die Anpassung des Kernels an das Threadkonzept f hrte einiges Weitere mit sich Die zentralen Datenstrukturen mussten nun gegen gleichzeitiges Manipu lieren abgesichert werden um Inkonsistenzen und Fehler zu vermeiden Leider fiihrte der Versuch dies mit synchronized Methoden zu bewerkstelligen zu enor men Performanceeinbriichen Dies veranlasste mich eine Art Pufferstruktur zu etablieren Genauer bedeu tet dies dass nicht mehr die vom Roboter gewollte Aktion direkt durchgefiihrt wird und somit Datenstrukturmanipulationen nach sich zieht sondern ledig lich diese Aktionsausf hrung als gewollt abgespeichert wird So tr gt jeder Ro boter seine gewollten Aktionen in eine fiir jeden Arbeitsthread existierende HashMap ein Diese werden anschliesend vor Beginn der neuen Runde sequen tiell durchlaufen und die zuvor gewollten Aktionen nun in die Datenstruktur bernommen 3 2 2 Messages Unter Messages fassen wir zwei verschiedene Typen auf 1 Messages zur Kommunikation mit Visualisierungsmodulen 2 Messages zur Inter Roboter Kommunikation Letztere werden im Kapitel Roboterverwaltung n her betrachtet In diesem Kapitel m chten wir uns mit dem unter Punkt 1 erw hnten Nach richtentypen besch ftigen Hierbei ist wichtig zu erkennen dass Messages keine TCP Packete oder dergleichen sind Der konkrete Transport wird ber
105. lyse der Teilmodule findet sich in ihren jeweiligen eige nen Kapiteln 2 1 Architektur des Gesamtsystems Abbildung 2 zeigt die grobe Architektur des gesamten Smartteams Systems Me gr en Framework Editor Generator Visualisierung Simulationskernel Robotermodul E 2D Visu Abbildung 2 Die Architektur des Gesamtsystems Das System setzt sich dabei aus den Hauptkomponenten Simulationskernel Robotermodul und Visualisierung zusammen zus tzlich umfa t es einen Editor und das Me gr en Framework Diese Komponenten werden im folgenden kurz erl utert und in ihren jeweiligen Kapiteln detailliert dargestellt 2 2 Simulationskernel Im Simulationskernel l uft die eigentliche Simulation ab Er speichert die Karte und f hrt Roboteraktionen auf ihr durch Des weiteren wickelt er die Kommunikation unter den Robotern ab und bietet eine Schnittstelle f r die Visualisierung der Simulation Fine genaue Beschreibung findet sich in Kapitel 3 2 3 Robotermodul Das Robotermodul detailliert beschrieben in Abschnitt 4 ist ber Schnitt stellen mit dem Simulationskernel verbunden und daf r verantwortlich die Ro boteraktionen zu berechnen und vorauszuplanen Des Weiteren ist es f r die 2 4 Visualisierung 2 ARCHITEKTUR UND KOMPONENTEN Datenhaltung der Roboter verantwortlich Strategien und Taktiken werden im Robotermodul implementiert 2 4 Visualisierung Die Visualisierung ausf hrliche Beschreibung in Abschnitt 5
106. m Kartenrand oder in einem Hindernis endet So bald eine g ltige Richtung generiert wurde wird die while schleife abgebrochen Sollte die als n chst auszuf hrende Bewegungsaktion nicht den Kartenrand erreichen bzw berschreiten wird berpr ft ob die Bewegung in einem Hindernis endet Falls dies der Fall ist wird nun mit Hilfe der Taktik Walk AlongBoundaries der Roboter um das Hindernis herum geleitet bis die angestrebte Richtung wieder Hindernisfrei ist Bei einer Hindernisfreien Richtung wird diese so lang beibe halten bis einer der oben beschriebenen F lle Kollision mit Hindernis oder Karetnrand eintritt 4 4 4 TreasureGreedStartegy Bei dieser Strategie ist das Ziel die Erkundung der Karte Lokalisierung Abbau und Abtransport von Sch tzen Der Roboter befindet sich stets in einem der folgenden Zust nde e SearchTreasureState Exploration der Karte Suche nach Sch tzen e WalkToTreasureState Roboter bewegt sich zum gefundenen Schatz e WorkTreasureState Sch tze abbauen e LoadTreasureState Sch tze aufladen e WalkToHomeBaseState Roboter bewegt sich zu HomeBase e UnloadTreasureState Sch tze abladen Zu Beginn der Simulation startet der Roboter im Zustand Search TreasureState d h er erkundet die Karte und ist auf der Suche nach Sch tzen So bald sich ein Schatz im Sichtradius des Roboters befindet wechselt die Strategie den Zu stand nach WalkToTreasureState In diesem Zustand verfolgt der Roboter den direkten
107. m TerrainQuadtree gespeicherten Gel nde bernimmt F r eine bessere Bildqualit t werden in inneren Knoten die zu geh rigen Farben der Kinder interpoliert Abbildung 34 Repr sentation der Karte im TerrainQuatree in unterschiedli chen Detailgraden In gr beren Detailgraden werden die Werte der Kinder interpoliert um auch feine Strukturen bei kleinen Zoomstufen angen hert darstellen zu k nnen wae Sh Abbildung 35 Resultat des Gel ndezeichnens ohne und mit Interpolation 69 5 2 Wichtige Klassen 5 VISUALISIERUNG 5 2 4 Detailansicht 5 2 5 Erkundete Karte und abgelaufene Wege Die 2D Visualisierung ist dazu in der Lage die erkundete Karte einzelner sowie aller Roboter anzuzeigen Dazu wird wenn dieses erstmalig vom User angefor dert wird der Quadtree der erkundeten Karte vom Roboter ber den Kernel zur Visualisierung geschickt und dort in einer eigenen Datenstruktur zu finden in der Klasse ExplorationQuadtrees gespeichert Weil das sinnvollerweise jede Runde die die explorierte Karte angezeigt werden soll geschehen m te damit die angezeigte explorierte Karte immer auf dem neuesten Stand ist w re die Netzwerklast sehr schnell sehr hoch Also werden die einzelnen Quadtrees vi suseitig nicht nur gespeichert sondern auch in jeder neuen Runde aktualisiert indem der Quadtree um das vom Roboter gesehene Gebiet erweitert wird Zus tzlich bietet die 2D Visualisierung die M glichkeit die abgelaufenen Wege
108. mit Hilfe der Tak tik WallkAlongBoundaries elegant umgangen Hat der Roboter die Homebase ereicht wechselt die Strategie nun in den Zustand UnloadTreasureState In die sem Zustand bleibt die Strategie so lange bis die Sch tze aus dem Container vollst ndig entladen sind So bald die Sch tze entladen sind wird durch den Aufruf this host hasRemainingTreasure abgefragt ob an der zu letzt besuch ten Schatzposition beim verlassen noch Sch tze vorhanden waren Falls dies der Fall ist wechselt die Strategie in den Zustand WalkToTreasureState um die restlichen Sch tze abzutransportieren Falls jedoch beim verlassen der Schatz position keine Sch tze mehr vorhanden waren wechsel die Strategie in den Zustand Search TreasureState und ist somit auf der Suche nach neuen Sch tzen Der gesamte Ablauf ist der Abbildung 29 zu entnehmen 60 4 4 Strategien 4 ROBOTER MODUL Sch tze in Sichtradius nicht leer Schatz noch nicht erreicht Keine Schatze in Sichtradius Gehe zu Schatz Verfolge Weg weiterhin k Erkund Karte Schatz erreicht Schatz abbauen en Schatz Schatz verschwunden Erkund Karte Container Kapazit t hatz ab Container leer und Schatz abbauen kein Schatzrest Erkund Karte Schatz erreicht und abgebauter Schatz Container Kapazit t Lade Schatz Container leer und Schatzrest vorhanden Laufe zu Schatz Container nicht leer Laden Schatz ab Abgebauter Schatz Co
109. n 75 Hindernisstrukturen an den Ecken h her aufl sen 75 Quadtree balancieren 2 2 Comm one 75 Iterativ Abst nde zum Rand berechnen 2 76 Dreiecke generieren 2 2 222 n ee 76 Einf gen eines kleines Dreiecks in einen Loose Octree 77 Beispiel f r pullUpSamples o o o 78 Beispiel fiir compressTreeStructure o o ee 79 Verschieben des Mittelpunktes bei shrinkBoundingBozes 79 Grober Aufbau der GUI o 81 Grober Aufbau der Sch tzeverwaltungsGUl 84 Aufbaue der RoboterkonfiguratiosnGUI 85 Aufbau eines RegionQuadtrees 000 0000 8 86 Klassen des Generators 0 00000 eee eee 87 Klassen des Wizards u a moa sos ae Re etii me RA we eS 88 Hilfsklassen f r Random function 90 Architektur des Messgr en frame works o o 91 Zwei Fl chendiagramm Balken und Kuchendiagramm 92 98 Tabellenverzeichnis Tabellenverzeichnis Tabellenverzeichnis 1 Message Typen Teill o o 10 2 Message Typen Teil 2 nn nn 11 3 Zustandsautomat der Klassse MainControl 66 4 Update Methoden f r die Ablaufsteuerung im Visualisierungs TO acord a a a ea E 67 5 Namensunterschiede von Methoden zwischen Implementierung und Paper 6 2 2 32 04 2 a a A eo ye 77 6 Testergebniss der Simulation mit unterschiedlichen Karten 80
110. n in der actionList in einer Kollision mit einem Hindernis en det Wenn das der Fall ist wird der Winkel um 90 Grad erh ht Das bedeutet der Roboter wendet um 90 Grad nach rechts Der Winkel wird so lange erh ht bis der Weg frei ist Falls jedoch die Bewegungsaktion in der actionList kein Kollision mit Hindernissen darstellt wird gepr ft ob das wenden nach Links m glich ist Ist das wenden m glich wird der aktuelle Winkel um 90 Grad re duziert und die vorliegende Bewegungsaktion durch eine neue mit dem neuen Winkel ersetzt Ist hingegen das Wenden nach links nicht m glich wird der aktuelle Winkel beibehalten Der Wert der Variable obstacleReached diem ers ten Aufruf von performAction auf true gesetzt Ist der Wert true wird beim Aufruf der Methode hasAction gepr ft ob eine Bewegung um 90 Grad nach links m glich ist Wenn dies m glich ist wird gepr ft ob eine Bewegung um 135 Grad nach links m glich ist Falls dies ebenfalls m glich ist wird der Wert von obstacleReached auf false gesetzt Das bedeutet dass der Roboter das Hinder nis nicht mehr umkreist Diese Funktion ist wichtig damit der Roboter nicht ewig um das Hindernis kreisen soll Das hei t man gibt in der Strategie eine Bewegungsaktion in die ActionList ein die von dem umkreisenden Hindernis wegf hrt Ruft man jetzt die Methode hasAction auf so wird diese feststellen dass das Hindernis nicht mehr umkreist wird Die Taktik OrbitLeft Around ist analog zu OrbitRight
111. n liegt nach wie vor im Mittelpunkt rechts Schrumpfen mit Verschiebung das darf nicht passieren Der Stein l ge nicht mehr im Mittelpunkt und w rde verschoben dargestellt gestrichelter Kreis W re an Stelle des Steins ein gleichgro es Drei eck so w re dies das korrekte Resultat der shrinkBoundingBoxes Methode Abbildung 46 Verschieben des Mittelpunktes bei shrinkBoundingBoxes 79 5 3 Preprocessing 5 VISUALISIERUNG 5 3 3 Ein paar Zahlen Gemessen auf einem Intel Core2 2 66GHz mit 4GB RAM und Xmx2500G Karte 512M moreReal leopard terr8192 benchm16km Quadtree Knoten 840 17 178 127 314 55 240 1 190 776 Quadtree Blatter 330 9 046 75 596 21 230 504 058 Preprocessing Zeit 6 6 s 9 9 s 27 s 94 s 510 s Preprocessing RAM 45M 11M 75 M 335 M 1 540 M Octree Knoten 5 037 19 884 138 547 750 426 3 254 970 Dreiecke 28 335 113 954 944 367 3 988 950 19 359 238 Steine 39 837 1 013 395 126 165 Ladezeit 0 7 s 0 8 s 5 6 s 23 s 128 s RAM 25M 52M 35 M 145 M 770 M Karte 16_10000 1615000 1630000 16100000 terrl00km Quadtree Knoten 578 157 861 736 1 687 942 5 369 011 4 947 243 Quadtree Blatter 295 419 443 029 877 994 2 862 177 3 752 398 Preprocessing Zeit 67s 101 s 212 s Preprocessing RAM 305 M 430 M 830 M out of mem bei 2 5 G Octree Knoten 555 053 830 613 1 647 228 NN Dreiecke 2 567 952 3 845 391 7 642 939 Steine 0 0 0 u Ladezeit 20 s 29 s 58 s SS RAM 120 M 175 M 347 M Tabelle 6 T
112. nd ein Paar Dinge zu beachten Daher hier eine kurze Anleitung Projekt aus CVS auschecken Der Code ist als vollst ndiges Eclipse Projekt im CVS enthalten Man kann es in Eclipse einbinden indem man beim Anlegen eines neuen Projekts project from CVS ausw hlt Die notwendigen Einstel lungen sind zum Zeitpunkt des Schreibens dieses Abschnittes e host sshgate cs upb de e path home f fg madh pg smartteams e user IMT Userdaten e connection type extssh e module smartteam Da die JOGL Bibliotheken plattformabh ngig sind muss jeder Benutzer indi viduell einstellen welche Version zu verwenden ist e in der Men leiste Window Preferences anw hlen e auf der linken Seite Java Build Path User Libraries ausw hlen e ganz rechts per New die User Library jogl erstellen e den neu erstellten Eintrag jogl ausw hlen e dann mit Add JARs folgende Bibliothek hinzuf gen Pfad zum Projekt lib Betriebssystem jogl jar e nochmal den Eintrag jogl ausw hlen e die gluegen rt jar aus dem selben Ordner hinzuf gen e beide JAR Eintr ge aufklappen dort Native library location ausw hlen e auf der rechten Seite per Edit folgenden Pfad im Workspace einstellen smartteam lib Betriebssystem einstellen Jetzt sollte der Code alle Bibliotheken finden und kompilierbar sein Um das Projekt zu starten muss in der Start Konfiguration unter dem
113. nelDescriptor RuntimeException WizardPanelNotFoundException Abbildung 52 Klassen des Wizards Die Klasse Wizard Diese Klasse implementiert einen grundlegenden Assistenten Dialog wo Pro grammierer eine oder mehrere Komponenten wie Panels behandeln k nnen Die se Panels k nnen beliebig durch Verwendung von Back oder Next Buttons navigiert werden oder den Dialog schliesen mit dem Cancel angeklickt wird Beachten Sie dass obwohl der Dialog ein CardLayout Manager verwendet ist die Reihenfolge der Felder nicht linear Jede Gruppe bestimmt w hrend der Laufzeit was ihre n chsten und vorherigen Panels sind Die Klasse WizardController Diese Klasse behandelt alle Ereignisse die durch Driicken eines der drei But tons Next Back und Cancel erzeugt werden In Abh ngigkeit was f r ein Button gedriickt wurde zeigt der Controller das aktuelle Panel und setzt die Zust nde von Buttons Die Klasse WizardModel Das Model fiir die Wizard Komponente enthalt Text Symbole und aktiviert einzelne Tasten sowie aktuelle Seite die angezeigt wird Beachten Sie dass das Modell in seiner jetzigen Form nicht eine Subklasse ist Die Klasse WizardPanelDescriptor Diese Klasse wird als Referenz fiir ein Panel im Wizard benutzt und beinhaltet alle Regeln wie sich ein Panel verhalten soll 88 6 5 Generator 6 EDITOR 6 5 3 Generatorimplementierung Der Generator Wizard besteht aus 4 Seiten e
114. ng 1 dargestellt Die Karte auf der die Roboter agieren nehmen wir als einen zweidimensionalen rechteckigen Ausschnitt aus einer Ebene an Darauf befinden sich eine Vielzahl von Hindernissen mit beliebiger Form Sie definieren Areale in denen Roboter sich nicht bewegen d rfen Es gibt zus tzlich eine einzelne Basisstation wel che als Startpunkt f r alle Roboter dient Dieses sind die statischen Elemente welche sich nach dem Start einer Simulation nicht mehr ver ndern 1 4 Projektteam 1 EINF HRUNG Im Gegensatz dazu gibt es noch dynamische Elemente Roboter und Sch tze Letztere k nnen von Roboter ausgegraben und transportiert werden Sie k nnen an jeder beliebigen stelle auf der Karte in unterschiedlichen Quantit ten vor kommen Desweiteren k nnen sich die Roboter in den passierbaren Regionen v llig frei bewegen Jeder Roboter hat einen Energievorrat der sich im Laufe der Zeit verringert abh ngig von den Aktionen die er ausf hrt aber an der Basisstation wieder aufgeladen werden kann Sollte ein Roboter jemals seinen kompletten Energievorrat verbrauchen so ist er f r den Rest der Simulati on deaktiviert Roboter empfangen Informationen ber ihre Umgebung inner halb eines festen aber frei w hlbaren Sichtradius Kommunikation mit anderen Robotern und somit der Austausch von Informationen ist analog durch einen Funkradius beschr nkt Es gibt verschiedene Robotertypen die alle gewisse Re striktionen haben Beispielsweise kann
115. ngsam und selten kommen und somit die ganze Navigation sehr ruckelnd wirkte 5 3 Preprocessing Im Kernel reicht es das Gel nde in Hindernis und kein Hindernis einzu teilen F r eine ansprechende Darstellung reicht dies nicht aus F r die 2D Visualisierung m ssen die Daten so aufbereitet werden dass auch die ganze Karte wenn stark herausgezoomt wird fl ssig gezeichnet werden kann dazu m ssen gr ere Fl chen durch einzelne Grauwerte approximiert werden F r die 3D Visualisierung m ssen aus den 2D Daten zun chst dreidimensionale Hinder nisse erzeugt werden und diese anschlie end in einer Datenstruktur gespeichert werden die das fl ssige Rendern erlaubt Da dieser Prozess speicher und zeitaufwendig ist findet er einmalig statt Da im Preprocessing Zeit nicht so eine gro e Rolle spielt wurde eher auf Spei cherverbrauch als auf Laufzeit optimiert Die resultierenden Datenstrukturen werden in Dateien geschrieben So k nnen die vorverarbeiteten Daten ohne lange Wartezeit in die Visualisierung geladen werden Der TerrainFor VisuConverter ist f r das Preprocessing zust ndig Er wird vom Editor oder per Kommandozeile aufgerufen und erh lt eine XML Gel ndebeschreibung Er delegiert die Erzeugung der 2D bzw 3D Daten an das Terrain2D bzw Ter rain3D Sind diese mit dem Preprocessing fertig werden sie in eine Datei se rialisiert welche im selben Ordner wie die XML Datei liegt und deren Namen sich nur durch die
116. nierter Regionen der Karte Wird fiir das Versenden von Kartenteilen ben tigt Default Wert ist 1 TacticManager Eine Instanz des Tacticmanagers erm glicht es einer Strate gie auf alle zu Verf gung stehenden Taktiken zuzugreifen um diese zu benut zen In einer zu implementierenden Strategie die eine Unterklasse der Klasse Strategy ist hat man bereits die M glichkeit auf eine Referenz der Klasse TacticManager zuzugreifen Dabei stehen folgende Methoden zu Vef gung e IMovementTactic useMovementTactic String name Gibt eine Instanz der zu verwendenden Taktik vom Typ Bewegung urueck e TargetMovementTactic useTargetMovementTactic String name Gibt ei ne Instanz der zu verwendenden Taktik vom Typ Bewegung zu Ziel Burueck e IDecisionTactic useDecisionTactic String name Gibt eine Instanz der zu verwendenden Taktik vom Typ Entscheidung urueck e ITeamTactic useTeamTactic String name Gibt eine Instanz der zu ver wendenden Taktik vom Typ Team urueck e void reset De registriert alle Taktiken vom das Interface ITacticHost implementieren und entlaedt diese auch aus der internen Verwaltung Eine Besonderheit der Taktiken ist dass sie zu Laufzeit geladen werden k nnen und durch den Aufruf reset wieder von der Strategie entkoppelt werden k nnen In der Klasse ExplorationGreedStrategy des smartteam Projekts kann eingesehen werden wie Taktiken benutzt werden ActionList Durch eine Instanz der Klasse
117. nikation mit der Visualisierung ist an zweierlei Stellen implementiert Einerseits mittels Interfaces die ebenfalls vom Kontrollmodul implementiert werden und die grunds tzliche Kommunikation ber RMI erm glichen und andererseits ber eine ganze Reihe von VisuMes sages Diese kapseln jeweils wichtige Informationen beispielsweise ber Simu lationsstatus oder ber Roboteraktionen und k nnen sowohl von Kernel zur Visualisierung f r beispielsweise Roboterdetails als auch von der Visualisie rung zum Kernel beispielsweise zur entfernten Steuerung des Kernels gesendet werden Mehr dazu findet sich in Abschnitt 3 2 2 Zu guter Letzt gibt es die graphische Benutzerschnittstelle des Kernels mittels dieser k nnen Karten oder Roboter und Schatzkonfigurationen geladen werden und die Simulation gestartet und gesteuert werden 3 2 Simulationsabwicklung und verwaltung Das Design des Kernels beschr nkt sich auf die Idee von wenigen Teilmodulen Innerhalb derer lassen sich abermals Submodule identifizieren bzw Strukturen welche solchen entsprechen Die Hauptarbeit das Simulieren von Roboterverhalten verrichtet der Kernel mit Hilfe von Arbeitsthreads Diese sind zum Abarbeiten der einzelnen Roboter da Aufgrund der Dual Kern Architektur unseres Referenzsystems wurden zwei Arbeitsthreads gew hlt auf welche ich sp ter n her eingehen werde Dar ber hinaus ist der Kernel die zentrale Einheit zur Nachrichtenabwick lung Darunter fallen
118. ntainer Kapazit t oder gesamter Schatz abgebaut Lade Schatz Homebase erreicht Laden Schatz ab Load reasure State Container voll Container nicht voll oder und Homebase nicht erreicht letzter Schatz aufgeladen transportierbarer Schatz noch vorhanden Verfolge Weg weiterhin Gehe zu Homabase Lade Schatz Abbildung 29 Zustandsautomat der Strategie TreasuregreedStrategy 4 4 5 WorkerStrategy Strategie die f r Roboter vom Typ Worker oder Multirobot geeignet ist Ein Roboter der diese Strategie benutzt ist also in der Lage die Karte zu erkunden und falls er dabei Sch tze lokalisiert werden diese abgearbeitet Zweck dieser Strategie ist f r einen Roboter vom Typ Transporter die Sch tze aufbereiten so dass dieser beim erreichen der Schatzpositionen die Sch tze aufladen und zu HomeBase transportieren kann Ein Roboter der die Strategie WorkerStrategy benutzt befindet sich zu jedem Zeitpunkt in einem der folgenden Zust nde e SearchTreasureState Exploration der Karte Suche nach Sch tzen e WalkToTreasureState Roboter bewegt sich zum gefundenen Schatz e WorkTreasureState Sch tze abbauen Zu Beginn der Simulation befindet sich der Roboter im Zustand Search Treasu reState d h er erkundet die Karte und h lt Ausschau nach Sch tzen So bald ein Schatz in seinem Sichtradius auftaucht wechselt die Strategie in den Zu stand WalkToTreasureState Nach jeder Runde wird berpr ft ob der Roboter den
119. ntereinander hergestellt 4 1 2 PhysicalUnit Das Package physical repr sentiert die physikalische Schicht des Roboters Neben der zentralen Kontrollklasse PhysicalUnit die die Ordnungsm igkeit aller Operationen des Roboters gew hrleisten soll beinhaltet dies die vier phy sikalischen Schnittstellen zum Kernel die MotionUnit f r Bewegungen des Ro boters die SensorUnit f r die Ermittlung von Robotern statischen und dyna mischen Objekten im Sichtradius die CommunicationUnit zum Ermitteln von Robotern im Kommunikationsradius und zum Empfangen und Versenden von Nachrichten sowie die ToolUnit f r das Bearbeiten Ablegen und Aufheben von dynamischen Objekten In der Initialisierung erh lt die PhysicalUnit von der RobotControl Zugriffe auf die RobotData ber das Interface IPhysicalToData eingeschr nkten Zu griff auf den Kernel Interface IRobotToKernel sowie die Eigenschaften des Ro boters IRobotFeatures und initialisiert den Rest des Packages Eine Aufgabe der PhysicalUnit ist die Ermittlung aller Umgebungsdaten ber die passenden Schnittstellen und die Weitergabe der Daten an die RobotData Dabei werden nie ung ltige Daten weitergegeben also etwa null sondern im Zweifelsfall leere Listen und dergleichen Weiter wird hier die Ausf hrung von Elementaraktio nen eingeleitet wobei sichergestellt wird dass alle Aktionen den F higkeiten des Roboters entsprechen Schlie lich ist die PhysicalUnit der Speicherort der korrekten
120. oboter befindet sich nun zun chst au erhalb der SubA rea OutOfAreaState Abb 24 und betritt diese nun von irgendeinem Punkt aus Die Strategie initialisiert in diesem Moment die Datenstruktur StripedArea welche die Stripes erstellt und verwaltet Dann bewegt sich der Roboter zum n chstgelegenen StripeEndCheckpoint eines der u eren beiden Stripes Mo ve ToStartStripeState Abb 24 Angenommen die Strategie ist an dem rechts oberen StripeEndCheckpoint angekommen in Abbildung 26 entspricht dies Punkt A Nun wird der Roboter versuchen auf direktem Weg an das entge gengesetzte Ende des Stripes zu gelangen ExploreStripeState Abb 24 Am Punkt B bemerkt die Strategie ein unbekanntes Hindernis und setzt daher einen ObstacleCheckpoint um es auf diesem Stripe als gesehen zu markieren Zus tzlich wird das bis hierhin entlanggelaufene Segment des Stripes als ex ploriert markiert Dann geht die Strategie in einer festgelegten Richtung an dem Hindernis entlang MoveForwardAlongObstacleState Abb 24 und trifft schlie lich auf den Rand der SubArea markiert durch Punkt C Hier wird ein BorderCheckpoint gesetzt der sp ter noch gebraucht wird Die Strategie beschlie t umzudrehen und das Hindernis in der anderen Richtung entlangzu gehen MoveBackwardAlongObstacleState Abb 24 Auf ihrem Weg setzt sie bei jedem Auftreffen auf einen Stripe einen ObstacleCheckpoint falls noch kei ner existiert Wenn sie an Punkt D angelangt ist kehrt sie zum Au
121. on ergibt liefert walk AlongBoundaries hasAction true als Ergebnis Somit wei man dass die geplante Bewegung eine Kollisi on mit einem Hindernis darstellt In diesem Fall kann nun mit dem Aufruf von walkAlongBoundaries performAction eine alternative Bewegung berech net werden Das Hei t in diesem Fall dass die geplante Bewegungsaktion aus der ActionList entfernt wird und eine neue Bewegungsaktion die um das Hinder nis herum f hrt eingef gt wird In der Strategie braucht man sich aber darum nicht k mmern d h mit walkAlongBoundaries hasAction wird festgestellt ob eine Kollision bevorsteht und mit walkAlongBoundaries performAction wird eine Kollision vermieden und gleichzeitig die Ziele der Strategie bevorzugte Richtung angestrebt Es stehen eine Reihe von Taktiken zu Verf gung die im Kapitel 4 3 1 nachgeschlagen werden k nnen Um ein vollst ndiges Beispiel ei ner Strategie einzusehen wird die Klasse ExplorationGreedStrategy aus dem smarteam Projekt empfohlen 4 2 2 Taktikkonzept Viele Strategien f hren immer wieder die selben Teilschritte aus wie z B ein Hindernis zu umrunden oder zur ck zur Basisstation zu gehen Dieses kann man auch als lokale Strategie auffassen oder kurz Taktik Um dem Entwickler die Ar beit zu erleichtern wurde ein Konzept entwickelt mit dem Taktiken gekapselt werden k nnen Damit brauch eine Taktik nur einmalig entworfen werden und kann dann von Entwicklern in jeder Strategie auf einfache W
122. ordert aber das Gel nde wurde nicht gefunden und wird daher beim Kernel angefragt TERRAIN_INITIALIZED Das Gel nde wurde initialisiert aber der Kernel hat noch nicht zum Initia lisieren der Scene aufgefordert SCENE_INITIALIZED Das Gel nde und die Scene wurden initialisiert aber der Kernel hat noch keine Runde gestartet SIMULATION_RUNNING Die Simulation l uft SIMULATION_PAUSED Die Simulation wurde pausiert Tabelle 3 Zustandsautomat der Klassse MainControl Mittels des Zustandsautomaten ist auch die Fehlerbehandlung implementiert Nachrichten vom Kernel werden nur immer in bestimmten Zust nden akzep tiert kommen zum Zustand nicht passende Nachrichten an werden diese nicht akzeptiert und es wird eine Fehlermeldung ausgegeben 66 5 2 Wichtige Klassen 5 VISUALISIERUNG Ein weiteres wichtiges Konzept der Ablaufsteuerung im Visualisierungsmodul ist die Implementierung des Observer Patterns wie bereits in Abschnitt 5 1 kurz angesprochen wurde Dieses Pattern sieht folgendes vor Objekte die ber nderungen im Kernel informiert werden sollen dazu z hlt insbesondere die konkrete Anzeige der Simulationsdaten aber beispielsweise auch Datenhal tungsobjekte registrieren sich beim Subject Objekt und zwar f r eine oder mehrere von verschiedenen Update Methoden Diese werden bei bestimmten Events dann in allen registrierten Objekten aufgerufen und sind im einzelnen Zustand Beschreibung f
123. ormen einzugeben Die Berechnung erfolgt folgendermassen Eingegebener Wert dieser Form Anteil einer Form von 100 Summe aller Werte von ausgewahlten Formen In Abbildung 53 sind alle Klassen die Random function benutzt dargestellt 89 6 5 Generator 6 EDITOR Forms isSelected addForm selected maxSize minSize name part imageName SY IN ASN Quadrat Tee addForm Abbildung 53 Hilfsklassen f r Random function Rectangle Rectangle addForm Das Panel Settings for file function Hier k nnen Parameter f r File function eingestellt werden Diese Funktion dient der Generierung einer Karte aus einem Bild Zur Zeit werden BMP JPG GIF und PNG Bild Formate unterst tzt Bei der Generierung wird alles was nicht wei ist als Hindernis interpretiert Das Panel Creating the map Hier wird den Fortschritt der Generierung mit Hilfe eines Balken angezeigt Bitte beachten Sie dass die Generierung einige Zeit in Anspruch nehmen kann 90 7 MESSGROSSEN 7 Messgr en 7 1 Einleitung Ein Hauptziel der PG Smarteams war es eine Plattform zu entwickeln um un terschiedliche Strategien in der Simulationsumgebung durchspielen zu k nnen Um diese Strategien besser zu analysieren wurde ein Framework entwickelt um relevante Daten der Strategien zu aggregieren und zu visualisieren Dabei wurde besonders Wert auf leichte Benutzung und Flexibilit t d
124. oter 2 s Roboter 2 Abbildung 18 SidestepRobotEvasion mit Parameterwert AngularRight l sst Roboter schr g aneinander vorbeigehen WalkAlongBoundaries WalkAlongBoundaries ist eine Taktik zum Umgehen von Hindernissen basie rend auf dem aus der Literatur bekannten Pledge Algorithmus Ein Hindernis wird dabei entlang dessen W nden umgangen Folgendes Vorgehen wird dabei verfolgt sobald eine Bewegung eines Roboters ein Hindernis treffen w rde Der Roboter dreht sich in eine Richtung zu Beginn rechts und versucht in diese weiterzugehen Ist das nicht m glich dreht er sich in 90 Grad Schritten solange weiter bis ihm kein Hindernis mehr im Weg ist pro Drehung erh ht sich ein interner Z hler um 1 Dabei benutzt er normalerweise die bzgl Hinder nissen und Roboterf higkeiten maximale m gliche Geschwindigkeit es sei denn er w rde dadurch an kleine L cken in Hindernissen vorbeilaufen In diesem Fall reduziert er die Geschwindigkeit entsprechend Jede Runde versucht der Robo ter nun sich wieder zur ckzudrehen sucht als nach Abbiegem glichkeiten nach links Ansonsten geht er weiter geradeaus oder dreht sich wenn n tig weiter nach rechts Jede Linksdrehung dekrementiert den Z hler wieder um 1 Nach Pledge Algorithmus ist das Hindernis umlaufen wenn der Z hler den Wert 0 erreicht Eine Ausnahme tritt auf wenn der Roboter den Kartenrand erreicht Dann n mlich wird die Richtung des Umgehens ge ndert denn sonst w rde der ges
125. paraten Dialogfeld welches aus der Men leiste heraus ge ffnet wird Das Dialogfeld ist aus einer Tabelle und zwei Buttons aufgebaut Abbildung 48 Die Tabelle enth lt zwei Spalten wobei nur die Zellen der zweiten Spalte vom Benutzer bearbeitet werden k nnen Jede Zelle der zweiten Spalte enth lt einen Spinner mit dem die Gr se eines Schatzes festgelegt wird Die erste Spalte enth lt lediglich die Koordinaten eines Schat zes der vorher in die Karte eingezeichnet wurde Mit dem Save Button werden sch tzeverwaltungs ll Abbildung 48 Grober Aufbau der Sch tzeverwaltungsG UI die Gr sen der Sch tze intern gespeichert es wird zu diesem Zeitpunkt keine xml Datei erstellt Die Sch tze sind in einer Liste gespeichert beim Speichern der nderungen wird die Liste durchgelaufen und die bisherigen Werte durch die Werte in den jeweiligen Spinnern ersetzt Mit dem Cancel Button werden die nderungen der Schatzgr gen nicht gespeichert Das Dialogfeld wird nach der Bet tigung jedes Buttons geschlossen 6 3 Roboterkonfiguration Die Roboterkonfiguration wird ebenfalls in einem separaten Dialogfeld erstellt Abbildung 49 Das Dialogfeld ist in drei Bereiche unterteilt Der obere Be 84 6 3 Roboterkonfiguration 6 EDITOR reich enthalt vier Buttons mit denen eine neue Roboterkonfiguration erstellt New Button eine bereits bestehende Roboterkonfiguration zu der in Bear beitung befindlichen Roboterkonfiguration hinzugefii
126. pitel beschreiben wir die dritte Hauptkomponente des Gesamtsys tems die Visualisierung und geben einen berblick ber ihre Bedienung sowie die Architektur und innere Abl ufe ebenso wie ber verwendete Datenstruk turen und Algorithmen Die Visualisierung besteht im Wesentlichen den vier Komponenten Men leiste Hauptansicht Minikarte und Detailansicht und ist in Abbildung 32 dargestellt Hide explored terrain round 98 41 MultiRobot 001 Position 136 40 105 99 Show static details v Show current state v Show explored a v Record visited paths Container 2 View Radius 20 00 Communication Radius 40 00 Max Speed 2 00 Strategy DividedExplorationStrategy Current Action Move 0 5 m s 289 Current Tactic HeadForCloseUnexploredRegion Load 0 Energy 99 02 Men leiste 1 Hauptansicht 2 Minikarte 3 Detailansicht 4 insgesamt explorierte Karte 5 von Roboter explorierte Karte 6 abgelaufene Wege 7 Abbildung 32 Die Visualisierung 5 1 Architektur Abbildung 33 zeigt einen berblick ber den Aufbau der Visualisierungskom ponente Die Schnittstelle zum Kernel wird durch die Klasse MainControl re pr sentiert Mit der MainControl verbunden sind a die GUI Klassen der Vi 64 5 2 Wichtige Klassen 5 VISUALISIERUNG OU ON Observer Pattern Map2D Map3D Observer MainView DetailView
127. rameUpdate Wird jeden Frame aufgerufen roundUpdate newRoundMessage Wird jede Runde aufgerufen sceneUpdate initSceneMessage Wird aufgerufen wenn eine neue Sze ne initialisiert wird terrainU pdate init TerrainMessage Wird aufgerufen wenn ein neues Ter rain initialisiert wird robotDetailU pdate robotDetailU pdateMessage Wird aufgerufen wenn ein Roboter seine Daten ndert Das umfa t ins besondere auch Positions nderungen des Roboters was diese Methode sehr wichtig macht groundObjectDetailUpdate g groundObjectDetailUpdateMessage Wird bei Anderungen von Bodenob jekten aufgerufen simulationMessage simulationPausedMessage Wird aufgerufen wenn die Simulati on pausiert wurde simulationMessage simulationResumedMessage Wird aufgerufen wenn die Simulati on fortgef hrt wurde simulationMessage simulationStoppedMessage Wird aufgerufen wenn die Simulati on gestoppt wurde simulationMessage simulationSpeedChanged Wird aufgerufen wenn kernelsei tig die Simulationsgeschwindigkeit ge ndert wurde Tabelle 4 Update Methoden f r die Ablaufsteuerung im Visualisierungsmodul 5 2 2 Datenhaltung F r die Datenhaltung im Visualisierungsmodul sind im wesentlichen die Klas sen Robots GroundObjects Selection ExplorationQuadtrees und VisitedPaths 67 5 2 Wichtige Klassen 5 VISUALISIERUNG verantwortlich dabei werden die beiden letzteren im Abschnitt 5 2 5 erl utert Die Klasse Ro
128. ray AAA as summary of robotypes total number of robots 44 Abbildung 55 Zwei Fl chendiagramm Balken und Kuchendiagramm Jede Aktion add remove auf den Datenmengen wird unmittelbar im Dia gramm angezeigt Bei l ngeren Simulationen oder kurzen update Intervallen Sch tze und Flags 7 4 Benutzereigene Messgr en 7 MESSGROSSEN werden die Werte auf der x Achse gestaut Wenn auto remove in der GUI ak tiviert wird werden Staus erkannt und jeweils das erste Element gel scht um Platz f r das ankommende Element zu schaffen 7 4 Benutzereigene Messgr en Um eigene Messgr en zu erfassen muss man erst berlegen von welchen Da tenstrukturen man sie sammeln m chte Der einfachste Weg w re es die bereits bestehende Datenstruktur vom Kernel und Roboter Modul zu benutzen und sie gegebenenfalls um eigene Parameter zu erweitern Anhand eines Beispiels m chte ich demonstrieren wie man vorgehen w rde Wir m chten anzeigen wie viel Prozent der Karte von welchen Robotertypen erforscht wurden Dazu w hlen wir das Kuchendiagramm um die Ergebnisse anzuzeigen Als erstes m ssen wir entscheiden woher wir die Daten bekommen Eine einfache M glichkeit w re es ber SceneControl auf einen Roboter zuzu greifen KernelToRobot RegionQuadTree Damit h tte man aber nur einen Roboter und nur einen Teil der erkundeten Karte Bei der Homebase werden alle erkundeten
129. s bekommt und eine Funktion die die Visualisierung ber ge nderte Objkete informiert Klasse PRNode Erzeugt die Knoten des PRQuadtrees kann daher entweder ein Wurzelknoten ein Innererknoten oder ein Blattknoten sein Verweist zu dem auf die Kindknoten NW NE SW SE falls es kein Blattknoten ist und enth lt als Blattknoten dynamische Objekte Klasse DynamicObject Erstellt ein Objekt welches im Quadtree gespei chert werden kann Jedes Objekt enth lt eine eigene ID Ein DynamicObject ist entweder ein Treasure oder ein Flag Klasse Treasure Erbt von der Klasse DynamicObject Erzeugt ein Schatz Objekt Diese enth lt zur ID noch den Typ und die Menge des Rohstoffes sowie die Menge die abgebaut wird Klasse Flag Erzeugt die Brotkr mmel 3 4 RMI Um die Daten zwischen dem Kernel und Visualisierung auszutauschen wird ein RMI Server Remote Method Invocation verwendet Der Server ist in der Klasse KernelToVisu realisiert Die wichtigsten Funktionen e deliver VisuMessage m Visualisierung holt eine Nachricht vom Ker nel e send VisuMessage m Kernel sendet eine Nachricht an Visualisierung Bei dem Start des Kernel startet der Server auf dem Standard Port Set tings java LOOKUPPORT Da man mehrere Server starten kann berpr ft der Server ob der Standard Port besetzt ist falls dass der Fall ist sucht er einen freien Port in dem er einfach n chsth heren ausprobiert Die RMI Verbindungsdaten k nnen dann in der
130. schlieslich Hindernisse leere Fl chen werden nicht explizit gespeichert Diesen RegionQuadtree aus XML Strukturen zu parsen Anforderung 2 ist keine allzu spannende Angelegenheit Der Parser geht rekursiv durch die XML Struktur hindurch und instanziiert je nach vorhandenen Hindernissen neue Knoten oder eben nicht Implementierungstechnisch gibt es an dieser Stelle ein wichtiges Detail Da die XML Struktur mittels der Open Source Software JDOM Hun geladen wird und dieser Vorgang viel Speicher ben tigt mus nach dem fertigen Instanziieren des RegionQuadtrees der Pointer auf die JDOM Klassen auf null gesetzt werden damit der Speicher durch den Garbage Collector freigegeben werden kann F r Anforderung 3 war ein schneller Algorithmus vonn ten der Bereichsan fragen f r Rechtecke schnell beantworten konnte Wir entwickelten dazu den folgenden Algorithmus 1 Aus den bergebenen Anfragekoordinaten ein Anfragerechteck konstruie ren 2 F r alle zu berpr fenden Knoten aus dem RegionQuadtree eigenes Recht 17 3 3 Datenstrukturen 3 SIMULATIONSKERNEL eck konstruieren 3 Anfragerechteck und Knotenrechteck vergleichen berschneiden sie sich gt Kandidat f r Hindernis im Anfragerechteck 4 Alle Kandidaten berpr fen ob sie bereits vollst ndige Hindernisse sind 5 Wenn ja Hindernisse direkt in Ergebnismenge speichern 6 Wenn nein Die Kinderknoten von Nicht Hindernissen rekursiv berpr fen 7 Nach der Rekursion
131. se Diese Taktik dient zum Hinbewegen zur HomeBase Die korrekte Benutzung der Taktik gew hrleistet dass die HomeBase erreicht wird Aktuell wird dazu folgende Methode verwendet Wenn der Roboter sich nicht an der HomeBase befindet wird eine Bewegung mit maximaler Geschwindig keit in Richtung der HomeBase angeboten sofern diese nicht auf ein Hindernis treffen wide In diesem Fall wird die Taktik WalkAlongBoundaries verwendet um das Hindernis zu umgehen Eigentlich sollte die Wegberechnung eingebaut werden Da sie bei Ende der Implementierungsarbeiten jedoch noch nicht stabil genug fertiggestellt war wurde auf die Aktivierung verzeichtet Die Vorberei tungen daf r sind im Code jedoch auskommentiert getroffen Bei Einbau w rde mittels dieser ein Weg zur HomeBase berechnet werden wenn die Methode hasAction das erste Mal aufgerufen wird Solange dieser Weg verfolgt wird finden keine relevanten neuen Berechnungen statt Erst wenn von diesem abge wichen wird muss beim n chsten Mal sinnvollerweise der Weg neu berechnet werden Das Vermeiden von Kollisionen mit Hindernissen hat lineare Laufzeit abh ngig zur Anzahl der Hindernisse im Sichtradius Alle anderen Berechnungen haben nur konstante zu vernachlssigende Laufzeit S mtliche relevanten Berechnungen finden in hasAction statt Alle Speicherungen ben tigen nur konstanten zu vernachl ssigenden Platz HeadForRelay Diese Taktik dient dem Hinbewegen zu einem Relais Die Benutzung der Tak
132. sgangspunkt B zur ck Durch die zwei BorderCheckpoints ist nur klar dass das Hinder nis die Subarea teilt Die Strategie w rde nun zum Punkt E gehen MoveTo NextObstaclePointState Abb 24 den dortigen Stripe nach oben entlanggehen 55 4 4 Strategien 4 ROBOTER MODUL OutOfAreaState MoveToStartStripeState MoveToNextStripeStartState MoveToNextBorderCheckpointState CirculateObstacleOutsideAreaState CirculateObstacleState T ExploreStripeState MoveForwardAlongObstacleState SubAreaExploredState MoveBackwardAlongObstacleState oo Abbildung 24 Zustandsautomat der Strategie SubAreaStrategy 56 4 4 Strategien 4 ROBOTER MODUL Abbildung 26 Beispiel zum Ablaufen eines Hindernisses bis zum Rand der SubArea ExploreStripeState Abb 24 und mit dem allgemeinen explorieren fortfah ren Wenn die Strategie am Ende des Stripes angelangt ist geht sie einfach zu n chsten ber MoveToNextStripeStartState Abb 24 Nun kann auch der Fall auftreten dass beim Entlanglaufen an einem Hinder nis kein Rand der SubArea getroffen wird Dieser Fall ist in Abbildung 27 dargestellt Der Roboter l uft von oben auf das Hindernis zu und setzt einen ObstacleCheckpoint an Punkt A Wie zuvor l uft die Strategie das Hindernis in einer festgelegten Richtung ab und setzt ObstacleCheckpoints wann immer sie einen Stripe kreuzt Bevor sie allerdings wie zuvor auf einen Rand
133. szuw hlen kann man jedem Dreieck ein Intervall zwischen 0 und dem Gesamtfl cheninhalt zuweisen welches seiner Gr e entspricht und sich mit keinem anderen Intervall berschneidet Nun w hlt man einen zuf lligen 77 5 3 Preprocessing 5 VISUALISIERUNG Wert zwischen 0 und dem Gesamtfl cheninhalt Das Dreieck in dessem Intervall dieser Wert liegt ist damit ausgew hlt Eine Einteilung in solche Intervalle kann man z B vornehmen indem man die Dreiecke so sortiert wie sie bei einem Baumdurchlauf post order auftreten w rden Dann ist a b das Intervall des i ten Dreiecks mit Fl cheninhalt area wobei a b _ und b a areas Nat rlich ist es unpraktikabel f r jede Dreiecksauswahl einen solchen Baumdurchlauf zu machen es geht aber auch viel einfacher Dazu muss in jedem Knoten gespeichert werden wie gro der Gesamtfl cheninhalt aller Dreiecke ist triangleArea die in ihm oder seinen Nachkommen ge speichert sind Dann kann man das gesuchte Dreieck in O log d k finden bei Baumtiefe d und k Dreiecken im Knoten der das gesuchte Dreieck enth lt Wie das funktioniert illustriert Abbildung 45 a Li b c 1 tA b tA c tA e 3 tA f oa D N ct Q 4 I Gegeben ist ein Baum der 5 Dreiecke mit den Fl cheninhalten 1 bzw 2 enth lt Der Gesamtfl
134. t werden diese in der XML Datei TacticLookupTa ble cml eingetragen 4 2 3 Schnittstellen f r die Strategieentwicklung In diesem Kapitel werden die Schnittstellen die f r den Entwurf einer Strategie relevant sind aufgelistet und kurz erl utert welchem Zweck sie dienen IStaticMapData Diese Schnittstelle erm glicht es der Strategie auf statische Kartendaten zuzugreifen Folgende Methoden werden bereitgestellt e Position getCurrentPosition Ermittelt die aktuelle Position des Robo ters und liefert einen R ckgabewert Position in x und y Koordinaten e List lt StaticObject gt getKnownObstacles Position upperLeft Position lo werRight Ermittelt die Hindernisse in einem Bereich der durch eine obe re Linke Position upperLeft und untere rechte Position lowerRight fest gelegt wird Sollte der Roboter den angefragten Bereich nicht vollst ndig 33 4 2 Strategie und Taktikkonzept 4 ROBOTER MODUL erkundet haben so bekommt er die Hindernisse aus dem angefragten Be reich die er tats chlich schon mal gesichtet hat lt StaticObject gt getObstaclesInViewRadius Ermittelt die aktuellen Hin dernisse im Sichtradius boolean isExplored Position position berpr ft ob die bergebene Po sition bereits erkundet wurde boolean isExplorationComplete berpr ft ob die komplette Karte er kundet wurde RegionQuadTreeNode getQuadTreeNode Position position Gibt den Quad Tree Knoten zur ck in dem die b
135. t auch zus tzlich das komplette Team w hrend die anderen Roboter lediglich sich selbst und den Anf hrer ken nen Eine Erweiterung war bislang nicht n tig k nnte jedoch verh ltnism ig einfach implementiert werden Alle Nachrichten des TeamManagements haben einen Pr fix TM In der Reihenfolge 1 processQueries 2 sendQueries 46 4 3 Taktiken 4 ROBOTER MODUL TeamBuildTactic Mit Hilfe dieser Taktik hat der Roboter die M glichkeit ein eigenes Team auf zubauen oder einem anderen Team beizutreten Der Ablauf basiert auf einem Protokoll mit einem 2 fachen Handshake Daf r sind 5 Nachrichtentypen defi niert worden e TM_INVITE e TM ACK1 INVITE e TM NACK1 INVITE e TM ACK2 INVITE e TM_NACK2 INVITE Das Protokoll funktioniert folgerndermafen Im ersten Schritt verschicken die Roboter Nachrichten vom Typ TM INVITE Zus tzlich wird an die Nachricht ein Gebot gekoppelt das modellieren soll wie wichtig diese Einladung fiir den jeweiligen Roboter sein soll Diese Zahl ist im Moment eine Zufallszahl zwischen 0 und 1000 Kriegt ein Roboter eine Ein ladung kann er darauf entweder mit der Nachricht TM_ACK1_INVITE oder TM_NACK1_INVITE reagieren ACK1 hei t in diesem Fall das der Roboter die Einladung annnimmt NACK1 ist entsprechend eine Ablehnung Kommt also ein NACK1 als Antwort geht der Roboter nicht weiter auf diesen Fall ein Kommt hingegen ein ACK1 gibt es wieder 2 M glichkeiten TM_ACK2_ INVITE oder TM
136. t auf G ltigkeit berpr ft Wenn der abzufragende Bereich da bei in noch nicht erkundetes Gebiet hineinragt wird keine Information ber die Hindernisse in diesem Bereich zur ckgegeben zum Beispiel das Hindernis in der Mitte auf Abbildung 15 Die Knoten des Quadtrees haben eine feste gt Abbildung 15 Funktionsweise der StaticMap Mindestgr fe Dadurch kommt eine gewisse Diskretisierung der Karte zustan de und kleine Ungenauigkeiten k nnen auftreten Dieses ist jedoch unerlaflich um die Funktionsweise des Quadtrees gew hrleisten zu k nnen Die DynamicMap So wie in der StaticMap statische Objekte Hindernisse gespeichert werden werden auch dynamische Objekte in einer eigenen Datenstruktur verwaltet Dabei handelt es sich um die Klasse DynamicDataList Die DynamicDataList ist eine Liste in der Daten z B die Roboter im Sichtbereich gespeichert wer den k nnen und zwar eine bestimmte Anzahl von Runden lang Die Anzahl 26 4 1 Architektur 4 ROBOTER MODUL der Runden die die Daten erhalten werden sollen ist dabei parametrisierbar In Abbildung 16 ist ein Beispiel fiir eine DynamicDataList in der Informatio nen 2 Runden lang erhalten sind In der DynamicMap werden nun 3 solcher Listen gehalten eine fiir die Ro boter im Kommunikationsradius robotsInCommRadius eine fiir die Robo ter im Sichtradius robotsInViewRadius und eine fiir die dynamischen Ob jekte in diesem Fall Flags im Sichtradius dynamicOb
137. ter Umst nden sehr gro e Komplexit t ei ner Taktik f r den Entwickler lediglich auf den Aufruf zweier Methoden XMLFile RobotData TacticLookupTable ata A data uges i Subject lt host OT TacticManager ITacticHost registerTactic tactic ITactic factory host IServiceHost data IRobotData ServiceManager deregisterTactic tactic Tactic TacticManager host IServiceHost data IRobotData notifyTactics getActionList host useMovementTactic name String IMovementTactic A useTargetMovementTactic name String ITargetMovementTactic useDecisionTactic name String IDecisionTactic en ed TacticManager gt reset implements l tacticProvider hy Strategy Observer TacticProvider abstract o tactics ITactic abstract update NY 5 hasAction boolean getTactics String Sa performAction hasTactic name String boolean gt getName String useTactic name String ITactic I i i implements i 1 I ConcreteStrategy IMovementTactic IDecisionTactic i I getNrMovements int I 1 getTargetPosition Position implements 1 I f p w i 1 _ lt implements _ _ 1 I l 1 I l I 1 I l I 1 I I 1 l I 1 1 ITargetMovementTact
138. timmt nur sein Mittelpunkte x Abbildung 43 Einf gen eines kleines Dreiecks in einen Loose Octree dem der Mittelpunkt des Steins liegt Grund f r die Tiefe in einem nor malen nicht loose Octree w rde dann der Stein mit Gr e 1 x 1 x 1 Meter exakt in die Boundingbox dieses Octreeknotens passen Der Mittelpunkt dieses Octreeknotens entspricht dann genau der Positi on des Steins Dies ist wichtig da im TerrainOctree um Platz zu sparen nur noch die Information gespeichert wird ob ein Stein in einem Knoten vorhanden ist nicht aber seine Position Diese ist nur noch implizit durch den Mittelpunkt des Octreeknotens gegeben 3 Ziehe zuf llig ausgew hlte Dreiecke im Octree nach oben Dies folgt dem Konzept des Randomized Sample Trees KKF 04 Die Implementie rung der Methode pullUpSamples ist eine direkte Umsetzung des Algo rithmus aus dem Paper Dort gibt es auch sch ne Illustrationen weswegen hier darauf verzichtet wird Es gibt zwischen Implementierung und Paper folgende Entsprechungen Implementierung Paper pullUpSamples createSample sample TreeQuality c area Quotient du numSamples Mu samples M trianglesArea A P u pullUpSample choose polygon with probability Tabelle 5 Namensunterschiede von Methoden zwischen Implementierung und Paper Dabei bedarf die Methode pullUpSample noch einiger Erl uterungen Um aus einer Menge von Dreiecken zuf llig eines gewichtet nach Fl cheninhalt au
139. tionen welche auserhalb der Zellenaufteilung liegen Bei einer Zellenbreite von 16 w re eine illegale Position in Abbildung 6 z B 70 10 16 3 3 Datenstrukturen 3 SIMULATIONSKERNEL Als L sung f r das Speicherproblem w hlten wir die Datenstruktur Region Quadtree Diese Baumstruktur zeichnet sich dadurch aus das jeder Knoten genau dann vier Kindsknoten erh lt wenn sich in einem von ihnen etwas befin det ansonsten besitzt ein Knoten keinerlei Kinder Ein einfaches Beispiel findet sich in Abbildung 7 gt AA amp 00 N iby Abbildung 7 Beispiel fiir einen RegionQuadtree Hier wird ersichtlich wie eine Karte die im konkreten Anwendungsfall natiirlich um ein vielfaches komplexer aussieht mittels Unterteilung in Viererboxen in der Datenstruktur gespeichert wird Auf der linken Seite der Abbildung findet sich ein Kartenausschnitt dieser wird so lange unterteilt bis s mtliche Hinder nisse schwarz dargestellt vollst ndig durch Rechtecke eingeschlossen sind Auf der rechten Seite der Abbildung ist die Repr sentation dieser Rechtecke durch Knoten in der Datenstruktur zu sehen Mittels dieser Art der Speicherung wird viel Speicherplatz gespart im Gegen satz zu einer naiven Speicherung in der beispielsweise s mtliche Hindernisse durch zwei Koordinaten in einer Liste oder i shnlichem gespeichert w rden Der Grund Der RegionQuadtree b ndelt die Hindernisse und speichert sie nicht punktweise Und er speichert aus
140. und Hindernisse ebenfalls nach einem vordefinierten Schema exploriert Sie arbeitet dabei v llig unabh ngig von anderen Robotern und speichert sich das bislang explorierte Gebiet in einer eigenen Datenstruktur Nachfolgend wird die Strategie anhand von Bildern beschrieben und parallel dazu der korrespondierende Zustandsau tomat in Abbildung 24 erkl rt Aus Gr nden des Umfangs kann nicht auf die Bedeutung aller Transitionen eingegangen werden Die Implementierung der Strategie wurde in Form eines State Patterns GHJV95 vorgenommen Nehmen wir einen rechteckigen Ausschnitt einer Karte wie in Abbildung 25 Die Begrenzung der SubArea ist durch die gestrichelte Linie dargestellt Hin dernisse sind grau hinterlegt Die blauen Streifen Stripes repr sentieren eine horizontale Unterteilung der SubArea in Abschnitte Die Stripes sind genau im doppelten Sichtradius des Roboters entfernt Das bedeutet wenn der Roboter jeden Streifen abgelaufen h tte dann w rde er die SubArea vollst ndig explo riert haben Die Punkte an den Enden der Streifen sind StripeEndCheckpoints welche dem Roboter indizieren dass er am Anfang bzw Ende eines Stripes ist Das Problem an dieser SubArea sind offenbar die Hindernisse Es muss nicht nur das obere Hindernis irgendwie umrundet werden sondern auch die begeh baren Bereiche unter dem unteren Hindernis exploriert werden Dazu muss die SubArea in einer sinnvollen Weise verlassen uns wiederbegangen werden Angenommen der R
141. ung der Taktiken gew hrleistet dass keine Kollision mit Hindernissen und oder anderen Robotern stattfindet Genaueres ist den enthaltenen Taktiken zu entnehmen Alle Taktiken gehen davon aus dass der Roboter seine als n chstes gew nschte Bewegung bereits berechnet hat und diese vorne in der ActionList liegt Nur dann kann sinnvollerweise getestet werden ob eine Kollision auftreten k nnte Dann also sollten etwaige Ausweichbewegungen berechnet werden Das Erkennen von Kollisionen mit Hindernissen ben tigt lineare Laufzeit in Abh ngigkeit zur Anzahl der Hindernisse im Sichtradius das Erkennen von Kollisionen mit Robotern ist linear abh ngig von der Anzahl der Roboter im Sichtradius Teilweise rufen die Taktiken diese Methoden mehrfach auf SidestepRobotEvasion SidestepRobotEvasion ist eine Taktik zum seitlichen Ausweichen anderer Ro boter Sie kann nur funktionieren wenn alle Roboter sie verwenden Dazu wird folgendes Verfahren bei jeder Bewegung des Roboters verfolgt e Pr fe ob die gew nschte Bewegung die Mittelsenkrechte zu anderen Ro botern kreuzt und finde ggf die naheste solche Mittelsenkrechte e W hle je nach Wert des Parameters SidestepTechnique siehe unten eine bestimmte Ausweichbewegung e Pr fe ob die Ausweichbewegung die Mittelsenkrechte zu anderen Robo tern kreuzt und f hre die Bewegung nur bis zur nahesten aus e Es ist der ausf hrenden Strategie selbst berlassen das eigentliche Ziel anzustreben
142. unt TreasurelD treasure Ermittelt den Anteil des spezifizierten Schatzes der schon abgebaut ist und von einem Roboter vom Typ Transportet abtransportiert werden kann int get TreasureUnworkedA mount TreasurelD treasure Ermittelt den An teil des spezifizierten Schatzes der noch nicht abgebaut ist 34 4 2 Strategie und Taktikkonzept 4 ROBOTER MODUL e int getTreasureAmount TreasurelD treasure Ermittelt die Gesamtkapa zit t des spezifizierten Schatzes Dies beinhaltet sowohl die schon abge bauten als auch die noch unbearbeiteten Anteile des Schatzes e Set lt RobotID gt getRobotsInCommRadius Ermittelt die Roboter im ak tuellen Kommunikationsradius e Map lt RobotID Position gt getRobotsInViewRadius Ermittelt die Ro boter im aktuellen Sichtradius Es existieren weitere Methoden in diesem Interface die man in der Java Doku mentation nachschlagen kann IMessageData Diese Schnittstelle erm glicht es der Strategie das Senden und Empfangen von Nachrichten F r ein paar spezielle Nachrichten wie das Sen den der eigenen Karte oder die Anfrage nach der Karte eines anderen Roboters stehen vordefinierte Methoden zur Verf gung Folgende Methoden werden be reitgestellt e List lt MessageInformation gt getReceivedMessages Ermittelt die zuletzt empfangenen Nachrichten e int getNumberOfMapRegions Ermittelt die Anzahl an vom Entwickler definierten Regionen der Karte Diese k nnen ber das Interface IDataPa
143. werden k nnen Diese beiden Werte k nnen in der Roboterkon figurationsdatei festgelegt werden 27 4 1 Architektur 4 ROBOTER MODUL Die MessageMemory Da die Roboter untereinander kommunizieren sollen ist es notwendig einen Speicher f r ausgehende und auch eintreffende Nachrichten zu schaffen so da sie im sp teren Verlauf von der Strategie analysiert werden k nnen Diese Auf gabe bernimmt die MessageMemory Es gibt eine Liste in der empfangene Nachrichten gespeichert werden myReceivedMessages eine in der bereits ge sendete Nachrichten gespeichert werden mySentMessages und eine in der noch zu sendende Nachrichten gespeichert werden myMessagesToSend Diese funktioniert wie ein Puffer es werden im Laufe der Aktionsphase Nachrichten hinzugef gt die dann mit Ablauf der Runde alle gesendet werden Wegberechnung Um die Wegberechnungen f r alle Roboter effizient durchf hrbar zu machen wird diese nicht auf der Originalkarte durchgef hrt sondern auf Regionen die miteinander verbunden sind Der Einfachheit halber wird der schon im Kernel vorhandene Quadtree genutzt und die durch den Quadtree definierten Zellen als Regionen genutzt F r diese Zwecke werden Kernelseitig f r jede Quadtree Zelle Informationen ber deren Nachbarn berechnet siehe Kapitel 3 3 Dies hat den Vorteil das diese Aufteilung nur ein einziges mal generiert werden muss und auch nur einmal im Speicher gehalten werden muss anstatt lokal bei jedem

Entwicklerhandbuch - Heinz Nixdorf Institut

Contents

Download Pdf Manuals

Related Search

Related Contents