Wie einem Labyrinth Roboter einen Funken Intelligenz verschaffen?

[robo_tom_24]

Hallo miteinander,
Es ist spät in der Nacht, und da kommen mir meist die besten Ideen für meine Projekte. So auch jetzt:
Mein Labyrinth-Roboter findet schon ganz brav und ohne externe Hilfe von außen durch ein Labyrinth. Das Ganze geschieht mit der "Rechten-Hand-Methode". Nun, ich hab verschiedene Labyrinthe versucht, aber im Wurst-Käse Szenario fährt der fast ewig durchs Labyrinth.
Wie kann ich nun am besten verschiedene Methoden miteinander verknüpfen um effektiv und möglichst schnell (relativ schnell - also das RP6 Chassis und Geschwindigkeit sind nicht unbedingt Freunde) durch ein Labyinth zu kommen?

Zum Robo:
Abstandssensoren links-vorne-rechts (jeweils ein Messbereich von 3-20cm)
Radencoder auf der nicht angetriebenen Kettenwelle (somit Schlupfresistent)
*Foto folgt noch*

Zur Hardware:
Arduino MEGA2560 mit eigens kreiertem "Labyrinth-Robo-Shield" (Doppel-H-Brücke als Motortreiber, ADC Eingänge für die Sensoren, Eingänge für die Encoder, I²C Port, Navigationstasten, "LCD-Port" für 4x20 LCD, U-Teiler zur U-Messung des Akkus und (ich weiß nicht wieso :rolleyes:) einen PC-Piepser) - für nähere Infos fragen ;)
24130
Programmiert in C (wirklichem C, nicht "Arduino-Sketch-C", aber auch das wäre möglich wenn mich die Faulheit überkommt ;) )

Ideen und Hirngespinste:
Ich zähl das Abbiegen mit und optimiere Sackgassen beim nächsten Durchlauf heraus: Abbiegen und Strecke messen bis zum nächsten Abbiegen, wenn dieses Abbiegen dann das Umkehren ist und die Hin- und Retourstrecke gleich ist ist es eine Sackgasse und es wird beim nächsten Durchlauf bei der Kreuzung xy nicht abgebogen

Ich bau noch einen Kompass dran, bzw. geh vom Ausgangszustand aus, und bekomm so meine aktuelle bzw. absolute "Himmelsrichtung", ich mess jede Strecke mit und versuche zu erkennen ob ich aufgrund der "Rechten-Hand-Methode" extrem weit abdrifte (Ich starte in der Mitte und fahr außen umher), wenn dies so ist werde ich versuchen eine Art "Linke-Hand-Methode" anzuwenden, somit "per Zufall" links abbiegen und probieren, je nachdem was kürzer ist, das wird das nächste mal genommen usw....

Eine Implementierung des Algorithmus von Gaston Tarr, wäre auch interessant mit dem Markieren von Gängen. Da muss man halt auch irgenwie erkennen, ob man in dem Gang schon war und ob dieser markiert ist, nur das wird mit Zählen und Messen denk ich nicht funktionieren. Doch wie kann man das anstellen? kleine Sticker mit einem Servo austeilen und per Farbsensor lesen? Oder vielleicht was mit einer Kamera?

Was habt ihr noch für Ideen? Wie kann man so etwas mathematisch angehen? Kann man so etwas irgendwie simulieren?

-Anm.: Einen Code zu kreieren ist nicht meine Absicht, maximal Ansätze dazu. Mathematische und logische Ansätze sind denk ich eher angebracht ;)

grüße

[Manf]

Bei einer generellen Lösung geht es darum, das Gelände zu erkunden und die Algorithmen auf eine Karte anzuwenden. Die Karte ist, wie es heißt, das Modell der Umgebung mit dem man effizient operieren kann.
Es kommt darauf an, ob Du soweit gehen willst.

http://www.google.de/imgres?um=1&hl=de&sa=N&tbo=d&biw=1135&bih=942&tbm=isch&tbnid=AwX_ajCUwlIPqM:&imgrefurl=http://realtimecollisiondetection.net/blog/%3Fp%3D83&docid=J6Tqc64R7syMCM&imgurl=http://realtimecollisiondetection.net/blog/wp-content/uploads/2008/09/akers_algorithm.png&w=462&h=168&ei=-lPdUKPpA8KttAarlIAI&zoom=1&iact=hc&vpx=182&vpy=155&dur=8820&hovh=134&hovw=369&tx=130&ty=97&sig=104779906298197210948&page=1&tbnh=100&tbnw=274&start=0&ndsp=34&ved=1t:429,r:1,s:0,i:91

[robo_tom_24]

So weit gehen...Ich hab Zeit, also warum nicht ;)

Die Frage ist nun aber auch, wie oft müsste man dann ein unbekanntes Labyrinth durchlaufen um an die erforderlichen Informationen zu kommen? Man müsste ja erst mal ein gesamtes "Bild" des Labyrinths erstellen um es rastern zu können. Wie erstellt man den effizient eine gute Karte? Ich denke, mit den mir im Moment zur Verfügung stehenden Mitteln (Abstandssensoren und Radencoder) wird das doch schwer werden. Oder seh ich das grad komplett falsch und es ist gar nicht so schwer? :cool:

[Manf]

Labyrinth - Irrgarten wenn man es genau nimmt sind das schon Unterschiede.
Ich nehme mal an es handelt sich um einen allgemeinen Irrgarten, zweidimensional und endlich in x und y Richtung.
Wenn man es mit einem Fahrzeug abfährt dann hat es eine Mindest- Wegbreite, vielleicht sind die Wege auch von konstanter Breite.
Im Idealfall ist es wie ein Schachbrett aufgebaut wobei jede der vier Feldgrenzen eine Wand hat oder nicht.
Man kann dann, nachdem man es durch Abfahren überprüft hat, zu jedem Feld speichern, welche Grenzen mit Wänden besetzt sind.

[robo_tom_24]

Ja, ganz normal. Ideal ist mein Testirrgarten nicht, aber die Wegbreite ist ziemlich konstant (+/- 2cm). Mir kommt aber gerade eine Idee zwecks dem Schachbrett: Es ist ja eigentlich egal, wie lange meine Sackgassen sind, oder? Wenn ich mir ein Modell erstelle, dann wird eine 5cm Sackgasse genau so gelöscht wie eine 5m Sackgasse...Aber die anderen "Felder" sind nicht gleich lang. Ich werd aber mal nachmessen, und versuchen einen Raster zu finden. Vielleicht auch ein wenig das Testgelände optimieren um einen 10cm Raster o.Ä. zu bekommen ;)

[Manf]

Ich meinte nicht die Genauigkeit in der Umsetzung, da kann man immer noch ein Bisschen optimieren.

Ich meinte die Organisation der Daten.
Man kann einerseits Wegstücke speichern mit Eigenschaften wie Wänden mit Ortsangaben und Richtungen.
So kommt man zu Listen von Wegen. Hat man eine große Fläche und wenige Wege dann könnte das vorteilhaft sein.
Die andere Möglichkeit ist eine Matrix von Feldern zu definieren und zu jedem Feld Eigenschaften zu speichern, welche Seite von einer Wand begrenzt ist.
Die Organisation der Daten nach Position in der Matrix kann leicht etwas umfangreich werden, aber wenn es geht, dann hat man gleich mit der Position alle Daten zugänglich.
Bei der Organisation nach Wegen sieht man nicht automatisch ob man den Weg den man gerade geht schon einmal beispielsweise von der anderen gegangen ist. Man müsste die bereits gegangen Wege anhand ihrer Position überprüfen.

[robo_tom_24]

Hmm, ok, mein Fehler ;)

Ok, somit ist die Wegmethode nur bei Irrgärten ohne "frei stehenden" Mauern sinnvoll möglich, also einem Irrgarten mit Sackgassen und nur einem möglichen Lösungsweg (also ein Labyrinth mit Sackgassen). Wie legt man jetzt aber so ein Raster an? Einfach mit Abfahren des Labyrinths und dann alle paar cm Messen wo es eine Mauer gibt usw.?

[Manf]

Ich habe noch das Beispiel vom ganz alten Micromouse Contest vor Augen. Da hatte man eine recht formalisierte einfache Umgebung.
Schachbrettartige Felder und nur Wände an Feldgrenzen, und dann auch von der ganzen Länge des Feldes. In einer solchen Umgebung kann man jeweils auf das nächste Feld fahren sich dort ausrichten und die 4 möglichen Wände überprüfen.

Das ist eben ein erprobtes Beispiel. Ich denke immer zuerst an dieses Beispiel.
Es gab dabei auch Roboter die mechanisch (vorsichtig) an die Wand gefahren sind um sich dadurch in der Richtung und in der Position auszurichten. Andere haben es mit Abstandssensoren gemacht.

Hier ist Beispiel aus neuerer Zeit, im 1981 lief das viel ruhiger ab.
Der Maus steht eine Gesamtzeit zur Verfügung in der sie das Feld erkunden und den Lauf von Start bis Ziel absolvieren darf. Sie fährt bei der Orientierung erst langsam und präzise. Der Schlusslauf ist dann zeitkritisch und läuft hier mit erstaunlicher Geschwindigkeit.
Es sind aber wie gesagt spezielle Regeln.


http://www.youtube.com/watch?v=ZtOtrVB_r0w

[robo_tom_24]

Ja, nach diesem Prinzip könnte man vorgehen. Was ich hier aber nicht ganz verstehe, wie kann man in so kurzer Zeit einen so "großen" Irrgarten kartographieren?

[Manf]

1. Man muss nicht jedes Feld befahren um seine Wände kennenzulernen da die Wände jeweils von 2 Seiten zu sehen sind.

2. Auch wenn man davon ausgeht dass es mehrere unterschiedlich gute Lösungen gibt kann man Gebiete ausschließen wenn ein Weg durch sie sie nicht besser werden kann als ein bereits gefundener Weg.

3. Man kann die Aufgabe unvollständig lösen um rechtzeitig fertig zu werden.

...

[robo_tom_24]

Ja, stimmt...