2006
fand der erste Robotwettbewerb mit dem c't eigenen Modell statt. In einem
simulierten, symmetrischen Labyrinth treten zwei c’t bots gegeneinander an. Der
Bot, der am schnellsten den Ausgang gefunden hatte oder dem Ausgang am nächsten
war bei Ende des Rennens, kam eine Runde weiter. Für jeden ist der Weg gleich
lang, aber das Gelände ist unbekannt und mit Fallen gespickt (>>
zur Wettbewerbsseite).
Natürlich
wollten wir (Jochen und ich) da mitmachen. Für Lernen oder Evolution war leider
nicht genug Zeit, also wählten wir einen klassischen Ansatz, den wir innerhalb
von etwa einer Woche zusammen-“hackten“. Im Wettbewerb selbst erlitt der Code
leider einen bis heute nicht nachvollziehbaren Absturz (wohl aufgrund der
anderen Laufzeitumgebung und eines anderen C-Compilers). Da unser Code in den
Tests jedoch besonders gute Ergebnisse lieferte, möchte ich hier schnell seine
Grundzüge vorstellen.
Die
lokale Karte - Das Herzstück unserer Planung:
Aus
jedem Scan wird ein lokaler Plan erstellt wie folgt (Zunächst wollten wir die
Scandaten über Histogramme analysieren, doch in einem Labyrinth geht es so
schneller):
Starte mit einem
quadratischen Messplan voll unbekannten Felder (Wert = 1). Die Anzahl der
Felder pro Seite ist 7*240/RES, wobei 240 [mm] dem Durchmesser des Bot und RES
(hier: =40) der Auflösung entsprechen. Den Bot denken wir uns in der Mitte.
Während der Bot sich um
gewünschten Scanwinkel dreht, tue alle DIFFWINKEL°:
·
Vergleiche
den gemessenen Lichtwert mit dem Letzten und merke dir den Wert und den Winkel
des hellsten gemessenen Punktes d.h. des niedersten gemessenen Wertes.
·
Miss
den Entfernungswert des rechten und linken Entfernungssensors. Ordne der
gemessenen Entfernung und Winkel das entsprechende Feld zu auf dem dieser Punkt
liegt. Belege dieses Feld mit einem Mauerstück (Wert = 2) und alle Felder
entlang des Vektors (Bot – Messpunkt) mit Freiraum (Wert = 0).
·
Warte
bis nächster Messpunkt erreicht. (hier: DIFFWINKEL= 5°)
Zwecks
bessere Toleranz von Messfehlern und erleichterter Planung komprimieren wir
diesen 42 x 42 Messplan nun zu einem 7 x 7 Aktionsplan, indem wir die Werte von
je 36 Messfeldern (6x6) zu einem Aktionsfeld summieren. So erhalten wir einen
einfachen und ‚sichereren’ Plan bei dem jedes Feld so breit ist wie der Bot und
in dem sich der Bot stets in der Mitte (x = y = 3) befindet.
Den
Code für die Planerstellung gibt es hier
Um den so gewonnenen Aktionsplan zu analysieren, bewegen wir uns zunächst nur entlang den Hauptachsen (x =3 bzw y = 3) bis wir auf ein Hindernis treffen. Von da aus suchen wir orthogonal weiter. Dabei gilt: Ist der Wert eines Feldes größer oder gleich als 36, sehen wir das Feld als Mauer, d.h. es ist nicht befahrbar.
Achtung: Wir scannen während einer
Punktdrehung und drehen danach nicht wieder auf den Anfangswinkel zurück, d.h.
die Blickrichtung des Plan entspricht der Anfangsposition und NICHT der aktuellen
Position des Bots.
Aktionsplanung:
·
Initialisierung:
Stelle deine Startposition (links oder rechts) fest, indem du die Bodenfarbe des Startfeldes überprüfst.
Stelle fest, in welche
Richtung das Ziel liegt. Mache dazu einen Rundumscan und suche nach direkt an
das Startfeld angrenzenden Wänden.
o Keine Wand => Ungültig.
Bot startet immer an der Rückwand!!
o Nur eine Wand => Ziel
liegt gegenüber dieser Wand
o Zwei parallele Wände =>
ungültig, da Hindernisse immer Mindestabstand von zwei Felder haben
o Zwei Wände im rechten
Winkel, d.h. Ecke
§
Ecklampe
in Sicht und ganz hell => Bot ist in der Aussenecke und das Ziel ist
gegenüber des Lichts d.h. gegenüber der Wand links / rechts neben dem Bot bei
Startposition rechts / links, ansonsten gegenüber der anderen Wand.
§
Nicht
Aussenecke, aber Bot sieht irgendwo noch Licht
1.
Licht
ist links vom Bot => Ziel ist geradeaus / hinter dem Bot bei Startposition
links / rechts
2.
Licht
ist hinter dem Bot => Ziel ist links / rechts vom Bot bei Startposition
links / rechts
3.
Licht
ist rechts vom Bot => Ziel ist hinter dem Bot / geradeaus bei Startposition
links / rechts
4.
Licht
ist vor dem Bot => Ziel ist rechts / links vom Bot bei Startposition links /
rechts
§
Eine
Wand ist kürzer (d.h. diese Wand ist nur ein Hindernis) => Ziel liegt
gegenüber der durchgehenden Wand
o Drei Wände => Ungültig.
Hindernisse haben immer einen Mindestabstand von zwei Felder.
o Vier Wände => Kein
Labyrinth
·
Im
Freiraum:
Richte dich zum Ziel hin
aus und fahre geradeaus bis
o der Bodensensor die
Zielmarkierung erkennt => Mit Vollgas rein, um keine Zeit zu verlieren.
Ende.
o der Bodensensor ein Loch
erkennt => Stop. Setze zurück. Scanne und plane neu und trage in dem Feld
vor dir das Loch in die Karte ein.
o der Entfernungssensor eine
Wand in Fahrtrichtung erkennt => Stop. Scanne und plane neu.
Dieses Verhalten gewährleistet, dass der Bot nicht unnötig Zeit verschenkt, indem er bei freier Fahrt anhält und scannt, neu plant etc.
·
Planen
am Ende eines Freiraums d.h. Bot steht vor Wand oder Loch:
Scanne zuerst 90° zur
Mitte hin (a). Findet der Bot in diesem Bereich eine Durchfahrt am Hindernis
vorbei, fahre am Hindernis vorbei.
Sonst scanne 180° in
entgegengesetzte Richtung (b). Findet der Bot auf dieser Seite eine Durchfahrt,
fahre am Hindernis vorbei.
Sonst steht der Bot vor
einer langen Wand und muss nach aussen hin daran entlang fahren.
a: Wir scannen von der
aktuellen Position nach innen, damit wir nach dem Scan einen meist kürzeren
Winkel zur neuen Fahrtrichtung haben. Da das Ziel in der Mitte der Aussenwand
liegt, bevorzugen wir nämlich Wege, die uns zur Mitte hin und nicht nach aussen
weg führen.
b: Neu zur Mitte
ausrichten, um nur die restlichen 90° zu scannen, würde mehr Zeit beanspruchen
·
Einer
Wand folgen / Sackgassen umfahren:
Fahre parallel zur Wand
o bis zum letzten Feld des
lokalen Plans => Scanne 90° in Zielrichtung. Findet der Bot in diesem
Bereich eine Durchfahrt am Hindernis vorbei, fahre am Hindernis vorbei in
Freiraum.
Sonst folge der Wand
weiter.
o Falls auf dem Weg dahin der
Bot auf eine weitere Wand trifft => Scanne 90° in Zielrichtung. Findet der
Bot in diesem Bereich eine Passage zwischen den Wänden (d.h. Weg knickt ab in
Richtung Ziel), fahre hindurch in Freiraum.
Sonst scanne 180° in entgegengesetzte Richtung. Findet der Bot auf dieser Seite eine Durchfahrt in der eben entdeckten Wand, fahre hindurch in Freiraum.
Sonst
o Folge wenn möglich der
eben entdeckten (zweiten) Wand bis eine Umfahrung möglich (d.h.
Weg knickt ab
entgegen dem Ziel).
o Wenn
nicht (d.h. echt Sackgasse) scanne weitere 90°.
§
Findet der Bot eine Durchfahrt, umfahre diese
dritte Wand.
§
Sonst folge dieser Wand weiter bis eine Umfahrung
möglich ist.
o Folge
der dritten auf der anderen Seite weiter als wäre es die erste (sonst würde der
Bot im Kreis fahren).
Um zu gewährleisten, dass
der Bot bei der Sache bleibt und nicht plötzlich in Richtung Ziel abdreht und
so in einen Kreislauf gerät (er würde wieder in genau die selbe Sackgasse
geraten), muss das Ziel zwischenzeitlich in Richtung der zu umfahrenden Wand
‚verschoben’ werden. Im letzten Fall, wo der Bot der dritten Wand folgen
muss, muss man während dieser
Phase zusätzlich die Startposition vertauschen. Aber Achtung: Nach einer
Durchfahrt daran denken alles wieder auf die echten Werte zurücksetzen !!