आंशिक रूप से देखने योग्य मार्कोव निर्णय प्रक्रिया

आंशिक रूप से देखने योग्य मार्कोव निर्णय प्रक्रिया (पीओएमडीपी) मार्कोव निर्णय प्रक्रिया (एमडीपी) का सामान्यीकरण है। एक पीओएमडीपी एक एजेंट निर्णय प्रक्रिया को मॉडल करता है, जिसमें यह माना जाता है कि प्रणाली की गतिशीलता एक एमडीपी द्वारा निर्धारित की जाती है, लेकिन एजेंट सीधे अंतर्निहित स्थिति का निरीक्षण नहीं कर सकता है। इसके अतिरिक्त, इसे एक सेंसर मॉडल (अंतर्निहित स्थिति को देखते हुए विभिन्न अवलोकनों की प्रायिकता वितरण) और अंतर्निहित एमडीपी को बनाए रखना चाहिए। एमडीपी में पॉलिसी फलन के विपरीत, जो अंतर्निहित अवस्थाओं को क्रियाओं के लिए मैप करता है, पीओएमडीपी की नीति टिप्पणियों के इतिहास (या विश्वास अवस्थाओं) से फलनों के लिए एक मानचित्रण है।

पीओएमडीपी ढांचा सामान्य रूप से वास्तविक विश्व की विभिन्न अनुक्रमिक निर्णय प्रक्रियाओं को मॉडल करने के लिए पर्याप्त है। अनुप्रयोगों में रोबोट नेविगेशन समस्याएं, मशीन रखरखाव और सामान्य रूप से अनिश्चितता के अनुसार योजना सम्मिलित है। 1965 में कार्ल जोहान एस्ट्रोम द्वारा अपूर्ण जानकारी के साथ मार्कोव निर्णय प्रक्रियाओं के सामान्य ढांचे का वर्णन किया गया था। असतत अवस्था स्थान के मामले में, और इसका संचालन अनुसंधान समुदाय में आगे अध्ययन किया गया था जहां संक्षिप्त नाम पीओएमडीपी गढ़ा गया था। इसे बाद में लेस्ली पी. केलब्लिंग और माइकल एल. लिटमैन द्वारा कृत्रिम बुद्धिमत्ता और स्वचालित योजना में समस्याओं के लिए अनुकूलित किया गया था।

पीओएमडीपी का एक स्पष्ट समाधान विश्व अवस्थाओं पर प्रत्येक संभावित विश्वास के लिए इष्टतम कार्रवाई करता है। इष्टतम कार्रवाई संभवतः अनंत क्षितिज पर एजेंट के अपेक्षित पुरस्कार (या व्यय को कम करती है) को अधिकतम करती है। इष्टतम क्रियाओं के अनुक्रम को एजेंट के पर्यावरण के साथ वार्तालाप के लिए इष्टतम नीति के रूप में जाना जाता है।

परिभाषा

औपचारिक परिभाषा

एक असतत-समय पीओएमडीपी एक एजेंट और उसके वातावरण के बीच संबंध को मॉडल करता है। औपचारिक रूप से, एक पीओएमडीपी 7-ट्यूपल $(S,A,T,R,\Omega ,O,\gamma )$ है, जहाँ

• $S$ अवस्थाओं का एक समूह है,
• $A$ क्रियाओं का एक समूह है,
• $T$ अवस्थाओं के बीच सशर्त संक्रमण प्रायिकताओं का एक समुच्चय है,
• $R:S\times A\to \mathbb {R}$ पुरस्कार फलन है।
• $\Omega$ टिप्पणियों का एक समुच्चय है,
• $O$ सशर्त अवलोकन प्रायिकताओं का एक समुच्चय है, और
• $\gamma \in [0,1)$ छूट कारक है।

प्रत्येक समय अवधि में, पर्यावरण किसी न किसी अवस्था में होता है $s\in S$. एजेंट कार्रवाई करता है $a\in A$, जो पर्यावरण को अवस्था में संक्रमण का कारण बनता है $s'$ प्रायिकता के साथ $T(s'\mid s,a)$. उसी समय, एजेंट एक अवलोकन $o\in \Omega$ प्राप्त करता है, जो पर्यावरण की नई स्थिति $s'$ पर निर्भर करती है, और अभी-अभी की गई कार्रवाई पर, $a$, $O(o\mid s',a)$ प्रायिकता के साथ (या कभी-कभी $O(o\mid s')$ सेंसर मॉडल पर निर्भर करता है) है। अंत में, एजेंट को $r$ के बराबर $R(s,a)$ पुरस्कार मिलता है। फिर प्रक्रिया दोहरायी जाती है। एजेंट के लिए लक्ष्य प्रत्येक समय कदम पर ऐसी कार्रवाइयों का चयन करना है जो उसके अपेक्षित भविष्य के छूट वाले पुरस्कार को अधिकतम करें: $E\left[\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\right]$, जहाँ $r_{t}$ समय पर अर्जित पुरस्कार है $t$. छूट का कारक $\gamma$ यह निर्धारित करता है कि अधिक दूर के पुरस्कारों पर कितने तात्कालिक पुरस्कार पसंद किए जाते हैं। जब $\gamma =0$ एजेंट केवल इस बात की चिंता करता है कि किस कार्रवाई से सबसे बड़ा अपेक्षित तत्काल पुरस्कार मिलेगा; जब $\gamma \rightarrow 1$ एजेंट भविष्य के पुरस्कारों की अपेक्षित राशि को अधिकतम करने की चिंता करता है।

चर्चा

क्योंकि एजेंट सीधे पर्यावरण की स्थिति का निरीक्षण नहीं करता है, एजेंट को सही पर्यावरण स्थिति की अनिश्चितता के अनुसार निर्णय लेना चाहिए। चूँकि, पर्यावरण के साथ वार्तालाप करके और अवलोकन प्राप्त करके, एजेंट वर्तमान स्थिति की संभाव्यता वितरण को अद्यतन करके वास्तविक स्थिति में अपने विश्वास को अद्यतन कर सकता है। इस संपत्ति का एक परिणाम यह है कि इष्टतम व्यवहार में अधिकांशतः (सूचना एकत्र करना) क्रियाएं सम्मिलित हो सकती हैं, जो विशुद्ध रूप से इसलिए की जाती हैं क्योंकि वे वर्तमान स्थिति के एजेंट के अनुमान में संशोधन करते हैं, जिससे भविष्य में उत्तम निर्णय लेने की अनुमति मिलती है।

मार्कोव निर्णय प्रक्रिया की परिभाषा के साथ उपरोक्त परिभाषा की तुलना करना शिक्षाप्रद है। एक एमडीपी में अवलोकन समुच्चय सम्मिलित नहीं होता है, क्योंकि एजेंट सदैव पर्यावरण की वर्तमान स्थिति को निश्चित रूप से जानता है। वैकल्पिक रूप से, एक एमडीपी को पीओएमडीपी के रूप में अवस्थाओं के समुच्चय के बराबर होने के लिए अवलोकन समुच्चय करके और अवलोकन सशर्त प्रायिकताओं को निश्चित रूप से सही स्थिति से मेल खाने वाले अवलोकन का चयन करके परिभाषित किया जा सकता है।

विश्वास अद्यतन

कार्रवाई करने के बाद $a$ और $o$ दिख रहा है, एक एजेंट को अवस्था में अपने विश्वास को अद्यतन करने की आवश्यकता है (या नहीं) पर्यावरण में हो सकता है (या नहीं)। चूंकि अवस्था मार्कोवियन है (धारणा के अनुसार), अवस्थाओं पर विश्वास बनाए रखने के लिए केवल पिछले विश्वास अवस्था के ज्ञान की, की गई कार्रवाई, और वर्तमान अवलोकन की आवश्यकता होती है। ऑपरेशन $b'=\tau (b,a,o)$ दर्शाया गया है। नीचे हम वर्णन करते हैं कि इस विश्वास अद्यतन की गणना कैसे की जाती है।

पहुंचने के बाद $s'$, एजेंट $o\in \Omega$ देखता है, $O(o\mid s',a)$ प्रायिकता के साथ। माना $b$ अवस्था स्थान पर संभाव्यता वितरण $S$ हो। $b(s)$ इस प्रायिकता को दर्शाता है कि पर्यावरण स्थिति में $s$ है। दिया गया $b(s)$, फिर कार्रवाई करने के बाद $a$ और $o$ दिख रहा है,

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

जहाँ $\eta =1/\Pr(o\mid b,a)$ के साथ एक सामान्यीकरण स्थिरांक $\Pr(o\mid b,a)=\sum _{s'\in S}O(o\mid s',a)\sum _{s\in S}T(s'\mid s,a)b(s)$ है।

विश्वास एमडीपी

एक मार्कोवियन विश्वास अवस्था एक पीओएमडीपी को मार्कोव निर्णय प्रक्रिया के रूप में तैयार करने की अनुमति देता है, जहां हर विश्वास एक अवस्था है। परिणामी विश्वास एमडीपी इस प्रकार एक निरंतर अवस्था स्थान पर परिभाषित किया जाएगा (तथापि मूल पीओएमडीपी में अवस्थाओं की सीमित संख्या हो: अनंत विश्वास अवस्था हैं ($B$ में) क्योंकि अवस्थाओं में असीमित संभाव्यता वितरण ($S$के) हैं।

औपचारिक रूप से, विश्वास एमडीपी को टपल के रूप में परिभाषित किया गया है $(B,A,\tau ,r,\gamma )$ जहाँ

• $B$ पीओएमडीपी अवस्थाओं पर विश्वास अवस्थाओं का समूह है,
• $A$ मूल पीओएमडीपी के समान कार्रवाई का एक ही सीमित समुच्चय है,
• $\tau$ विश्वास अवस्था संक्रमण फलन है,
• $r:B\times A\to \mathbb {R}$ विश्वास अवस्थाओं पर पुरस्कार फलन है,
• $\gamma$ के बराबर छूट कारक है $\gamma$ मूल पीओएमडीपी में।

यहाँ इन, $\tau$ और $r$ मूल पीओएमडीपी से प्राप्त करने की आवश्यकता है। $\tau$ है

$\tau (b,a,b')=\sum _{o\in \Omega }\Pr(b'|b,a,o)\Pr(o|a,b),$ जहाँ $\Pr(o|a,b)$ पिछले खंड में प्राप्त वैल्यू है और

$Pr(b'|b,a,o)={\begin{cases}1&{\text{if the belief update with arguments }}b,a,o{\text{ returns }}b'\\0&{\text{otherwise }}\end{cases}}$

विश्वास एमडीपी पुरस्कार फलन ($r$) विश्वास अवस्था वितरण पर पीओएमडीपी पुरस्कार फलन से अपेक्षित पुरस्कार है:

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

विश्वास एमडीपी अब आंशिक रूप से देखने योग्य नहीं है, क्योंकि किसी भी समय एजेंट अपने विश्वास को जानता है, और विस्तार से विश्वास एमडीपी की स्थिति।

नीति और वैल्यू फलन

प्रारंभिक पीओएमडीपी के विपरीत (जहां प्रत्येक क्रिया केवल एक अवस्था से उपलब्ध है), संबंधित विश्वास एमडीपी में सभी विश्वास अवस्था सभी फलनों की अनुमति देते हैं, क्योंकि आप (लगभग) सदैव विश्वास करने की कुछ प्रायिकता रखते हैं कि आप किसी भी (मूल) अवस्था में हैं। जैसे की, $\pi$ एक क्रिया निर्दिष्ट $a=\pi (b)$ करता है, किसी ट्रस्ट $b$ के लिए।

यहां यह माना जाता है कि उद्देश्य अनंत क्षितिज पर अपेक्षित कुल रियायती पुरस्कार को अधिकतम करना है। जब $R$ एक व्यय को परिभाषित करता है, उद्देश्य अपेक्षित व्यय का न्यूनीकरण हो जाता है।

नीति के लिए अपेक्षित पुरस्कार $\pi$ विश्वास से प्रारंभ $b_{0}$ परिभाषित किया जाता है

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

जहाँ $\gamma <1$ छूट कारक है। इष्टतम नीति $\pi ^{*}$ लंबी अवधि के पुरस्कार का अनुकूलन करके प्राप्त किया जाता है।

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

जहाँ $b_{0}$ प्रारंभिक विश्वास है।

इष्टतम नीति, $\pi ^{*}$ द्वारा निरूपित, प्रत्येक विश्वास अवस्था के लिए उच्चतम अपेक्षित पुरस्कार वैल्यू प्राप्त करता है, जो कि इष्टतम वैल्यू फलन $V^{*}$ द्वारा कॉम्पैक्ट रूप से दर्शाया गया है। यह मान फलन बेलमैन समीकरण का हल है:

$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 ]}$

परिमित-क्षितिज पीओएमडीपी के लिए, इष्टतम मान फलन टुकड़ावार-रैखिक और उत्तल है। इसे सदिशों के परिमित समुच्चय के रूप में प्रदर्शित किया जा सकता है। अनंत-क्षितिज सूत्रीकरण में, एक परिमित वेक्टर समुच्चय $V^{*}$ अनुमानित हो सकता है, इच्छानुसार ढंग से निकटता से, जिसका आकार उत्तल रहता है। वैल्यू इटरेशन डायनामिक प्रोग्रामिंग अपडेट को प्रयुक्त करता है जिससे वैल्यू में धीरे-धीरे संशोधन हो सके जब तक कि अभिसरण नहीं हो जाता $\epsilon$-ऑप्टिमल वैल्यू फलन, और इसकी टुकड़े-टुकड़े रैखिकता और उत्तलता को बनाये रखता है। वैल्यू में संशोधन करके, नीति में निहित रूप से संशोधन किया जाता है। नीति पुनरावृत्ति नामक एक अन्य गतिशील प्रोग्रामिंग तकनीक स्पष्ट रूप से नीति का प्रतिनिधित्व करती है और इसके अतिरिक्त संशोधन करती है।

अनुमानित पीओएमडीपी समाधान

व्यवहार में, पीओएमडीपी अधिकांशतः कम्प्यूटेशनल रूप से कम्प्यूटेशनल जटिलता सिद्धांत वास्तव में हल करने के लिए इंट्रेक्टेबिलिटी होते हैं, इसलिए कंप्यूटर वैज्ञानिकों ने ऐसी विधियाँ विकसित की हैं, जो पीओएमडीपी के लिए अनुमानित समाधान हैं। ग्रिड-आधारित एल्गोरिदम एक अनुमानित समाधान तकनीक सम्मिलित करें। इस दृष्टिकोण में, वैल्यू फलन की गणना विश्वास स्थान में बिंदुओं के एक समुच्चय के लिए की जाती है, और इंटरपोलेशन का उपयोग उन अन्य विश्वास अवस्थाओं के लिए इष्टतम कार्रवाई निर्धारित करने के लिए किया जाता है जो ग्रिड बिंदुओं के समुच्चय में नहीं हैं। अधिक हाल के कार्य नमूनाकरण तकनीकों, सामान्यीकरण तकनीकों और समस्या संरचना के शोषण का उपयोग करते हैं, और लाखों अवस्थाओं के साथ बड़े डोमेन में पीओएमडीपी समाधान को विस्तारित किया है। उदाहरण के लिए, अनुकूली ग्रिड और बिंदु-आधारित विधियाँ यादृच्छिक पहुंच योग्य विश्वास बिंदुओं का नमूना लेती हैं, जो विश्वास स्थान में प्रासंगिक क्षेत्रों की योजना को विवश करती हैं।

सिद्धांत घटक विश्लेषण का उपयोग करते हुए आयाम में कमी का भी पता लगाया गया है। पीओएमडीपी को हल करने के लिए अनुमानित समाधान तकनीकों की एक और पंक्ति पिछली टिप्पणियों, फलनों और पुरस्कारों के इतिहास को एक छद्म अवस्था के रूप में उपयोग करने (एक सबसमुच्चय) पर निर्भर करती है। इन छद्म अवस्थाओं के आधार पर एमडीपी को हल करने के लिए सामान्य तकनीकों का उपयोग किया जा सकता है (जैसे क्यू-लर्निंग)। आदर्श रूप से छद्म अवस्थाओं में यथासंभव संकुचित होने के दौरान पूरे इतिहास (पूर्वाग्रह को कम करने के लिए) से सबसे महत्वपूर्ण जानकारी होनी चाहिए (ओवरफिटिंग को कम करने के लिए)।

पीओएमडीपी सिद्धांत

पीओएमडीपी में नियोजन सामान्य रूप से अनिर्णीत समस्या है। चूँकि, कुछ समुच्चयिंग्स को निर्णायक होने के लिए पहचाना गया है (देखें तालिका 2 में, नीचे पुनरुत्पादित)। विभिन्न उद्देश्यों पर विचार किया गया है। बुच्ची उद्देश्यों को बुच्ची ऑटोमेटा द्वारा परिभाषित किया गया है। रीचैबिलिटी एक बुच्ची स्थिति का एक उदाहरण है (उदाहरण के लिए, एक अच्छी स्थिति तक पहुँचना जिसमें सभी रोबोट घर हैं)। कोबुच्ची उद्देश्य उन निशानों के अनुरूप हैं जो किसी दी गई बुच्ची स्थिति को संतुष्ट नहीं करते हैं (उदाहरण के लिए, खराब स्थिति में नहीं पहुँचना जिसमें कुछ रोबोट की मृत्यु हो गई)। समता उद्देश्यों को समता खेल के माध्यम से परिभाषित किया जाता है; वे जटिल उद्देश्यों को परिभाषित करने में सक्षम होते हैं जैसे कि हर 10 बार एक अच्छी स्थिति तक पहुँचना। उद्देश्य को पूरा किया जा सकता है:

• लगभग-निश्चित रूप से, अर्थात् उद्देश्य को पूरा करने की प्रायिकता 1 है;
• सकारात्मक, अर्थात् उद्देश्य को पूरा करने की प्रायिकता 0 से अधिक है;
• मात्रात्मक, अर्थात उद्देश्य को पूरा करने की प्रायिकता दी गई सीमा से अधिक है।

हम परिमित स्मृति स्थिति पर भी विचार करते हैं जिसमें एजेंट एक परिमित-अवस्था मशीन है, और सामान्य स्थिति जिसमें एजेंट की अनंत स्मृति होती है।

उद्देश्य	लगभग सुनिश्चित (अनंत स्मृति)	लगभग सुनिश्चित (परिमित स्मृति)	सकारात्मक (अनंत mem.)	सकारात्मक (परिमित mem.)	मात्रात्मक (अनंत mem)	मात्रात्मक (परिमित mem.)
बुच्ची	एक्सपटाइम-पूर्ण	एक्सपटाइम-पूर्ण	अनिर्णनीय	एक्सपटाइम-पूर्ण	अनिर्णनीय	अनिर्णनीय
कोबुच्ची	अनिर्णनीय	एक्सपटाइम-पूर्ण	एक्सपटाइम-पूर्ण	एक्सपटाइम-पूर्ण	अनिर्णनीय	अनिर्णनीय
समानता	अनिर्णनीय	एक्सपटाइम-पूर्ण	अनिर्णनीय	एक्सपटाइम-पूर्ण	अनिर्णनीय	अनिर्णनीय

अनुप्रयोग

पीओएमडीपी का उपयोग कई तरह की वास्तविक विश्व की समस्याओं के मॉडल के लिए किया जा सकता है। उल्लेखनीय अनुप्रयोगों में इस्कीमिक हृदय रोग के रोगियों के प्रबंधन में पीओएमडीपी का उपयोग सम्मिलित है, डिमेंशिया वाले व्यक्तियों के लिए सहायक तकनीक, गंभीर रूप से लुप्तप्राय और सुमात्रन बाघों का पता लगाना मुश्किल है और विमान टक्कर परिहार।

बाहरी संबंध

• APPL, a fast point-based POMDP solver
• Finite-state Controllers using Branch-and-Bound An Exact POMDP Solver for Policies of a Bounded Size
• pomdp: Infrastructure for Partially Observable Markov Decision Processes (POMDP) an R package which includes an interface to Tony Cassandra's pomdp-solve program.
• POMDPs.jl, an interface for defining and solving MDPs and POMDPs in Julia and python with a variety of solvers.
• pyPOMDP, a (PO)MDP toolbox (simulator, solver, learner, file reader) for Python by Oliver Stollmann and Bastian Migge
• zmdp, a POMDP solver by Trey Smith