Szybko eksplorujące losowe drzewo

Wizualizacja wykresu RRT po 45 i 390 iteracjach

Animacja RRT rozpoczynająca się od iteracji od 0 do 10000

Szybko eksplorujące drzewo losowe (RRT) to algorytm zaprojektowany do wydajnego przeszukiwania niewypukłych , wielowymiarowych przestrzeni poprzez losowe budowanie drzewa wypełniającego przestrzeń . Drzewo jest konstruowane przyrostowo z próbek pobranych losowo z przestrzeni poszukiwań i jest z natury nastawione na rozrastanie się w kierunku dużych, niezbadanych obszarów problemu. RRT zostały opracowane przez Stevena M. LaValle'a i Jamesa J. Kuffnera Jr. Z łatwością radzą sobie z problemami z przeszkodami i ograniczeniami różniczkowymi ( nieholonomiczne i kinodynamiczne) i są szeroko stosowane w planowaniu ruchu autonomicznych robotów .

RRT można postrzegać jako technikę generowania trajektorii w pętli otwartej dla systemów nieliniowych z ograniczeniami stanu. RRT można również uznać za Monte-Carlo polegającą na ukierunkowaniu wyszukiwania na największe regiony Woronoja grafu w przestrzeni konfiguracyjnej. Niektóre odmiany można nawet uznać za fraktale stochastyczne .

RRT mogą być używane do obliczania przybliżonych zasad sterowania w celu sterowania wielowymiarowymi systemami nieliniowymi z ograniczeniami stanu i działania.

Opis

RRT rozwija drzewo zakorzenione w początkowej konfiguracji, używając losowych próbek z przestrzeni wyszukiwania. Gdy każda próbka jest rysowana, następuje próba połączenia między nią a najbliższym stanem w drzewie. Jeśli połączenie jest wykonalne (przechodzi całkowicie przez wolną przestrzeń i przestrzega wszelkich ograniczeń), skutkuje to dodaniem nowego stanu do drzewa. Przy jednolitym próbkowaniu przestrzeni poszukiwań prawdopodobieństwo rozszerzenia istniejącego państwa jest proporcjonalne do wielkości jego regionu Woronoja . Ponieważ największe regiony Woronoja należą do państw na granicy poszukiwań, oznacza to, że drzewo preferencyjnie rozszerza się w kierunku dużych, niezbadanych obszarów.

Długość połączenia między drzewem a nowym stanem jest często ograniczona przez czynnik wzrostu. Jeśli próbka losowa znajduje się dalej od najbliższego stanu w drzewie, niż pozwala na to ograniczenie, zamiast samej próbki losowej używany jest nowy stan w maksymalnej odległości od drzewa wzdłuż linii do próbki losowej. Losowe próbki można zatem postrzegać jako kontrolujące kierunek wzrostu drzewa, podczas gdy czynnik wzrostu określa jego tempo. Utrzymuje to tendencję do wypełniania przestrzeni RRT, jednocześnie ograniczając rozmiar przyrostowego wzrostu.

Wzrost RRT można obciążyć, zwiększając prawdopodobieństwo próbkowania stanów z określonego obszaru. Większość praktycznych implementacji RRT wykorzystuje to do kierowania poszukiwań w kierunku celów problemu planowania. Osiąga się to poprzez wprowadzenie małego prawdopodobieństwa próbkowania celu do procedury próbkowania stanu. Im większe to prawdopodobieństwo, tym bardziej zachłannie rośnie drzewo w kierunku celu.

Algorytm

Dla ogólnej przestrzeni konfiguracyjnej C algorytm w pseudokodzie jest następujący:


       
         Algorytm  BuildRRT Wejście: Konfiguracja początkowa  q _init , liczba wierzchołków w RRT  K  , przyrost odległości  Δq  Wyjście: RRT graph  G  G  .init(  q _init )  for  k  = 1  to  K  do  q _rand ← RAND_CONF()  q _near ← NAJBLIŻSZY_VERTEX(  q _rand ,  G  )  q _nowy ← NEW_CONF(  q  _blisko ,  q _rand ,  Δq  )  G  .add_vertex(  q _nowy )  G  .add_edge(  q _blisko ,  q _nowy )  powrót  G

„←” oznacza przypisanie . Na przykład „ największy ← przedmiot ” oznacza, że wartość największego zmienia się na wartość elementu .
„ return ” kończy działanie algorytmu i wyświetla następującą wartość.

W powyższym algorytmie „ RAND_CONF ” pobiera losową konfigurację q _rand w C . Można to zastąpić funkcją „ RAND_FREE_CONF ”, która wykorzystuje próbki w C _free , odrzucając próbki w C _obs za pomocą algorytmu wykrywania kolizji.

„ NEAREST_VERTEX ” to funkcja, która przechodzi przez wszystkie wierzchołki v na grafie G , oblicza odległość między q _rand i v za pomocą jakiejś funkcji pomiarowej, zwracając w ten sposób najbliższy wierzchołek.

„ NEW_CONF ” wybiera nową konfigurację q _new , przesuwając przyrostową odległość Δq od q _blisko w kierunku q _rand . (Według problemów holonomicznych należy to pominąć i zamiast q _{new użyć} q _rand .)

Warianty i ulepszenia do planowania ruchu

RRT-Rope, metoda szybkiego, prawie optymalnego planowania ścieżki z wykorzystaniem deterministycznego podejścia do skracania, bardzo skuteczna w otwartych i dużych środowiskach.
RRT ukierunkowane na grę (PDRRT), metoda, która łączy RRT z metodą gry częściowej w celu udoskonalenia wyszukiwania tam, gdzie jest to potrzebne (na przykład wokół przeszkód), aby móc szybciej planować i rozwiązywać więcej problemów z planowaniem ruchu niż RRT
Szybko badająca losowa pętla zamknięta (CL-RRT), rozszerzenie RRT, które pobiera próbki danych wejściowych do stabilnego systemu zamkniętej pętli składającego się z pojazdu i kontrolera

Wykazano, że w „łagodnych warunkach technicznych” koszt najlepszej ścieżki w RRT prawie na pewno zbiega się do wartości nieoptymalnej. Z tego powodu pożądane jest znalezienie wariantów RRT zbieżnych do optimum, takich jak RRT*. Poniżej znajduje się lista metod opartych na RRT* (zaczynając od samego RRT*). Jednak nie wszystkie metody pochodne same w sobie zbiegają się do optimum.

Szybko eksplorujący graf losowy (RRG) i RRT*, wariant RRT, który zbiega się w kierunku optymalnego rozwiązania
LQR-RRT , wariant kinodynamiczny dla złożonej lub niedostatecznej dynamiki
RRT ⁺ , rodzina planistów opartych na RRT, których celem jest generowanie rozwiązań dla systemów wielowymiarowych w czasie rzeczywistym, poprzez stopniowe przeszukiwanie podprzestrzeni o niższych wymiarach.
RRT*-Smart, metoda przyspieszania tempa konwergencji RRT* za pomocą optymalizacji ścieżki (w sposób podobny do Theta* ) i inteligentnego próbkowania (poprzez ukierunkowanie próbkowania w kierunku wierzchołków ścieżki, które – po optymalizacji ścieżki – prawdopodobnie będą bliskie do przeszkód)
A*-RRT i A*-RRT*, dwufazowa metoda planowania ruchu , która wykorzystuje algorytm przeszukiwania grafów do wyszukiwania początkowej możliwej ścieżki w przestrzeni niskowymiarowej (nie biorąc pod uwagę pełnej przestrzeni stanów) w pierwszej fazie, unikanie niebezpiecznych obszarów i preferowanie tras o niskim ryzyku, które są następnie wykorzystywane do skoncentrowania wyszukiwania RRT * w ciągłej przestrzeni wielowymiarowej w drugiej fazie
RRT*FN, RRT* ze stałą liczbą węzłów, co losowo usuwa węzeł liścia w drzewie w każdej iteracji
RRT*-AR, planowanie alternatywnych tras na podstawie próbkowania
Poinformowany RRT* poprawia szybkość konwergencji RRT* poprzez wprowadzenie heurystyki, podobnej do sposobu, w jaki A* ulepsza algorytm Dijkstry
Real-Time RRT* (RT-RRT*), wariant RRT* i informowanego RRT*, który wykorzystuje strategię ponownego okablowania drzewa online, która umożliwia ruch korzenia drzewa wraz z agentem bez odrzucania wcześniej próbkowanych ścieżek w celu uzyskania rzeczywistych planowanie ścieżki czasowej w dynamicznym środowisku, takim jak gra komputerowa
RRT ^X i RRT ^# , optymalizacja RRT* dla środowisk dynamicznych
Theta*-RRT, dwufazowa metoda planowania ruchu podobna do A*-RRT*, która wykorzystuje hierarchiczne połączenie wyszukiwania pod dowolnym kątem z planowaniem ruchu RRT w celu szybkiego generowania trajektorii w środowiskach ze złożonymi ograniczeniami nieholonomicznymi
RRT* FND, rozszerzenie RRT* dla środowisk dynamicznych
RRT-GPU, trójwymiarowa implementacja RRT wykorzystująca akcelerację sprzętową
APF-RRT, połączenie planowania RRT z metodą sztucznych pól potencjału, które upraszczają ponowne planowanie
CERRT, planista RRT modelujący niepewność, która zmniejsza się wykorzystując kontakty
MVRRT*, Minimalne naruszenie RRT*, algorytm, który znajduje najkrótszą trasę, która minimalizuje poziom zagrożenia („koszt” naruszonych zasad środowiskowych, np. przepisów ruchu drogowego)
RRT-Blossom, narzędzie do planowania RRT dla bardzo ograniczonych środowisk.
RRV, wydajnie rozszerzaj drzewo wokół przeszkód i przez wąskie przejścia, wykorzystując dominujące wektory własne wokół węzłów drzewa.
RBT wykorzystuje proste obliczenia odległości w obszarze roboczym, aby rozszerzyć drzewo zamiast kosztownego sprawdzania kolizji.
TB-RRT, oparty na czasie algorytm RRT do planowania spotkania dwóch systemów dynamicznych.
RRdT*, narzędzie do planowania oparte na RRT*, które wykorzystuje wiele lokalnych drzew do aktywnego równoważenia eksploracji i eksploatacji przestrzeni poprzez lokalne pobieranie próbek.

Zobacz też

Linki zewnętrzne

Media związane z Szybkim odkrywaniem losowego drzewa w Wikimedia Commons
Wizualizator Java RRT i RRT* wraz z edytorem map
Implementacja RRT w C++ przy użyciu ścieżek o minimalnym czasie Dubinsa
Implementacja Open Motion Planning Library RRT*