Mindestanforderungen
Ein Roboter wird in einen quadratischen Kasten von in vernünftigen Zeiträumen abfahrbarer Kantenlänge gesetzt. Der Roboter hat als vordere “Stoßstange” einen Drucksensor, der beim Aufprall den Rückwärtsgang aktiviert. Ziel ist es, durch das protokollierte Abfahren eine Karte der möglichen Pfade innerhalb des Kastens anzulegen, und daraus dann auf die Form des Kastens zu schließen. Wie groß ist der kleinstmögliche Satz von Regeln, um diese Aufgabe zu bewältigen?
Meinem Asuro habe ich zur Erledigung einer ähnlichen Aufgabe in meinem Büro folgende Regeln in den Atmel geschaufelt:
- Fahre solange geradeaus, wie du auf keinerlei Hindernisse stößt.
- Wenn du auf ein Hindernis stößt, setze kurz zurück, mache eine 90 Grad Drehung nach rechts, und folge dann wieder Regel 1.
Die möglichen Bahnen dieses Manövers sehen von oben so ähnlich aus wie die kleinen Windräder, die man als Kind auf dem Rummelplatz zum Lebkuchenherz bekam: ein Viereck mit jeweils verlängerter Kante an jeder Ecke, die vom Zurücksetzen des Roboters herrührt. Das zentrale Problem ist nun, zu verhindern, dass der Roboter zu schnell wieder in die selbe Bahn einschwenkt und damit in eine ständig sich wiederholende Schleife gerät, solange die Batterien halten. Aber wie kann ich jetzt daraus auf die Form des umgebenden Kastens schließen?
Aber dann ist mir ein anderer Gedanke gekommen.
Kehren wir zur ursprünglichen Fragestellung zurück: Ein Roboter fährt eine Bahn ab und protokolliert sie. Wie wahrscheinlich ist es, dass er selbst bei penibelster Programmierung (was das kleinere Problem wäre) und optimaler technischer Präparierung (schon wesentlich schwieriger) jemals wieder auf die selbe Spur gerät? Null. Oder etwas das nur unwesentlich von Null verschieden ist. Und dieses etwas sinkt mit jeder angenommenen Umrundung, d.h. selbst wenn der Roboter später noch mal in die selbe Spur geraten sollte, was wie gesagt entsetzlich unwahrscheinlich ist, würde er es noch entsetzlich unwahrscheinlicher ein weiteres mal tun. Ganz zu Schweigen von den Wahrscheinlichkeiten für eine absolute Bahnstabilität, und je länger man darüber nachdenkt, umso mehr Unwahrscheinlichkeiten fallen einem ein.
Kurzum, diese vollkommene Bahnstabilität tritt in der Realität nicht ein. Die wird eher so aussehen, dass der Roboter mit jedem Einschwenken in eine bereits abgefahrene Bahn um einen bestimmten Betrag von dieser abweicht. Viel wahrscheinlicher ist also eine Bahn, die so aussieht wie eine etwas kantig geratene Rosette, Lissajouschen Figuren nicht unähnlich. Das geht dann so lange, bis der Roboter bei seiner Drift fast parallel und sehr nahe an eine Kante gerät. Dann kommt ein chaotisches Element hinzu, weil man jetzt nicht mehr voraussagen kann, wann die Drucksensoren reagieren, und dieser “Streifschuss” in eine neue Bahn mündet. Erst wenn der Roboter wieder den Rückwärtsgang einlegt stellt sich wieder das Bild mit den einbeschriebenen Quadraten ein.
Wie muss ich also, bei einem derartig zu erwartenden Protokollverlauf, die Software programmieren, um auf das Quadrat schließen zu können?
Der primitivste Weg ist eigentlich, nach ausreichend langer Fahrzeit immer jeweils die Umkehrpunkte des Roboters mit ihren nächsten Nachbarn zu verbinden. Dann müsste schon von alleine ein Quadrat zum Vorschein kommen.
Nachtrag: Bahnverhalten noch mal überdenken! Simulation programmieren mit “eingebauter” Drift.
Nachtrag: Das Problem muss von der anderen Seite angegangen werden! Der Rekonstruktionsalgorithmus liefert letztendlich die Form des Kastens! Je mehr möglichst dicht beieinanderliegende Umkehrpunkte existieren, umso besser wird die Form wiedergegeben. Wie sieht also der Satz von Regeln aus, der diese Umkehrpunkte am besten liefert?
- Fahre solange geradeaus, wie du auf kein Hindernis stößt.
- Wenn du auf ein Hindernis stößt, setze kurz zurück, drehe dich um 90 Grad, fahr kurz geradeaus, stoppe, drehe dich um 90 Grad zurück und befolge wieder Regel 1.
Die langwierigen Erörterungen über die möglichen Bahnen erübrigen sich dann (hoffentlich). Wieviele Regeln sind das jetzt eigentlich? Ist das optimal (glaube ich nicht)? Beweis!
Nachtrag: Hat sich jetzt erledigt… (siehe Eintrag M II)
