D*
D* (wymawiane jako „gwiazda D”) to jeden z trzech powiązanych algorytmów wyszukiwania przyrostowego :
- Oryginalny D*, autorstwa Anthony'ego Stentza, jest świadomym algorytmem wyszukiwania przyrostowego.
- Focused D* to świadomy, przyrostowy algorytm wyszukiwania heurystycznego autorstwa Anthony'ego Stentza, który łączy idee A* i oryginalnego D*. Focused D* jest wynikiem dalszego rozwoju oryginalnego D*.
- D* Lite to przyrostowy algorytm wyszukiwania heurystycznego autorstwa Svena Koeniga i Maxima Likhacheva, który opiera się na LPA* , przyrostowym algorytmie wyszukiwania heurystycznego, który łączy idee A* i Dynamic SWSF-FP.
Wszystkie trzy algorytmy wyszukiwania rozwiązują te same problemy planowania ścieżki oparte na założeniach, w tym planowanie z założeniem wolnej przestrzeni, gdzie robot musi nawigować do zadanych współrzędnych celu w nieznanym terenie. Przyjmuje założenia dotyczące nieznanej części terenu (na przykład, że nie zawiera ona przeszkód) i przy tych założeniach znajduje najkrótszą drogę od jej aktualnych współrzędnych do współrzędnych celu. Następnie robot podąża ścieżką. Kiedy obserwuje nowe informacje na mapie (takie jak wcześniej nieznane przeszkody), dodaje te informacje do swojej mapy i, jeśli to konieczne, ponownie planuje nową najkrótszą ścieżkę od swoich aktualnych współrzędnych do podanych współrzędnych celu. Powtarza ten proces, aż osiągnie współrzędne celu lub stwierdzi, że współrzędne celu nie mogą zostać osiągnięte. Podczas przemierzania nieznanego terenu często można odkrywać nowe przeszkody, więc przeplanowanie musi być szybkie. Algorytmy wyszukiwania przyrostowego (heurystycznego) przyspieszają wyszukiwanie sekwencji podobnych problemów wyszukiwania, wykorzystując doświadczenie z poprzednimi problemami do przyspieszenia wyszukiwania bieżącego. Zakładając, że współrzędne celu nie zmieniają się, wszystkie trzy algorytmy wyszukiwania są bardziej wydajne niż powtarzane wyszukiwania A*.
D* i jego warianty są szeroko stosowane w nawigacji robotów mobilnych i pojazdów autonomicznych . Obecne systemy są zwykle oparte na D* Lite, a nie na oryginalnym D* lub Focused D*. W rzeczywistości nawet laboratorium Stentza używa D* Lite zamiast D* w niektórych implementacjach. Takie systemy nawigacyjne obejmują prototypowy system przetestowany na łazikach marsjańskich Opportunity i Spirit oraz system nawigacyjny zwycięskiej pracy w konkursie DARPA Urban Challenge , oba opracowane na Uniwersytecie Carnegie Mellon .
Oryginalny D* został wprowadzony przez Anthony'ego Stentza w 1994 roku. Nazwa D* pochodzi od terminu „Dynamiczny A*”, ponieważ algorytm zachowuje się jak A*, z wyjątkiem tego, że koszty łuku mogą się zmieniać w miarę działania algorytmu.
Operacja
Poniżej opisano podstawowe działanie D*.
Podobnie jak algorytm Dijkstry i A*, D* utrzymuje listę węzłów do oceny, znaną jako „lista OTWARTA”. Węzły są oznaczone jako posiadające jeden z kilku stanów:
- NOWY, co oznacza, że nigdy nie znalazł się na liście OPEN
- OPEN, czyli aktualnie znajduje się na liście OPEN
- ZAMKNIĘTA, co oznacza, że nie znajduje się już na liście OTWARTYCH
- PODBIJ, wskazując, że jego koszt jest wyższy niż ostatnim razem, gdy był na liście OPEN
- NIŻSZY, wskazując, że jego koszt jest niższy niż ostatnim razem, gdy był na liście OTWARTYCH
Ekspansja
Algorytm działa poprzez iteracyjne wybieranie węzła z listy OPEN i ocenianie go. Następnie propaguje zmiany węzła do wszystkich sąsiednich węzłów i umieszcza je na liście OPEN. Ten proces propagacji jest określany jako „ekspansja”. W przeciwieństwie do kanonicznego A*, który podąża ścieżką od początku do końca, D* zaczyna się od wyszukiwania wstecz od węzła docelowego. Oznacza to, że algorytm faktycznie oblicza optymalną ścieżkę A* dla każdego możliwego węzła początkowego. Każdy rozwinięty węzeł ma wskaźnik wsteczny, który odnosi się do następnego węzła prowadzącego do celu, a każdy węzeł zna dokładny koszt dla celu. Kiedy węzeł początkowy jest następnym węzłem do rozwinięcia, algorytm jest zakończony, a ścieżkę do celu można znaleźć, po prostu podążając za wskaźnikami wstecznymi.
Rozbudowa w toku. Węzeł końcowy (żółty) znajduje się pośrodku górnego rzędu punktów, węzeł początkowy znajduje się pośrodku dolnego rzędu. Czerwony oznacza przeszkodę; czarny/niebieski oznacza rozszerzone węzły (jasność wskazuje koszt). Zielony wskazuje węzły, które są rozwijane.
Rozbudowa zakończona. Ścieżka jest oznaczona kolorem cyjan.
Radzenie sobie z przeszkodami
Gdy na zamierzonej ścieżce zostanie wykryta przeszkoda, wszystkie punkty, których to dotyczy, zostaną ponownie umieszczone na liście OTWARTE, tym razem oznaczone jako PODNIEŚ. Zanim jednak węzeł RAISED wzrośnie, algorytm sprawdza sąsiadów i sprawdza, czy może obniżyć koszt węzła. Jeśli nie, stan RAISE jest propagowany do wszystkich potomków węzłów, to znaczy węzłów, które mają do niego wskaźniki wsteczne. Te węzły są następnie oceniane, a stan PODNIESIENIA jest przekazywany dalej, tworząc falę. Kiedy węzeł PODNIESIONY może zostać zredukowany, jego wskaźnik wsteczny jest aktualizowany i przekazuje stan NIŻSZY swoim sąsiadom. Te fale stanów PODNIESIENIA i OBNIŻENIA są sercem D*.
W tym momencie cała seria innych punktów nie może zostać „dotknięta” przez fale. Algorytm pracował zatem tylko w punktach, na które ma wpływ zmiana kosztów.
Dodano przeszkodę (czerwony) i zaznaczono węzły PODNIEŚ (żółty).
Rozbudowa w toku. Żółty oznacza węzły oznaczone PODNOSZENIE, zielony oznacza węzły oznaczone NIŻSZY.
Następuje kolejny impas
Tym razem impasu nie da się tak elegancko ominąć. Żaden z punktów nie może znaleźć nowej trasy przez sąsiada do miejsca docelowego. Dlatego nadal propagują wzrost kosztów. Można znaleźć tylko punkty poza kanałem, które mogą prowadzić do miejsca docelowego realną trasą. W ten sposób rozwijają się dwie Dolne fale, które rozszerzają się jako punkty oznaczone jako nieosiągalne z nowymi informacjami o trasie.
Kanał zablokowany przez dodatkowe przeszkody (czerwony)
Ekspansja w toku (podnieś falę na żółto, obniż falę na zielono)
Znaleziono nową ścieżkę (cyjan)
Pseudo kod
while ( ! openList . isEmpty ()) { point = openList . pobierzPierwszy (); rozwinąć ( punkt ); }
Zwiększać
void expand ( bieżący punkt ) { boolean isRaise = isRaise ( currentPoint ); podwójny koszt ; for each ( sąsiad w currentPoint . getNeighbors ()) { if ( isRaise ) { if ( sąsiad . nextPoint == currentPoint ) { sąsiad . setNextPointAndUpdateCost ( bieżący punkt ); otwórz listę . dodaj ( sąsiada ); } else { koszt = sąsiad . obliczCostVia ( bieżący punkt ); if ( koszt < sąsiad . getCost ()) { currentPoint . setMinimumCostToCurrentCost (); otwórz listę . dodaj ( bieżący punkt ); } } } else { koszt = sąsiad . obliczCostVia ( bieżący punkt ); if ( koszt < sąsiad . getCost ()) { sąsiad . setNextPointAndUpdateCost ( bieżący punkt ); otwórz listę . dodaj ( sąsiada ); } } } }
Sprawdź podwyżkę
boolean isRaise ( punkt ) { podwójny koszt ; if ( point . getCurrentCost () > point . getMinimumCost ()) { for each ( sąsiad w punkcie . getNeighbors ()) { cost = point . obliczCostVia ( sąsiad ); if ( koszt < punkt . getCurrentCost ()) { punkt . setNextPointAndUpdateCost ( sąsiad ); } } } punkt powrotu . getCurrentCost () > punkt . pobierz minimalny koszt (); }
Warianty
skupiony D*
Jak sama nazwa wskazuje, Focused D* jest rozszerzeniem D*, które wykorzystuje heurystykę do skupienia propagacji PODNOSZENIA i OPUSZCZANIA w kierunku robota. W ten sposób aktualizowane są tylko istotne stany, w taki sam sposób, w jaki A* oblicza koszty tylko dla niektórych węzłów.
D* Lite
D* Lite nie jest oparty na oryginalnym D* ani Focused D*, ale implementuje to samo zachowanie. Jest prostszy do zrozumienia i można go zaimplementować w mniejszej liczbie linii kodu, stąd nazwa „D* Lite”. Pod względem wydajności jest równie dobry lub lepszy od Focused D*. D* Lite bazuje na Lifelong Planning A* , które kilka lat wcześniej wprowadzili Koenig i Likhachev. D* Lite
Koszt minimalny a koszt bieżący
W przypadku D* ważne jest rozróżnienie między kosztami bieżącymi i minimalnymi. Ta pierwsza jest ważna tylko w momencie zbierania, a druga jest krytyczna, ponieważ sortuje OpenList. Funkcja, która zwraca minimalny koszt, jest zawsze najniższym kosztem do bieżącego punktu, ponieważ jest to pierwszy wpis w OpenList.
- ^ Stentz, Anthony (1994), „Optymalne i wydajne planowanie ścieżki dla częściowo znanych środowisk”, Proceedings of the International Conference on Robotics and Automation : 3310–3317, CiteSeerX 10.1.1.15.3683
- ^ Stentz, Anthony (1995), „The Focussed D * Algorithm for Real-Time Replanning”, Proceedings of the International Joint Conference on Artificial Intelligence : 1652–1659 , CiteSeerX 10.1.1.41.8257
- Bibliografia _ Nilsson, N.; Raphael, B. (1968), „Formalna podstawa heurystycznego określania ścieżek minimalnych kosztów”, IEEE Trans. Syst. Nauka i cybernetyka , SSC-4 (2): 100–107, doi : 10.1109/TSSC.1968.300136
- Bibliografia _ Likhachev, M. (2005), „Szybkie ponowne planowanie nawigacji w nieznanym terenie”, Transactions on Robotics , 21 (3): 354–363, CiteSeerX 10.1.1.65.5979 , doi : 10.1109/tro.2004.838026
- Bibliografia _ Lichaczow, M.; Furcy, D. (2004), „Planowanie przez całe życie A *”, Sztuczna inteligencja , 155 (1–2): 93–146, doi : 10.1016/j.artint.2003.12.001
- Bibliografia _ Reps, T. (1996), „Przyrostowy algorytm uogólnienia problemu najkrótszej ścieżki”, Journal of Algorithms , 21 (2): 267–305, CiteSeerX 10.1.1.3.7926 , doi : 10.1006/jagm.1996.0046
- Bibliografia _ Smirnow, Y.; Tovey, C. (2003), „Granice wydajności planowania w nieznanym terenie”, Sztuczna inteligencja , 147 (1–2): 253–279, doi : 10.1016 / s0004-3702 (03) 00062-6
- ^ Drewniane, D. (2006). Planowanie ścieżki oparte na wykresach dla robotów mobilnych (praca dyplomowa). Georgia Institute of Technology.
- ^ Stentz, Anthony (1995), „The Focussed D * Algorithm for Real-Time Replanning”, Proceedings of the International Joint Conference on Artificial Intelligence : 1652–1659 , CiteSeerX 10.1.1.41.8257
- ^ Murphy, Robin R. (2019). Wprowadzenie do robotyki AI (wyd. 2). Książki Bradforda. Ustęp 14.5.2. ISBN 978-0262038485 .