Eksploracja granic
Jak działa
1) Mapa zajętości: robot utrzymuje occupancy grid z komórkami wolnymi, zajętymi i nieznanymi, aktualizowany z czujników (lidar, kamera głębi, sonar), zwykle wraz z systemem SLAM lokalizującym robota. 2) Detekcja granic: algorytm znajduje komórki wolne sąsiadujące z co najmniej jedną komórką nieznaną — to komórki granic (frontier cells). 3) Grupowanie: sąsiadujące komórki granic są łączone w spójne regiony (frontiers); zbyt małe regiony są odrzucane jako szum. 4) Wybór celu: spośród regionów wybierany jest jeden cel — w klasycznym ujęciu środek (centroid) najbliższego regionu; w wariantach rozszerzonych stosuje się funkcję kosztu/użyteczności łączącą odległość z oczekiwanym przyrostem informacji. 5) Nawigacja: planer ścieżki wyznacza trasę do celu, a robot nią jedzie, cały czas aktualizując mapę. 6) Pętla: po dotarciu (lub gdy pojawią się nowe dane) granice są wyznaczane ponownie i cykl się powtarza. 7) Zakończenie: gdy nie ma już żadnych granic, cały osiągalny teren jest zmapowany i eksploracja się kończy.
Rozwiązany problem
Rozwiązuje pytanie „dokąd jechać dalej?" podczas budowy mapy nieznanego środowiska. Bez takiej strategii robot musiałby eksplorować losowo lub z góry znać teren, co jest wolne i pozostawia luki w mapie. Frontier Exploration daje prostą, zachłanną heurystykę, która gwarantuje stały przyrost informacji: kierowanie się na granice zawsze prowadzi w stronę nieodkrytej przestrzeni, aż do pełnego zmapowania osiągalnego terenu.
Komponenty
Siatka komórek klasyfikowanych jako wolne, zajęte lub nieznane; podstawowa reprezentacja wiedzy robota o otoczeniu.
Moduł wyszukujący komórki wolne sąsiadujące z nieznanymi i grupujący je w regiony granic.
Reguła wybierająca następny cel spośród regionów granic — klasycznie najbliższy region, w wariantach funkcja kosztu/użyteczności (odległość vs. przyrost informacji).
Wyznacza wykonalną trasę od aktualnej pozycji robota do wybranego celu granicy, omijając przeszkody.
Cykl jedź–mapuj–przelicz-granice powtarzany aż do zniknięcia wszystkich granic.
Implementacja
Naiwne skanowanie całej siatki przy każdej iteracji skaluje się słabo dla dużych map o wysokiej rozdzielczości.
Kierowanie się zawsze do najbliższej granicy prowadzi do zbędnego zawracania i wydłuża łączną trasę eksploracji.
Szum czujników i artefakty SLAM tworzą drobne, fałszywe granice, które marnują czas eksploracji.
Ewolucja
Brian Yamauchi publikuje „A Frontier-Based Approach for Autonomous Exploration" (IEEE CIRA '97), definiując pojęcie granic na mapie zajętości i zachłanną strategię „jedź do najbliższej granicy".
Yamauchi rozszerza podejście na zespoły robotów dzielące wspólną mapę („Frontier-Based Exploration Using Multiple Robots", AGENTS '98), kładąc podwaliny pod skoordynowaną eksplorację wielorobotową.
Hiperparametry (konfigurowalne osie)
Sposób wyszukiwania granic: pełne skanowanie siatki vs. metody falowe/inkrementalne (np. WFD, FFD).
Próg liczby komórek, poniżej którego region granic jest odrzucany jako szum.
Kryterium wyboru celu: najbliższa granica vs. ważona kombinacja odległości i oczekiwanego przyrostu informacji.
Zasięg lidaru/kamery głębi; wpływa na tempo odkrywania i rozmieszczenie granic.
Jak często ponownie wyznaczane są granice i cel w trakcie jazdy.
Złożoność obliczeniowa
Złożoność czasowa: O(C) na iterację detekcji granic. Złożoność przestrzenna: O(C).
Wymagania sprzętowe
Klasyczny algorytm oparty na przeszukiwaniu siatki i grafów; działa wydajnie na standardowym CPU pokładowym robota, bez potrzeby akceleracji GPU.
Niewielkie wymagania obliczeniowe pozwalają uruchomić go na szerokim zakresie platform wbudowanych.