Częściowo obserwowalny proces decyzyjny Markowa - Partially observable Markov decision process

Częściowo obserwowalny proces Markowa ( POMDP ) jest uogólnieniem z decyzyjnym Markowa (MDP). POMDP modeluje proces decyzyjny agenta, w którym zakłada się, że dynamika systemu jest określana przez MDP, ale agent nie może bezpośrednio obserwować stanu bazowego. Zamiast tego musi zachować model czujnika (rozkład prawdopodobieństwa różnych obserwacji w danym stanie) i bazowy MDP. W przeciwieństwie do funkcji polityki w MDP, która odwzorowuje stany leżące u podstaw działań, polityka POMDP polega na odwzorowaniu obserwacji (lub stanów przekonań) na działania.

Struktura POMDP jest wystarczająco ogólna, aby modelować różne sekwencyjne procesy decyzyjne w świecie rzeczywistym. Zastosowania obejmują problemy z nawigacją robotów, konserwację maszyn i ogólnie planowanie w warunkach niepewności. Ogólne ramy procesów decyzyjnych Markowa z niedoskonałą informacją zostały opisane przez Karla Johana Åströma w 1965 roku w przypadku dyskretnej przestrzeni stanów i były dalej badane w środowisku badań operacyjnych, gdzie ukuto akronim POMDP. Został później dostosowany do problemów sztucznej inteligencji i automatycznego planowania przez Leslie P. Kaelbling i Michaela L. Littmana .

Dokładne rozwiązanie POMDP daje optymalne działanie dla każdego możliwego przekonania o stanach świata. Optymalne działanie maksymalizuje (lub minimalizuje) oczekiwaną nagrodę (lub koszt) agenta w możliwie nieskończonym horyzoncie. Sekwencja optymalnych działań jest znana jako optymalna polityka agenta w zakresie interakcji z jego otoczeniem.

Definicja

Formalna definicja

POMDP dyskretnego czasu modeluje relacje między agentem a jego środowiskiem. Formalnie POMDP to 7-krotka , gdzie ${\ Displaystyle (S, A, T, R, \ Omega, O, \ gamma)}$

• ${\displaystyle S}$ to zbiór stanów,
• ${\ Displaystyle A}$ to zestaw działań,
• ${\ Displaystyle T}$ jest zbiorem warunkowych prawdopodobieństw przejścia między stanami,
• ${\ Displaystyle R: S \ razy A \ do \ mathbb {R}}$ jest funkcją nagrody.
• ${\ Displaystyle \ Omega}$ to zbiór obserwacji,
• ${\ Displaystyle O}$ jest zbiorem warunkowych prawdopodobieństw obserwacji, oraz
• ${\ Displaystyle \ gamma \ w [0,1]}$ jest czynnikiem dyskontowym.

W każdym okresie środowisko jest w pewnym stanie . Agent podejmuje akcję , która powoduje, że środowisko przechodzi w stan z prawdopodobieństwem . Jednocześnie agent otrzymuje obserwację, która z prawdopodobieństwem (lub czasem w zależności od modelu czujnika) zależy od nowego stanu środowiska , oraz od właśnie podjętej akcji , . Na koniec agent otrzymuje nagrodę równą . Następnie proces się powtarza. Celem jest, aby agent na każdym kroku wybierał działania, które maksymalizują jego oczekiwaną przyszłą obniżoną nagrodę: , gdzie jest nagrodą zdobytą w danym momencie . Współczynnik rabatu określa, w jakim stopniu nagrody bezpośrednie są preferowane w stosunku do nagród bardziej odległych. Gdy agentowi zależy tylko na tym, które działanie przyniesie największą oczekiwaną natychmiastową nagrodę; gdy agentowi zależy na maksymalizacji oczekiwanej sumy przyszłych nagród. ${\displaystyle s\w S}$${\displaystyle a\w A}$${\displaystyle s'}$${\displaystyle T(s'\mid s,a)}$${\ Displaystyle o \ w \ Omega}$${\displaystyle s'}$${\displaystyle a}$${\displaystyle O(o\mid s',a)}$${\displaystyle O(o\mid s')}$${\ Displaystyle r}$${\displaystyle R(s,a)}$${\ Displaystyle E \ lewo [\ suma _ {t = 0} ^ {\ infty} \ gamma ^ {t} r_ {t} \ prawej]}$${\displaystyle r_{t}}$${\displaystyle t}$${\ Displaystyle \ gamma}$${\ Displaystyle \ gamma = 0}$${\ Displaystyle \ gamma = 1}$

Dyskusja

Ponieważ agent nie obserwuje bezpośrednio stanu środowiska, agent musi podejmować decyzje w warunkach niepewności co do rzeczywistego stanu środowiska. Jednak poprzez interakcję z otoczeniem i odbieranie obserwacji, agent może zaktualizować swoje przekonanie o prawdziwym stanie, aktualizując rozkład prawdopodobieństwa bieżącego stanu. Konsekwencją tej własności jest to, że optymalne zachowanie może często obejmować działania (gromadzenie informacji), które są podejmowane wyłącznie dlatego, że poprawiają ocenę stanu bieżącego przez agenta, umożliwiając w ten sposób podejmowanie lepszych decyzji w przyszłości.

Pouczające jest porównanie powyższej definicji z definicją procesu decyzyjnego Markowa . MDP nie zawiera zestawu obserwacji, ponieważ agent zawsze z całą pewnością zna aktualny stan środowiska. Alternatywnie, MDP można przeformułować jako POMDP, ustawiając zbiór obserwacji jako równy zbiorowi stanów i definiując prawdopodobieństwa warunkowe obserwacji, aby deterministycznie wybrać obserwację, która odpowiada prawdziwemu stanowi.

Aktualizacja wiary

Po podjęciu działania i obserwacji agent musi zaktualizować swoje przekonanie o stanie, w jakim może (lub nie) znajdować się środowisko. Ponieważ państwo jest markowskie (z założenia), utrzymywanie przekonania o stanach wymaga jedynie znajomości poprzedniego stan przekonania, podjęte działanie i bieżąca obserwacja. Operacja jest oznaczona . Poniżej opisujemy, w jaki sposób obliczana jest ta aktualizacja przekonań. ${\displaystyle a}$${\displaystyle o}$${\displaystyle b'=\tau (b,a,o)}$

Po dotarciu agent obserwuje z prawdopodobieństwem . Niech będzie rozkład prawdopodobieństwa w przestrzeni stanów . oznacza prawdopodobieństwo, że środowisko jest w stanie . Biorąc pod uwagę , to po podjęciu działania i obserwacji , ${\displaystyle s'}$${\ Displaystyle o \ w \ Omega}$${\displaystyle O(o\mid s',a)}$${\displaystyle b}$${\displaystyle S}$${\displaystyle b(s)}$${\displaystyle s}$${\displaystyle b(s)}$${\displaystyle a}$${\displaystyle o}$

${\ Displaystyle b '(s') = \ eta O (o \ mid s', a) \ suma _ {s \ w S} T (s' \ mid s, a) b (s)}$

gdzie jest stałą normalizującą z . ${\ Displaystyle \ eta = 1 / \ Pr (o \ mid b, a)}$${\ Displaystyle \ Pr (o \ mid b, a) = \ suma _ {s '\ w S} O (o \ mid s', a) \ suma _ {s \ w S} T (s '\ mid s ,a)b(s)}$

Wiara MDP

Stan wiary Markowa pozwala na sformułowanie POMDP jako procesu decyzyjnego Markowa, w którym każde przekonanie jest stanem. Wynikowe przekonanie MDP będzie zatem zdefiniowane w ciągłej przestrzeni stanów (nawet jeśli „pochodzący” POMDP ma skończoną liczbę stanów: istnieją nieskończone stany przekonań (in ), ponieważ istnieje nieskończona liczba rozkładów prawdopodobieństwa w stanach (z )). ${\ Displaystyle B}$${\displaystyle S}$

Formalnie przekonanie MDP definiuje się jako krotkę, w której ${\displaystyle (B,A,\tau,r,\gamma)}$

• ${\ Displaystyle B}$ jest zbiorem stanów przekonań nad stanami POMDP,
• ${\ Displaystyle A}$ jest tym samym skończonym zbiorem akcji jak w oryginalnym POMDP,
• ${\ Displaystyle \ tau}$ jest funkcją przejścia do stanu wiary,
• ${\ Displaystyle r: B \ razy A \ do \ mathbb {R} }$ jest funkcją nagrody w stanach przekonań,
• ${\ Displaystyle \ gamma}$jest współczynnikiem dyskontowym równym w oryginalnym POMDP.${\ Displaystyle \ gamma}$

Spośród nich i muszą pochodzić z oryginalnego POMDP. jest ${\ Displaystyle \ tau}$${\ Displaystyle r}$${\ Displaystyle \ tau}$

${\ Displaystyle \ tau (b, a, b') = \ suma _ {o \ w \ Omega} \ Pr (b' | b, a, o) \ Pr (o | a, b)}$

gdzie jest wartość uzyskana w poprzedniej sekcji i ${\ Displaystyle \ Pr (o | a, b)}$

${\ Displaystyle Pr(b'|b,a,o)={\rozpocznij {przypadki}1&{\tekst{jeśli przekonanie zostanie zaktualizowane z argumentami}}b,a,o{\text{zwraca}}b'\\ 0&{\text{inaczej }}\end{przypadki}}.}$

Funkcja nagrody przekonania MDP ( ) to oczekiwana nagroda z funkcji nagrody POMDP w stosunku do rozkładu stanu przekonania: ${\ Displaystyle r}$

${\ Displaystyle r (b, a) = \ suma _ {s \ w S} b (s) R (s, a)}$.

Przekonanie MDP nie jest już częściowo obserwowalne, ponieważ w danym momencie agent zna swoje przekonanie, a co za tym idzie stan przekonania MDP.

Funkcja polityki i wartości

W przeciwieństwie do „początkowego” POMDP (gdzie każda akcja jest dostępna tylko w jednym stanie), w odpowiednim MDP przekonań wszystkie stany przekonań pozwalają na wszystkie działania, ponieważ (prawie) zawsze masz pewne prawdopodobieństwo, że uwierzysz, że znajdujesz się w jakimkolwiek (początkowym) stanie. Jako taki określa działanie dla każdego przekonania . ${\displaystyle \pi}$${\ Displaystyle a = \ pi (b)}$${\displaystyle b}$

Tutaj zakłada się, że celem jest maksymalizacja oczekiwanej całkowitej zdyskontowanej nagrody w nieskończonym horyzoncie. Kiedy definiuje koszt, celem staje się minimalizacja oczekiwanego kosztu. ${\ Displaystyle R}$

Oczekiwaną nagrodę za polisę, począwszy od przekonania, definiuje się jako ${\displaystyle \pi}$${\displaystyle b_{0}}$

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

gdzie jest czynnik dyskontowy. Optymalną politykę uzyskuje się poprzez optymalizację długoterminowej nagrody. ${\ Displaystyle \ gamma <1}$${\ Displaystyle \ pi ^ {*}}$

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

gdzie jest początkowe przekonanie. ${\displaystyle b_{0}}$

Polityka optymalna, oznaczona , daje najwyższą oczekiwaną wartość nagrody dla każdego stanu przekonania, zwięźle reprezentowaną przez funkcję wartości optymalnej . Ta funkcja wartości jest rozwiązaniem równania optymalności Bellmana : ${\ Displaystyle \ pi ^ {*}}$${\ Displaystyle V ^ {*}}$

${\ Displaystyle V ^ {*} (b) = \ max _ {a \ w A} {\ Bigl [} r (b, a) + \ gamma \ suma _ {o \ w \ omega} \ Pr (o \ mid b,a)V^{*}(\tau (b,a,o)){\Bigr ]}}$

W przypadku POMDP o skończonym poziomie funkcja wartości optymalnej jest odcinkowo liniowa i wypukła. Może być reprezentowany jako skończony zbiór wektorów. W sformułowaniu nieskończonego horyzontu zbiór wektorów skończonych może być dowolnie przybliżony , którego kształt pozostaje wypukły. Iteracja wartości stosuje dynamiczną aktualizację programowania, aby stopniowo poprawiać wartość aż do zbieżności do funkcji wartości -optymalnej i zachowuje jej liniowość odcinkową i wypukłość. Poprawiając wartość, polityka jest domyślnie ulepszana. Inna technika programowania dynamicznego, zwana iteracją zasad, wyraźnie reprezentuje i ulepsza zasady. ${\ Displaystyle V ^ {*}}$${\displaystyle \epsilon}$

Przybliżone rozwiązania POMDP

W praktyce POMDPs są często obliczeniowo trudny do rozwiązania dokładnie, więc informatycy opracowali metody, które przybliżonych rozwiązań dla POMDPs.

Algorytmy oparte na siatce zawierają jedną przybliżoną technikę rozwiązania. W tym podejściu funkcja wartości jest obliczana dla zbioru punktów w przestrzeni przekonań, a interpolacja jest używana do określenia optymalnego działania, jakie należy podjąć dla innych napotkanych stanów przekonań, które nie znajdują się w zbiorze punktów siatki. Nowsze prace wykorzystują techniki próbkowania, techniki uogólniania i eksploatację struktury problemu, a także rozszerzyły rozwiązywanie POMDP na duże domeny z milionami stanów. Na przykład, siatki adaptacyjne i metody punktowe próbują losowo osiągalne punkty przekonań, aby ograniczyć planowanie do odpowiednich obszarów w przestrzeni przekonań. Zbadano również redukcję wymiarowości za pomocą PCA .

teoria POMDP

Planowanie w POMDP jest generalnie nierozstrzygnięte . Określono jednak, że niektóre ustawienia są rozstrzygalne (patrz Tabela 2, przytoczona poniżej). Rozważano różne cele. Cele Büchi są definiowane przez automaty Büchi . Osiągalność to przykład stanu Büchi (na przykład osiągnięcie dobrego stanu, w którym wszystkie roboty są w domu). Cele coBüchi odpowiadają śladom, które nie spełniają danego warunku Büchi (na przykład nie osiągnięcie złego stanu, w którym zginął jakiś robot). Cele parytetów są określane poprzez gry z parytetami ; pozwalają zdefiniować złożone cele tak, aby co 10 kroków czasowych osiągnąć dobry stan. Cel może zostać osiągnięty:

• prawie na pewno, to znaczy, że prawdopodobieństwo spełnienia celu wynosi 1;
• dodatnie, czyli prawdopodobieństwo spełnienia celu jest ściśle większe niż 0;
• ilościowe, czyli prawdopodobieństwo osiągnięcia celu jest większe niż określony próg.

Rozważamy również przypadek pamięci skończonej, w którym agent jest maszyną skończoną, oraz przypadek ogólny, w którym agent ma nieskończoną pamięć.

Cele	Prawie pewny (pamięć nieskończona)	Prawie na pewno (pamięć skończona)	Pozytywny (pamięć inf.)	Pozytywny (pamięć skończona)	Ilościowe (inf. mem)	Ilościowe (pamięć skończona)
Buchi	EXPTIME -Complete	EXPTIME-ukończony	nierozstrzygalny	EXPTIME-ukończony	nierozstrzygalny	nierozstrzygalny
coBuchi	nierozstrzygalny	EXPTIME-ukończony	EXPTIME-ukończony	EXPTIME-ukończony	nierozstrzygalny	nierozstrzygalny
parytet	nierozstrzygalny	EXPTIME-ukończony	nierozstrzygalny	EXPTIME-ukończony	nierozstrzygalny	nierozstrzygalny

Aplikacje

POMDP mogą być używane do modelowania wielu rodzajów rzeczywistych problemów. Godne uwagi zastosowania obejmują wykorzystanie POMDP w leczeniu pacjentów z chorobą niedokrwienną serca, technologię wspomagającą osoby z demencją, ochronę krytycznie zagrożonych i trudnych do wykrycia tygrysów sumatrzańskich oraz unikanie kolizji samolotów.

Bibliografia

Zewnętrzne linki

• Strony POMDP Tony'ego Cassandry z samouczkiem, przykładami problemów modelowanych jako POMDP i oprogramowaniem do ich rozwiązywania.
• pomdp: Solver for Partially Observable Markov Decision Processes (POMDP) pakiet R dostarczający interfejs do solvera POMDP Tony'ego Cassandry.
• zmdp , solwer POMDP autorstwa Trey Smith
• APPL , szybki solwer POMDP oparty na punktach
• pyPOMDP , zestaw narzędzi (PO)MDP (symulator, solver, uczeń, czytnik plików) dla Pythona autorstwa Olivera Stollmanna i Bastiana Migge
• Kontrolery skończone wykorzystujące rozgałęzienie i powiązanie Dokładny solwer POMDP dla polityk o ograniczonym rozmiarze
• POMDPs.jl , interfejs do definiowania i rozwiązywania MDP i POMDP w Julii za pomocą różnych solwerów.