Planowanie ścieżki pod dowolnym kątem - Any-angle path planning

Ścieżka znaleziona przez A * na siatce oktylowej w porównaniu z najkrótszą ścieżką między węzłem początkowym i docelowym.

Algorytmy planowania ścieżki pod dowolnym kątem są podzbiorem algorytmów odnajdywania ścieżki , które wyszukują ścieżkę między dwoma punktami w przestrzeni i pozwalają, aby zwoje na ścieżce miały dowolny kąt. Rezultatem jest ścieżka, która prowadzi bezpośrednio do celu i ma stosunkowo niewiele zakrętów. Inne algorytmy odnajdywania ścieżek, takie jak A *, ograniczają ścieżki do siatki, która generuje postrzępione, pośrednie ścieżki.

tło

Świat rzeczywisty i wiele map w grze ma otwarte obszary, po których można najskuteczniej przechodzić w sposób bezpośredni. Tradycyjne algorytmy nie są odpowiednio przygotowane do rozwiązania tych problemów:

• A * z 8-połączonym dyskretnym wykresem siatki jest bardzo szybki, ale patrzy tylko na ścieżki w 45-stopniowych przyrostach. Szybki krok po wygładzaniu może być użyty do wyprostowania (a tym samym skrócenia) postrzępionego wyjścia, ale wynik nie jest gwarantowany jako optymalny, ponieważ nie wygląda na wszystkie możliwe ścieżki. (Mówiąc dokładniej, nie mogą zmienić, po której stronie zablokowanej komórki jest przechodzona). Zaletą jest to, że zostaną zastosowane wszystkie optymalizacje siatki A *, takie jak wyszukiwanie punktów przeskoku .
• Wykres widoczność ze wszystkich punktów siatki mogą być przeszukiwane z d * rozwiązania optymalnego. Jednak wydajność jest problematyczna, ponieważ liczba krawędzi na wykresie z wierzchołkami wynosi . ${\ displaystyle V}$${\ Displaystyle O (V ^ {2})}$

Algorytm planowania ścieżki pod dowolnym kątem ma na celu stworzenie optymalnych lub prawie optymalnych rozwiązań, zajmując mniej czasu niż podstawowe podejście oparte na wykresie widoczności. Szybkie algorytmy pod dowolnym kątem zajmują mniej więcej tyle samo czasu, co obliczenia oparte na siatce.

Definicje

Napięta ścieżka

Ścieżka, na której każda zmiana kursu na ścieżce „ściśle otacza” jakąś przeszkodę. Aby uzyskać jednolitą siatkę, optymalne mogą być tylko napięte ścieżki.

Pojedyncze źródło

Problem ze znajdowaniem ścieżki, który ma na celu znalezienie najkrótszej ścieżki do wszystkich części wykresu, zaczynając od jednego wierzchołka.

Algorytmy

Oparty na A *

Do tej pory opracowano pięć głównych algorytmów planowania ścieżki pod dowolnym kątem, opartych na heurystycznym algorytmie wyszukiwania A * , z których wszystkie propagują informacje wzdłuż krawędzi siatki:

• Pole D * (FD *) i 3D Field D * - algorytmy dynamicznego wyszukiwania ścieżki oparte na D *, które wykorzystują interpolację podczas każdego rozszerzania wierzchołków i znajdują prawie optymalne ścieżki poprzez regularne , niejednorodne siatki kosztów. Dlatego pole D * próbuje rozwiązać problem obszaru ważonego, a pole 3D D * odpowiadający mu problem trójwymiarowy.
  • Pole D * o wielu rozdzielczościach - rozszerzenie pola D * dla siatek o wielu rozdzielczościach.
• Theta * - Używa samą główną pętlę jako *, ale dla każdego ekspansji wierzchołka , jest line-of-sight check pomiędzy i następca , . Jeśli istnieje linia wzroku, używana jest ścieżka od do, ponieważ zawsze będzie co najmniej tak krótka, jak ścieżka od do i do . Ten algorytm działa tylko na siatkach o jednolitych kosztach. AP Theta * to optymalizacja Theta *, która wykorzystuje propagację kąta w celu zmniejszenia kosztów wykonywania obliczeń linii wzroku do O (1) , a Lazy Theta * to kolejna optymalizacja Theta *, która wykorzystuje leniwą ocenę w celu zmniejszenia liczby obliczeń linii wzroku poprzez opóźnienie obliczeń linii wzroku dla każdego węzła od momentu eksploracji do rozwinięcia. Przyrostowa Phi * to przyrostowy , bardziej wydajny wariant Theta * przeznaczony do nieznanych środowisk 2D. ${\ displaystyle s}$${\ displaystyle rodzic (e)}$${\ displaystyle s}$${\ displaystyle s '}$${\ displaystyle rodzic (e)}$${\ displaystyle s '}$${\ displaystyle rodzic (e)}$${\ displaystyle s}$${\ displaystyle s}$${\ displaystyle s '}$
  • Strict Theta * i Recursive Strict Theta * ulepsza Theta *, ograniczając przestrzeń wyszukiwania do Taut Paths wprowadzonych przez ANYA. Podobnie jak Theta *, jest to algorytm, który zwraca prawie optymalne ścieżki.
• Blok A * - generuje lokalną bazę danych odległości zawierającą wszystkie możliwe ścieżki na małym odcinku siatki. Odwołuje się do tej bazy danych, aby szybko znaleźć fragmentaryczne ścieżki pod dowolnym kątem.
• ANYA - znajduje optymalne ścieżki pod dowolnym kątem, ograniczając przestrzeń poszukiwań do ścieżek napiętych (ścieżka, w której każda zmiana kursu na ścieżce „ściśle otacza” jakąś przeszkodę); postrzeganie przedziału punktów jako węzła, a nie pojedynczego punktu. Najszybsza znana optymalna technika online.
• CWave - wykorzystuje geometryczne prymitywy (dyskretne okrągłe łuki i linie) do reprezentowania rozchodzącej się fali na siatce. W przypadku planowania ścieżki z jednego źródła na praktycznych mapach wykazano, że jest szybszy niż metody oparte na przeszukiwaniu grafów. Istnieją optymalne i arytmetyczne implementacje liczb całkowitych.

Istnieje również algorytm oparty na A * różniący się od powyższej rodziny:

• Wydajność podejścia opartego na wykresie widoczności można znacznie poprawić, stosując podejście rzadkie, które uwzględnia tylko krawędzie zdolne do tworzenia napiętych ścieżek. Wiadomo, że wersja wielopoziomowa o nazwie ENLSVG jest szybsza niż ANYA, ale można jej używać tylko z przetwarzaniem wstępnym.
• Podobnie jak w przypadku rozwiązania RRT omówionego poniżej, często konieczne jest uwzględnienie ograniczeń kierowania podczas pilotowania prawdziwego pojazdu. Hybryda A * jest rozszerzeniem A *, które uwzględnia dwa dodatkowe wymiary reprezentujące stan pojazdu, dzięki czemu ścieżki są rzeczywiście możliwe. Został stworzony przez Stanford Racing jako część systemu nawigacji dla Juniorów, ich wejścia do DARPA Urban Challenge . Bardziej szczegółową dyskusję dokonali Peterit i in.

Oparte na RRT

Poza tym w przypadku wyszukiwania w wielowymiarowych przestrzeniach wyszukiwania, na przykład gdy przestrzeń konfiguracji systemu obejmuje wiele stopni swobody, które należy wziąć pod uwagę (patrz Planowanie ruchu ), i / lub należy wziąć pod uwagę pęd (który mógłby skutecznie podwoić liczba wymiarów przestrzeni poszukiwań; ta większa przestrzeń zawierająca pęd jest znana jako przestrzeń fazowa ), opracowano warianty szybko eksplorującego drzewa losowego (RRT), które (prawie na pewno) zbiegają się do ścieżki optymalnej, znajdując coraz krótsze i krótsze ścieżki:

• Szybko eksplorujący losowy wykres (RRG) i RRT *
• Informed RRT * poprawia szybkość zbieżności RRT * poprzez wprowadzenie heurystyki, podobnej do sposobu, w jaki A * poprawia algorytm Dijkstry .

Aplikacje

Planowanie ścieżki pod dowolnym kątem jest przydatne do nawigacji robotów i gier strategicznych w czasie rzeczywistym, w których pożądane są bardziej optymalne ścieżki. Na przykład hybryda A * została użyta jako wejście do wyzwania DARPA. Niektóre przykłady związane ze świadomością kierowania przekładają się również na samochody autonomiczne.

Zobacz też

• Planowanie ruchu

Bibliografia

Linki zewnętrzne

• Lazy Theta *: Szybsze planowanie ścieżki pod dowolnym kątem
• A. Nash i S. Koenig. Planowanie ścieżki pod dowolnym kątem . Artificial Intelligence Magazine , 34, (4), 85-107, 2013.
• Any Angle Pathfinding , kod demonstracyjny open source Shunhao Oh