Czym różnią się najnowocześniejsze algorytmy wyszukiwania ścieżek do zmiany wykresów (D *, D * -Lite, LPA * itd.)?

W ostatnich latach opracowano wiele algorytmów wyszukiwania ścieżek, które potrafią obliczyć najlepszą ścieżkę w odpowiedzi na zmiany wykresu znacznie szybciej niż A * - czym one są i czym się różnią? Czy są w różnych sytuacjach, czy też niektóre są przestarzałe?

Oto te, które do tej pory udało mi się znaleźć:

• D * (1994)
• Focused D * (1995)
• DynamicSWSF-FP (1996)
• LPA (1997)
• LPA * / Incremental A * (2001)
• D * Lite (2002)
• SetA * (2002)
• HPA * (2004)
• Anytime D * (2005)
• PRA * (2005)
• Pole D * (2007)
• Theta * (2007)
• HAA * (2008)
• GAA * (2008)
• LEARCH (2009)
• BDDD * (2009 - Nie mam dostępu do tego dokumentu: |)
• Przyrostowe Phi * (2009)
• GFRA * (2010)
• MTD * -Lite (2010)
• Tree-AA * (2011)

Nie jestem pewien, które z nich dotyczą mojego konkretnego problemu - przeczytam je wszystkie, jeśli to konieczne, ale zaoszczędziłbym dużo czasu, gdyby ktoś mógł napisać streszczenie.

Mój konkretny problem: mam siatkę z początkiem, wykończeniem i niektórymi ścianami. Obecnie używam A *, aby znaleźć najlepszą ścieżkę od początku do końca.

Użytkownik przesunie jedną ścianę i muszę ponownie przeliczyć całą ścieżkę. „Move-wall / przeliczyć-path” krok dzieje się wiele razy z rzędu, więc szukam dla algorytmu, który będzie w stanie szybko przeliczyć najlepszej ścieżki bez konieczności uruchamiania pełnego iteracji *.

Chociaż niekoniecznie szukam zmiany w A * - może to być zupełnie osobny algorytm.

Przeszukałem gazety i właśnie to lśniło. Jeśli w temacie jest ktoś bardziej kompetentny, popraw mnie, jeśli się mylę (lub dodaj własną odpowiedź, a ja ją zaakceptuję!) .

Linki do każdego artykułu można znaleźć w pytaniu powyżej.

• Proste przeliczenia
  • D * (alias Dynamic A * ) (1994): Podczas pierwszego uruchomienia D * działa bardzo podobnie do A *, bardzo szybko znajdując najlepszą ścieżkę od początku do końca. Jednakże, gdy jednostka przesuwa się od początku do końca, jeśli wykres się zmieni, D * jest w stanie bardzo szybko ponownie obliczyć najlepszą ścieżkę od pozycji tej jednostki do mety, znacznie szybciej niż po prostu ponownie uruchomić A * z pozycji tej jednostki. D * ma jednak reputację niezwykle złożonej i został całkowicie przestarzały przez znacznie prostszą D * -Lite.
  • Focused D * (1995): Ulepszenie D *, aby przyspieszyć / „więcej w czasie rzeczywistym”. Nie mogę znaleźć żadnych porównań z D * -Lite, ale biorąc pod uwagę, że jest to starszy i D * -Lite mówi się o wiele więcej, zakładam, że D * -Lite jest jakoś lepszy.
  • DynamicSWSF-FP (1996): Przechowuje odległość od każdego węzła do węzła końcowego. Ma dużą konfigurację początkową do obliczenia wszystkich odległości. Po zmianach na wykresie może aktualizować tylko te węzły, których odległości uległy zmianie. Niepowiązane zarówno z A *, jak i D *. Przydatne, gdy po każdej zmianie chcesz znaleźć odległość od wielu węzłów do mety; w przeciwnym razie LPA * lub D * -Lite są zwykle bardziej przydatne.
  • LPA * / przyrostowe A * (2001): LPA * (Lifelong Planowanie A *) , znany również jako przyrostowe A * (a czasem, złudzenia, jak "LPA", choć ma ona żadnego związku z innym algorytmem nazwie LPA) jest połączenie DynamicSWSF-FP i A *. Przy pierwszym uruchomieniu jest dokładnie taki sam jak A *. Jednak po drobnych zmianach na wykresie kolejne wyszukiwania z tej samej pary początkowej / końcowej są w stanie wykorzystać informacje z poprzednich serii, aby drastycznie zmniejszyć liczbę węzłów, które należy zbadać, w porównaniu do A *. To jest dokładnie mój problem, więc wygląda na to, że LPA * będzie moim najlepszym dopasowaniem. LPA * różni się od D * tym, że zawsze znajduje najlepszą ścieżkę od tego samego początku do tego samego końca; nie jest używane, gdy punkt początkowy się porusza(takie jak jednostki poruszające się po początkowej najlepszej ścieżce) . Jednak...
  • D * -Lite (2002): Ten algorytm wykorzystuje LPA * do naśladowania D *; oznacza to, że używa LPA *, aby znaleźć nową najlepszą ścieżkę dla jednostki, gdy porusza się wzdłuż początkowej najlepszej ścieżki, a wykres zmienia się. D * -Lite jest uważane za znacznie prostsze niż D *, a ponieważ zawsze działa co najmniej tak szybko, jak D *, całkowicie przestarzałe D *. Dlatego nigdy nie ma powodu, aby używać D *; zamiast tego użyj D * -Lite.
• Ruch pod dowolnym kątem
  • Pole D * (2007): wariant D * -Lite, który nie ogranicza ruchu do siatki; to znaczy najlepsza ścieżka może sprawić, że jednostka będzie się poruszać pod dowolnym kątem, a nie tylko 45- (90-) stopni między punktami siatki. Został wykorzystany przez NASA do wyszukiwania ścieżek dla łazików marsjańskich.
  • Theta * (2007): wariant A *, który daje lepsze (krótsze) ścieżki niż pole D *. Ponieważ jednak jest oparty na A *, a nie D * -Lite, nie ma możliwości szybkiego przeplatania, jakie ma pole D *. Zobacz także .
  • Incremental Phi * (2009): Najlepsze z obu światów. Wersja Theta *, która jest inkrementalna (aka pozwala na szybkie przebudowywanie)
• Przenoszenie punktów docelowych
  • GAA * (2008): GAA * (Uogólniony adaptacyjny A *) to wariant A *, który obsługuje ruchome punkty docelowe. Jest to uogólnienie jeszcze wcześniejszego algorytmu o nazwie „Moving Target Adaptive A *”
  • GRFA * (2010): GFRA * (Generalized Fringe-Retrieving A *) wydaje się (?) Być uogólnieniem GAA * na dowolne wykresy (tj. Nie ogranicza się do 2D) przy użyciu technik z innego algorytmu zwanego FRA *.
  • MTD * -Lite (2010): MTD * -Lite (Moving Target D * -Lite) to „rozszerzenie D * Lite, które wykorzystuje zasadę uogólnionego wyszukiwania Fringe-Retrieving A *” do szybkiego przeszukiwania ruchomych obiektów docelowych.
  • Tree-AA * (2011): (???) Wydaje się być algorytmem do wyszukiwania nieznanego terenu, ale opiera się na Adaptive A *, podobnie jak wszystkich innych algorytmach w tej sekcji, więc umieściłem go tutaj. Nie jestem pewien, jak to się ma do innych w tej sekcji.
• Szybki / nieoptymalny
  • Anytime D * (2005): Jest to wariant D * -Lite „Anytime” , wykonywany przez połączenie D * -Lite z algorytmem o nazwie Anytime Repairing A * . Algorytm „Anytime” to taki, który może działać w dowolnych ograniczeniach czasowych - na początku bardzo szybko znajdzie bardzo nieoptymalną ścieżkę, a następnie ulepszy tę ścieżkę, im więcej czasu jej poświęci.
  • HPA * (2004): HPA * (Hierarchical Path-Finding A *) służy do wyszukiwania ścieżek dużej liczby jednostek na dużym wykresie, na przykład w grach wideo RTS (strategia czasu rzeczywistego) . Wszystkie będą miały różne lokalizacje początkowe i potencjalnie różne lokalizacje końcowe. HPA * dzieli wykres na hierarchię, aby szybko znaleźć „prawie optymalne” ścieżki dla wszystkich tych jednostek znacznie szybciej niż uruchamianie A * na każdym z nich osobno. Zobacz też
  • PRA * (2005): Z tego, co rozumiem, PRA * (Częściowe udoskonalenie A *) rozwiązuje ten sam problem co HPA *, ale w inny sposób. Oba mają „podobną charakterystykę wydajności”.
  • HAA * (2008): HAA * (Hierarchical Annotated A *) to uogólnienie HPA *, które pozwala na ograniczone przemieszczenie niektórych jednostek na niektórych terenach (np. Mała ścieżka, którą niektóre jednostki mogą przejść, ale większe nie; lub dziurę, którą mogą przelecieć tylko jednostki latające; itp.)
• Inne / nieznane
  • LPA (1997): LPA (algorytm znajdowania pętli bez pętli) wydaje się być algorytmem routingu tylko w niewielkim stopniu związanym z problemami, które rozwiązują inne algorytmy tutaj. Wspominam o tym tylko dlatego, że ten artykuł jest myląco (i niepoprawnie) odnoszony w kilku miejscach w Internecie jako artykuł przedstawiający LPA *, co nie jest.
  • LEARCH (2009): LEARCH to kombinacja algorytmów uczenia maszynowego, służąca do uczenia robotów samodzielnego wyszukiwania prawie optymalnych ścieżek. Autorzy sugerują połączenie LEARCH z polem D * w celu uzyskania lepszych wyników.
  • BDDD * (2009): ??? Nie mam dostępu do gazety.
  • SetA * (2002): ??? Jest to najwyraźniej wariant A *, który wyszukuje w modelu „binarnego schematu decyzyjnego” (BDD) na wykresie? Twierdzą, że w niektórych przypadkach działa „kilka rzędów wielkości szybciej niż A *” . Jednak, jeśli dobrze rozumiem, to są przypadki, gdy każdy węzeł na wykresie ma wiele krawędzi?

Biorąc to wszystko pod uwagę, wydaje się, że LPA * najlepiej pasuje do mojego problemu.

Podczas używania D *, D * -Lite lub dowolnego z algorytmów przyrostowych w tej kategorii istnieje duże zastrzeżenie (i warto zauważyć, że to zastrzeżenie rzadko jest wymieniane w literaturze). Tego rodzaju algorytmy wykorzystują wyszukiwanie odwrócone. Oznacza to, że obliczają koszty na zewnątrz od węzła celu, jak fala rozciągająca się na zewnątrz. Kiedy zmieniają się koszty krawędzi (np. Dodajesz lub usuwasz ścianę w swoim przykładzie), wszystkie one mają różne skuteczne strategie tylko aktualizacji podzbioru zbadanych (zwanych „odwiedzonymi”) węzłów, na które wpływ mają te zmiany.

Duże zastrzeżenie polega na tym, że lokalizacja tych zmian w odniesieniu do lokalizacji celu ma ogromną różnicę w wydajności algorytmów. W różnych artykułach i mojej pracy dyplomowej pokazałem, że jest całkowicie możliwe, że w najgorszym przypadku działanie któregokolwiek z tych algorytmów przyrostowych jest gorsze niż wyrzucenie wszystkich informacji i rozpoczęcie od nowa z czymś niekrementalnym, jak zwykły stary A *.

Gdy zmienione informacje o kosztach są blisko obwodu rozszerzającego się frontu wyszukiwania („odwiedzanego” regionu), niewiele ścieżek musi się zmienić, a aktualizacje przyrostowe są szybkie. Istotnym przykładem jest robot mobilny z czujnikami przymocowanymi do jego korpusu. Czujniki widzą świat tylko w pobliżu robota, dlatego zmiany zachodzą w tym regionie. Ten region jest punktem początkowym wyszukiwania, a nie celem, więc wszystko działa dobrze, a algorytmy bardzo skutecznie aktualizują optymalną ścieżkę, aby poprawić zmiany.

Gdy zmienione informacje o kosztach są bliskie celowi wyszukiwania (lub twój scenariusz widzi lokalizacje zmiany celu, a nie tylko początek), algorytmy te ulegają katastrofalnemu spowolnieniu. W tym scenariuszu prawie wszystkie zapisane informacje muszą zostać zaktualizowane, ponieważ zmieniony region jest tak blisko celu, że prawie wszystkie wstępnie obliczone ścieżki przechodzą przez zmiany i muszą zostać ponownie ocenione. Ze względu na obciążenie związane z przechowywaniem dodatkowych informacji i obliczeń w celu aktualizacji przyrostowych ponowna ocena w tej skali jest wolniejsza niż nowy początek.

Ponieważ wydaje się, że Twój przykładowy scenariusz pozwala użytkownikowi przesunąć dowolną ścianę, której pragniesz, ten problem wystąpi, jeśli użyjesz D *, D * -Lite, LPA * itp. Wydajność algorytmu będzie zmienna w zależności od użytkownika Wejście. Ogólnie rzecz biorąc „to zła rzecz” ...

Na przykład grupa Alonzo Kelly z CMU miała fantastyczny program o nazwie PerceptOR, który próbował łączyć roboty naziemne z robotami lotniczymi, wszystkie dzieląc się informacjami o postrzeganiu w czasie rzeczywistym. Kiedy próbowali użyć helikoptera do zapewnienia aktualizacji kosztów w czasie rzeczywistym w systemie planowania pojazdu naziemnego, natknęli się na ten problem, ponieważ śmigłowiec mógł latać przed pojazdem naziemnym, obserwując zmiany kosztów bliżej celu, a tym samym spowalniając w dół ich algorytmów. Czy omawiali tę interesującą obserwację? Nie. W końcu najlepiej udało im się latać helikopterem bezpośrednio nad pojazdem naziemnym - co czyni go najdroższym masztem czujnikowym na świecie. Jasne, jestem małostkowy. Ale to duży problem, o którym nikt nie chce rozmawiać - i powinni,

Jest tylko garść artykułów na ten temat, głównie przeze mnie. Z prac napisanych przez autorów lub studentów autorów oryginalnych prac wymienionych w tym pytaniu mogę pomyśleć tylko o jednym, który faktycznie wspomina o tym problemie. Likhachev i Ferguson sugerują próbę oszacowania wymaganej skali aktualizacji i opróżnienia przechowywanych informacji, jeśli szacunkowa aktualizacja potrwa dłużej niż nowy początek. Jest to całkiem rozsądne obejście, ale są też inne. Mój doktor uogólnia podobne podejście w szerokim zakresie problemów obliczeniowych i wykracza poza zakres tego pytania, jednak odniesienia mogą być przydatne, ponieważ zawiera dokładny przegląd większości tych algorytmów i nie tylko. Zobacz http://db.acfr.usyd.edu.au/download.php/Allen2011_Thesis.pdf?id=2364 dla szczegółów.

Główną ideą jest zastosowanie algorytmu przyrostowego, który jest w stanie skorzystać z poprzednich obliczeń, gdy początkowa obliczona trasa zostanie zablokowana. Jest to często badane w kontekście robotów, nawigacji i planowania.

Koenig i Likkachev, Szybkie zastępowanie nawigacji w nieznanym terenie, IEEE Transactions on Robotics, obj. 21, nr 3, czerwiec 2005 wprowadza D * Lite. Można bezpiecznie powiedzieć, że D * jest przestarzały w tym sensie, że D * Lite jest zawsze tak szybki jak D *. Ponadto D * jest złożony, trudny do zrozumienia, analizy i rozszerzenia. Rycina 9 podaje pseudokod dla D * Lite, a Tabela 1 pokazuje wyniki eksperymentalne z D * Lite w porównaniu do BFS, wstecznego A *, do przodu A *, DynamicSWSF-P i D *.

Nie znam wymienionych przez ciebie nowych algorytmów (Anytime D *, Field D *, LEARCH). Ostatnio widziałem robota, który używał D * Lite do planowania w środowisku z przypadkowymi spacerowiczami. W tym sensie nie sądzę, że D * Lite jest w żadnym wypadku przestarzały. Jeśli chodzi o twój praktyczny problem, myślę, że próba zwykłego inżynieryjnego sposobu nie zaszkodzi: podejmij jakieś podejście, a jeśli to nie pasuje do twoich potrzeb, spróbuj czegoś innego (bardziej złożonego).

Chciałbym dodać coś o szybkim badaniu losowych drzew lub RRT. Podstawowy pomysł ma dobrą dyskusję w Internecie, ale prawdopodobnie bezpiecznie jest zacząć od linków na stronie Wikipedii oraz od oryginalnych artykułów Kuffnera i LaValle'a na ten temat.

Najważniejszą cechą RRT jest to, że mogą radzić sobie z bardzo cennymi przestrzeniami o bardzo dużych wymiarach bez zadławienia. Potrafią poradzić sobie z dynamiką, nie są optymalne, ale są probabilistycznie kompletne (gwarantowane, że odniesie sukces, jeśli czas obliczeń zbliża się do nieskończoności) i są w stanie poradzić sobie z ruchomymi celami. Istnieje kilka rozszerzeń, które pozwalają im pracować w przestrzeniach niestatycznych, z których najlepszym wydaje się być wieloczęściowa praca RRT, którą podłączyłem poniżej.

• http://en.wikipedia.org/wiki/Rapidly_exploring_random_tree
• http://swing.adm.ri.cmu.edu/pub_files/pub4/zucker_matthew_2007_1/zucker_matthew_2007_1.pdf

Struktury danych zwane wyroczniami odległości radzą sobie z takimi problemami. Jednak większość wyników badań dotyczy wyłącznie wykresów statycznych .

Jeśli wykresy są siatkami (a zatem i płaskimi), istnieją pewne dynamiczne struktury danych (niejasne, czy stałe są wystarczająco małe dla danej aplikacji):

Dokładnie najkrótsze ścieżki:

Jittat Fakcharoenphol, Satish Rao: wykresy płaskie, ujemne krawędzie wagowe, najkrótsze ścieżki i czas prawie liniowy. J. Comput. Syst. Sci. 72 (5): 868–889 (2006)

Przybliżone najkrótsze ścieżki:

Philip N. Klein, Sairam Subramanian: W pełni dynamiczny program aproksymacji dla najkrótszych ścieżek na wykresach planarnych. Al Algorytmica 22 (3): 235–249 (1998)

Ittai Abraham, Shiri Chechik, Cyril Gavoille: W pełni dynamiczne przybliżone wyrocznie odległościowe dla płaskich wykresów za pomocą zakazanych etykiet odległości. STOC 2012: 1199-1218

W szkole zajmowałem się optymalizacją kolonii mrówek . W niektórych tekstach reklamowano go jako rozwiązanie do ciągłej zmiany wykresów, trasowania sieci itp. To nie jest rozwiązanie inżynieryjne, ale adaptacja tego, w jaki sposób mrówki poruszają się po przeszkodach, rozkładając feromony, aby oznaczyć dobre i złe ścieżki. Nie mam pojęcia, czy to działa na twój problem, ale myślę, że to interesujący punkt widzenia.