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

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

पीओएमडीपी ढांचा सामान्य रूप से वास्तविक विश्व की विभिन्न अनुक्रमिक निर्णय प्रक्रियाओं को मॉडल करने के लिए पर्याप्त है। अनुप्रयोगों में रोबोट संकेतन समस्याएं, मशीन देखरेख और सामान्य रूप से अनिश्चितता के अनुसार योजनायें सम्मिलित हैं। 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(o\mid s',a)$ के साथ $o\in \Omega$ देखता है। माना $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)$.

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

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

प्रारंभिक पीओएमडीपी के विपरीत (जहां प्रत्येक क्रिया केवल एक अवस्था से उपलब्ध है), संबंधित धारणा एमडीपी में सभी धारणा अवस्था सभी फलनों की अनुमति देते हैं, क्योंकि आप (लगभग) सदैव धारणा करने की कुछ प्रायिकता रखते हैं कि आप किसी भी (मूल) अवस्था में हैं। जैसे की, किसी ट्रस्ट $b$ के लिए, $\pi$ क्रिया निर्दिष्ट $a=\pi (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 में, नीचे पुनरुत्पादित)। विभिन्न उद्देश्यों पर विचार किया गया है। बुच्ची उद्देश्यों को बुच्ची ऑटोमेटा द्वारा परिभाषित किया गया है। रीचैबिलिटी बुच्ची अवस्था का उदाहरण है (उदाहरण के लिए, अच्छी अवस्था तक पहुँचना जिसमें सभी रोबोट घर हैं)। coBüchi उद्देश्य उन निशानों के अनुरूप हैं जो किसी दी गई बुच्ची अवस्था को संतुष्ट नहीं करते हैं (उदाहरण के लिए, खराब अवस्था में नहीं पहुँचना जिसमें कुछ रोबोट की मृत्यु हो गई)। समता उद्देश्यों को समता खेल के माध्यम से परिभाषित किया जाता है; वे जटिल उद्देश्यों को परिभाषित करने में सक्षम होते हैं जैसे कि हर 10 बार अच्छी अवस्था तक पहुँचना। उद्देश्य को पूरा किया जा सकता है:

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

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

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

अनुप्रयोग

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

बाहरी संबंध

• 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