MAP-Board

[Chris266]

Hallo zusammen,

mir schwebt seit kurzem ein Gedanke durch den Kopf der mich immer wieder einholt. Es gibt für so viele Dinge eine fertige Lösung: Motortreiber/Board, Servo-Chips, Controller-Boards, Kompassmodul, etc.

Doch eines, was vielen Roboterbastlern am Herzen liegt (zumindest mir), fehlt als "ready-to-run" Applikation: ein "MAP-Board".

Ich verstehe darunter ein kompaktes Board mit dessen Hilfe der Robi Punkte anfahren kann um den Weg von A nach B (von B nach F etc.) zu finden.

Mal angenommen es würde tatsächlich funktionieren: gefüttert wird das Board mit Odometriedaten, berechnet daraus seine ungefähre Position (X,Y Koordinaten). Mit einem Tastendruck kann diese Position "gespeichert" werden. Anschließend fährt der Robi weiter, bleibt stehen (X und Y Position werden weiterhin aktualisiert) und soll auf einen erneuten Knopfdruck wieder zur vorherigen Position zurück finden - auf dem kürzesten Weg.

Sollten Hindernisse detektiert werden, müsste es möglich sein dem "Map-Board" dies mitzuteilen. Dieses Hinderniss wird in der "Map" des Board gespeichert und wird in Zukunft umfahren.

Ich habe (noch) keine Erfahrung mit Odometriedaten, zumindest nicht um eine zuvor gespeicherte Position wieder zu finden. Bisher habe ich die Odometriedaten lediglich für eine bessere Geradeausfahrt verwendet.

Als Alternative zu den Odometriedaten könnten ggf. auch Beschleunigungssensoren und ein Gyro dienen. Doch auch hierzu habe ich keine pratischen Erfahrungen.

Es geht mir nicht darum eine zuvor gespeicherte Position auf den mm wieder anfahren zu können, ein paar cm Abweichung sind sicherlich akzeptabel: beispielsweise für das autonome Staubsaugen in einer Wohnung.

Mal angenommen es würde funktionieren, wäre es nicht schön wenn ein Roboter, beispielsweise über I2C oder SPI Interface ein externes "MAP-Board" fragen könnte: "Ich muss nach X=329, Y=100. In welche Richtung soll ich fahren und wie weit?". Diese "Frage" müsste selbstverständlich wiederholt werden damit "Abbiegungen" möglich sind. Sobald die zu fahrende Strecke = 0 ist, wäre der Robi am "Ziel", mit etwas Abweichung.

Mit einem kleinen ATMega Chip könnte sowas ggf. möglich sein. Kommt eben auf die Auflösung der internen MAP an und die gewählte Speichermethode. Soll die Wohnung bzw. die Umgebung in ein 8x8cm Raster unterteilt werden so könnte man mit 512 Bytes Speicher eine Fläche von 5,12m x 5,12m abspeichern sofern für jedes Feld ein Bit verwendet wird:

512 Bytes = 4096 Bits = 64 x 64 Felder mit 1 Bit pro Feld (0=frei, 1=Hinderniss).
Pro Feld eine Fläche von 0,08m x 0,08m = 64 * 0,08 * 64 * 0,08 = 26qm.

Die zurück gelegte Strecke als auch die aktuelle Ausrichtung des Robis (bei Zweiradantrieb) lässt sich mittels der Odometriedaten theoretisch errechnen.

Wenn ich mich jetzt nicht verschätzt habe (nicht ausgerechnet) müsste mit 4096 Bytes Speicher etwa eine Fläche von 100qm möglich sein (bei 8cm Auflösung)?

Die X und Y Position des Robis könnte in einer "höheren" Auflösung stattfinden (Bsp. mm). Es geht also nur darum "Kästchen" abzufahren.

Leider steigt der Speicherbedarf für den A*Pathfinding Algo (um gezielt den kürzesten Weg zwischen zwei bekannten Punkten ermitteln zu können) mit größerer MAP erheblich! Da für jedes Feld im Schlimmsten Fall ein X,Y,I(Index zum Vorgänger), H und G gespeichert sein muss (F wird beispielsweise permanent neu berechnet um Speicher zu sparen).
Wird eine MAP mit 512 Bytes verwendet (64x64 Felder) so ergibt sich, sofern für X,Y,I, H und G NUR ein Byte verwendet wird ein maximaler Speicherbedarf von 4096Felder*5Bytes=20480Bytes.
Diese Zahl ist zum Glück nur im Extremfall notwendig. Genau genommen muss X und Y kein ganzes Byte breit sein: schließlich sind in diesem Beispiel nur 64 Positionen in X und Y Richtung zu addressieren.

Ich möchte hier, zumindest zu diesem Zeitpunkt, nicht weiter auf die technischen Details eingehen.

Was mich interessiert:

Hat jemand Lust an der Entwicklung mit zu wirken?

Grüße und Danke!

[HannoHupmann]

Wenn du Zeit hast lies dir mal ein Buch über Roboter Odometrie durch, dann weist du warum es solch ein MAP-Board noch nicht gibt.

Das Problem an Odometrie ist, sie wird extrem schnell verfälscht. Räder rutschen druch und geben eine längere Strecke als wirklich gefahren aus. Der Roboter bleibt an einer Ecke hängen ohne es zu merken und ändert seine Richtung etwas.

Es gibt einige Versuche wo Roboter immer eine feste Strecke in einem Zimmer fahren, nur mit Odometrie und meistens ganz wo anderes heraus kommen als bei der ersten Runde.

Der nächste Punkt ist es erst mal eine 8x8 Karte der Umgebung zu erstellen, entweder (und das ist ziemlich aufwendig) per Hand einprogrammiert. Was aber ewiges nachmessen bedeutet.

Die einzige Möglichkeit eine sinnvolle Odometrie zu erstellen ist die Kombination aller Sensoren und Referenzmarken in der Wohnung an denen sich der Roboter neu ausrichten kann.
Ich denke da an:
-IR für die Referenzmarken
-Ultraschall für Hinternisse
-Kompas um die eigene Richtung zu ermitteln
-Odometrie um die Wegstrecke zu ermitteln
-Beschleunigungsensoren etc.

Das Problem ist nämlich, es arbeiten sehr viele daran alle Probleme der Odometrie in den Griff zu bekommen.
Man kann die Schwirigkeiten übrigens sehr leicht selber testen, zusagen im Selbstversuch. Überleg dir eine gerade Strecke in einem Zimmer (A und B) und dann lauf diese Blind (ohne zu schummeln) 5 mal auf und ab und schau wo du raus kommst (ich fürchte nicht mehr an Punkt A).
Wenn es so halbwegs klappt, dann versuch es mal mit einem Hinderniss in der Mitte, oder lass dich von jemanden ein bischen verdrehen. Da wird einem schnell klar wie kompliziert das ganze wird.

So den ganzen Pessimismus in ehren, den ich oben verzapft hab. Ich denke mit etwas überlegung kann man das ganze viel einfacher realisieren. Ich mein ich überleg mir auch nicht jeden Schritt vom PC zum Kühlschrank und zurück sondern ich geh einfach hin und wieder zurück.

Konkret: Ausgangspunkt A und Ausgangspunkt B. D.h. der Roboter fährt einfach mal los und nach ein paar Sekunden überprüft er an Hand seiner Karte ob er näher am Zielort B ist. Danach fährt er wieder ein Stück usw. Dabei reicht es erst mal den Zielort nur sehr grob zu kennen. Erst wenn man sich in unmittelbarer Nähe befindet solte der Roboter seine Karte abgleichen (Referenzpunkte) und die Position genau anfahren.

Vorteil die Karte kann sehr viel Gröber sein und im Raster variabel angelegt werden. Wenn der Zielpunkt für den Roboter einfach zu finden ist (IR Barke) dann reicht sogar schon ein einfacher Sichtkontakt um das Ziel anzusteuern.

das nur so meine Überlegung (ich will es eigentlich in meinem Roboter genau so ausprobieren).

mfg Hanno

[Chris266]

Ich habe unter anderem aus diesem Grund einen kleinen Robi gekauft der über Odometrie verfügt, inkl. Bumpern und Sensoren. Basteln wird also nicht mehr notwendig sein.

Jop, Räder rutschen durch, etc. Mein damals selbstgebauter Panzer-Roboter und der nachgerüsteten Odometrie einer Maus, zeigte jedoch nicht wirklich durchrutschende Räder Naja, war ja auch nur für den besseren Geradeauslauf.

Ich denke die Fahrt an sich wird nicht wirklich das Problem sein: 500mm vor und wieder zurück. Das Problem wird sicherlich die Rotation des Robis sein. Doch mehr kann ich erst dazu sagen wenn ich meinen neuen Robi mal ein Rechteck abfahren lasse, beispielsweise 5 oder 10 Runden um die tatsächliche Abweichung zu ermitteln. Übergänge von Teppich auf Fließen beispielsweise sollten, geschätzt, ebenfalls Abweichungen hervor rufen.

Als Alternative hatte ich mir auch Beschleunigungssensoren überlegt. Diese besitzen keine durchrutschenden Räder. Leider ist auch hier eine Toleranz bis zu 4% (laut Datenblatt) möglich. Doch auch hier wird erst die Praxis zeigen in wie weit dies zutrifft.

In zwei Wochen werde ich dazu kommen die ersten Tests durchführen zu können.

Meine Frage bleibt: Auch wenn es nicht klappen sollte, hat jemand Interesse daran mit zu wirken?

[hacker]

Du willst da auf dem kürzesten Weg zu deinem Punkten? ...Da hast du aber mit deinem Mega8 viel vor.
Außerdem würde so ein Map-Board nur in Verbindung mit Irgenteim Hindernissscanmodul effektiv sein. Oder willst du dauernd gegen Hindernisse fahren? Du müsstest auch die Positionen der Hindernisse kennen.

Meiner Meinung nach ist das Mapping eigentlich noch das Gebiet innerhalb der autonomen Roboter, wo noch keine komplett gekaufte Lösung möglich ist. Da hat man noch eine Herrausforderung und individuelle Lösungen winken.