Überlegungen zum Mapbuilding

[Reinald]

Hallo Zusammen,

mich würde mal interressieren, wie sich eure Roboter so die Umgebung merken, da gibt es ja grundsätzlich einige unterschiedliche Möglichkeiten:

- 2-D "Bitmap" mit fester Auflösung und "vorprogrammiert"
- 2-D "Bitmap" und der Roboter scannt selber
- Vektorkarte ind 2D oder 3D

Aber da sind mir doch einige Fragen offen, vielleicht hat sich da ja schon mal jemand Gedanken gemacht:
z.B. Welche Auflösung - sollte die Auflösung kleiner sein als der Roboter groß ist? Dann müsste man den Roboter selber mit seinem "Flächenbedarf" mitrechnen. Wenn die Auflösung der Karte kleiner ist als der Roboter, dann wäre das nicht so wichtig.

Unterscheidet man in der Karte zwischen "befahrbar", "nicht befahrbar", "keine Information"?

Wie kann man (oder soll man) zwischen "festen" und "beweglichen" Hindernissen unterscheiden? Die Katze als klassisches Beispiel - kann sich zwischen den Scanvorgängen bewegen. Oder einfach nur eine statistische Methode, die Daten zu bewerten?

Hat sich schon jemand Gedanken zu einem "Standard-Format" gemacht? Treffen sich zwei Roboter, sagt der eine "ey, haste mal ne Karte", sagt der andere "ja klar, aber da hinten ist nix los, brauchste nicht hinfahrn..." Für ein solches Format könnte man dann auch einen Viewer bauen, um die Ergebnisse zu kontrollieren.

Meine Überlegungen bis jetzt:
- Für die einfachste Variante ist vermutlich eine 2D-Bitmap ausreichend. Das Minimiert auch den Speicherbedarf, so daß es auch in den Microcontroller paßt.
- genauer und für größere Datenmengen wird dann irgendwann die Vektorkarte günstiger. Vermutlich aber erst bei Datenmengen > 100kb. Dafür wird die Verarbeitung aufwändiger. Eine moderne GPU könnte dann aber z.B. Kollisionsberechnung in Echtzeit machen. Braucht vermutlich eine übergeordneten Rechner (PC oder extern), ist mit einem Mikrocontroller nicht zu lösen. Oder Spezialhardware resp. Vektor-Rechner mit größerem Speicher.
- Ein Standard "Dateiformat" würde die Entwicklung vereinfachen, Ergebnisse können besser verglichen werden. Für die Kooperation mehrerer Einheiten ist eine gemeinsame Datenbasis unumgänglich.

Eure Meinungen dazu?

Gruß
Reinald

[NumberFive]

Zum Thema Karte gibt es hier im Forum doch so einige Threads aber wirklich relaisiert habe ich es noch nicht gesehen bis jetzt. bis auf bei http://www.wiesolator.de/

wie du auch ein kleine Bimapkarte in den controller bringen willst ist mir nicht so klar den wenn wir mal das von aus gehen die karte hat ein auf lösung von 50 cm du brauchst drei bit mindestens um eine punkt zu beschreiben wird der speicher bedarf doch sehr schnell sehr groß.

20 m² raum 5 x 4 m = 80 Quadarte * 3 Bit macht 240 bit = 30 Byte infor mation die relativ schwer zu decodieren ist da du ja die bytes in bit zerlegen mußt und bei drei immer über die byte grenze kommst.

Standard-Format währe klasse weil man sich dann die Arbeit teilen könnte Anzeigen, Routing und so weiter.

Mein Gedanke war immer drei Karten zu haben 0 cm höhe 20 cm höhe und 40 cm höhe. Um überfahrbare Hindernisse ein zeichnen zu können aber nicht den Aufwand für 3D zu haben.

Währe ein nettes Addon für hier:
https://www.roboternetz.de/phpBB2/viewtopic.php?t=16297

Soweit erst mal

[marvin42x]

Freu freu,

Wie NumberFive schon andeutete haben wir ein RN -Projekt, das solch eine Komponente in der nächsten Ausbaustufe braucht.
Das Projekt stellt in Kürze ein paar Demos vor, da es von der text mäßigen Beschreibung der Sache her etwas unhandlich zu verstehen ist.
Mit den fertigen Komponenten könnte man das Mapbuilding auch gleich praktisch ausprobieren. Und herausfinden welche Überlegungen machbar/nützlich sind und welche nicht.

Mapbuilding:
Dazu ein Standard zu vereinbaren wäre für den Erfolg eines verwertbaren Map –Buildings aus meiner Sicht ausschlaggebend.
Nebenher: Das macht dann auch viel mehr Spaß, wenn man mit Freunden zusammen an einem Mapbuilding –Motor bastelt kann


Zum mir bekannten Umfeld:
MrNiemand hat eine Software die eine 3D gerenderte Darstellung eines Bots innerhalb einer Map bereits kann. Wenn er Koordinaten bekommt kann er das 3d darstellen.
Schuldigung MrNiemand, das ich hier so über Deinen Kopf hinweg mit deinen Sachen angebe.
Ganz oben genanntes Projekt stellt die Infra -Struktur der Kommunikation und ein µC Betriebssystem welches damit umgehen kann nebst PC –Komponenten zur Steuerung und Überwachung der Robs.
Der Von NumberFive gepostete Link zeigt ein sehr gelungenes Projekt.

Das war jetzt mal zum beleuchten der Umgebung gedacht um erstmal ein paar praktische Optionen ins Bild zu bringen.

Netter Gruß

[marvin42x]

@Reinald:
Deine ersten Überlegungen sind meiner Meinung nach eine gute Ausgangsbasis um sich der Sache zu näher.

Allgemein:
Die kleinen µC’s können da nicht die großen Sprünge machen.
Was ich mir vorstellen könnte ist ein kleines µMapsystem und einen großen Bruder der auf einem PC gehostet wird.

PC:
Auf dem PC würde mir eine Datenbank –Anbindung vorschweben. Damit kann man große Datenmengen in akzeptabler Geschwindigkeit verhütten ohne eigenen Speicher und Verwaltungsprogramme zu schreiben.
Das ist bewährte Technik, die zudem auch Netzwerkfähig ist.
Davor oder dahinter schaltet man Auswertesoftware die mit den bereitgestellten Daten was anfangen kann.
Viewer für das Ganze stehen in den Startlöchern.

µController
Auf den Kleinen fällt mir nicht viel ein. Es ist sehr eng.
Dort kann eigentlich nur ein kleiner aktueller Kartenausschnitt überleben welcher ihn aber durchaus autark macht. Das Format der Koordinaten sollte auch Speichersparsamer sein, anders als auf dem PC.
Hier birgt auch die Vernetzung der Kleinen Vorteile, also so wie Du Eingangs schon gesagt hast.
Ich vermute, dass man nur Koordinaten von existierenden Messungen ablegt, ohne ganze Arrays zu errichten die eine Map repräsentieren.

Netter Gruß

[Reinald]

So, um das Ganze ein bischen zu strukturieren:

Step 1: Vereinbarung einer Datenstruktur, um µ-Maps auf einem µ-Controller zu speichern. Dateiformat ist hier wohl zu hoch gegriffen. Eine einheitliche Struktur würde aber die Wiederverwendung von Code-Snippets vereinfachen. Mein Vorschlag: Rasterdaten mit 4 Bit / Pixel. Damit lassen sich genug Werte codieren, um
- befahrbar
- nicht befahrbar
- hier bin ich
- hier steht eine Bake
- undefiniert
- "gestern war hier noch frei heute steht hier was ist es vielleicht die katze?"
zu codieren.
Für den Zugriff auf die Karte sollte man einen Satz passender Funktionen bauen, damit ist dann auch das Aufsplitten in die oberen/unteren 4 Bit verkapselt. Im ersten Schritt könnte die Karte auch erstmal "fest" codiert werden, d.h. händisch erstellt und geladen. Man kann davon ausgehen, den Bot beim Start auf ein definierte Position zu stellen bzw. ihm seine Position mitzuteilen. Orientierung und Rückkehrgenauigkeit stellen die erste Herausforderung an den Bot und seine Steuerung - Navigation - Odometrie. Eine zweite/dritte "Ebene" würde ich an der Stelle für überflüssig halten (oder gibt es da einen Anwendungsfall für?)

Step 2a: Aufbau der Karte durch den Bot selber. Dabei sollte es darum gehen, die Daten vom Bot selber erfassen zu lassen. Heraus kommt dabei eine Karte, die weniger in "go vs. nogo" eingeteilt ist, als grundsätzliche "wo könnte ich fahren"- Informationen. Praktische Herausforderungen werden sein, passende Filter für die Bewertung der Sensorinformationen zu entwickeln. Wann wird ein Pixel "schwarz", wann wird es "weiß"? Was mache ich mit wiedersprüchlichen informationen unterschiedlicher Sensoren? Was mache ich mit Wiedersprüchlichen Informationen zwischen Karte und Sensor-Input?

Step 2b: Die Orientierung innerhalb der Karte. Geht man in Step 1 und 2a noch davon aus, daß der Bot auf einem definierten Startpunkt steht, ist es natürlich spannender wenn er "spontan" beim Einschalten seine Position erkennen kann. Was man Outdoor mit DGPS halbwegs lösen kann, ist indoor eine andere Aufgabenstellung. Hier finde ich die Überlegungen zu einem "Local Positioning System" sehr gut, "Leuchttürme" die rotieren und dabei die Winkelinformation verschicken. Damit können die aufsummierten Fehler der Wegeerfassung wieder ausgeglichen werden.

Bis hierhin sollte das alles auf dem Mikro-Controller gelöst werden können.

Step 3ff: Kommunikation mit einem Steuer-PC. Dabei spielt es keine Rolle, ob der PC "onboard" sitzt oder per Funk angebunden ist. Also:
- Karten upload
- Karten download
- Statusabfragen
- Steuerbefehle
- rendern einer Pixel-Karte aus der "großen" Vektorkarte

Als Datenformat auf dem PC würde ich entweder ein XML-basiertes Format vorschlagen, oder einen offenen Standard aus der 3-D Welt. Letzteres hätte den Vorteil, daß es Viewer fertig gibt. Ersteres wäre "human readable" und könnte einfach in Datenbanken abgelegt werden.

Soweit erst mal.
Reinald

[wkrug]

Ich hätt da noch mal eine vieleicht blöde Frage - bin selber kein Roboterbauer:

Wenn man Karten benutzen will muß man doch wissen wo sich der Bot befindet um eine Route oder das nächste Hindernis finden zu können.

Müsste das dann nicht auch noch irgendwie realisiert werden ?
Das mindeste wäre doch ein fester Bezugspunkt ?

Und wenn Ja, wie realisiert man das, ohne im gewünschten Zielgebiet umfangreiche Installationen zu machen?

Tschuldigung - ich frag blos aus Neugier...

[MrNiemand]

Hi,

ich halte eine dynamische Verwaltung für viel zu Aufwendig, und ein Array mit fester Größe kann ein µC auch noch effektiv verwenden.

als Beispiel:

ein Array mit 512x512 Werten jeder Wert entspricht dabei 10cm
=> die Maßfläche liegt bei 5120cmx5120cm

das ganze braucht dabei nur 32kbyte Speicher wenn nur abgespeichert werden soll ob ein Hinderniss auf diesem Punkt ist oder nicht.
(Das macht durchaus Sinn, denn so weis der Bot gleich "holla da war ich schon, da will ich nimmer hin")

Ok für den Fall "da war ich noch noch nicht" muss man sich was einfallen lassen, aber ich finde 4bit doch reichlich viel, für die Position des Bots reicht ja z.b. ein Datensatz, da muss man nicht das ganze Array zuschmeißen damit, zumal es für den Bot dann schwer ist, sich auch selbst wieder zu finden in dem Teil.
Eine Katz z.b. ist schnell erledigt, beim letzten Scan war ein Hinderniss da, nun nicht mehr => Hindernissinfo löschen.

[marvin42x]

Na das hört sich doch schon nicht schlecht an.

Reinald, ich muss sagen, ich bin ganz auf Deiner Linie.
Auch die 3D –Engins habe ich im Augenwinkel.

Ich habe mich die letzte Zeit nur mit dem Kommunikationsprojekt befasst.
Das wird dabei auch voll zum Tragen kommen.
Dadurch sind diese Einzelkomponenten wie Map -Building bei mir noch nicht bis ins Detail durchdacht.
Das mindert meine Kritikfähigkeit

Mal sehen ob noch ein paar Kundige was dazu sagen. Damit das Bild rund wird.
MrNiemand wird ja dazu auch schon konkret.

Die Frage ob und wie dynamisch, und welche Lastenverteilung zwischen PC und µC die richtige Wahl ist werden wir abwägen müssen.

Des weiteren ob der Robi Arrays benutzt oder nur Koordinaten von Hindernissen und dem „Zaun„ des Gebietes was er schon gescannt hat speichert.

Auch das Format in dem Kommuniziert werden soll ist Thema.

Ich freu mich erstmal, dass das so konkret losgeht.

Netter Gruß

[PicNick]

Ich wär mal für ein "RAW" Format.

Was ist denn eigentlich eine Karte ?
Ein Karte ist eine Sammlung von koordinaten + zugeordneter Sensorwert,
die nach den Koordinaten sortiert ist.

Übermitteln kann man das en block oder einzeln, das ändert erstmal nix.

Was muß ein Empfänger wissen ?
Type xy(z) oder vektor
Sensortyp
Units (cm, m, inch, etc.) /absolut/relativ
Das braucht wohl nur einmal zwischen den Partnern festgelegt zu werden.

Und je "Pixel" Information eben x, y, (z bei 3D) und der Sensorwert.

Das kann ein Robby nun direkt zum PC schicken, er kann natürlich auch selbst seine Informationen rausholen, muß er aber nicht.

Gerade für eine langsame Robby-PC Strecke word man wohl eine art RLE Verfahren anwenden, dh. heißt sendung nur dann, wenn sich der Sensorwert um einen gewissen Wert ändert (parametrisierbarer Threshold ?)
Dann sollte er aber schon auch seine Odometriedaten auch schicken.
Für die gilt wieder Ähnliches, also ganz primi nur steps links/rechts oder schon aufbereitet .

[marvin42x]

Hi PicNick
Das wird ja ein netter Abend.

So wie Du das beschrieben hast könnte ich mir das vorstellen.
Eine Frage dazu:
Brauchen wir zu den Koordinaten x,y, eventuell z noch einen Sensorwert?
Oder können wir den einspaaren?

Auch die Datengröße der Koordinaten müsste man mal abschätzen.
Ob 8 bit, 16 oder was weis ich.

Netter Gruß