Partikelfilter

Eine eher technische Behandlung dieses Blogbeitrags wurde ursprünglich im Udacity-Blog veröffentlicht .

Roboter verwenden einen überraschend einfachen, aber leistungsstarken Algorithmus, um herauszufinden, wo sie sich auf einer Karte befinden, ein Problem, das von Ingenieuren als Lokalisierung bezeichnet wird. Der als Partikelfilterung bekannte Algorithmus sieht erstaunlich cool aus. Der erste Teil dieses zweiteiligen Artikels wurde hier veröffentlicht . In diesem ersten Artikel erläutern wir die Mathematik, die zum Bau eigener Partikelfilter erforderlich ist.

Selbstfahrende Autos sind so konzipiert, dass sie sich ähnlich wie menschliche Fahrer verhalten. Ein typisches selbstfahrendes Fahrzeugsystem besteht aus sechs Komponenten. Jede der sechs Komponenten löst ein kritisches Problem, das zum autonomen oder anderweitigen Fahren benötigt wird. Man kann sich vorstellen, dass die Komponenten die Funktionen ausführen, die menschliche Fahrer nachahmen, nämlich:

Lokalisierung : Wo sind wir?
Routenplanung : Wie kommen wir ans Ziel?
Wahrnehmung : Was gibt es sonst noch in der Umgebung?
Prognose : Wie wird das Umfeld wenig später aussehen?
Planung : Welchen Kurs verfolgen wir in den nächsten Sekunden?
Kontrolle : Wie werden wir den Kurs verfolgen, den wir wollen?

Die Lokalisierung für Menschen ist in der Regel sehr einfach. Wir erinnern uns normalerweise aus dem Gedächtnis, wo wir uns auf der Welt befinden, oft unterstützt durch ein GPS-Gerät wie ein Smartphone, das uns hilft, unseren Standort auf einer Karte viel genauer zu bestimmen. Wir verwenden auch visuelle Hinweise wie Navigationszeichen, Fahrspurmarkierungen und unser Verständnis von anderen Fahrzeugen, der Straße und der Umgebung, um sicherzustellen, dass wir immer auf der richtigen Spur, auf der richtigen Straße und in die richtige Richtung fahren.

Für die Lokalisierung benötigt das autonome Fahren auch die Position und die Richtung, in die sich das Fahrzeug bewegt, auch Heading genannt. Im Gegensatz zum Menschen ist der Präzisionsbedarf autonomer Fahrzeuge jedoch sehr hoch. Es reicht nicht aus, nur zu wissen, dass sich ein Fahrzeug auf der rechten Spur befindet und parallel zur Spur fährt. Bei der Planung ist höchste Präzision gefragt. Wenn die Lokalisierung um mehr als ein paar Zentimeter von der Position oder um mehr als ein paar Grad von der Richtung abweicht, kann die Planungskomponente einen katastrophalen Kurs erzeugen, der neben vielen anderen unerwünschten Ergebnissen zu einer Kollision führt.

Wie Menschen erhalten auch autonome Fahrzeuge ihre erste Schätzung der Position und Fahrtrichtung von einem GPS. GPS-Empfänger, selbst die winzigen auf einem Smartphone, neigen dazu, ziemlich genau zu sein. Die Genauigkeit der von einem GPS empfangenen Lokalisierungsinformationen ist jedoch für ein sicheres autonomes Fahren unzureichend . Beispielsweise kann die gemeldete Position von einem Meter bis zu mehreren Metern oder im schlimmsten Fall sogar noch mehr abweichen.

Die Genauigkeit schwankt häufig und stark in Abhängigkeit von Faktoren wie der Anzahl der für den Empfänger sichtbaren Satelliten, Reflexionen von Satellitenstrahlen von großen Objekten wie Gebäuden und Absorption durch atmosphärische Elemente.

Wenn das nicht schlimm genug ist, ist die Rate, mit der GPS die Lokalisierungsinformationen aktualisiert, auch ziemlich langsam und liegt zwischen 1 und 10 Hz. Selbst bei 10 Hz hätte sich ein Fahrzeug, das sich mit verspäteten 20 km/h bewegt, zwischen zwei GPS-Updates etwa einen halben Meter bewegt.

Um die Unsicherheit bei der Lokalisierung aufgrund von Bewegung zu mindern, verwenden autonome Fahrzeuge Trägheitsmesseinheiten (IMUs). IMUs sind schnell und genau und messen die Beschleunigung und Wendegeschwindigkeit eines Fahrzeugs. Diese Informationen können dann verwendet werden, um die Position des Autos zwischen zwei aufeinanderfolgenden GPS-Aktualisierungen zu ermitteln. IMUs neigen dazu, im Laufe der Zeit kleine Näherungsfehler zu akkumulieren, aber das ist nicht das Problem, mit dem wir uns hier befassen.

Das Kernproblem, mit dem das Lokalisierungssystem zu kämpfen hat, besteht darin, dass die GPS-Updates von Natur aus ungenau sind. Anstatt beispielsweise eine genaue Position zu melden, meldet das GPS einen kleinen Bereich auf dem Boden, wo sich wahrscheinlich ein Fahrzeug befindet, wenn sich das GPS selbst aktualisiert. Wir bezeichnen diesen Bereich als GPS-Spot.

Das Problem der Durchführung einer genauen Lokalisierung reduziert sich auf das Problem der Verringerung der Fläche des GPS-Spots.

Eine der Techniken, die in der Robotik zur genauen Lokalisierung verwendet wurden, ausgehend von einer weniger genauen, ist als Partikelfilterung bekannt . Es ist nützlich, wenn die Umgebung eine Reihe von Orientierungspunkten aufweist, d. h. große, stationäre Objekte, die Ort, Aussehen und Größe nicht häufig ändern. Dies können Gebäude, Mobilfunkmasten, Brückenpfeiler, Strommasten oder Verkehrssignale und Beschilderungen sein.

Um zu verstehen, wie Partikelfilterungen durchgeführt werden, verwenden wir eine Analogie. Angenommen, Sie kommen müde in ein Hotelzimmer zurück, schalten das Licht aus und fallen mit dem Gesicht nach unten ins Bett. Sie wachen mitten in der Nacht auf und wollen wissen, wo Sie sind. Natürlich erinnern Sie sich, wie Sie ins Bett gekracht sind, aber Sie möchten wissen, in welche Richtung Sie schauen, wo die Lichtschalter sind und wo Ihre Hausschuhe sind. Dies erfordert mehr Genauigkeit als eine schwache Erinnerung daran, im Bett zu liegen.

Zur schnellen Orientierung nutzt man die Umgebung. Sie stellen sich zuerst an verschiedenen Stellen auf dem Bett vor. Dann erfühlst du die „Wahrzeichen“-Objekte in der Umgebung, indem du sie berührst und identifizierst. Du könntest eine Wasserflasche von einem Tisch in der Nähe stoßen oder deinen Zeh gegen einen Stuhl stoßen. Diese Beobachtungen geben Ihnen wichtige Hinweise darauf, wo Sie sich wahrscheinlich im Bereich des Hotelbettes aufhalten werden. Da Sie sich daran erinnern, wo sich die Flasche, der Tisch und der Stuhl relativ zum Bett befanden, können Sie Ihre Position auf dem Bett genauer ableiten. Mit jeder neuen Beobachtung können Sie bestimmte Orte auf dem Bett ausschließen und Ihre Chancen erhöhen, an anderen Orten zu sein.

Genau so funktioniert die Partikelfilterung für autonome Fahrzeuge. Ausgestattet mit einem anfänglichen GPS-Spot kennt das Fahrzeug seine ungefähre Position und Richtung auf der Karte. Diese grobe Position wird dann in kleine imaginäre Zellen unterteilt. Das Fahrzeug weiß auch, welche Orientierungspunkte sich in der Nähe dieses groben Ortes befinden. Das Fahrzeug prüft dann die Entfernung zu diesen Orientierungspunkten mit einem bordeigenen Lidar. Das Lokalisierungssystem vergleicht dann diese Messungen mit jeder imaginären Zelle. Da immer mehr Orientierungspunkte untersucht werden, werden die meisten Zellen ausgeschlossen und nur wenige sehr wahrscheinliche bleiben als wahrscheinliche Orte übrig.

Der Name Partikelfilterung kommt von der Tatsache, dass die Position jeder imaginären Zelle als Partikel auf der Karte dargestellt wird und wir Partikel ausschließen, indem wir sie filtern, indem wir Entfernungen zu Orientierungspunkten berechnen und Partikel verwerfen, die nicht die richtige Entfernung zu haben scheinen die Wahrzeichen.

Die folgende Animation zeigt die anfängliche Position der Partikel, die sich über eine beträchtliche Fläche erstrecken, die über mehrere Fahrspuren, Straßen und offene Flächen verteilt sein könnte. Das Erfassen oder Sondieren der Umgebung wird durch blaue Strahlen dargestellt. Der grüne Punkt, der die wahrscheinlichste Position darstellt, springt zunächst auf der Karte herum, beruhigt sich aber sehr schnell, da immer mehr Partikel durch die Erfassung der Umgebung ausgeschlossen werden.

Die Partikelfilterung ist ein unglaublich einfacher Algorithmus, der viele Roboter und autonome Autos antreibt. Nvidia Drive Labs hat ein kurzes Video darüber veröffentlicht, wie die Lokalisierung von reichhaltigen Karten mit einer Vielzahl von Orientierungspunkten profitieren kann. Uber ATG hat hier einen Blog darüber veröffentlicht, wie sie die GPS-Genauigkeit verbessern .