Navigation Staubsaugerroboter

[tomg]

Hallo,

ich hoffe ihr könnt mir weiterhelfen!

Und zwar folgendes:
Ich entwerfe momentan einen Staubsaugerroboter und brauche Hilfe von euch.

Ich möchte einen Erkundungsmodus in dem der Roboter die Gegend erkundet und alle Informationen speichert um später beim Abruf der Karte intelligenter saugen zu können, ohne Bereiche auszulassen.

Meine Frage nun: Welche Kartentechnik eignet sich hierfür am besten in Verbindung mit welchem Microcontroller?
Topologische oder Metrische, Raster- oder Vektorkarten?
Sind Rasterkarten aufgrund des großen Speicherbedarfes überhaupt geeignet für Microcontroller?

Danke im Vorraus für die Antworten!

Gruß Tom

[tompcat]

Hallo

Schreib mal erstmal was dein microkontroller kann... wieviel Speicher er hat welche prozessorleistung.... hab leider nicht viel Ahnung von den Dingern bin nur ein informatiker. Ich persönlich bin ja ein FAN vom Potentialfeld ansatz, der Vectorbassiert verläuft. Dieser wird zwar normalerweise benutzt um inteligent Hindernisse zu umfahren, aber für deine Zwecke sollte er auch gut einsetzbar sein. Der Ansatz funktioniert bildlich gesprochen wie ein Planschbecken mit Fontainen. Wenn du ein Blatt neben eine Fontaine stellst wird es weggeschwemmt, und das was das Blatt macht, soll dein Roboter dann auch machen.... Du must halt überall wo du dich zu Lange aufgehalten hast eine Fontaine hinsetzen, damit dein Roboter weiterfährt und nich wieder dahin zurückfährt. Zum anderen soll er zu großen Freiflächen hingezogen werden. Dort sollte man dann einen Strudel hinsetzten, der das Blatt anzieht. Dass kann man natürlich auch mathematisch formulieren, aber so ungefähr funktioniert es. Ich schreib dir mehr, wenn es hoffnung gibt, dass dein microcontroller das auch schafft.

Bye

Tompcat

[tomg]

Hi Tompcat,

Ich stecke noch mitten im Entwurf, es ist noch kein Microcontroller vorhanden.
Ich werde mir den Microcontroller danach aussuchen für welche Kartierungstechnik ich mich entscheide. Allerdings liegt gerade hierbei das Problem. Ich weiß nicht wirklich wieviel Rechenleistung und Speicher ich jeweils benötige für welche Kartierungstechnik.

Aber klar ist, dass die Navigation ohne externen Rechner möglich sein soll.

Tom

[tompcat]

Hi

Najut diese Frage kann ich leicht beantworten. Für einen Vektorbassierten ansatzt steigt der Aufwand der berechnung linear zur abgefahrenen strecke zu. Bei einem Rasterverfahren hast du direkt am anfang einen ziemlich hochen aufwand und der bleibt konstant. Sagen wir bei einem 4x4m großen raum mit einer auflösung von 5cm währe wir bei 6400 Punkten. Hierbei kann man sich aber sehr viel sparen, weil man sich meistens nur die Umgebung ganz gezielt angucken kann, wo der roboter sich gerade befindet. Bei Vectoren muß man meistens alle durchlaufen, was ziemlich anstrengend sein kann für einen schwachen prozessor aber gut für einen Controller, der wenig speicher hat. Aber es gibt auch möglichkeit den Speicheraufwand für die Rasterung zu minimieren. Du könntest dafür eine abwandlung des Warnock-Algorithmus verwenden. Der Grundgedanke ist einfach. Wenn ein großes Quadrat leer ist braucht man sich nur merken dass es leer ist und nicht, dass jedes einzelne element des quadrates leer ist. Also definiert man am anfang eine Baum struktur mi einem Quadrat oben links unten links oben rechts und unten rechts. Am Anfang. Jedes Quadrat hat wieder so einen Baum und so weiter bis man wieder auf rasterebene ist. Somit kann man jeden rasterpunkt ansprechen. Dass coole ist nur, dass du schon auf oberer ebene entscheiden kannst, dass ein großes Quadrat noch nie befahren wurde braucht man sich die äste des baumes nicht mitzuspeichern. Wenn du jetzt noch deinem Roboter beibrings immer das nähs größere quadrat abzufahren, währe dein Speicheraufwand minimal. Ist halt nur etwas schwieriger zu implementieren. Wenn du dich also entscheiden würdest in diesem 4x4m raum dir immer nur 1x1m hintereinander abzufahren brauchst du maximal 408 einträge, womit du enorm viel speicher gespaar hast im gegensatz zu 6400 einträgen. Und die anzal der Einträge wird nochmal enorm kleiner wenn du dich entscheidest nu 0.5mx0.5m abzufahren. Da sinds dann nur noch 112 einträge usw.... Also kannst du einen belibig großen raum abfahren, wenn du nur die schritte klein hälst.

Vieleicht dient dir das ein bischen als Maßstab.

bye

[tomg]

Hi,

das bringt mich schonmal ein ganzes Stück weiter!
Wäre es denn möglich mit deiner beschriebenen Methode die jeweilige Karte eines Raumes langfristig zu speichern um z.B. beim nächsten Mal wenn dann der Staubsauger den gleichen Raum nochmals saugen soll die Karte abrufen zu können?

Bzw das man bis zu 3 Karten speichert und dann je nach Raum die bereits vorhandene Karte wählen kann.

Tom

[harato]

Natürlich wäre es möglich, aber dann bringt dir die von tompcat beschriebene Methode zur verkleinerung der Karte nichts mehr, weil du dann trotzdem alle Punkte abspeichern müsstest.

Ein Problem bei der beschriebenen Methode sehe ich trotzdem noch (vorausgesetzt ich habe alles richtig verstanden):
Der Roboter müsste immer ganz genau Wissen in welchem Raum, in welchem Quadranten mit welcher Himmelsrichtung er gerade gestartet wird, oder sehe ich das falsch?

Gruss

harato

[tompcat]

Hi Harato

Ja das siehst du komplett richtig. Der Roboter muß immer genau wissen wo er sich befindet und in welche Richtung er fährt. Aber das Problem hat man leider bei jedem Kartenbasiertem Ansatz. Falls du eine idee hast, wie man SLAM mit einem Microcontroler ordentlich implementieren kann dann her damit. Ich glaube aber auch, dass es genau daran scheitert.

Eins hast du aber schlecht verstanden. Die Methode bringt immer etwas auch wenn man mehrere Räume hat... macht ja kein Unterschied zu anderen Methoden. Es ist einfach nur eine inteligente Methode eine Rasterkerte effektiv abzuspeichern. Aber da hat harato wieder recht, dass es nicht mehr ganz so viel bringt wie beim staubsaugen, weil du die Hindernisse im Raum nicht dazu br.ingen kannst quadratisch zu sein Aber sobald man irgendwie größere Flächen hat, die als belegt gelten bringt es wieder ein kleines bischen speicherersparniss.

Also für dein Problem gilt, dass du 2 Unterschiedliche Sachen speicher möchtest. Zum einen wo der Roboter war und zum einem wo die Wände / Hindernisse sind um diese seperat abzuspeichern. Naja die einfache methode währe es einfach 2 solcher Baumstrukturen zu haben (eine für den Raum/Hindernisse und eine für wo der Robo schonmal war).... eine andere währe es, dass du in den Ästen abspeicherst ob es sich um eine Wand oder um ein Hinderniss handelt. Dann wird es besser aber für dich sicherlich schwer zu programieren sein, was in den Knoten passiert. In jedem Knoten kann jetzt drinstehen, dass ein Quadrat :
-Völlig frei
-Völlig besetzt
-Komplett abgefahren
-teilweise besetzt und teilweise abgefahren
-teilweise frei teilweise abgefahren
-teilweise frei, teilweise abgefahren, teilweise besetzt
und alle weitere kombinationen ist..

Damit kannst du dann erreichen, dass du weniger Prozessorleistung benötigst um zu gucken, wo der Roboter den noch hinmuss, weil du bei teilweise besetzt und teilweise abgefahren weißt, dass du durch dieses Feld zwar durchfahren kannst, es aber nicht mehr durchsuchen mußt, wenn du prüfst wo du noch nicht gesaugt hast. Und trotzdem könntest du später beim abspeicher wissen wo dein roboter die Hindernisse gefunden hat und diese seperat abspeichern und beim nähsten mal wiederverwenden.

Wenn du die Hindernisse und die Information wo du warst einfach seperat abspeicherst hättest du aber deutlich weniger programieraufwand und es würde auch funktionieren, wenn auch etwas langsamer und etwas speicheraufwendiger.


Meine Frage ist, wie willst du den Roboter so genau im Raum lokalisieren? Du weißt hoffentlich, dass man sich auf die Mechanische odometrie nicht verlassen kann... besonders bei Drehungen (Kompas würde schon was helfen). Und GPS ist sicherlich zu grob für dich. Ich schätze du kommst bei einem Microkontroller nicht drum herum ihm irgendwelche markierungen auf den boden zu legen um die odometrieabweichungen zu kompensieren.

Tompcat

[harato]

Ich schätze du kommst bei einem Microkontroller nicht drum herum ihm irgendwelche markierungen auf den boden zu legen um die odometrieabweichungen zu kompensieren.

Du meinst schwarze Linien denen man nachfahren kann?

nein im mal im ernst, der Vorteil von der Methode besteht ja darin dass du immer nur einen Teil eines Raumes abfährst und so die benötigten Felder auf 408 (in deinem Beispiel) verringern kannst, wenn du nun aber alles abspeichern willst brauchst du ja doch wieder die Daten aller 6400 Felder?

mfg

harato

[tompcat]

Hi

Also da du darauf bestehst, dass man alles spiechern muss hab ich mich mal entschlossen es dir einfachmal an einem Bild zu erklären. Also du würdest diese felder in 4x4 große raster packen und dann alle rote oder weiße qadrate speicher. 1101 1100 1100 0010 0010.

Ich aber unterteile das bild zuerst in 4 quadrate, sodass im ersten oben links alles rot ist, im 2. oben rechts teilweise rot und teilweise weis ist. und 3. unten rechts teilweise rot und teilweise Weis ist und 4. ganz weiß. "1" ist rot "0" ist weiß "m" heißt gemischt. Somit ist die erste ebene 1mm0.

Das Reicht aber noch nicht um alles zu beschreiben. Nach dem ersten m muß ich mir also merken, dass ich mich jetzt im 2. Quadrat befinde: 1m0100....

Damit habe ich jetzt die beiden oberen großen quadrate beschrieben. Die 1 am anfang ist die große ausgefüllte fläche und das m0100 beschreibt das 2. Quadrat. Jetzt weil kein weiteres m hinzugekommen ist weiß ich, dass ich mich wieder auf der größeren quadratebene befinde. Die endgültige codierung währe also:
1 m0100 m1010 0 die Leerzeichen habe ich mal zur verdeutlichung hinzugefügt, weil es sich da um die 4 großen quadrate handelt. Auf diese weise kann man sich den Baum speichern und muss nicht jedes Raster mitschleppen.

Noch fragen?

mfg
Tompcat

[tomg]

Ich nehme mal an der rote Bereich bei dir bedeutet "nicht befahrbar" und der weiße "befahrbar"?

Dann wäre es für den Staubsaugerroboter doch sinnvoll wenn man zusätzlich einen Algoritmus einbaut, der dafür sorgt, dass sobald ein weißer Bereich abgefahren wurde, den ebenso auf rot setzt, damit er diesen nicht nochmal saugt.
Das Problem was wiederum hierbei auftauchen könnte ist, dass dann eine Rote Fläche so positioniert ist, dass eine noch weiße nicht erreicht werden kann. Deshalb müsste zusätzlich noch ein Verweis eingebaut werden, der kennzeichnet, dass die Fläche zwar schon gesaugt ist, aber dennoch durchfahren werden kann um zur nächsten weißen Fläche zu gelangen.

Und zu deiner Frage bzgl. der Genauigkeit der Navigation bzw. der Lokalisation:
GPS fällt definitiv weg, ist für innerhalb kaum zu gebrauchen und die Genauigkeit liegt nur im Meterbereich.
Mit dem Fehler der durch die mechanische Odometrie entsteht muss man dann eben leben, aber da gibt es auch verschiedene Möglichkeiten den möglichst gering zu halten.

Tom

Edit:
Wie könnte denn ein Codebeispiel in C aussehen? Gibt ja genügend Mikrocontroller die Hochsprachen unterstützen und ehrlich gesagt ist C auch die einzige die mir ein wenig liegt