🤖 Robot Navigator — Value Iteration MDP dal vivo

La value iteration è un algoritmo di programmazione dinamica model-based per risolvere un Processo Decisionale di Markov (MDP): uno spazio degli stati S, uno spazio delle azioni A, un modello di transizione noto P(s'|s,a), una funzione di ricompensa R(s,a,s') e un fattore di sconto γ. Partendo da una funzione di valore V(s) arbitraria, applica ripetutamente il backup di ottimalità di Bellman V(s) ← max_a Σ_s' P(s'|s,a)[R(s,a,s') + γV(s')] a tutti gli stati simultaneamente (uno sweep sincrono). Poiché questo backup è una mappa di contrazione per γ<1, sweep ripetuti convergono dimostrabilmente all'unica funzione di valore ottimale V*, dalla quale è possibile leggere direttamente la politica ottimale π*(s) = argmax_a Σ_s' P(s'|s,a)[R(s,a,s') + γV*(s')].

La value iteration è model-based: richiede che le probabilità di transizione P(s'|s,a) e la funzione di ricompensa R(s,a,s') siano note in anticipo, e calcola un valore atteso esatto su ogni possibile esito di ogni azione in ogni stato a ogni sweep — non è necessaria alcuna simulazione o esplorazione dell'ambiente. Il Q-learning (trattato nella simulazione dedicata al reinforcement learning di questo sito) è model-free: l'agente non conosce P né R in anticipo, quindi deve effettivamente agire nell'ambiente, osservare transizioni campionate (s, a, r, s') e aggiornare in modo incrementale Q(s,a) con una regola a differenza temporale Q(s,a) ← Q(s,a) + α[r + γ·max_a' Q(s',a') − Q(s,a)]. La value iteration converge al V* esatto in un numero limitato di sweep dato il modello; il Q-learning converge solo asintoticamente, tramite esplorazione per tentativi ed errori, e non necessita di alcun modello di transizione esplicito. Questa simulazione implementa deliberatamente il caso model-based in modo che le due famiglie di algoritmi possano essere distinte con chiarezza.

I robot reali e gli agenti fisici raramente eseguono un'azione in modo perfetto — le ruote slittano, i sensori derivano, i pavimenti sono irregolari. Questa simulazione modella questo aspetto con un classico modello di transizione stocastico: scegliere di muoversi in una data direzione ha successo con probabilità P(intended) (regolabile, valore predefinito 0.80), mentre la probabilità restante è divisa equamente tra una deviazione di 90° a sinistra e una di 90° a destra rispetto alla direzione voluta. Il backup di Bellman somma tutti e tre i possibili esiti pesati per le rispettive probabilità, ed è esattamente questo che rende l'ambiente un vero MDP anziché una ricerca deterministica del percorso più breve — la politica ottimale deve tutelarsi contro la possibilità di uno scivolamento indesiderato contro un muro o un ostacolo.

Tre termini di ricompensa si combinano per definire R(s,a,s'): un piccolo costo per passo negativo (predefinito −0.04) applicato a ogni mossa non terminale, che spinge la politica ottimale verso percorsi più brevi; una penalità per urto contro ostacolo/muro (predefinita −0.75) applicata ogni volta che una transizione è bloccata da un muro, un ostacolo o il confine della griglia, che spinge la politica a mantenere un margine di sicurezza attorno agli ostacoli, soprattutto quando le transizioni sono rumorose; e una ricompensa terminale per l'obiettivo (+1) ricevuta entrando nella cella obiettivo, che è ciò che rende utile raggiungere l'obiettivo. La value iteration propaga tutte e tre attraverso il backup di Bellman, così le celle vicine all'obiettivo acquisiscono per prime valori elevati, e questo segnale ad alto valore si propaga all'indietro, sweep dopo sweep, finché ogni stato raggiungibile non ha una stima accurata del suo ritorno atteso a lungo termine.

Ogni sweep sincrono registra la variazione assoluta massima nel valore di uno stato qualsiasi, max_s |V_new(s) − V_old(s)|, e la simulazione traccia questa quantità in scala logaritmica rispetto al numero di sweep. Poiché l'operatore di ottimalità di Bellman è una γ-contrazione, questa sequenza di delta massimi è garantita ridursi in modo monotono verso zero; la simulazione dichiara la convergenza quando scende sotto 1e-4. A quel punto V(s) si trova entro un errore piccolo e limitato rispetto al vero V*(s), e la politica greedy estratta da essa, π(s) = argmax_a Q(s,a), è la politica ottimale per l'MDP così configurato.

Sì. γ controlla quanto il valore di uno stato sia influenzato dalle ricompense molti passi nel futuro: con γ vicino a 1, le ricompense dell'obiettivo lontano si propagano quasi senza attenuazione su tutta la griglia, quindi la politica ottimale pianifica con largo anticipo ed è disposta a compiere deviazioni più lunghe ma più sicure attorno agli ostacoli. Con γ più vicino a 0.5, le ricompense future vengono scontate drasticamente, quindi la politica diventa miope — può accettare un percorso più breve ma più rischioso vicino a un ostacolo, perché il valore scontato di raggiungere l'obiettivo qualche passo più tardi non vale molto di più rispetto a raggiungerlo un passo prima. γ controlla anche il tasso di convergenza: un γ più piccolo fa contrarre più rapidamente l'operatore di Bellman, quindi fattori di sconto più bassi in genere convergono con meno sweep.