Un problema MDP parzialmente osservabile ( POMDP )

Un problema POMDP è un processo decisionale di Markov ( MDP) in un ambiente parzialmente osservabile ( PO ). In questi casi, l'agente non conosce il proprio stato corrente.

Un esempio pratico. L'agente deve arrivare alla casella C2 ma l'ambiente è parzialmente osservabile. Ad esempio, è al buio. Quindi, l'agente non conosce la sua posizione nella mappa, né quali azioni consentono di raggiungere l'obiettivo.
un esempio di problema decisionale di Markov parzialmente osservabile

E' un tipico problema non deterministico in cui la soluzione va cercata tramite un modello probabilistico.

La differenza tra MDP e POMDP

In un problema MDP l'agente conosce in quale stato si trova.

Quindi, per trovare la politica ottimale π(s), l'agente fa direttamente riferimento al proprio stato reale s.

L'agente si limita a eseguire la politica raccomandata per lo stato corrente.

un esempio di problema decisionale di Markov ( MDP ) pienamente osservabile

In un problema POMDP parzialmente osservabile, invece, l'agente non conosce lo stato s in cui si trova.

Nota. Nel problema POMDP l'agente non sa di trovarsi nella casella C2. In base all'osservazione diretta, l'agente sa di trovarsi in una casella di confine con un solo muro e di non aver raggiunto la casella obiettivo C2. Quindi, l'agente potrebbe trovarsi anche in B1 o in B3.

In questi casi, la politica ottimale π dipende dagli stati credenza.

L'agente ipotizza una distribuzione di stati possibili in cui potrebbe trovarsi ( stati credenza ) e associa a ciascuna una probabilità.

un esempio di problema POMDP

Nota. Nella precedente situazione l'agente ha tre stati credenza ( A2, B1 , B3 ). Ogni stato credenza ha una probabilità del 33%.

Per decidere l'agente deve ridurre l'incertezza con la raccolta di informazioni aggiuntive tramite l'aggiunta di un modello sensoriale delle osservazione.

Quindi un problema POMDP è decisamente più difficile dei problemi MDP.

Il modello POMDP

Il processo POMDP ( pomdipi ) è composto da un modello di transizione, una funzione di ricompensa e un modello sensoriale.

Nota. Si distingue dal processo MDP per l'aggiunta del modello sensoriale ( o modello delle osservazioni ).

A cosa serve il modello delle osservazioni?

Il modello delle osservazioni fornisce le probabilità degli stati (s) a partire dall'osservazione (o).

il modello POMDP

In base alle azioni effettuate dall'agente (a) e dall'osservazione corrente della situazione (s), il modello delle osservazioni elabora una distribuzione delle probabilità degli stati.

C'è però un'altra differenza importante rispetto al modello MDP da considerare. Nel modello POMDP L'agente non conosce con certezza lo stato corrente (s) ossia la posizione (s) in cui si trova.

Quindi, il modello di transizione non può essere tra lo stato corrente e lo stato successivo T(s,a,s').

Nel modello POMDP il modello di transizione è tra lo stato credenza corrente, ossia dove l'agente potrebbe trovarsi, e lo stato corrente successivo T(b,a,b').

il modello POMDP

Cos'è lo stato credenza?

Lo stato credenza b è una distribuzione di probabilità.

Ogni elemento dello stato credenza b(s) indica la probabilità p(s) che l'agente si trovi in un determinato stato (s) ossia posizione della mappa.

Il nuovo modello di transizione T(b,a,b') è il seguente:

il nuovo modello di transizione

Questo modello di transizione calcola la probabilità di passare dallo stato credenza b a b' compiendo l'azione a.

In conclusione, per risolvere un problema POMDP nello spazio degli stati fisici, si può trasformare il problema in un MDP nello spazio degli stati credenza.

Un esempio pratico

L'agente deve raggiungere l'obiettivo nella casella C2 ed evitare la trappola nella casella C3.

L'ambiente è parzialmente osservabile, quindi l'agente non conosce la sua posizione nella mappa.

un esempio di problema decisionale di Markov parzialmente osservabile

Non conoscendo in quale casella si trova, l'agente non può decidere una politica ottimale.

Inoltre, l'agente è al buio e non vede nulla intorno a sé.

Secondo il modello delle osservazioni la distribuzione delle probabilità è la seguente:

un esempio di modello sensoriale

La probabilità di trovarsi nella casella A1 è uguale a 1/7 ossia p=0.14.

La stessa probabilità ( 14% ) si ha anche nelle caselle A2, A3, B1, B2, B3 e C1.

Nota. Nel computo escludo le caselle C2 (obiettivo) e C3 (trappola) perché se fosse là l'agente se ne accorgerebbe. Quindi la probabilità di trovarsi in queste due caselle è zero. Per questa ragione la probabilità è una su sette pur essendo nove le caselle della mappa.

Questa distribuzione di probabilità rappresenta lo stato credenza iniziale (b).

lo stato di credenza iniziale

Per decidere la mossa da compiere si utilizza un algoritmo simile a quello del filtraggio ( monitoring ).

Dato lo stato credenza corrente l'agente decide l'azione migliore possibile (a).

la decisione (azione migliore) dipende dallo stato credenza corrente b(s)

In questo caso l'azione ottimale (a) dipende dallo stato-credenza perché l'agente non conosce la casella in cui si trova.

Nota. Nei problemi MDP invece l'azione ottimale dipende dallo stato corrente perché l'agente sa esattamente dove si trova nella mappa.

Dopo aver attuato l'azione ottimale (a), l'agente si sposta dallo stato s allo stato s' (stato di credenza successivo).

A questo punto l'agente osserva l'ambiente circostante per aggiorna le informazioni del modello sensoriale O.

Poi calcola il nuovo stato credenza b'(s') tramite la seguente formula:

il modello delle osservazioni

Ad esempio, l'agente si sposta a destra (a) giungendo su una nuova casella.

Nella nuova casella non ha osservato (o) né il traguardo, né la trappola.

Quindi, secondo il modello delle osservazioni (O), adesso l'agente dovrebbe trovarsi in B2, B3, B4 o C1.

il ricalcolo dello stato credenza

Nota. L'agente esclude A1, A2, A3 perché non potrebbe raggiungerle spostandosi a destra. Così facendo ha ottenute nuove informazioni sulla sua posizione reale.

Il nuovo stato credenza è b(s') è composto da quattro caselle possibili { B1, B2, B3, C1 }.

Ogni casella dello stato credenza ha una probabilità pari a 1/4 ossia 0.25 ( p=25% ).

Come decide l'agente?

Quando l'agente deve decidere come muoversi, non conosce ancora le conseguenze dell'azione.

Quindi non può accedere alle osservazioni (o) sullo stato successivo s'.

Si potrebbe pensare che la scelta di una direzione sia casuale. In realtà, non è così.

L'agente deve scegliere l'azione (a) che conduce dallo stato credenza attuale b(s) al migliore dei possibili stati credenza possibili successivi b(s').

la scelta dello stato credenza successivo

Abbiamo trovato il modello di transizione.

Ora scriviamo anche la funzione di ricompensa in funzione dello stato credenza.

la funzione di ricompensa in base allo stato credenza

Possiamo così trasformare il modello POMDP in un modello MDP sugli stati credenza.

il modello MDP costruito nello spazio degli stati-credenza

Per capire quali stati-credenza sucessivi (b') sono possibili, l'agente deve analizzare le azioni possibili a partire dallo stato-credenza attuale (b).

Le azioni possibili sono le seguenti:

  1. spostarsi a destra
  2. spostarsi a sinistra
  3. spostarsi in alto
  4. spostarsi in basso

Se l'agente scegliesse di spostarsi a destra avrebbe le sequenti possibili osservazioni:

le possibili osservazioni dello spostamento a destra

Se si spostasse a sinistra avrebbe una le seguenti osservazioni:

le osservazioni dello spostamento a sinistra

Nota. In questo caso non potrebbe osservare né di raggiungere l'obiettivo, né la trappola, perché sono logicamente impossibili da trovare spostandosi a sinistra.

Se invece si spostasse in alto avrebbe le seguenti osservazioni

le osservazioni dello spostamento in alto

Infine, se si spostasse in basso avrebbe le seguenti osservazioni:

le osservazioni dopo lo spostamento in basso

Il passo 1

L'agente decide il primo spostamento.

Secondo lo stato credenza iniziale, l'agente potrebbe trovarsi in una delle sette caselle ( A1, A2, A3, B1, B2, B3, C1 ) con pari probabilità ( p=1/7=0.14 ).

lo stato di credenza iniziale

Le osservazioni possibili dopo la mossa sono le seguenti:

  1. L'agente si sposta in una casella vuota
    (16 possibilità)
  2. L'agente si sposta nella casella obiettivo (C2)
    (2 possibilità)
  3. L'agente si sposta nella casella trappola (C3)
    (1 possibilità)
  4. L'agente non si sposta a causa di un muro
    (9 possibilità)

Nota. Quando deve decidere, l'agente non può ancora osservare il feed-back dell'azione. Quindi, considera tutte le possibili osservazioni possibili.

Se l'agente decidesse di spostarsi verso il basso ( azione = down ) avrebbe le seguenti probabilità di osservare questi eventi:

le probabilità delle osservazioni dopo l'azione DOWN

Nota. Per spiegare il procedimento di calcolo prendo come riferimento la prima tabella. Secondo il modello delle osservazioni O(s',o) , l'agente può osservare di raggiungere l'obiettivo (o) solo quando si trova effettivamente nella casella C2. Quindi soltanto questa possibilità è uguale a 1 nella colonna O(s',o). Analizzando gli stati possibili di provenienza (s), la casella C2 (s') è raggiungibile con uno spostamento verso il basso (a=down) soltanto dalla casella C1 (s). Quindi T(s,a,s') è uguale a 1 soltanto per s=C1 quando a=down e s'=C2. La probabilità dello stato credenza b(s) in C1 è uguale a 1/7 ossia 0.14. Essendoci soltanto questa possibilità, la sommatoria è uguale a 0.14. Quindi, la probabilità di raggiungere l'obiettivo con uno spostamento verso il basso nello stato credenza iniziale è pari al 14%.

Se invece si spostasse verso l'alto ( azione = up ) le probabili osservazioni sarebbero le sequenti:

le probabilità di scontrare a un muro dopo lo spostamento verso l'alto

Se si spostasse a sinistra ( a = left )

le probabilità degli eventi se si spostasse a sinistra

Se si spostasse a destra ( azione = right ) avrebbe le seguenti probabilità di evento

le probabili osservazioni dopo uno spostamento a destra

Ricapitolando, le probabilità delle possibili osservazioni (o) dopo la prima azione (a) nel modello di transizione T(b,a,b') sono le seguenti

le probabilità delle osservazioni condizionate alle azioni

A questo punto bisogna calcolare la funzione di ricompensa per ogni stato credenza R(b).

la ricompensa

All'agente converrebbe muovere verso il basso ( a=down ) perché è l'azione che massimizza l'utilità attesa.

Dopo la mossa, l'agente riaggiorna lo stato di credenza attuale considerando le osservazioni rilevate dopo l'azione e così via.

Esempio. Se dopo lo spostamento verso il basso l'agente incontra il muro, il nuovo stato credenza diventa il seguente:
il nuovo stato credenza

Il procedimento per decidere la seconda mossa è simile alla prima.

Tuttavia, nei passi successivi l'agente ha più informazioni sulla sua posizione.

Quindi, passo dopo passo, la politica ottimale del modello POMDP tende a eguagliare quella di un modello MDP.

Nota. La sequenza di azioni per raggiungere l'obiettivo nel precedente modello POMDP è down + up + right ( + right ). In tre o quattro mosse l'agente raggiunge l'obiettivo.
la politica ottimale per raggiungere l'obiettivo nel modello POMDP
L'agente non conosceva la sua posizione iniziale nella mappa ma, basandosi sugli stati-credenza, è riuscito comunque a risolvere il problema, riducendo al minimo i costi e i rischi dell'esplorazione ( raccolta delle informazioni ).



Per scrivere un commento

knowledge base

Libri di approfondimento

Il ragionamento artificiale