Planowanie ścieżek dla UAV: RRT* i pola potencjalne

Dwa rodziny planerów, jedna zadanie

Przeniesienie dronu z punktu A do B przez przeszkody to problem planowania ruchu, a prawie każda jego rozwaga należy do jednej z dwóch rodzin. Planery bazujące na próbkowaniu tworzą dyskretny graf stanów możliwych, losując przypadkowo wolne przestrzeń i łącząc bliskie próbki; planery reaktywne obliczają siłę lub gradient w bieżącym położeniu dronu i podążają za nim, chwilę po chwili, bez mapy całościowej przestrzeni. RRT* jest koniakiem pierwszej rodziny, a pola potencjalne klasycznym przykładem drugiej, a ta symulacja obie w tym samym polu 3D przeszkód, umożliwiając obserwację trade-off bezpośrednio.

RRT*: rosnące drzewo w stronę celu

Szybko-rzuciłe drzewa losowe (RRT, LaValle 1998) budują drzewo korzeniujące się od pozycji początkowej. Każda iteracja losuje punkt w 3D, znajduje najbliższy istniejący węzeł drzewa i rozszerza o stałą długość krok z tego węzła w stronę wylosowanego punktu. Jeśli nowy krawędź jest bezkolizyjny, dołącza on do drzewa. Powtarzaj dla kilku tysięcy iteracji — i z prawdopodobieństwem bliskim jedności liście drzewa są gęste, że jeden z nich jest blisko celu.

pętla: x_rand = losuj_wolne_pole() x_near = najbliższy_węzeł(drzewo, x_rand) x_new = steruj(x_near, x_rand, krok) // poruszenie o stałą długość w stronę x_rand if bezkolizyjny(x_near, x_new): drzewo.dodaj(x_new, rodzic = x_near) if w_rejonie_cele(x_new): zakończ Standardowe RRT znajduje ścieżkę szybko, ale jest rzadko dobrym rozwiązaniem — krzyży i zwija się, ponieważ nigdy nie odwiedza on ponownie decyzji. RRT* (Karaman & Frazzoli, 2011) naprawia to dwoma dodatkowymi krokiem na każdym.iteracji: gdy dołącza nowy węzeł, sprawdza wszystkie węzły drzewa w zrównywającym się promieniu (1) wybiera on rodzica spośród nich, który daje najtańszą ścieżkę od korzenia, a następnie (2) przewiązuje dowolne z tych bliskich węzłów przez nowy węzeł, jeśli to spowalnia ich własny koszt. Ta lokalna re-optimizacja, powtarzana tysięcy razy, dowodowo konverguje do najkrótszej bezkolizyjnej ścieżki — RRT* jest asymptotycznie optymalny, standardowe RRT nie jest.

koszt to więcej bookkeepingu na iterację (najbliższy sąsiad i zapytanie o promień zamiast jednego), dlatego praktyczne implementacje przechowują węzły drzewa w k-d tree zamiast płaskiej tablicy — bez tego, każda z tych operacji spada do O(n) i całe planowanie staje się O(n kwadratowej) podczas wykonywania.

loop:
  x_rand  = sample_free_space()
  x_near  = nearest(tree, x_rand)
  x_new   = steer(x_near, x_rand, step)      // move one fixed step toward x_rand
  if collision_free(x_near, x_new):
    tree.add(x_new, parent = x_near)
    if in_goal_region(x_new): done

Pola potencjalne: bez planowania, tylko spadek gradientu

Pole potencjałowe sztuczne (Khatib, 1986) pomija całą grafikę. Cel wydaje potencjał atrakcyjny, który przyciąga dron do siebie, jakby był to dolina; każdy obiekt przeszkodniczy wydaje potencjał odpychający, który odpycha drona, silnie blisko i znikająco poza pewnym promieniem bezpieczeństwa. Na każdym momencie dron prosto lata w dół kombinowanego gradientu — bez drzewa, bez pamięci o przestrzeni, niewielka obliczalność na każdej kroku, dlatego jest to domyślne rozwiązanie dla szybkiego pętli kontroli wewnętrznego rzeczywistego drona kwadratowego reagującego na lidar, który właśnie przeczytał.

F_total(x) = -grad(U_attract(x)) - sum_i grad(U_repel_i(x)) U_attract(x) = 0.5 * k_att * ||x - x_goal||^2 U_repel(x) = 0.5 * k_rep * (1/d(x) - 1/d0)^2 if d(x) Problem polega na tym, dlaczego ta demonstracja paruje te dwie metody: czysto reaktywny sterownik nie ma przewidywania w przyszłość, więc może być zatrapiony w lokalnym minimum — punkcie, gdzie atrakcyjne przyciągnięcie do celu jest dokładnie zrównane przez odpychające oddziaływanie konwexnej przeszkody, takiej jak wnętrze ściany U. Dron siedzi tam, całe siły netto zero, cel nie osiągnięty, nie ma to znaczenia, ile czasu czekasz. Planery oparte na próbkowaniu nie mają tej wadliwej cechy, ponieważ eksplorują całą przestrzeń zamiast spadać po jednym polu skalarnym; cena jest taka, że RRT* potrzebuje globalnej mapy na początku i znacznie dłużej tworzy ścieżkę.

F_total(x) = -grad(U_attract(x)) - sum_i grad(U_repel_i(x))
U_attract(x) = 0.5 * k_att * ||x - x_goal||^2
U_repel(x)   = 0.5 * k_rep * (1/d(x) - 1/d0)^2   if d(x) < d0, else 0

Co rzeczywiste zestawy dla UAV naprawdę robią

Rzadko jest sytuacja, że produkcyjne systemy autonomii wybierają jedno i odrzuca drugie. Popularna architektura wykonuje planera globalnego bazującego na próbkowaniu lub wyszukiwaniu (RRT*, czy jego wariant lattice/A*) z niską częstotliwością nad mapą znanej, tworząc szeroką korytarz punktów celu, a także warstwę reaktywną szybkiego reagowania — pola potencjalne lub jej bardziej łagodny wariant przeszkody prędkości — do uniknięcia kolizji na lokalnym poziomie z przeszkodami, które mapą globalną nadal nie zna. Planer globalny dostarcza widoczność daleko przed siebie, która uwalnia się z lokalnych minimum; warstwa reaktywna dostarcza reakcję milisekundową, której nie ma miejsca w obliczeniach globalnej replanifikacji lub ruchu przeszkód.

Inne praktyczne zagadnienie to kinodynamiczna realizowalność: koordynator czwórotorowy nie może natychmiast zmieniać prędkości ani obracać się na dime, więc ścieżka RRT* zbudowana z linii prostej musi być posmazana i ponownie parametryzowana w oparciu o rzeczywiste ograniczenia przyspieszeń pojazdu (zwykle za pomocą dopasowania trajektorii minimalnego-snapa lub minimalnego-jerk) zanim będzie ona lotna. Najszybsza ścieżka geometryczna nie musi być taka, która jest lotna.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz UAV Path Planning: RRT* & Potential Fields i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.