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.
