Algorithmus zur Raumexploration

[Harumpel]

Hi ihr,

ich habe einen (sehr theoretischen) Algorithmus zur Raumexploration für mobile Roboter geschrieben und würde ihn gerne mit was vergleichbarem messen.

Weiss einer einen Algorithmus zur Exploration von unbekannten Räumen? Sowas wie SLAM?

Schönen Gruß
Harumpel

[vohopri]

Hi du,

ich hab mich nicht damit beschäftigt, weil ich in bekannten Räumen navigiere, aber ich meine, dass ich da im Forum schon was gesehen habe. Schau mal in die Suche.

grüsse,
Hannes

[Ceos]

Pledge-Algorithmus

mein persönlicher favorit

[i_make_it]

Pledge ist eigentlich nur für Labyrinthe gut.
Also nur für einen speziellen Fall eines unbekannten Raumes.

Bei unbekannten Räumen unbekannter Ausdehnung und Geometrie wird das etwas schwieriger.

Wenn es sich um Räume in einem Gebäude handelt, kann man eine Abwandlung vom Pledge benutzen.

Ich habe die erste Wand gesucht und bin dieser im Uhrzeigersinn gefolgt.
Bei einer zurückspringenden Ecke, bin ich mindestens 1,2 Meter der Ausrichtung der ursprünglichen Wand gefolgt um Türöffnungen zu überspringen. (Annahme das eine Tür nie breiter als 100cm ist)
Bei vorspringenden Ecken folge ich der Wand.
So bekommt man ein Rechteck oder eine Spirale. (Bedingt durch Möbel oder weil man tatsächlich in einem Labyrinth ist)
1-
Im Falle eines Rechteckes habe ich die Fläche dann ausgerastert um Hindernisse im Raum mit zu erfassen.

2- Im Falle einer Spirale bekommt man irgendwann ein "U" und dann eine zurückspringende Kante.
Womit dann zwangsläufig ein kleines Rechteck entsteht und Fall 1 gilt.
Bei der Kartierung benutze ich drei Zustände für die Karte.
A-unerforscht
B-frei
C-blockiert
Wobei ich C noch mit einem Timestamp versehe, so können zeitweise Sperrungen durch bewegliche Objekte später erkannt werden.

Die Karte baue ich erst als Rasterkarte mit einer Punktgröße von 1/4 des Roboters auf.
est Später wandele ich das in Vektorkaten um, damit der Speicherbedarf sinkt.

3- Bei Allen Stellen wo man bei der Erkundung an einer unerforschten Stelle vorbei kommt, fahre ich die linke zurückspringende Ecke an und folge dieser Kante dann wieder nach dem ursprünglichen Prinzip.
Also Uhrzeigersinn, zurückspringende Ecken 1,2m überfahren und vorspringenden Ecken folgen.

4- Beim Fall das bei einer zurücksringenden Ecke nach 1,2m keine Wand kommt, fahre ich zurück und behandle nach Fall 3.

Damit habe ich bisher jedes Gebäude vollständig kartieren können.

Mittlerweile habe ich das ganze dahingehend erweitert, das meine Fernsensoren bei einer durchschnittlichen Schranktiefe von 60cm ja die Wand nach dem Ende einer Schrankfront links sehen können.
Somit habe ich in der Karte zwei weitere Zustände eingeführt für vermutlich frei und vermutlich blockiert.

Bereiche die diese Stati haben, werden zuerst kartiert bevor es an Bereiche geht die den Status unerforscht haben.
Das erhöht die Chance einer vollständigen Erforschung eines Raumes bevor es an den nnächsten geht.

Beim widerholten Abfahren der Räume (ausrastern) erhebe ich die genauen Maße für die spätere Vektorkarte.

In Zukunft plane ich die Vekorkarte schon von Beginn an parallel zur Rasterkarte aufzubauen und die Ecken als Landmarken und Verknüpfungen zwichen beiden Karten zu nehmen.

Auf lange sicht möchte ich dann komplett weg von der Rasterkarte.
Aber für die erste Visualisierung am PC war die einfach schneller und einfacher realisiert.

Die Wahl ob Uhrzeigersinn oder Gegenuhrzeigersinn, ist eigentlich willkürlich.

[Netzman]

Wie wandelst du die Rasterdaten in Vektoren um?

mfg

[i_make_it]

Winkelfunktionen!

Jeder Rasterpunkt ist ja ein Quadrat definierter Kantenlänge.
Ich nehme die "Landmarken" (Ecken) und umschließe so Rasterpunkte mit dem Status "blockiert".
Da die Maße so ziemlich ungenau sind, messe ich beim Abrastern (streifenweises Abfahren) der Flächen noch mal nach und bekomme so exakte maße.

Ich weis das ist nicht optimal. Ist halt historisch gewachsen. Soll ja auch noch besser werden.

[Netzman]

Du umschließt also im Prinzip größere Ansammlungen von blockierten Zellen mit einem Rechteck?

mfg