Filtry cząstek stałych

Bardziej techniczne podejście do tego posta zostało pierwotnie opublikowane na blogu Udacity .

Roboty używają zaskakująco prostego, ale potężnego algorytmu, aby dowiedzieć się, gdzie się znajdują na mapie, co inżynierowie nazywają lokalizacją. Algorytm znany jako filtrowanie cząstek wygląda niesamowicie fajnie. Pierwsza część tego dwuczęściowego artykułu została opublikowana tutaj . W tym pierwszym artykule wyjaśnimy matematykę potrzebną do zbudowania własnych filtrów cząstek stałych.

Samochody samojezdne są zaprojektowane tak, aby zachowywały się podobnie jak ludzie. Typowy system samojezdnego samochodu składa się z sześciu elementów. Każdy z sześciu komponentów rozwiązuje krytyczny problem potrzebny do jazdy autonomicznej lub innej. Komponenty można traktować jako wykonujące funkcje naśladujące ludzkich kierowców, którymi są:

Lokalizacja : Gdzie jesteśmy?
Planowanie trasy : Jak dotrzemy do celu?
Percepcja : Co jeszcze jest w okolicy?
Prognoza : Jak środowisko będzie wyglądać nieco później?
Planowanie : Jaki kurs obierzemy w ciągu najbliższych kilku sekund?
Kontrola : Jak mamy podążać kursem, który chcemy?

Lokalizacja dla ludzi wydaje się być bardzo łatwa. Zwykle przypominamy sobie z pamięci, gdzie się znajdujemy na świecie, często wspomagane przez urządzenie GPS, takie jak smartfon, które pomaga nam znacznie dokładniej określić naszą lokalizację na mapie. Korzystamy również ze wskazówek wizualnych, takich jak znaki nawigacyjne, oznaczenia pasów ruchu, a także z naszego rozumienia innych pojazdów, drogi i otoczenia, aby upewnić się, że zawsze znajdujemy się na właściwym pasie, na właściwej drodze i zmierzamy we właściwym kierunku.

Jeśli chodzi o lokalizację, autonomiczna jazda wymaga również pozycji i kierunku, w którym porusza się pojazd, zwanego też kursem. Jednak w przeciwieństwie do ludzi poziom precyzji wymagany od pojazdów autonomicznych jest bardzo wysoki. Nie wystarczy po prostu wiedzieć, że pojazd znajduje się na prawym pasie i jedzie równolegle do pasa. Do planowania potrzebna jest duża precyzja. Jeśli lokalizacja jest przesunięta o więcej niż kilka centymetrów w stosunku do pozycji lub o więcej niż kilka stopni w stosunku do kursu, komponent planowania może wygenerować katastrofalny kurs, powodując kolizję z wieloma innymi niepożądanymi rezultatami.

Podobnie jak ludzie, pojazdy autonomiczne uzyskują pierwsze oszacowanie pozycji i kierunku z GPS. Odbiorniki GPS, nawet te maleńkie, które można znaleźć w smartfonie, są dość dokładne. Jednak precyzja informacji o lokalizacji otrzymanych z GPS jest niewystarczająca do bezpiecznej autonomicznej jazdy. Na przykład zgłoszona pozycja może różnić się od jednego do kilku metrów, aw najgorszym przypadku nawet o więcej.

Precyzja zmienia się często i gwałtownie w zależności od czynników, takich jak liczba satelitów widocznych dla odbiornika, odbicia wiązek satelitarnych od dużych obiektów, takich jak budynki, oraz pochłanianie przez elementy atmosferyczne.

Jeśli to nie wystarczy, szybkość, z jaką GPS aktualizuje informacje o lokalizacji, jest również dość powolna, w zakresie od 1 do 10 Hz. Nawet przy częstotliwości 10 Hz pojazd poruszający się z opóźnieniem 20 km/h przemieściłby się o około pół metra między dwiema aktualizacjami GPS.

Aby złagodzić niepewność lokalizacji spowodowaną ruchem, pojazdy autonomiczne wykorzystują inercyjne jednostki pomiarowe (IMU). Jednostki IMU są szybkie i dokładne oraz mierzą przyspieszenie i prędkość skrętu pojazdu. Informacje te można następnie wykorzystać do ustalenia pozycji samochodu między dwiema kolejnymi aktualizacjami GPS. IMU mają tendencję do gromadzenia małych błędów aproksymacji w czasie, ale nie jest to problem, z którym mamy tutaj do czynienia.

Podstawowym problemem, z którym musi borykać się system lokalizacyjny, jest to, że aktualizacje GPS są z natury niedokładne. Na przykład zamiast zgłaszać dokładną pozycję, GPS zgłasza niewielki obszar na ziemi, na którym prawdopodobnie znajduje się pojazd, gdy GPS sam się aktualizuje. Nazywamy ten obszar punktem GPS.

Problem wykonania dokładnej lokalizacji sprowadza się do problemu zmniejszenia powierzchni punktu GPS.

Jedna z technik stosowanych w robotyce do dokładnej lokalizacji, zaczynając od mniej dokładnej, jest znana jako filtrowanie cząstek . Jest to przydatne, gdy w środowisku występuje wiele punktów orientacyjnych, czyli dużych, nieruchomych obiektów, które rzadko zmieniają położenie, wygląd i rozmiar. Mogą to być budynki, wieże telefonii komórkowej, filary mostów, słupy energetyczne lub sygnalizacja świetlna i oznakowanie.

Aby zrozumieć sposób filtrowania cząstek, użyjemy analogii. Załóżmy, że wracasz zmęczony do pokoju hotelowego, wyłączasz światła i kładziesz się twarzą do łóżka. Budzisz się w środku nocy i chcesz wiedzieć, gdzie jesteś. Oczywiście pamiętasz, jak wpadłeś na łóżko, ale chciałbyś wiedzieć, w którą stronę patrzysz, gdzie są włączniki światła i gdzie są twoje kapcie. Wymaga to większej dokładności niż słabe wspomnienie bycia w łóżku.

Aby szybko się zorientować, korzystasz z otoczenia. Najpierw wyobrażasz sobie siebie w różnych miejscach na łóżku. Następnie wyczuwasz „punkty orientacyjne” w otoczeniu, dotykając ich i identyfikując. Możesz zepchnąć butelkę wody z pobliskiego stołu lub uderzyć się palcem o krzesło. Te obserwacje dostarczają ważnych wskazówek na temat tego, gdzie prawdopodobnie znajdziesz się w królestwie hotelowego łóżka. Ponieważ pamiętasz położenie butelki, stołu i krzesła względem łóżka, możesz dokładniej określić swoją pozycję na łóżku. Z każdą nową obserwacją możesz wykluczyć pewne miejsca na łóżku i zwiększyć swoje szanse na przebywanie w innych miejscach.

Dokładnie tak działa filtrowanie cząstek stałych w pojazdach autonomicznych. Uzbrojony w początkowy punkt GPS, pojazd zna przybliżoną pozycję i kierunek na mapie. Ta przybliżona pozycja jest następnie dzielona na małe wyimaginowane komórki. Pojazd wie również, jakie punkty orientacyjne znajdują się w pobliżu tego przybliżonego miejsca. Następnie pojazd bada odległość do tych punktów orientacyjnych za pomocą pokładowego lidaru. Następnie system lokalizacji porównuje te pomiary z każdą wyimaginowaną komórką. W miarę sondowania coraz większej liczby punktów orientacyjnych większość komórek zostaje wykluczona, a tylko kilka wysoce prawdopodobnych pozostaje jako prawdopodobne lokalizacje.

Nazwa filtrowanie cząstek pochodzi od faktu, że lokalizacja każdej wyimaginowanej komórki jest reprezentowana na mapie przez cząstkę, a my wykluczamy cząsteczki, filtrując je, obliczając odległości do punktów orientacyjnych i odrzucając cząsteczki, które nie wydają się być w odpowiedniej odległości od punkty orientacyjne.

Poniższa animacja pokazuje początkową lokalizację cząstek na sporym obszarze, który można rozłożyć na kilka pasów ruchu, dróg i otwartych przestrzeni. Wykrywanie lub sondowanie środowiska jest pokazane przez niebieskie promienie. Zielona kropka przedstawiająca najbardziej prawdopodobną pozycję początkowo przeskakuje po mapie, ale ustala się bardzo szybko, ponieważ coraz więcej cząstek jest wykluczanych przez wykrywanie środowiska.

Filtrowanie cząstek stałych to niezwykle prosty algorytm, który napędza wiele robotów i autonomicznych samochodów. Nvidia Drive Labs opublikowało krótki film o tym, jak lokalizacja może skorzystać z bogatych map z różnymi punktami orientacyjnymi. Uber ATG opublikował tutaj blog o tym, jak poprawiają dokładność GPS .