Delvis observerbar Markov-beslutsprocess

En delvis observerbar Markov-beslutsprocess ( POMDP ) är en generalisering av en Markov-beslutsprocess (MDP). En POMDP modellerar en agentbeslutsprocess där det antas att systemdynamiken bestäms av en MDP, men agenten kan inte direkt observera det underliggande tillståndet. Istället måste den upprätthålla en sensormodell (sannolikhetsfördelningen av olika observationer givet det underliggande tillståndet) och den underliggande MDP. Till skillnad från policyfunktionen i MDP som kartlägger de underliggande tillstånden till handlingarna, är POMDP:s policy en kartläggning från observationshistoria (eller trostillstånd) till handlingarna.

POMDP-ramverket är tillräckligt generellt för att modellera en mängd olika verkliga sekventiella beslutsprocesser. Tillämpningar inkluderar robotnavigeringsproblem, maskinunderhåll och planering under osäkerhet i allmänhet. Det allmänna ramverket för Markovs beslutsprocesser med ofullkomlig information beskrevs av Karl Johan Åström 1965 i fallet med ett diskret statligt rum, och det studerades vidare inom verksamhetsforskningssamhället där förkortningen POMDP myntades. Den anpassades senare för problem med artificiell intelligens och automatiserad planering av Leslie P. Kaelbling och Michael L. Littman .

En exakt lösning på en POMDP ger den optimala åtgärden för varje möjlig tro över världens stater. Den optimala åtgärden maximerar den förväntade belöningen (eller minimerar kostnaden) för agenten över en möjligen oändlig horisont. Sekvensen av optimala åtgärder är känd som agentens optimala policy för att interagera med sin omgivning.

Definition

Formell definition

En tidsdiskret POMDP modellerar förhållandet mellan en agent och dess miljö. Formellt är en POMDP en 7-tuppel ${\displaystyle (S,A,T,R,\Omega ,O,\gamma )} ,$ där

• $S$ är en uppsättning tillstånd,
• $A$ är en uppsättning åtgärder,
• $T$ är en uppsättning villkorade övergångssannolikheter mellan tillstånd,
• $R:S\times A\to \mathbb {R}$ är belöningsfunktionen.
• $\Omega$ är en uppsättning observationer,
• $O$ är en uppsättning villkorade observationssannolikheter, och
• $\gamma \in [0,1)$ är diskonteringsfaktorn.

Vid varje tidsperiod är miljön i något tillstånd $s\in S$ . Agenten vidtar en åtgärd $a\in A$ , som får miljön att övergå till tillstånd $s'$ med sannolikhet ${\displaystyle T(s$ . Samtidigt får agenten en observation $o\in \Omega$ som beror på omgivningens nya tillstånd, ${\displaystyle s'} ,$ och på den just vidtagna åtgärden, ${ \displaystyle a}$ , med sannolikhet $O(o\mid s',a)$ (eller ibland $O(o\mid s' )$ beroende på sensormodell). Slutligen får agenten en belöning $r$ lika med $R(s,a)$ . Sedan upprepas processen. Målet är att agenten ska välja åtgärder vid varje tidssteg som maximerar dess förväntade framtida rabatterade belöning: $E\left[\sum _{t=0}^{\ infty }\gamma ^{t}r_{t}\right]$ , där $r_{t}$ är belöningen som tjänas in vid tidpunkten $t$ . Rabattfaktorn $\gamma$ bestämmer hur mycket omedelbara belöningar gynnas framför mer avlägsna belöningar. När $\gamma =0$ bryr sig agenten bara om vilken åtgärd som kommer att ge den största förväntade omedelbara belöningen; när $\gamma \rightarrow 1$ bryr sig agenten om att maximera den förväntade summan av framtida belöningar.

Diskussion

Eftersom agenten inte direkt observerar miljöns tillstånd, måste agenten fatta beslut under osäkerhet om det verkliga miljötillståndet. Genom att interagera med omgivningen och ta emot observationer kan agenten emellertid uppdatera sin tro på det sanna tillståndet genom att uppdatera sannolikhetsfördelningen för det aktuella tillståndet. En konsekvens av denna egenskap är att det optimala beteendet ofta kan inkludera (informationsinsamling) åtgärder som vidtas enbart för att de förbättrar agentens uppskattning av det aktuella tillståndet, vilket gör att den kan fatta bättre beslut i framtiden.

Det är lärorikt att jämföra definitionen ovan med definitionen av en Markov-beslutsprocess . En MDP inkluderar inte observationsuppsättningen, eftersom agenten alltid med säkerhet känner till miljöns nuvarande tillstånd. Alternativt kan en MDP omformuleras till en POMDP genom att sätta observationsuppsättningen till att vara lika med uppsättningen av tillstånd och definiera de villkorade observationssannolikheterna för att deterministiskt välja den observation som motsvarar det sanna tillståndet.

Uppdatering av tro

Efter att ha vidtagit åtgärden $a$ och observerat $o$ , måste en agent uppdatera sin tro på det tillstånd som miljön kan (eller inte) vara i. Eftersom tillståndet är Markovian (genom antagande), att upprätthålla en övertygelse om staterna kräver enbart kunskap om den tidigare övertygelsen, de åtgärder som vidtagits och den aktuella observationen. Operationen betecknas $b'=\tau (b,a,o)$ . Nedan beskriver vi hur denna trosuppdatering beräknas.

Efter att ha nått $s'$$O(o\mid s',a)$ agenten $o\in \Omega$ med sannolikhet . Låt $b$ vara en sannolikhetsfördelning över tillståndsutrymmet $S$ . $b(s)$ anger sannolikheten att miljön är i tillstånd $s$ . Givet $b(s)$ , ​​sedan efter att ha vidtagit åtgärder $a$ och observerat $o$ ,

$b'(s')=\eta O(o\ mid s',a)\summa _{s\in S}T(s'\mid s,a)b(s)$

där $\eta =1/\Pr(o\mid b,a)$ är en normaliseringskonstant med $\Pr(o\mid b,a)=\summa _{s'\in S }O(o\mid s',a)\summa _{s\in S}T(s'\mid s,a)b(s)$ .

Tro MDP

En markovisk trosstat tillåter en POMDP att formuleras som en Markov-beslutsprocess där varje tro är en stat. Den resulterande övertygelsen MDP kommer således att definieras på ett kontinuerligt tillståndsutrymme (även om den "ursprungs" POMDP har ett ändligt antal tillstånd: det finns oändliga trostillstånd (i ${\displaystyle B} )$ eftersom det finns ett oändligt antal sannolikheter fördelningar över tillstånden (av ${\displaystyle S} ))$ .

Formellt definieras tron ​​MDP som en tupel $(B,A,\tau ,r,\gamma )$ där

• $B$ är uppsättningen trostillstånd över POMDP-tillstånden,
• $A$ är samma ändliga uppsättning åtgärder som för den ursprungliga POMDP,
• $\tau$ är övergångsfunktionen för trostillstånd,
• $r:B\times A\to \mathbb {R}$ är belöningsfunktionen på trostillstånd,
• $\gamma$ är diskonteringsfaktorn lika med $\gamma$ i den ursprungliga POMDP.

Av dessa måste $\tau$ och ${\displaystyle r} härledas från den ursprungliga POMDP.$$\tau$ är

$\tau (b,a,b')=\summa _{o\in \Omega }\Pr(b'|b,a,o)\Pr(o|a,b),$

där $\Pr(o|a,b)$ är värdet som härleds i föregående avsnitt och

$Pr(b'|b,a,o)={\begin{cases}1&{\text{om tron ​​uppdateras med argument }}b,a,o{\text{ returnerar }}b'\\ 0&{\text{annars }}\end{case}}.$

Belief MDP-belöningsfunktionen ( $r$ ) är den förväntade belöningen från POMDP-belöningsfunktionen över belief state-fördelningen:

$r(b,a)=\summa _{s\in S}b(s)R(s,a)$ .

Tron MDP är inte delvis observerbar längre, eftersom agenten vid varje given tidpunkt känner till sin tro, och i förlängningen tillståndet för övertygelsen MDP.

Policy och värdefunktion

Till skillnad från den "ursprungliga" POMDP (där varje handling är tillgänglig från endast ett tillstånd), i motsvarande övertygelse MDP tillåter alla trostillstånd alla handlingar, eftersom du (nästan) alltid har en viss sannolikhet att tro att du befinner dig i vilket (ursprungs)tillstånd som helst . Som sådan $\pi$ en åtgärd $a=\pi (b)$ för alla övertygelser $b$ .

Här antas målet är att maximera den förväntade totala diskonterade belöningen över en oändlig horisont. När $R$ definierar en kostnad, blir målet att minimera den förväntade kostnaden.

Den förväntade belöningen för policy $\pi$ från tro $b_{0}$ definieras som

$V^{\pi }(b_{0})=\summa _{t=0}^{\infty }\gamma ^{t}r(b_{t},a_{t})=\summa _{t=0}^{ \infty }\gamma ^{t}E{\Bigl [}R(s_{t},a_{t})\mid b_{0},\pi {\Bigr ]}$

där $\gamma <1$ är diskonteringsfaktorn. Den optimala policyn $\pi ^{*}$ erhålls genom att optimera den långsiktiga belöningen.

$\pi ^{*}={\underset {\pi }{\mbox{argmax}}}\ V^{\pi }(b_{0})$

där $b_{0}$ är den ursprungliga tron.

Den optimala policyn, betecknad med $\pi ^{*}$ , ger det högsta förväntade belöningsvärdet för varje trostillstånd, kompakt representerat av den optimala värdefunktionen $V^{*}$ . Denna värdefunktion är lösningen på Bellmans optimalitetsekvation :

$V^{ *}(b)=\max _{a\in A}{\Bigl [}r(b,a)+\gamma \sum _{o\in \Omega }\Pr(o\mid b,a)V ^{*}(\tau (b,a,o)){\Bigr ]}$

För POMDP:er med ändlig horisont är den optimala värdefunktionen styckvis linjär och konvex. Det kan representeras som en ändlig uppsättning vektorer. I formuleringen med infinite-horisont kan en finit vektoruppsättning approximera $V^{*}$ godtyckligt nära, vars form förblir konvex. Värdeiteration tillämpar dynamisk programmeringsuppdatering för att gradvis förbättra värdet tills konvergens till en $\epsilon$ -optimalt värdefunktion, och bevarar dess bitvis linjäritet och konvexitet. Genom att förbättra värdet förbättras policyn implicit. En annan dynamisk programmeringsteknik som kallas policy iteration representerar och förbättrar uttryckligen policyn istället.

Ungefärliga POMDP-lösningar

I praktiken är POMDPs ofta beräkningsmässigt svårlösta att lösa exakt, så datavetare har utvecklat metoder som approximerar lösningar för POMDPs.

Grid-baserade algoritmer omfattar en ungefärlig lösningsteknik. I detta tillvägagångssätt beräknas värdefunktionen för en uppsättning punkter i trosutrymmet, och interpolation används för att bestämma den optimala åtgärden att vidta för andra trostillstånd som påträffas och som inte finns i uppsättningen av rutnätspunkter. Nyare arbete använder sig av samplingstekniker, generaliseringstekniker och utnyttjande av problemstrukturer och har utvidgat POMDP-lösning till stora domäner med miljontals stater. Till exempel kan adaptiva rutnät och punktbaserade metoder prova slumpmässiga nåbara trospunkter för att begränsa planeringen till relevanta områden i trosområdet. Dimensionalitetsreduktion med PCA har också undersökts.

En annan linje med ungefärliga lösningstekniker för att lösa POMDP:er bygger på att använda (en delmängd av) historiken för tidigare observationer, åtgärder och belöningar fram till det aktuella tidssteget som ett pseudotillstånd. Vanliga tekniker för att lösa MDP baserat på dessa pseudo-tillstånd kan sedan användas (t.ex. Q-learning ) . Idealt bör pseudotillstånden innehålla den viktigaste informationen från hela historien (för att minska bias) samtidigt som de är så komprimerade som möjligt (för att minska överanpassning).

POMDP teori

Planering i POMDP är generellt sett obeslutlig . Vissa inställningar har dock identifierats som avgörbara (se Tabell 2 i, återgiven nedan). Olika mål har övervägts. Büchis mål definieras av Büchi automata . Nåbarhet är ett exempel på ett Büchi-tillstånd (till exempel att nå ett bra tillstånd där alla robotar är hemma). coBüchi-mål motsvarar spår som inte uppfyller ett givet Büchi-villkor (till exempel att inte nå ett dåligt tillstånd där någon robot dog). Paritetsmål definieras via paritetsspel ; de gör det möjligt att definiera komplexa mål så att man når ett bra tillstånd vart tionde tidssteg. Målet kan uppfyllas:

• nästan säkert, det är sannolikheten för att uppfylla målet är 1;
• positiv, det vill säga sannolikheten för att uppfylla målet är strikt större än 0;
• kvantitativ, det vill säga sannolikheten för att uppnå målet är större än en given tröskel.

Vi betraktar också det finita minnesfallet där agenten är en finita-tillståndsmaskin, och det allmänna fallet där agenten har ett oändligt minne.

Mål	Nästan säker (oändligt minne)	Nästan säker (ändligt minne)	Positiv (inf. mem.)	Positiv (finite mem.)	Kvantitativ (inf. mem)	Kvantitativ (finita mem.)
Buchi	EXPTIME -fullständig	EXPTIME-klar	oavgörbart	EXPTIME-klar	oavgörbart	oavgörbart
coBüchi	oavgörbart	EXPTIME-klar	EXPTIME-klar	EXPTIME-klar	oavgörbart	oavgörbart
paritet	oavgörbart	EXPTIME-klar	oavgörbart	EXPTIME-klar	oavgörbart	oavgörbart

Ansökningar

POMDP:er kan användas för att modellera många typer av verkliga problem. Anmärkningsvärda tillämpningar inkluderar användningen av en POMDP vid hantering av patienter med ischemisk hjärtsjukdom, hjälpmedel för personer med demens, bevarandet av de kritiskt hotade och svårupptäckta sumatranska tigrarna och undvikande av flygplanskollisioner.

externa länkar

• pomdp: Solver for Partially Observable Markov Decision Processes (POMDP) ​​ett R-paket som tillhandahåller ett gränssnitt till Tony Cassandras POMDP-lösare.
• zmdp , en POMDP-lösare av Trey Smith
• APPL , en snabb punktbaserad POMDP-lösare
• pyPOMDP , en (PO)MDP-verktygslåda (simulator, lösare, inlärare, filläsare) för Python av Oliver Stollmann och Bastian Migge
• Finite-state Controllers som använder Branch-and-Bound en exakt POMDP-lösare för policyer av en begränsad storlek
• POMDPs.jl , ett gränssnitt för att definiera och lösa MDP:er och POMDP:er i Julia och python med en mängd olika lösare.