Dlaczego Reinforcement Learning jest tak rzadko stosowany w poszukiwaniu ścieżek?

Czcigodny algorytm teoretyczny grafu z najkrótszą ścieżką A * i kolejne ulepszenia (np. Hierarchiczny opis z komentarzem A *) to wyraźnie technika wyboru ścieżki wyszukiwania w grze.

Zamiast tego wydaje mi się, że RL jest bardziej naturalnym paradygmatem do poruszania postacią po polu gry.

A jednak nie znam żadnego twórcy gier, który wdrożył silnik wyszukiwania ścieżek oparty na Reinforcement Learning. (Nie wnioskuję z tego, że zastosowanie RL w wyszukiwaniu ścieżek wynosi 0, tylko że jest bardzo małe w stosunku do A * i przyjaciół.)

Bez względu na powód, nie dzieje się tak dlatego, że ci programiści nie są świadomi RL, o czym świadczy fakt, że RL jest często używany gdzie indziej w silniku gry.

To pytanie nie jest pretekstem do wyrażenia opinii na temat RL w poszukiwaniu ścieżek; w rzeczywistości zakładam, że milcząca preferencja dla A * i in. ponad RL jest poprawne - ale ta preferencja oczywiście nie jest dla mnie oczywista i jestem bardzo ciekawy tego powodu, szczególnie od każdego, kto próbował użyć RL do wyszukiwania ścieżek.

Wyobrażam sobie, że to dlatego, że ponieważ nie dostaniesz żadnego użytecznego uogólnienia polityki z niczego poza problemami związanymi z zabawkami, a funkcja nagrody będzie podejrzanie wyglądać jak heurystyka A ​​*, perspektywa użycia RL wydaje się być naprawdę przebudowany, nieefektywny sposób uzyskiwania wyników, które w najlepszym razie są identyczne z A *, ale prawdopodobnie nie będą prawie tak dobre.

Może to być niesprawiedliwe wobec RL, a jeśli tak, to chciałbym dowiedzieć się, dlaczego, ale tak naprawdę nie widzę nic, co by to wskazywało.

Wielu z nas pamięta też, jak wyglądało szukanie ścieżek w grach przed powszechnym przyjęciem A *, i nie są chętni do narzucania graczom niczego przypominającego te dni, ani ponoszenia konsekwencji rynkowych.

Nie wiedząc wiele o RL, postaram się odpowiedzieć na twoje pytanie innymi pytaniami:

Czy używając RL możesz ustalić, czy możliwe jest dotarcie do punktu A z punktu B?

Czy RL może zagwarantować powtarzalne / spójne / testowalne zachowanie nawigacyjne?

Jak wypada porównanie wymagań dotyczących pamięci i czasu pracy procesora w porównaniu z A *? Podobnie, ile można wstępnie obliczyć w porównaniu do, powiedzmy, siatek nawigacyjnych?

Jak działa RL w środowisku z dynamiczną kolizją?

O ile trudniejsze jest prawidłowe zrozumienie i wdrożenie RL w porównaniu z, powiedzmy, zachowaniami sterującymi?

Czy są jacyś dobrzy dostawcy oprogramowania pośredniego dla RL?

Być może te pytania pomogą ci w udzieleniu odpowiedzi.

Jestem zdezorientowany sugestią, że RL jest „bardziej naturalnym paradygmatem”. Nie widzę, w jaki sposób uczenie się zbrojenia mapuje domenę problemu w tak czysty lub dokładny sposób, jak w przypadku wyszukiwania grafów. Zazwyczaj nie chcesz, aby agent się uczył - zakładałeś, że już zna trasę. Zamiast tego chcesz, aby wybrali i wykorzystali najbardziej bezpośrednią dostępną trasę, a wyszukiwanie wykresów ułatwia to w prawie optymalny sposób. Jeśli użyjesz RL offline, aby obliczyć najlepszy kierunek, jaki należy obrać w danym węźle dla dowolnego miejsca docelowego, w rezultacie przyniosłoby to zasadniczo ekwiwalent A *, z wyjątkiem wymagającej znacznie większej pamięci *, a także wymagającej od deweloperów bardzo ostrożnego upewnij się, że wszystkie węzły zostały odpowiednio zbadane podczas szkolenia. Trening przyniesie po prostu wartość, którą możemy już bardzo dobrze oszacować za pomocą równania Pitagorasa, ponieważ z góry wiemy, że wykres jest zgodny z euklidesowymi regułami odległości. (Nie dotyczy to oczywiście wszystkich sytuacji, w których można zastosować wyszukiwanie grafów i / lub uczenie się przez wzmocnienie.)

(Jeśli chodzi o problem z pamięcią: jeśli miałeś 1000 możliwych skwantyzowanych pozycji na mapie, to 1000 węzłów plus 1000 * krawędzi M (gdzie M jest średnią liczbą węzłów osiągalnych z dowolnego innego węzła). To, plus heurystyka, wystarcza dla A * do działania. Aby nauka zbrojenia działała, przynajmniej tak, jak ją sobie wyobrażam, potrzebujesz również 1000 wpisów dla każdej z tych 1000 * krawędzi M, aby zdobyć wartość nagrody za podążanie za tą krawędzią dla dowolnego z 1000 możliwych miejsc docelowych. To dużo danych - i każdy ich fragment musi być dość dokładny, aby uniknąć pętli, objazdów lub ślepych zaułków.

Wyszukiwanie ścieżek jest stosunkowo „rozwiązanym” problemem, RL nie.

Dzięki A * programiści mogą szybko tworzyć heurystykę i z czasem ją ulepszać. RL (mówię o Q-Learning, odnosząc się tutaj do RL), wymaga czasu, aby obliczyć najlepsze wskaźniki uczenia się i czynniki rabatowe (czas, który warto poświęcić na inne aspekty gry).

To naprawdę zależy od rodzaju gry. Jeśli wszystko w grze jest nieruchome, bardziej efektywne jest użycie wyszukiwania A *. Jeśli jednak w tym samym obszarze poruszają się inni ludzie, wyszukiwanie A * gwarantuje niepowodzenie. Wyszukiwanie * nie ma pojęcia, dokąd zmierzają inni gracze. Z drugiej strony RL może modelować zachowanie innych graczy i znaleźć lepszą ścieżkę uwzględniającą ruch innych graczy.