SLAM: jednoczesne lokalizowanie i tworzenie mapy

Problem kurczaka i jajca

Robot wpadnięty w nieznane przestrzenie z jedynym nozdrzywym lidarem i odmetryczką kółkową napotkuje na cykliczne zależności: aby wiedzieć, gdzie się znajduje, potrzebuje dokładnej mapy; aby stworzyć dokładną mapę, musi wiedzieć dokładnie, gdzie stał się, gdy zabrał każdy skan. jednoczesne lokalizowanie i tworzenie mapy rozwiązuje to jednocześnie, traktując je jako jedno wspólne estymacyjne zadanie zamiast dwóch sekwencyjnych — ta symulacja uruchamia rzeczywisty filtr cząstek dla pół lokalizacji i bayesowską siatkę zajętościowa dla pół mapowania, aktualizując je wzajemnie na każdym kroku.

Lokalizacja: filtry cząsteczkowe

Filter cząsteczkowy (lub Monte Carlo Localization) reprezentuje przekonanie robota o swoim położeniu — nie jako jedno liczbę, ale jako chmura tysięcy hipotez ważonych, każda z nich jest kandydatem (x, y, theta). Każde kroku wykonuje trzy fazy:

1. przewidywanie: przesuń każdą cząstkę o czytnik odometrii + szum 2. aktualizacja: ocena każdej cząstki na podstawie tożsamości jej przewidzianego skanu lidaru (wybranego w kierunku bieżacego estymowanego mapowania) względem rzeczywistego czytnika robota 3. resampling: wylosuj nową zestaw cząstek, prawdopodobieństwo proporcjonalne do oceny — wysokie ocenione cząstki są podwójne, niskie ocenione zanikają Ponieważ czytnik odometrii ma tendencję do błądzenia (skręty koła, kompilacja błędu integracji w czasie), jedynym krokiem przewidywania pozwalałoby chmurze rozszerzyć się i zacząć odlegać się od prawdy. Krok aktualizacyjny jest to co powraca: cząstka, której hipotetyczne położenie wygenerowałoby bardzo inny skan lidaru niż taki, jaki sensoresz rzeczywiście zobaczył, otrzymuje niskie wagi i jest usunięta podczas resamplingu. Po wystarczającym liczebności kroków przeżytą chmurę skupia się ciasno wokół prawdziwego położenia — ta koncentracja, widoczna w demo jako zanurzanie się chmury cząstek, to lokalizacja konverguje.

1. predict:  move every particle by the odometry reading + noise
2. update:   score each particle by how well its predicted lidar
             scan (cast against the current map estimate) matches
             the robot's actual lidar reading
3. resample: draw a new particle set, probability proportional to
             score - high-scoring particles get duplicated,
             low-scoring ones vanish

Mapowanie: siatka logarytmicznych szans zajętego pola

W tym czasie środowisko jest reprezentowane jako siatka komórek, każda z której przechowuje prawdopodobieństwo, że ta komórka jest zajęta. Jedna słaba dowodnicza zwrotna od laserowego detektora odświeżania (LIDAR) to słabe dowody — może być fałszywym dodatkiem, odbiciem lub szumem sensorowym — dlatego zamiast przechowywać proste prawdopodobieństwa (które niewłaściwie saturują na 0 i 1), standardowa technika przechowuje logarytmiczne szanse zajętego pola, co zamienia aktualizacje Bayesa w prostą dodawanie:

l(komórka) = log( p(zajęte) / (1 - p(zajęte)) ) // każda linia od LIDAR: l(komórka) += l_hit jeśli promień zakończył się w tej komórce (dowód: zajęte) l(komórka) += l_miss jeśli promień przeszedł przez tę komórkę (dowód: wolne, l_miss Każda dodatkowa skanowanie przez komórkę niszczy jej logarytmiczne szanse w kierunku pewności w jednym kierunku; kilka zgodnych wykryć jest wystarczające, aby być pewnym, że ścianka istnieje, podczas gdy pojedyncze nieprawidłowe zwroty niemal nie ruchą estymację. To dokładnie dlaczego siatka logarytmicznych szans zaczyna się od szarego niepewności i przekształca się w pewne czarne ściany oraz białe wolne przestrzenie po pierwszych kilkudziesięciu skanach demo.

l(cell) = log( p(occ) / (1 - p(occ)) )

// each lidar ray:
l(cell) += l_hit   if the ray terminated in this cell   (evidence: occupied)
l(cell) += l_miss  if the ray passed through this cell  (evidence: free, l_miss < 0)

p(occ) = 1 / (1 + e^(-l(cell)))   // convert back to a probability for display

Dlaczego są sobie niezbędne

Krok obserwacji filtra cząsteczkowego potrzebuje mapy, aby ocenić przewidywania lidaru, a aktualizacja siatki zajętości wymaga postawy, aby wiedzieć, przez które komórki przechodziła strzałka — każdy jest dla drugiego źródłem danych. W FastSLAM, klasycznej algorytmie, który ten styl symulacji follows, ta krągłość rozwiązuje się, podając każdemu cząstce własną siatkę zajętości: hipotezę postawy i hipotezę mapy podróżują razem, a resampling cenzuruje pary niepoprawnej postawy i niepoprawnej mapy jako całość, zamiast próbować rozdzielić niepoprawną postawę od niepoprawnej mapy po fakcie. To jest również przyczyną tego, że liczba cząstek stanowi rzeczywisty koszt obliczeniowy dla SLAM, a nie tylko lokalizacji — każda cząstka nosi całą siatkę.

Niezrozwikana forma niepowodzenia dowolnego lokalnego metody to zamknięcie pętli: po długim przebiegu, zbierany odchód może sprawić, że mapa staje się samoodpornym, więc powrót do poprzednio odwiedzonego pokoju może pokazać dwie nadmiarowe kopie tej samej gangi przesuniętej o odchód. Zauważenie, że robot wrócił gdzieś i zasilenie mapy (poprzez optymalizację grafu postaw) to osobna, trudniejsza problem, który ten demo symulacji skanowania lokalnego nie próbuje rozwiązać — to jest to, co konwertuje SLAM na współczesne systemy SLAM, takie jak SLAM oparte na grafie i SLAM oparty na czynnikach.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz SLAM: Simultaneous Localization and Mapping i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.