Un procés de decisió de Màrkov parcialment observable (POMDP) és una generalització d'un procés de decisió de Màrkov (MDP). Un POMDP modela un procés de decisió d'agent en què s'assumeix que la dinàmica del sistema està determinada per un MDP, però l'agent no pot observar directament l'estat subjacent. En canvi, ha de mantenir un model de sensor (la distribució de probabilitat de diferents observacions donat l'estat subjacent) i el MDP subjacent. A diferència de la funció de política de l'MDP que assigna els estats subjacents a les accions, la política del POMDP és una assignació de l'historial d'observacions (o estats de creença) a les accions.

El marc POMDP és prou general per modelar una varietat de processos de decisió seqüencials del món real. Les aplicacions inclouen problemes de navegació de robots, manteniment de màquines i planificació sota incertesa en general. El marc general dels processos de decisió de Màrkov amb informació imperfecta va ser descrit per Karl Johan Åström el 1965 en el cas d'un espai d'estats discret, i es va estudiar més a fons a la comunitat de recerca operativa, on es va encunyar l'acrònim POMDP. Posteriorment, Leslie P. Kaelbling i Michael L. Littman el van adaptar per a problemes d'intel·ligència artificial i planificació automatitzada.

Una solució exacta a un POMDP produeix l'acció òptima per a cada creença possible sobre els estats del món. L'acció òptima maximitza la recompensa esperada (o minimitza el cost) de l'agent sobre un horitzó possiblement infinit. La seqüència d'accions òptimes es coneix com la política òptima de l'agent per interactuar amb el seu entorn.

Definició Definició formal Un POMDP de temps discret modela la relació entre un agent i el seu entorn. Formalment, un POMDP és una tupla de 7 , on

és un conjunt d'estats, és un conjunt d'accions, és un conjunt de probabilitats de transició condicionals entre estats, és la funció de recompensa. és un conjunt d'observacions, és un conjunt de probabilitats d'observació condicionals, i és el factor de descompte.

En cada període de temps, l'entorn es troba en algun estat L'agent realitza una acció. , cosa que fa que l'entorn passi a l'estat amb probabilitat Al mateix temps, l'agent rep una observació que depèn del nou estat del medi ambient, , i sobre l'acció que s'acaba de dur a terme, , amb probabilitat (o de vegades (depenent del model de sensor). Finalment, l'agent rep una recompensa igual a Aleshores, el procés es repeteix. L'objectiu és que l'agent esculli accions a cada pas de temps que maximitzin la seva recompensa futura descomptada esperada: , on és la recompensa obtinguda en aquell moment El factor de descompte determina quant es prefereixen les recompenses immediates per sobre de les recompenses més llunyanes. Quan a l'agent només li importa quina acció produirà la recompensa immediata esperada més gran; quan L'agent es preocupa per maximitzar la suma esperada de recompenses futures.

Discussió Com que l'agent no observa directament l'estat de l'entorn, ha de prendre decisions sota incertesa sobre l'estat real de l'entorn. Tanmateix, en interactuar amb l'entorn i rebre observacions, l'agent pot actualitzar la seva creença en l'estat real actualitzant la distribució de probabilitat de l'estat actual. Una conseqüència d'aquesta propietat és que el comportament òptim sovint pot incloure accions (de recopilació d'informació) que es duen a terme únicament perquè milloren l'estimació de l'agent de l'estat actual, permetent-li així prendre millors decisions en el futur.

És instructiu comparar la definició anterior amb la definició d'un procés de decisió de Màrkov. Un MDP no inclou el conjunt d'observacions, perquè l'agent sempre coneix amb certesa l'estat actual de l'entorn. Alternativament, un MDP es pot reformular com un POMDP establint el conjunt d'observacions per ser igual al conjunt d'estats i definint les probabilitats condicionals d'observació per seleccionar determinísticament l'observació que correspon a l'estat veritable.

Actualització de creences Després d'haver pres l'acció i observant , un agent necessita actualitzar la seva creença en l'estat en què l'entorn pot estar (o no). Com que l'estat és markovià (per suposició), mantenir una creença sobre els estats només requereix coneixement de l'estat de creença previ, l'acció realitzada i l'observació actual. L'operació es denota A continuació descrivim com es calcula aquesta actualització de creences.

Després d'arribar , l'agent observa amb probabilitat Deixa sigui una distribució de probabilitat sobre l'espai d'estats . denota la probabilitat que l'entorn estigui en l'estat Donat , després de prendre mesures i observant ,

on és una constant normalitzadora amb .

Creença MDP Un estat de creença markovià permet formular un POMDP com un procés de decisió de Màrkov on cada creença és un estat. El POMDP de creença resultant es definirà, doncs, en un espai d'estats continu (fins i tot si el POMDP "originari" té un nombre finit d'estats: hi ha estats de creença infinits (en ) perquè hi ha un nombre infinit de distribucions de probabilitat sobre els estats (de )).

Formalment, el MDP de creença es defineix com una tupla on

és el conjunt d'estats de creença sobre els estats del POMDP, és el mateix conjunt finit d'accions que per al POMDP original, és la funció de transició d'estat de creença, és la funció de recompensa sobre els estats de creença, és el factor de descompte igual a la del POMDP original.

D'aquests, i s'han de derivar del POMDP original. és

on és el valor derivat a la secció anterior i

La funció de recompensa MDP de creença ( ) és la recompensa esperada de la funció de recompensa POMDP sobre la distribució de l'estat de creença:

.

La creença MDP ja no és parcialment observable, ja que en qualsevol moment donat l'agent coneix la seva creença i, per extensió, l'estat de la creença MDP.

Funció política i de valor A diferència del POMDP "originari" (on cada acció només està disponible des d'un estat), en el corresponent MDP de creença tots els estats de creença permeten totes les accions, ja que (gairebé) sempre tens alguna probabilitat de creure que ets en qualsevol estat (originari). Com a tal, especifica una acció per a qualsevol creença .

Aquí se suposa que l'objectiu és maximitzar la recompensa total descomptada esperada en un horitzó infinit. Quan defineix un cost, l'objectiu esdevé la minimització del cost esperat.

La recompensa esperada per la política començant per la creença es defineix com

on és el factor de descompte. La política òptima s'obté optimitzant la recompensa a llarg termini.

on és la creença inicial.

La política òptima, denotada per , dona el valor de recompensa esperat més alt per a cada estat de creença, representat de manera compacta per la funció de valor òptim Aquesta funció de valor és la solució de l'equació d'optimalitat de Bellman:

Per a POMDPs d'horitzó finit, la funció de valor òptima és lineal a trossos i convexa. Es pot representar com un conjunt finit de vectors. En la formulació d'horitzó infinit, un conjunt de vectors finit pot aproximar arbitràriament proper, la forma del qual roman convexa. La iteració de valor aplica l'actualització dinàmica de la programació per millorar gradualment el valor fins a la convergència cap a un funció de valor òptim i preserva la seva linealitat i convexitat a trossos. En millorar el valor, la política millora implícitament. Una altra tècnica de programació dinàmica anomenada iteració de polítiques representa i millora explícitament la política.

Solucions POMDP aproximades A la pràctica, els POMDP sovint són computacionalment difícils de resoldre amb exactitud. Aquesta dificultat sovint es deu a la maledicció de la dimensionalitat o a la maledicció de la història (el fet que les polítiques òptimes poden dependre de tota la història d'accions i observacions). Per abordar aquests problemes, els informàtics han desenvolupat diverses solucions aproximades de POMDP. Aquestes solucions normalment intenten aproximar el problema o la solució amb un nombre limitat de paràmetres, planificar només sobre una petita part de l'espai de creences en línia o resumir la història d'acció-observació de manera compacta.

Teoria POMDP La planificació en POMDP és generalment indecidible. Tanmateix, s'han identificat alguns entorns com a decidibles (vegeu la Taula 2 reproduïda a continuació). S'han considerat diferents objectius. Els objectius de Büchi es defineixen mitjançant autòmats de Büchi. L'abast és un exemple d'una condició de Büchi (per exemple, arribar a un bon estat en què tots els robots són a casa). Els objectius de coBüchi corresponen a traces que no satisfan una condició de Büchi determinada (per exemple, no arribar a un mal estat en què algun robot mor). Els objectius de paritat es defineixen mitjançant jocs de paritat; permeten definir objectius complexos de manera que s'arribi a un bon estat cada 10 passos de temps. L'objectiu es pot satisfer:

gairebé amb tota seguretat, aquesta és la probabilitat de satisfer l'objectiu és 1; positiva, és a dir, la probabilitat de satisfer l'objectiu és estrictament més gran que 0; quantitativa, és a dir, la probabilitat de complir l'objectiu és superior a un llindar determinat.

També considerem el cas de memòria finita en què l'agent és una màquina d'estats finits, i el cas general en què l'agent té una memòria infinita. ObjectiusGairebé segur (memòria infinita)Gairebé segur (memòria finita)Positiu (inf. mem.)Positiu (mem. finita)BüchiEXPTIME -completEXPTIME-completindecidibleEXPTIME-completcoBüchiindecidibleEXPTIME-completEXPTIME-completEXPTIME-completparitatindecidibleEXPTIME-completindecidibleEXPTIME-complet

Aplicacions Els POMDP es poden utilitzar per modelar molts tipus de problemes del món real. Entre les aplicacions destacades hi ha l'ús d'un POMDP en la gestió de pacients amb cardiopatia isquèmica, tecnologia assistiva per a persones amb demència, la conservació dels tigres de Sumatra, en perill crític d'extinció i difícils de detectar, i la prevenció de col·lisions d'aeronaus.

Una aplicació és un cas docent, un problema de nadó plorant, on un pare o una mare ha de decidir seqüencialment si alimentar el nadó basant-se en l'observació de si el nadó plora o no, la qual cosa és una representació imperfecta de l'estat real de gana del nadó.

Referències

Categoria:Probabilitat