Roboter Labyrinth

[Peter S. (wuhu)]

Hallo.

Wie ihr sicher unschwer erkennen werdet, bin ich kein Profi, 
strenggenommen bin ich wohl eher Anfänger. Trotzdem möchte ich natürlich 
-auch wenn es jeder Vernunft widerspricht- hoch hinaus.

Folgendes Problem:
Ich habe in einem Buch in etwa folgendes gesehen:

##################
#           #    #
# ###### ####### #
# # #    #     # #
# # ## ###### ####
# #      #     # #
# ###### # ##### #
#                #
##################

Es stellte ein Labyrinth dar und war noch etwas komplexer und deutlich 
schöner als meins hier.
Es wurde dann in diesem Buch scheinbar ein Programm entwickelt, dass 
einen Weg durch das Labyrinth bzw. von einem Punkt a zu Punkt b findet.
Ich selbst besitze einen kleinen Roboter eine sogenannte "Robolaus" die 
auf einem Amtel Board ( 
http://www.krause-robotik.de/service/download/atmel/kr-mega32-16v23.pdf 
) basiert.
Mein Traum wäre es jetzt, dass ich dem Roboter einen "Rahmen" einer 
bestimmten Größe vorgebe (z.B. 2x2m) und wenn ich ihn dann in ein 
abgegrenztes Feld dieser Größe stelle, erkundet er selbstständig den 
Raum und "markiert" jedes Hindernis, auf das er stößt. Günstig wäre es, 
wenn er mir diese "Karte" dann ausgeben (sprich an den Computer senden) 
könnte, vielleicht auch während der Fahrt.  bzw, dass er anhand der 
Daten die er sammelt sich selbst einen Weg durch den Raum bahnen kann, 
ohne an einem dieser Objekte anzustoßen.

Meine Frage ist nicht, wie ich die Hindernisse erkenne und aus den 
Sensoren (Ultraschall, IR, ...) Daten auslese, sondern mir geht es um 
Folgendes:
- Wie definiere ich den Rahmen für diese Erkundungsfahrt? Und brauche 
ich den überhaupt?
- Wie kann ich eine Markierung setzen und wie kann ich sie beim 
weiterfahren wieder auslesen um nicht noch einmal auf dasselbe Hindernis 
zu prallen.
- Wie kann ich Daten an den PC senden/empfangen?
- und vor allem: ist meine Idee überhaupt umsetzbar?

Ich weiß: viele Fragen auf einmal... sry!
Paul

[TestX .. (xaos)]

ne karte mit ultraschall, ir...hm joa irgendwie geht das wird aber 
unschön...besorg dir nen SIG 2d laserscanner, damit kann man dann auch 
was anfangen ;)
ansonsten ist das kein großés problem..wenn du ein abgeschlossenes 
gebiet hast brauchst du keinen rahmen zu definieren oder ähnliches (denk 
nur an die größe der karte...). markierungen etc setzt du, in der aus 
den daten erzeugten, umgebungskarte.
senden/empfangen über zB wlan, bluetooth, funktransceiver (RFM12 etc)..

[Karl H. (kbuchegg)]

Und noch was.
Ehe du das ganze mit realer Hardware machst, probier es am PC aus. So 
ein Labyrinth in einem 2D-Feld ist schon ein guter Ansatz.

> Wie kann ich eine Markierung setzen
Gar nicht. Dein Robbi baut sich intern eine Karte seiner Umgebung auf. 
Im Grunde muss er während der Erkundungsfahrt genau den Inhalt dieses 2D 
Arrays rausfinden, den du ihm im ersten Schritt bei deinen Versuchen auf 
dem PC vorgibst.

Auch wenn du davon träumst: Fang in kleinen Schritten an. Eine 
Teilaufgabe nach der anderen.

[STK500-Besitzer (Gast)]

Sowas haben wird damals in der Schule im Informatikunterricht in Pascal 
programmiert:
Ein Labyrinth als Array erzeugt (Rahmen, Hindernisse).
Da haben wir einen Roboter "reingesetzt", der nach vorne, links und 
rechts gucken konnte (und immer in dieser Reihenfolge nach dem weg 
gesucht hat)
Er ist dann immer in die Richtung "gefahren", in der zuerst kein 
Hindernis war. Wenn alle Richtungen getestet waren, bewegte er sich zur 
vorhergehenden Position und testete die übrigen Richtungen. Irgendwann 
hatte er das Zeil erreicht.
"Einfaches" Beispiel für "Trial'n'Error" und Rekursion.

[Rolf Magnus (Gast)]

Das entspricht einer einfachen Tiefensuche:
http://de.wikipedia.org/wiki/Tiefensuche

[Karl H. (kbuchegg)]

STK500-Besitzer schrieb:

> Er ist dann immer in die Richtung "gefahren", in der zuerst kein
> Hindernis war. Wenn alle Richtungen getestet waren, bewegte er sich zur
> vorhergehenden Position und testete die übrigen Richtungen. Irgendwann
> hatte er das Zeil erreicht.
> "Einfaches" Beispiel für "Trial'n'Error" und Rekursion.

Sowas hab ich auch immer gerne meinen Schülern im Kapitel Rekursion als 
Aufgabe gegeben. Der Titel war "Wie kommt die Maus zum Käse"
Die eigentliche Suche ist rekursiv ein paar Zeilen lang und wenn man 
Rekursionen verstanden hat, eigentlich sehr simpel. Aber bis man das 
Vertrauen hat, dass diese paar Zeilen zusammen mit der Rekursion das 
Problem lösen können, das ist ein langwieriger Prozess :-)

Ach ja, was ich sagen wollte: Man bezeichnet das auch als 
'Backtracking'. Versuch einfach mal eine Richtung. Wenns klappt: super. 
Wenns nicht klappt, versuch eine andere wenns noch eine gibt.
Ist ein sehr mächtiges Werkzeug, das jeder in seinem Wekzeugkasten 
vorrätig haben sollte. Die Programmiersprache Prolog baut in 
wesentlichen Grundzügen darauf auf.

[Klaus W. (mfgkw)]

Als Zusatzaufgabe kann man dann gleich mit dazugeben, ob der Stack
dafür auch reicht.
Also überschlagen, wieviele Byte auf dem Stack pro Ebene benötigt
werden und wie tief die Rekursion maximal gehen kann.
Sonst ist die Rekursion schnell mal die ganz böse Rekursion.

[Peter S. (wuhu)]

Wow. Danke erst einmal. Ich versuche mich jetzt zunächst daran eure 
Vorschläge zu überdenken und dann werde ich euch sicher noch einmal mit 
Fragen zu diesem Thema belästigen. Danke!