Lokalisierung nach Markov bzw. Monte-Carlo

Hallo!

Würde gerne meinen Bot eine Lokalisierung nach Markov spendieren. Hat das schon mal jemand umgesetzt?
Welche und wie viele Sensoren sind dafür nötig um eine gute (+/- 10cm in Räumen - 200qm verteilt auf 4 Räume) Genauigkeit zu erreichen?

Derzeit mache ich meine Positionsbestimmung über Wegstreckenberechnung. Diese hat den Nachteil, dass sich die Fehler aufrechnen. D.h. wenn ich im letzten Raum bin, kommen schon Abweichungen von bis zu einem Meter zusammen (je nachdem wie oft mein Bot ungeplant ausweichen muss).

Aktueller Aufbau: Arduino Mega, zwei IR Sensoren, einen US Sensor auf einem Servo, Kompass, G-Sensor und, zwar schon vorhanden aber nicht eingebunden, die Kinect.
Notebook (Core i7 mit genug Speed und Speicher ;))


LG, Arno

OK - anscheinend gibt es keine Fans von Markov ;)

Anders gefragt, wie setzte Ihr die Lokalisierung Eurer Bot´s um?

LG, Arno

Stichwort is naturlich odometrie. Das ist relatif genau, aber abhangig von fiele randbedingungen. Wichtige Einfluss factoren :
Auflosung encoder, Rundlauf Rader, Schlag Rader, Abstand zwischen Rader, Material Boden und Rader usw. Mit meine Roboter habe ich relatif gute Erfahrungen mit odometrie, aber eine Korrectur auf bestimmte Zeitpunkten schein mir notwendig (Kalman Filter). In Anhang eine Graphic von eine Strecke die der Robby gefahren hat mit Linienfolgen. Sie sehen dan nach eine Runde die Abweichung nog relatif klein ist.
Anhang 21309

Ich hab die Monte Carlo Methode nicht ganz durchschaut, um ehrlich zu sein. Müsste dazu und zu den Partikel/Kalman Filtern mal ein besseres Beispiel als bei Wikipedia sehen um es umsetzen zu können.

Mein derzeitiger Plan ist meinen Robi mit US Sensoren auszustatten und die Position über Template Matching zu ermitteln. Eine Rasterkarte ist ja schon vorhanden, und es gibt noch genug Speicher um deren Auflösung zu verbessern. Ist so primitiv dass man es in einem Atmega1284 berechnen kann. Hab diese Methode aber erst am Papier und Excel überprüft, und es wird noch länger dauern bis ich es am Robi umsetzen kann.

LG!

Ich mach das etwas anders (bescheidener). Denn GATTACA bewegt sich auch nur in einer definierten Spielarena von ca. 3m * 3m mit glatten Wänden. Ich habe die Odometrie und zwei Distanzsensoren auf dem Roboter die in einem deutlichen (und bekanntem) Winkel zueinander stehen. Durch die Odometrie habe ich (inkrementell) die Positionswerte (x, y, a), durch die Distanzsensoren habe ich Distanzwerte (Da, Db) zu Wänden.

a) Zu Beginn setze ich den Roboter an eine definierte Stelle in die Arena. Dadurch sind (x0, y0, a0, Da0, Db0) bekannt und die Odometrie initialisiert sich mit (x0, y0, a0).

b) Nach kurzer Fahrzeit dt entstehen fünf neue Werte (x1, y1, a1, Da1, Db1). Die sind aber (systembedingt) ungenau (fehlerbehaftet). Durch die systembedingten Fehler passen sie auch nicht unbedingt gut zueinander. Theoretisch sollten sie aber zueinander passen, denn zwischen (x1, y1, a1) einerseits und (Da1, Db1) andererseits sollte es (bei bekannter Spielarena) immer einen mathematischen Zusammenhang geben. Ist der durch die realen Werte nicht gegeben, gibt es einen inneren Fehler.

c) Jetzt kommt Monte Carlo ins Spiel: In der Nähe des aktuellen Vektor (x1, y1, a1, Da1, Db1) rate ich zufällige andere Vektoren (xi, yi, ai, Dai, Dbi). Wenn man so will, entsteht dadurch um (x1, y1, a1, Da1, Db1) eine kleine Vektor- bzw. Partikel-Wolke. Jeder Vektor hat seinen eigenen inneren Fehler zwischen (xi, yi, ai) und (Dai, Dbi). Habe ich genügend Vektoren geraten wähle ich natürlich den mit dem kleinsten inneren Fehler zum Gewinner. Diesem "vertraue" ich am meisten und erkläre ihn zu meinem neuen Vektor (xg, yg, ag, Dag Dbg). Bemerkung: g steht für Gewinner. Daraus nimmt und initialisiert sich die Odometrie auf die Werte (xg, yg, ag) und das Spiel geht bei b) weiter.

Hier ein Video:
http://www.youtube.com/watch?v=-CyXC...er&list=UL
Der linke Teil des Bildes wurde nachträglich aus Logdaten berechnet und visualisiert:
Hellgrau die Position des Roboters ohne Monte Carlo.
Dunkelgrau die Position des Roboters mit Monte Carlo.

Danke für die Erklärung, jetzt wird mir einiges klar! Bild hier  
Aber wäre es nicht auch möglich aus Da1, Db1 direkt x1 und y1 zu berechnen?

LG!

Glaube der Grund ist, dass beide Messungen fehlerbehaftet sind. Anstatt aufwändig den Punkt mit der geringsten Fehlerwahrscheinlichkeit zu errechnen (unter Umständen gibt es ja sogar viele Lösungen) werden einfach einige Punkte zufällig ausgewählt und der Beste davon ausgesucht. Scheinbar funktioniert das richtig gut.

mfG
Markus

@damfino
Oh, da ist was schief gelaufen,
an Deiner Antwort merke ich gerade, dass ich ganz schlecht erklärt habe, weil ich wohl nicht klar machen konnte, dass Da1 und Db1 natürlich auch fehlerbehaftet sind. Und deshalb nicht als stabile Grundlage zur Berechnung von (x1, y1, a1) taugen.

Tut mir leid.

Alles hat systembedingte Fehler: x1, y1, a1, Da1 und Db1. Ist es jetzt klarer?

Konkret nutze ich zwei GP2Y0A02YK. Die liefern nur ungefähre Distanz. Insbesondere läßt die Genauigkeit bei höherem Abstand nach. Darüber hinaus habe ich mit Reflexionen (besonders in den Ecken), Gegenlicht, Blitzlicht, schräger Draufsicht auf die Wände etc. zu kämpfen.