🤖 Nawigator robota — iteracja wartości MDP na żywo

Iteracja wartości to oparty na modelu algorytm programowania dynamicznego służący do rozwiązywania procesu decyzyjnego Markowa (MDP): przestrzeni stanów S, przestrzeni akcji A, znanego modelu przejść P(s'|s,a), funkcji nagrody R(s,a,s') oraz współczynnika dyskontowania γ. Zaczynając od dowolnej funkcji wartości V(s), wielokrotnie stosuje aktualizację optymalności Bellmana V(s) ← max_a Σ_s' P(s'|s,a)[R(s,a,s') + γV(s')] do wszystkich stanów jednocześnie (przebieg synchroniczny). Ponieważ ta aktualizacja jest odwzorowaniem zwężającym przy γ<1, kolejne przebiegi w sposób dowiedziony zbiegają do jedynej optymalnej funkcji wartości V*, na podstawie której optymalną politykę π*(s) = argmax_a Σ_s' P(s'|s,a)[R(s,a,s') + γV*(s')] można odczytać bezpośrednio.

Iteracja wartości jest metodą opartą na modelu: wymaga wcześniejszej znajomości prawdopodobieństw przejść P(s'|s,a) i funkcji nagrody R(s,a,s') i oblicza dokładną wartość oczekiwaną po wszystkich możliwych wynikach każdej akcji w każdym stanie w każdym przebiegu — nie jest w ogóle potrzebna żadna symulacja ani eksploracja środowiska. Q-learning (omówiony w osobnej symulacji uczenia ze wzmocnieniem na tej stronie) jest metodą bezmodelową: agent nie zna P ani R z góry, więc musi faktycznie działać w środowisku, obserwować próbkowane przejścia (s, a, r, s') i stopniowo aktualizować Q(s,a) regułą różnic czasowych Q(s,a) ← Q(s,a) + α[r + γ·max_a' Q(s',a') − Q(s,a)]. Iteracja wartości zbiega do dokładnego V* w ograniczonej liczbie przebiegów, mając dany model; Q-learning zbiega jedynie asymptotycznie, poprzez eksplorację metodą prób i błędów, i nie potrzebuje żadnego jawnego modelu przejść. Ta symulacja celowo implementuje przypadek oparty na modelu, aby wyraźnie odróżnić te dwie rodziny algorytmów.

Prawdziwe roboty i agenci fizyczni rzadko wykonują akcję idealnie — koła się ślizgają, czujniki dryfują, a podłoża są nierówne. Ta symulacja modeluje to za pomocą klasycznego stochastycznego modelu przejść: wybór ruchu w danym kierunku kończy się sukcesem z prawdopodobieństwem P(zamierzone) (regulowanym, domyślnie 0,80), a pozostałe prawdopodobieństwo jest dzielone równo między skręt o 90° w lewo i o 90° w prawo od zamierzonego kierunku. Aktualizacja Bellmana sumuje wszystkie trzy możliwe wyniki ważone ich prawdopodobieństwami, co dokładnie sprawia, że jest to prawdziwy MDP, a nie deterministyczne wyszukiwanie najkrótszej ścieżki — optymalna polityka musi zabezpieczać się przed ryzykiem niezamierzonego zsunięcia się na ścianę lub przeszkodę.

Trzy składniki nagrody łączą się, tworząc R(s,a,s'): niewielki ujemny koszt kroku (domyślnie −0,04) naliczany przy każdym nieterminalnym ruchu, który skłania optymalną politykę do wybierania krótszych ścieżek; kara za uderzenie w przeszkodę/ścianę (domyślnie −0,75) naliczana za każdym razem, gdy przejście jest zablokowane przez ścianę, przeszkodę lub granicę siatki, co skłania politykę do zachowania marginesu bezpieczeństwa wokół przeszkód, zwłaszcza gdy przejścia są zaszumione; oraz terminalna nagroda za cel (+1) otrzymywana przy wejściu do komórki celu, która sprawia, że dotarcie do celu w ogóle się opłaca. Iteracja wartości propaguje wszystkie trzy składniki przez aktualizację Bellmana, więc komórki blisko celu jako pierwsze uzyskują wysokie wartości, a ten sygnał wysokiej wartości rozprzestrzenia się wstecz, przebieg po przebiegu, aż każdy osiągalny stan uzyska dokładne oszacowanie swojego długoterminowego oczekiwanego zwrotu.

Każdy synchroniczny przebieg rejestruje maksymalną bezwzględną zmianę wartości dowolnego stanu, max_s |V_new(s) − V_old(s)|, a symulacja wykreśla tę wielkość w skali logarytmicznej względem numeru przebiegu. Ponieważ operator optymalności Bellmana jest odwzorowaniem zwężającym o współczynniku γ, ta sekwencja maksymalnych zmian gwarantowanie maleje monotonicznie do zera; symulacja ogłasza zbieżność, gdy spadnie ona poniżej 1e-4. W tym momencie V(s) mieści się w niewielkim, ograniczonym błędzie od prawdziwego V*(s), a zachłanna polityka z niej wyprowadzona, π(s) = argmax_a Q(s,a), jest optymalną polityką dla tak skonfigurowanego MDP.

Tak. γ kontroluje, w jakim stopniu wartość stanu jest kształtowana przez nagrody odległe o wiele kroków w przyszłości: przy γ bliskim 1 odległe nagrody za cel propagują się niemal bez osłabienia po całej siatce, więc optymalna polityka planuje daleko naprzód i jest skłonna wybierać dłuższe, bezpieczniejsze objazdy wokół przeszkód. Przy γ bliższym 0,5 przyszłe nagrody są mocno dyskontowane, więc polityka staje się krótkowzroczna — może zaakceptować krótszą, ale bardziej ryzykowną trasę obok przeszkody, ponieważ zdyskontowana wartość dotarcia do celu kilka kroków później nie jest dużo wyższa niż dotarcie do niego krok wcześniej. γ kontroluje też tempo zbieżności: mniejsze γ sprawia, że operator Bellmana zwęża się szybciej, więc niższe współczynniki dyskontowania zwykle zbiegają w mniejszej liczbie przebiegów.