Partially observable Markov decision process
આંશિક રીતે અવલોકનક્ષમ માર્કોવ નિર્ણય પ્રક્રિયા (પી. ઓ. એમ. ડી. પી.) એ માર્કોવ નિર્ણય પ્રક્રિયા (એમ. ડી. પી.) નું સામાન્યીકરણ છે. પી. ઓ. એમ. ડી. પી. એજન્ટ નિર્ણય પ્રક્રિયાને મોડેલ કરે છે જેમાં એવું માનવામાં આવે છે કે સિસ્ટમની ગતિશીલતા એમ. ડી. પી. દ્વારા નક્કી કરવામાં આવે છે, પરંતુ એજન્ટ અંતર્ગત સ્થિતિનું સીધું નિરીક્ષણ કરી શકતો નથી. તેના બદલે, તેણે સેન્સર મોડેલ (અંતર્ગત સ્થિતિને ધ્યાનમાં રાખીને વિવિધ અવલોકનોની સંભાવના વિતરણ) અને અંતર્ગત એમડીપી જાળવવી આવશ્યક છે. એમ. ડી. પી. માં નીતિ કાર્યથી વિપરીત, જે ક્રિયાઓ માટે અંતર્ગત રાજ્યોનો નકશો બનાવે છે, પી. ઓ. એમ. ડી. પી. ની નીતિ અવલોકનો (અથવા માન્યતા રાજ્યો) ના ઇતિહાસમાંથી ક્રિયાઓનું નકશા બનાવે છે. પી. ઓ. એમ. ડી. પી. માળખું વિવિધ વાસ્તવિક-વિશ્વ ક્રમિક નિર્ણય પ્રક્રિયાઓનું મોડેલ બનાવવા માટે પૂરતું સામાન્ય છે. એપ્લિકેશન્સમાં રોબોટ નેવિગેશન સમસ્યાઓ, મશીનની જાળવણી અને સામાન્ય રીતે અનિશ્ચિતતા હેઠળ આયોજનનો સમાવેશ થાય છે. અપૂર્ણ માહિતી સાથે માર્કોવ નિર્ણય પ્રક્રિયાઓના સામાન્ય માળખાને કાર્લ જોહાન એસ્ટ્રોમ દ્વારા 1965 માં એક અલગ રાજ્ય જગ્યાના કિસ્સામાં વર્ણવવામાં આવ્યું હતું, અને તેનો વધુ અભ્યાસ કામગીરી સંશોધન સમુદાયમાં કરવામાં આવ્યો હતો જ્યાં ટૂંકાક્ષર પી. ઓ. એમ. ડી. પી. ની રચના કરવામાં આવી હતી. પાછળથી તેને લેસ્લી પી. કેલ્બલિંગ અને માઈકલ એલ. લિટમેન દ્વારા કૃત્રિમ બુદ્ધિ અને સ્વચાલિત આયોજનની સમસ્યાઓ માટે સ્વીકારવામાં આવ્યું હતું. પી. ઓ. એમ. ડી. પી. નો ચોક્કસ ઉકેલ વિશ્વના રાજ્યો પરની દરેક સંભવિત માન્યતા માટે શ્રેષ્ઠ કાર્યવાહી આપે છે. શ્રેષ્ઠ ક્રિયા સંભવતઃ અનંત ક્ષિતિજ પર એજન્ટના અપેક્ષિત પુરસ્કારને મહત્તમ કરે છે (અથવા ખર્ચ ઘટાડે છે). શ્રેષ્ઠ ક્રિયાઓનો ક્રમ તેના પર્યાવરણ સાથે ક્રિયાપ્રતિક્રિયા કરવા માટે એજન્ટની શ્રેષ્ઠ નીતિ તરીકે ઓળખાય છે. વ્યાખ્યા ઔપચારિક વ્યાખ્યા એક સ્વતંત્ર-સમયનો પી. ઓ. એમ. ડી. પી. એજન્ટ અને તેના પર્યાવરણ વચ્ચેના સંબંધનું મોડેલ બનાવે છે. ઔપચારિક રીતે, પી. ઓ. એમ. ડી. પી. એ 7-ટુપલ છે, જ્યાં રાજ્યોનો સમૂહ છે, ક્રિયાઓનો સમૂહ છે, રાજ્યો વચ્ચે શરતી સંક્રમણ સંભાવનાઓનો સમૂહ છે, તે પુરસ્કાર કાર્ય છે. તે નિરીક્ષણોનો સમૂહ છે, શરતી નિરીક્ષણ સંભાવનાઓનો સમૂહ છે, અને તે ડિસ્કાઉન્ટ પરિબળ છે. દરેક સમયગાળામાં પર્યાવરણ કોઈક સ્થિતિમાં હોય છે. એજન્ટ એક ક્રિયા કરે છે, જે પર્યાવરણને સંભાવના સાથે સ્થિતિમાં પરિવર્તિત કરે છે. તે જ સમયે, એજન્ટ એક નિરીક્ષણ મેળવે છે જે પર્યાવરણની નવી સ્થિતિ પર અને સંભાવના સાથે (અથવા કેટલીકવાર સેન્સર મોડેલ પર આધાર રાખીને) હમણાં જ લેવામાં આવેલી કાર્યવાહી પર આધાર રાખે છે. છેવટે, એજન્ટને તેની બરાબરનું ઇનામ મળે છે. પછી પ્રક્રિયા પુનરાવર્તન થાય છે. એજન્ટ માટે દરેક સમયે પગલાં પસંદ કરવાનું લક્ષ્ય છે જે તેના અપેક્ષિત ભાવિ ડિસ્કાઉન્ટેડ પુરસ્કારને મહત્તમ કરે છેઃ, તે સમયે મેળવેલ પુરસ્કાર ક્યાં છે. ડિસ્કાઉન્ટ પરિબળ નક્કી કરે છે કે વધુ દૂરના પારિતોષિકો પર તાત્કાલિક પારિતોષિકોની કેટલી તરફેણ કરવામાં આવે છે. જ્યારે એજન્ટ માત્ર તેની જ કાળજી રાખે છે કે કઈ કાર્યવાહીથી સૌથી વધુ અપેક્ષિત તાત્કાલિક પુરસ્કાર મળશે; જ્યારે એજન્ટ ભવિષ્યના પારિતોષિકોની અપેક્ષિત રકમને મહત્તમ કરવાની કાળજી રાખે છે. ચર્ચા કારણ કે એજન્ટ પર્યાવરણની સ્થિતિનું સીધું નિરીક્ષણ કરતું નથી, એજન્ટે સાચા પર્યાવરણની સ્થિતિની અનિશ્ચિતતા હેઠળ નિર્ણયો લેવા જોઈએ. જો કે, પર્યાવરણ સાથે ક્રિયાપ્રતિક્રિયા કરીને અને અવલોકનો પ્રાપ્ત કરીને, એજન્ટ વર્તમાન સ્થિતિના સંભાવના વિતરણને અપડેટ કરીને સાચી સ્થિતિમાં તેની માન્યતાને અપડેટ કરી શકે છે. આ ગુણધર્મનું પરિણામ એ છે કે શ્રેષ્ઠ વર્તણૂકમાં ઘણીવાર (માહિતી ભેગી કરવી) ક્રિયાઓ શામેલ હોઈ શકે છે જે ફક્ત એટલા માટે લેવામાં આવે છે કારણ કે તે એજન્ટના વર્તમાન સ્થિતિના અંદાજમાં સુધારો કરે છે, જેનાથી તે ભવિષ્યમાં વધુ સારા નિર્ણયો લઈ શકે છે. માર્કોવ નિર્ણય પ્રક્રિયાની વ્યાખ્યા સાથે ઉપરોક્ત વ્યાખ્યાની સરખામણી કરવી ઉપદેશક છે. એમ. ડી. પી. માં નિરીક્ષણ સમૂહનો સમાવેશ થતો નથી, કારણ કે એજન્ટ હંમેશા પર્યાવરણની વર્તમાન સ્થિતિને નિશ્ચિતતા સાથે જાણે છે. વૈકલ્પિક રીતે, એમ. ડી. પી. ને અવલોકન સમૂહને સ્થિતિઓના સમૂહની બરાબર સેટ કરીને અને અવલોકનની શરતી સંભાવનાઓને વ્યાખ્યાયિત કરીને જે સાચું સ્થિતિને અનુરૂપ હોય તે નિરીક્ષણને નિર્ધારિત રીતે પસંદ કરીને પી. ઓ. એમ. ડી. પી. તરીકે પુનઃરચના કરી શકાય છે. માન્યતા અપડેટ પગલાં લીધા પછી અને નિરીક્ષણ કર્યા પછી, એજન્ટે પર્યાવરણની સ્થિતિમાં (અથવા નહીં) તેની માન્યતાને અપડેટ કરવાની જરૂર છે. રાજ્ય માર્કોવિયન (ધારણા દ્વારા) હોવાથી, રાજ્યો પરની માન્યતા જાળવી રાખવા માટે ફક્ત અગાઉની માન્યતા સ્થિતિ, લેવામાં આવેલી કાર્યવાહી અને વર્તમાન અવલોકનનું જ્ઞાન જરૂરી છે. કામગીરી સૂચવવામાં આવે છે. નીચે આપણે વર્ણવીએ છીએ કે આ માન્યતા સુધારાની ગણતરી કેવી રીતે કરવામાં આવે છે. પહોંચ્યા પછી, એજન્ટ સંભાવના સાથે નિરીક્ષણ કરે છે. ચાલો સ્ટેટ સ્પેસ પર પ્રોબેબીલીટી ડિસ્ટ્રિબ્યુશન હોઈએ. તે પર્યાવરણની સ્થિતિ હોવાની સંભાવનાને સૂચવે છે. આપેલ છે, પછી પગલાં લીધા પછી અને અવલોકન કર્યા પછી, જ્યાં સાથે નોર્મલાઇઝિંગ કોન્સ્ટન્ટ છે. માન્યતા એમ. ડી. પી. એ માર્કોવિયન માન્યતા સ્થિતિ પી. ઓ. એમ. ડી. પી. ને માર્કોવ નિર્ણય પ્રક્રિયા તરીકે ઘડવાની મંજૂરી આપે છે જ્યાં દરેક માન્યતા એક રાજ્ય છે. પરિણામી માન્યતા એમ. ડી. પી. ને આમ સતત સ્થિતિ અવકાશ પર વ્યાખ્યાયિત કરવામાં આવશે (ભલે "મૂળ" પી. ઓ. એમ. ડી. પી. માં મર્યાદિત સંખ્યામાં સ્થિતિઓ હોયઃ ત્યાં અનંત માન્યતા સ્થિતિઓ (માં) છે કારણ કે સ્થિતિઓ (ની) પર અનંત સંખ્યામાં સંભાવના વિતરણો છે). ઔપચારિક રીતે, માન્યતા એમ. ડી. પી. ને ટુપલ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે જ્યાં પી. ઓ. એમ. ડી. પી. રાજ્યો પર માન્યતા રાજ્યોનો સમૂહ છે, મૂળ પી. ઓ. એમ. ડી. પી. માટે સમાન મર્યાદિત સમૂહ છે, માન્યતા રાજ્ય સંક્રમણ કાર્ય છે, માન્યતા રાજ્યો પર પુરસ્કાર કાર્ય છે, મૂળ પી. ઓ. એમ. ડી. પી. માં સમાન ડિસ્કાઉન્ટ પરિબળ છે. આમાંથી, અને મૂળ પી. ઓ. એમ. ડી. પી. માંથી મેળવવાની જરૂર છે. અગાઉના વિભાગમાં મેળવેલ મૂલ્ય ક્યાં છે અને માન્યતા એમ. ડી. પી. પુરસ્કાર કાર્ય () એ માન્યતા રાજ્ય વિતરણ પર પી. ઓ. એમ. ડી. પી. પુરસ્કાર કાર્યમાંથી અપેક્ષિત પુરસ્કાર છેઃ એમ. ડી. પી. ની માન્યતા હવે આંશિક રીતે અવલોકનક્ષમ નથી, કારણ કે કોઈ પણ સમયે એજન્ટ તેની માન્યતા જાણે છે, અને વિસ્તરણ દ્વારા માન્યતા એમ. ડી. પી. ની સ્થિતિ જાણે છે. નીતિ અને મૂલ્ય કાર્ય "મૂળ" પી. ઓ. એમ. ડી. પી. (જ્યાં દરેક ક્રિયા માત્ર એક જ રાજ્યમાંથી ઉપલબ્ધ હોય છે) થી વિપરીત, સંબંધિત બિલીફ એમ. ડી. પી. માં તમામ માન્યતાઓ તમામ ક્રિયાઓને મંજૂરી આપે છે, કારણ કે તમારી પાસે (લગભગ) હંમેશા એવું માનવાની થોડી સંભાવના હોય છે કે તમે કોઈપણ (મૂળ) સ્થિતિમાં છો. જેમ કે, કોઈપણ માન્યતા માટે ક્રિયાને સ્પષ્ટ કરે છે. અહીં એવું માનવામાં આવે છે કે ઉદ્દેશ અનંત ક્ષિતિજ પર અપેક્ષિત કુલ ડિસ્કાઉન્ટેડ પુરસ્કારને મહત્તમ કરવાનો છે. જ્યારે ખર્ચને વ્યાખ્યાયિત કરવામાં આવે છે, ત્યારે ઉદ્દેશ અપેક્ષિત ખર્ચને ઘટાડવાનો બને છે. માન્યતાથી શરૂ થતી પોલિસી માટે અપેક્ષિત પુરસ્કારને ડિસ્કાઉન્ટ પરિબળ ક્યાં છે તે તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. શ્રેષ્ઠ નીતિ લાંબા ગાળાના પુરસ્કારને શ્રેષ્ઠ બનાવીને મેળવવામાં આવે છે. પ્રારંભિક માન્યતા ક્યાં છે? શ્રેષ્ઠતમ નીતિ, દ્વારા સૂચવવામાં આવે છે, દરેક માન્યતા સ્થિતિ માટે સૌથી વધુ અપેક્ષિત પુરસ્કાર મૂલ્ય આપે છે, જે શ્રેષ્ઠ મૂલ્ય કાર્ય દ્વારા સઘન રીતે રજૂ થાય છે. આ મૂલ્ય કાર્ય બેલમેન ઓપ્ટિમાલિટી સમીકરણનો ઉકેલ છેઃ મર્યાદિત-ક્ષિતિજ પી. ઓ. એમ. ડી. પી. માટે, શ્રેષ્ઠ મૂલ્ય કાર્ય પીસવાઇઝ-રેખીય અને બહિર્મુખ છે. તેને વેક્ટરના મર્યાદિત સમૂહ તરીકે રજૂ કરી શકાય છે. અનંત-ક્ષિતિજ રચનામાં, એક મર્યાદિત વેક્ટર સમૂહ આપખુદ રીતે નજીકથી અંદાજ લગાવી શકે છે, જેનો આકાર બહિર્મુખ રહે છે. મૂલ્ય પુનરાવર્તન એ-ઓપ્ટિમલ મૂલ્ય કાર્યમાં કન્વર્જન્સ ન થાય ત્યાં સુધી મૂલ્યમાં ધીમે ધીમે સુધારો કરવા માટે ગતિશીલ પ્રોગ્રામિંગ અપડેટ લાગુ કરે છે, અને તેની પીસવાઇઝ રેખીયતા અને બહિર્મુખતાને જાળવી રાખે છે. મૂલ્યમાં સુધારો કરીને, નીતિમાં સ્પષ્ટ રીતે સુધારો કરવામાં આવે છે. નીતિ પુનરાવર્તન તરીકે ઓળખાતી અન્ય ગતિશીલ પ્રોગ્રામિંગ તકનીક સ્પષ્ટપણે નીતિને રજૂ કરે છે અને તેમાં સુધારો કરે છે. અંદાજે પી. ઓ. એમ. ડી. પી. ઉકેલો વ્યવહારમાં, પી. ઓ. એમ. ડી. પી. ઘણીવાર ગણતરીત્મક રીતે બરાબર ઉકેલવા માટે અવ્યવહારુ હોય છે, તેથી કોમ્પ્યુટર વૈજ્ઞાનિકોએ એવી પદ્ધતિઓ વિકસાવી છે જે પી. ઓ. એમ. ડી. પી. માટે અંદાજિત ઉકેલો આપે છે. ગ્રીડ-આધારિત અલ્ગોરિધમ્સમાં એક અંદાજિત ઉકેલ તકનીકનો સમાવેશ થાય છે. આ અભિગમમાં, માન્યતા અવકાશમાં બિંદુઓના સમૂહ માટે મૂલ્ય કાર્યની ગણતરી કરવામાં આવે છે, અને ઇન્ટરપોલેશનનો ઉપયોગ અન્ય માન્યતા સ્થિતિઓ માટે લેવા માટે શ્રેષ્ઠ પગલાં નક્કી કરવા માટે થાય છે જેનો સામનો કરવો પડે છે જે ગ્રીડ બિંદુઓના સમૂહમાં નથી. વધુ તાજેતરના કાર્યમાં નમૂનાની તકનીકો, સામાન્યીકરણ તકનીકો અને સમસ્યાના માળખાના ઉપયોગનો ઉપયોગ કરવામાં આવ્યો છે, અને લાખો રાજ્યો સાથે મોટા ક્ષેત્રોમાં પી. ઓ. એમ. ડી. પી. ને વિસ્તૃત કર્યું છે. ઉદાહરણ તરીકે, અનુકૂલનશીલ ગ્રીડ અને બિંદુ-આધારિત પદ્ધતિઓ માન્યતા અવકાશમાં સંબંધિત ક્ષેત્રોમાં આયોજનને મર્યાદિત કરવા માટે અવ્યવસ્થિત રીતે પહોંચી શકાય તેવા માન્યતા બિંદુઓનો નમૂનો લે છે. પી. સી. એ. નો ઉપયોગ કરીને પરિમાણીય ઘટાડાનું પણ સંશોધન કરવામાં આવ્યું છે. પી. ઓ. એમ. ડી. પી. ને ઉકેલવા માટે અંદાજિત ઉકેલ તકનીકોની બીજી રેખા બનાવટી સ્થિતિ તરીકે વર્તમાન સમયના પગલા સુધીના અગાઉના અવલોકનો, ક્રિયાઓ અને પારિતોષિકોના ઇતિહાસનો ઉપયોગ (એક ઉપગણ) કરવા પર આધાર રાખે છે. આ સ્યુડો-સ્ટેટ્સના આધારે એમ. ડી. પી. ને ઉકેલવા માટેની સામાન્ય તકનીકોનો ઉપયોગ કરી શકાય છે (દા. ત. ક્યૂ-લર્નિંગ). આદર્શ રીતે સ્યુડો-સ્ટેટ્સમાં સમગ્ર ઇતિહાસની સૌથી મહત્વપૂર્ણ માહિતી હોવી જોઈએ (પૂર્વગ્રહ ઘટાડવા માટે) જ્યારે શક્ય તેટલી સંકુચિત હોવી જોઈએ (ઓવરફિટિંગ ઘટાડવા માટે). પી. ઓ. એમ. ડી. પી. માં પી. ઓ. એમ. ડી. પી. સિદ્ધાંત આયોજન સામાન્ય રીતે અનિશ્ચિત છે. જો કે, કેટલીક સેટિંગ્સ નિર્ણાયક હોવાનું ઓળખવામાં આવ્યું છે (કોષ્ટક 2 જુઓ, નીચે પુનઃઉત્પાદિત). વિવિધ હેતુઓ પર વિચાર કરવામાં આવ્યો છે. બુચી ઉદ્દેશો બુચી ઓટોમેટા દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે. સુલભતા એ બુચી સ્થિતિનું ઉદાહરણ છે (ઉદાહરણ તરીકે, સારી સ્થિતિમાં પહોંચવું જેમાં તમામ રોબોટ્સ ઘરે હોય). કોબુચી ઉદ્દેશો એવા નિશાનને અનુરૂપ છે જે આપેલ બુચી સ્થિતિને સંતોષતા નથી (દાખલા તરીકે, ખરાબ સ્થિતિ સુધી પહોંચતા નથી જેમાં કેટલાક રોબોટ મૃત્યુ પામ્યા હતા). સમાનતાના ઉદ્દેશોને સમાનતાની રમતો દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે; તેઓ જટિલ ઉદ્દેશોને વ્યાખ્યાયિત કરવામાં સક્ષમ બનાવે છે જેમ કે દર 10 સમયે સારી સ્થિતિ સુધી પહોંચવું. ઉદ્દેશને સંતોષી શકાય છેઃ લગભગ ચોક્કસપણે, એટલે કે ઉદ્દેશ્યને સંતોષવાની સંભાવના 1 છે; હકારાત્મક, એટલે કે ઉદ્દેશ્યને સંતોષવાની સંભાવના 0 કરતા સખત રીતે વધારે છે; માત્રાત્મક, એટલે કે ઉદ્દેશ્યને સંતોષવાની સંભાવના આપેલ થ્રેશોલ્ડ કરતા વધારે છે. આપણે ફાઈનાઈટ મેમરી કેસને પણ ધ્યાનમાં લઈએ છીએ જેમાં એજન્ટ એક ફાઈનાઈટ-સ્ટેટ મશીન છે, અને સામાન્ય કેસ જેમાં એજન્ટ પાસે અનંત મેમરી છે. એપ્લિકેશન્સ પી. ઓ. એમ. ડી. પી. નો ઉપયોગ ઘણી પ્રકારની વાસ્તવિક દુનિયાની સમસ્યાઓનું મોડેલ બનાવવા માટે થઈ શકે છે. નોંધપાત્ર ઉપયોગોમાં ઇસ્કેમિક હૃદય રોગ ધરાવતા દર્દીઓના સંચાલનમાં પી. ઓ. એમ. ડી. પી. નો ઉપયોગ, ડિમેન્શિયા ધરાવતા લોકો માટે સહાયક તકનીક, ગંભીર રીતે લુપ્તપ્રાય અને સુમાત્રાના વાઘને શોધવામાં મુશ્કેલ સંરક્ષણ અને વિમાન અથડામણ ટાળવાનો સમાવેશ થાય છે. એક એપ્લિકેશન શિક્ષણનો કેસ છે, રડતી બાળકની સમસ્યા, જ્યાં માતાપિતાએ બાળક રડતું હોય કે નહીં તેના નિરીક્ષણના આધારે બાળકને ખવડાવવું કે નહીં તે ક્રમિક રીતે નક્કી કરવાની જરૂર છે, જે બાળકની ભૂખની વાસ્તવિક સ્થિતિનું અપૂર્ણ પ્રતિનિધિત્વ છે. સંદર્ભો બાહ્ય લિંક્સ એ. પી. પી. એલ., એક ઝડપી બિંદુ-આધારિત પી. ઓ. એમ. ડી. પી. સોલ્વર ફાઈનાઇટ-સ્ટેટ કંટ્રોલર્સ, જે બાઉન્ડેડ સાઇઝ પી. ઓ. એમ. ડી. પી. ની નીતિઓ માટે શાખા-અને-બાઉન્ડ એક ચોક્કસ પી. ઓ. એમ. ડી. પી. સોલ્વરનો ઉપયોગ કરે છેઃ આંશિક રીતે અવલોકનક્ષમ માર્કોવ નિર્ણય પ્રક્રિયાઓ માટે ઇન્ફ્રાસ્ટ્રક્ચર (પી. ઓ. એમ. ડી. પી.) એક આર પેકેજ જેમાં ટોની કાસાન્ડ્રાના પી. ઓ. એમ. ડી. પી.-સોલ્વ પ્રોગ્રામનો ઇન્ટરફેસ શામેલ છે. POMDPs.jl, વિવિધ ઉકેલકો સાથે જુલિયા અને પાયથોનમાં MDPs અને POMDPs ને વ્યાખ્યાયિત કરવા અને ઉકેલવા માટેનું ઇન્ટરફેસ છે. પાયપોમડીપી, ઓલિવર સ્ટોલમેન અને બેસ્ટિયન મિગ ઝેડએમડીપી દ્વારા પાયથોન માટે (પી. ઓ.) એમ. ડી. પી. ટૂલબોક્સ (સિમ્યુલેટર, સોલ્વર, લર્નર, ફાઇલ રીડર), ટ્રે સ્મિથ ડાયનેમિક પ્રોગ્રામિંગ માર્કોવ દ્વારા પી. ઓ. એમ. ડી. પી. સોલ્વર સ્ટોકેસ્ટિક નિયંત્રણની પ્રક્રિયા કરે છે.