Algorithmus zur Lokalisation auf einem Fussballfeld gesucht

Hallo zusammen,

sorry, dass ich Eure umfangreichen Beiträge noch nicht gewürdigt habe !!! In dieser Woche fehlt ein wenig Zeit ...

Danke für die Überlegungen an @mare_crisium, da brauche ich glaube ich ein paar Stunden um das ganze zu durchschauen ... spätestens am Wochenende bin ich wieder da, wahrscheinlich mit einer Handvoll Fragen. Die Mehrdeutigkeit der Lösung ist mir, zumal sehr anschaulich von Dir geschildert schon klar, ich möchte dieses Problem gern durch ein Tracken der Position aus einer definierten Inertialposition heraus lösen.

Dazu passt auch der Hinweis von @rossir wenn ich anhand der Odometrie schon eine Positionsschätzung habe, brauche ich nicht alle möglichen Positionen des Spielfeldes abzusuchen sondern nur das engere Umfeld !!!

Grüße

Sebastian

Hallo zusammen,

ok, da habe ich wieder losgebastelt ohne vorher zu überlegen. Bisher war ich völlig auf 3 gleichverteilte Sensoren am Roboter eingeschossen, dass man mit denen unter Umständen gar keine (auch mit Richtungswissen) Aussage zur Position treffen kann, ist mir erst anhand der Kartoffelscheiben Darstellung von @mare_crisium klar geworden.

Also habe ich mich jetzt erst mal damit beschäftigt herauszufinden, wie viele Sensoren ich eigentlich am Roboter brauche, um mich in allen Position auf dem Tisch zu recht zu finden. Klar, wenn ich nur Sensoren mit einer geringen Reichweite habe, nützt der mir in der Mitte des Tisches nichts, kann am Rand aber noch ganz brauchbare Ergebnisse liefern.

Ich habe einen Simulator geschrieben und für bis zu 10 Sensoren mit einer Reichweite von 1cm bis zur Tischdiagonalen die Frage testet - Siehe Gesamtübersicht.pdf . Ich untersuche für jeden Eintrag in der Matrix (1 cm als Auflösung) jede Orientierung des Roboters darauf, ob eine hinreichende Zahl von Messwerten besteht um eine Lokalisierung auszuführen.
Interessant ist, dass man offenbar mindestens 6 Sensoren braucht um sich bei dieser Tischkonfiguration (122 x 188) zurecht zu finden.

Um das Ganze etwas zu illustrieren zwei Bilder unterschiedlicher Reichweiten mit 3 und 6 Sensoren ... wobei die Reichweite (85cm) auch für 6 Sensoren noch nicht ganz ausreicht, um sich auf dem ganzen Tisch lokalisieren zu können. (0 bedeutet, dass in keiner Richtung eine korrekte Positionierung möglich ist, 1 sagt hier funktioniert die Lokalisierung in allen Richtungen)


Soweit so gut ... Was meint Ihr, ist die gleichverteilte Anordnung der Sensoren zu nicht zu toppen oder bekommt man mit unsymetrischer Verteilung unter Umständen eine Positionierung mit geringerer Reichweite hin? Das Problem ist die Performance meiner Simulation. Um alle in 8 Sensorkonfigurationen aus der Gesamtdarstellung durchzuspielen hat mein Rechner über eine Stunde gebraucht :-(

Grüße und einen schönen Sonntag noch

Sebastian

Irgendeine Voraussetzung Deiner Simulation verschweigst Du oder verstehe ich nicht.


Hier zwei Gegenbeispiele:
Kein Roboter (auch mit 1000 Lasersensoren (symetrisch oder asymetrisch angeordnet) die jeweils unendliche Reichweite hätten) kann zwischen den folgenden Positionen (x, y, a) unterscheiden:
Gegenbeispiel 1
(10, 10, 180) und (112, 178, 0)

Gegenbeispiel 2
(61, 94, 0) und (61, 94, 180)

Allgemein:
Die Laserlokalisation allein hilft nicht um zwischen einer Position und der punktgespiegelten Position zu unterscheiden.

D.h. bei Deiner Untersuchung dürfte höchsten der Wert 0.5 (statt 1.0) raus kommen.

Das mit der 1cm Auflösung Deiner Matrix verstehe ich zwar aber Du sagst nichts zur Auflösung der untersuchten Roboterblickrichtungen.

Ok, das habe ich nicht richtig deutlich gemacht ... Ich gehe zunächst noch davon aus, dass ich eine fehlerfreie Schätzung der Orientierung des Roboters habe. In der nächsten Stufe baue ich dann ein Modell zur Ableitung der Orientierung aus der Odometrie ein. Dann muss ich mir entsprechend einen Kopf machen, wie man die Ungenauigkeiten gegeneinander abwägt damit das Ganze über der Zeit nicht aus dem Ruder läuft.

Die Auflösung des Winkels beträgt ein Grad.

Grüße

Sebastian

Du hälst also nichts von der MonteCarlo Localisation Variante (siehe weiter oben)?

Ich frage, weil ich selbst einen Roboter plane der sich mit drei IR-Distanzsensoren in einem 3m x 3m Feld zurecht finden soll. Auch mit dem Problem der Schätzung der Position über längere Zeitspannen.

@rossir

Welche Sensoren schweben Dir da vor? Wenn ich mir die Ergebnisse der Simulation anschaue, kann ich selbst bei optimaler Schätzung der Orientierung mit 3 Sensoren keine Positionierung in jedem Punkt gewährleisten. Oder brauchst Du das gar nicht, sondern genügt eine Prüfung der Positionsschätzung von Zeit zu Zeit.

Ich denke die Dein Ansatz zur Monte Carlo Localisation ist gut geeignet um die Positionsschätzung mit der Richungsschätzung zu verschmelzen. In mehreren Iterationen kann man ausgehend von der Berechnung anhand der Odometrie immer wieder die Richtung anhand der Berechneten Postion verfeinern. Hast Du ein Paper dazu, dass man rasch mal überfliegen kann?

Kann mir jemand eine Tipp geben, in welchem Buch oder wissenschaftlichen Paper sich schon mal jemand mit der Frage "Wieviele Distanzsensoren brauche ich für die Lokalisierung" auseinander gesetzt hat?

Tausend Dank wie immer

@Sebastian,

die Frage, wieviel Sensoren und welche, stellt sich erst, nachdem die Frage nach dem Algorithmus beantwortet ist ;-). In diesem Sinne: Guck' doch mal hier:

http://www.allpsych.uni-giessen.de/d...s/particle.pdf

Die Suchwort-Kombination "+Kalman+Partikelfilter" liefert reiche Beute; u.a. hinsichtlich Monte-Carlo-Verfahren (@rossir ;-) )!

Eine Alternative könnten ortsfeste Navigationsbaken sein. Die Ortsberechnung aus den Peilrichtungen bzw. Peilrichtungen und Entfernungen ist klar. Für die Aufgabe, die Baken aufzufinden ;-) und zu identifizieren, müsste man eine geeignete Methode aussuchen.

Ciao,

mare_crisium

Ich möchte den IR Sensor GP2Y0A02YK nutzen.

Zur Anzahl der Lasersensoren habe ich keine Lösung, aber folgende Überlegung anzubieten.
Wenn der Roboter sich nicht drehen kann, dann reichen zwei Lasersensoren um den Ort genau zu bestimmen:
Einer der senkrecht auf die Längsseite des Spielfeldes (x-Achse) zeigt und
ein anderer (um genau 90 Grad versetzt) der senkrecht auf die Kurzseite (y-Achse) zeigt.

Ich denke, Allgemein wird gelten: Nur wenn ein Laser die x-Achse trifft und (irgend) ein anderer Laser die y-Achse trifft kann ich die Position bestimmen.

Jetzt lautet die Frage: Wieviel Laser brauche ich, damit immer einer davon die x-Achse trifft und irgend ein anderer die y-Achse trifft. Selbst dann, wenn der Teufel den Roboter auf dem Spielfeld positioniert und ausrichtet.

Der Teufel hat auf der Mittellinie gute Chancen den Roboter so zu drehen, dass kein Laser auf eine der beiden Kurzseiten trifft. Am Mittelpunkt selbst ist die Chance am größten.

Der Winkel zwischen dem Mittelpunkt (61, 94) und zwei benachbarten kurzen Ecken (0,0) und (0, 122) ist
2*acos(94/(sqrt(94*94+61*61)))
Das sind ca. 66 Grad.

D.h. man braucht 6 Laser (360/6=60) damit der Teufel keine Chance hat. Die kann man ruhig asymetrisch anbringen, solange zwischen Nachbarn nirgends mehr als 66 Grad entstehen.

@Sebastian und @rossir,

es müsste doch mit dem Teufel zugehen, wenn man das nicht auch ausrechnen kann :-) . Für den Fall mit vier Sensoren und eine der möglichen Situationen bin ich nahe daran, eine Lösung auszurechnen. Der letzte Schritt fehlt noch, aber das scheint mir nur noch eine Frage der Ausdauer zu sein...

Ciao,

mare_crisium

EDIT: Anhang gelöscht: Der Ansatz im Posting vom 18.05. ist viel besser.

Nimm doch einfach Drei Sensoren und lagerst die drehbar(servo).Du wertest einfach das Abstandssignal aus, merkst dir den Winkel.Dann zeichnest du Drei virtuelle Kreise am Schnittpunkt von allen ist dann der Roboter.(du musst natürlich auch noch die positionen dar Sensoren auf deinem Roboter mit einbeziehen).