Partially observable Markov decision process
جزوی طور پر قابل مشاہدہ مارکوف فیصلہ عمل (پی او ایم ڈی پی) مارکوف فیصلہ عمل (ایم ڈی پی) کی عمومی شکل ہے۔ پی او ایم ڈی پی ایک ایجنٹ کے فیصلے کے عمل کا نمونہ بناتا ہے جس میں یہ فرض کیا جاتا ہے کہ نظام کی حرکیات کا تعین ایم ڈی پی کے ذریعے کیا جاتا ہے، لیکن ایجنٹ براہ راست بنیادی حالت کا مشاہدہ نہیں کر سکتا۔ اس کے بجائے، اسے ایک سینسر ماڈل (بنیادی حالت کو دیکھتے ہوئے مختلف مشاہدات کی امکان کی تقسیم) اور بنیادی ایم ڈی پی کو برقرار رکھنا چاہیے۔ ایم ڈی پی میں پالیسی فنکشن کے برعکس جو بنیادی ریاستوں کو اعمال سے جوڑتا ہے، پی او ایم ڈی پی کی پالیسی مشاہدات (یا عقیدے کی ریاستوں) کی تاریخ سے لے کر اعمال تک کی نقشہ سازی ہے۔ پی او ایم ڈی پی فریم ورک مختلف قسم کے حقیقی دنیا کے ترتیب وار فیصلہ سازی کے عمل کو ماڈل بنانے کے لیے کافی عام ہے۔ ایپلی کیشنز میں روبوٹ نیویگیشن کے مسائل، مشین کی دیکھ بھال، اور عام طور پر غیر یقینی صورتحال میں منصوبہ بندی شامل ہیں۔ نامکمل معلومات کے ساتھ مارکوف کے فیصلہ سازی کے عمل کے عمومی ڈھانچے کو کارل جوہان آستروم نے 1965 میں ایک مجرد ریاستی جگہ کے معاملے میں بیان کیا تھا، اور اس کا مزید مطالعہ آپریشنز ریسرچ کمیونٹی میں کیا گیا جہاں مخفف پی او ایم ڈی پی تیار کیا گیا تھا۔ اسے بعد میں لیسلی پی کیلبلنگ اور مائیکل ایل لٹ مین نے مصنوعی ذہانت اور خودکار منصوبہ بندی کے مسائل کے لیے ڈھال لیا۔ پی او ایم ڈی پی کا ایک درست حل عالمی ریاستوں کے ہر ممکنہ عقیدے کے لیے بہترین عمل فراہم کرتا ہے۔ زیادہ سے زیادہ عمل ممکنہ طور پر لامحدود افق پر ایجنٹ کے متوقع انعام کو زیادہ سے زیادہ (یا لاگت کو کم سے کم) کرتا ہے۔ بہترین اقدامات کی ترتیب کو اپنے ماحول کے ساتھ تعامل کے لیے ایجنٹ کی بہترین پالیسی کے طور پر جانا جاتا ہے۔ تعریف رسمی تعریف ایک مجرد وقت کا پی او ایم ڈی پی ایک ایجنٹ اور اس کے ماحول کے درمیان تعلقات کا نمونہ بناتا ہے۔ رسمی طور پر، ایک پی او ایم ڈی پی ایک 7-ٹپل ہے، جہاں ریاستوں کا ایک مجموعہ ہوتا ہے، اعمال کا ایک مجموعہ ہوتا ہے، ریاستوں کے درمیان مشروط منتقلی کے امکانات کا ایک مجموعہ ہوتا ہے، انعام کا کام ہوتا ہے۔ یہ مشاہدات کا ایک مجموعہ ہے، مشروط مشاہدے کے امکانات کا ایک مجموعہ ہے، اور رعایتی عنصر ہے۔ ہر وقت کی مدت میں ماحول کسی نہ کسی حالت میں ہوتا ہے۔ ایجنٹ ایک کارروائی کرتا ہے، جس کی وجہ سے ماحول امکان کے ساتھ حالت میں منتقل ہوتا ہے۔ ایک ہی وقت میں، ایجنٹ کو ایک مشاہدہ موصول ہوتا ہے جو ماحول کی نئی حالت پر منحصر ہوتا ہے، اور صرف کی گئی کارروائی پر، امکان کے ساتھ (یا بعض اوقات سینسر ماڈل پر منحصر ہوتا ہے)۔ آخر میں، ایجنٹ کو اس کے برابر انعام ملتا ہے۔ اس کے بعد عمل دہرایا جاتا ہے۔ ایجنٹ کا مقصد یہ ہے کہ وہ ہر وقت کے مرحلے پر ایسے اقدامات کا انتخاب کرے جو اس کے متوقع مستقبل کے رعایتی انعام کو زیادہ سے زیادہ کرے:، وقت پر حاصل کردہ انعام کہاں ہے۔ ڈسکاؤنٹ فیکٹر اس بات کا تعین کرتا ہے کہ زیادہ دور کے انعامات کے مقابلے میں کتنے فوری انعامات کو ترجیح دی جاتی ہے۔ جب ایجنٹ صرف اس بات کی پرواہ کرتا ہے کہ کون سی کارروائی سب سے زیادہ متوقع فوری انعام دے گی ؛ جب ایجنٹ مستقبل کے انعامات کی متوقع رقم کو زیادہ سے زیادہ کرنے کی پرواہ کرتا ہے۔ بحث چونکہ ایجنٹ براہ راست ماحول کی حالت کا مشاہدہ نہیں کرتا ہے، اس لیے ایجنٹ کو حقیقی ماحولیاتی حالت کی غیر یقینی صورتحال میں فیصلے کرنے چاہئیں۔ تاہم، ماحول کے ساتھ تعامل کرکے اور مشاہدات حاصل کرکے، ایجنٹ موجودہ حالت کی امکان کی تقسیم کو اپ ڈیٹ کرکے حقیقی حالت میں اپنے عقیدے کو اپ ڈیٹ کر سکتا ہے۔ اس خاصیت کا نتیجہ یہ ہے کہ زیادہ سے زیادہ رویے میں اکثر (معلومات اکٹھا کرنا) اقدامات شامل ہو سکتے ہیں جو خالصتا اس وجہ سے کیے جاتے ہیں کہ وہ موجودہ حالت کے بارے میں ایجنٹ کے تخمینے کو بہتر بناتے ہیں، اس طرح اسے مستقبل میں بہتر فیصلے کرنے کی اجازت دیتے ہیں۔ مندرجہ بالا تعریف کا مارکوف فیصلہ سازی کے عمل کی تعریف سے موازنہ کرنا سبق آموز ہے۔ ایم ڈی پی میں مشاہداتی سیٹ شامل نہیں ہوتا ہے، کیونکہ ایجنٹ ہمیشہ ماحول کی موجودہ حالت کو یقین کے ساتھ جانتا ہے۔ متبادل طور پر، ایک ایم ڈی پی کو مشاہدے کے سیٹ کو اسٹیٹس کے سیٹ کے برابر ترتیب دے کر اور مشاہدے کے مشروط امکانات کی وضاحت کر کے پی او ایم ڈی پی کے طور پر دوبارہ تشکیل دیا جا سکتا ہے تاکہ اس مشاہدے کو فیصلہ کن طور پر منتخب کیا جا سکے جو حقیقی حالت سے مطابقت رکھتا ہے۔ عمل کرنے اور مشاہدہ کرنے کے بعد، ایک ایجنٹ کو اس حالت میں اپنے عقیدے کو اپ ڈیٹ کرنے کی ضرورت ہوتی ہے جس میں ماحول ہو سکتا ہے (یا نہیں)۔ چونکہ ریاست مارکووین ہے (مفروضے کے مطابق)، ریاستوں پر یقین برقرار رکھنے کے لیے صرف سابقہ عقیدے کی حالت، کی گئی کارروائی اور موجودہ مشاہدے کا علم درکار ہوتا ہے۔ آپریشن کی نشاندہی کی جاتی ہے۔ ذیل میں ہم بیان کرتے ہیں کہ اس عقیدے کی تازہ کاری کا حساب کیسے لگایا جاتا ہے۔ پہنچنے کے بعد، ایجنٹ امکان کے ساتھ مشاہدہ کرتا ہے۔ ریاستی جگہ پر امکان کی تقسیم ہونے دیں۔ اس امکان کو ظاہر کرتا ہے کہ ماحول حالت میں ہے۔ دیا گیا، پھر کارروائی کرنے اور مشاہدہ کرنے کے بعد، جہاں کے ساتھ ایک نارملائزنگ مستقل ہے۔ یقین ایم ڈی پی ایک مارکووین عقیدے کی حالت ایک پی او ایم ڈی پی کو مارکوف فیصلہ سازی کے عمل کے طور پر وضع کرنے کی اجازت دیتی ہے جہاں ہر عقیدہ ایک ریاست ہے۔ اس طرح نتیجے میں آنے والے عقیدے ایم ڈی پی کی تعریف ایک مسلسل ریاستی جگہ پر کی جائے گی (یہاں تک کہ اگر "اصل" پی او ایم ڈی پی میں ریاستوں کی ایک محدود تعداد ہو: لامحدود عقیدے کی ریاستیں (میں) ہیں کیونکہ ریاستوں (کے) پر امکانات کی تقسیم کی ایک لامحدود تعداد موجود ہے)۔ رسمی طور پر، عقیدے ایم ڈی پی کو ایک ٹپل کے طور پر بیان کیا گیا ہے جہاں پی او ایم ڈی پی ریاستوں پر عقائد کا مجموعہ ہے، اصل پی او ایم ڈی پی کے طور پر کارروائی کا وہی محدود مجموعہ ہے، عقیدے کی ریاست کی منتقلی کا فنکشن ہے، عقیدے کی ریاستوں پر انعام کا فنکشن ہے، اصل پی او ایم ڈی پی کے برابر رعایت کا عنصر ہے۔ ان میں سے، اور اصل پی او ایم ڈی پی سے اخذ کرنے کی ضرورت ہے۔ پچھلے حصے میں حاصل کردہ قدر کہاں ہے اور ٹرسٹ ایم ڈی پی ریوارڈ فنکشن () ٹرسٹ اسٹیٹ ڈسٹری بیوشن پر پی او ایم ڈی پی ریوارڈ فنکشن سے متوقع انعام ہے: ایم ڈی پی کا عقیدہ اب جزوی طور پر قابل مشاہدہ نہیں ہے، کیونکہ کسی بھی وقت ایجنٹ اپنے عقیدے کو جانتا ہے، اور توسیع کے ذریعے عقیدے کی حالت ایم ڈی پی کو جانتا ہے۔ پالیسی اور ویلیو فنکشن "اصل" پی او ایم ڈی پی کے برعکس (جہاں ہر عمل صرف ایک ریاست سے دستیاب ہے)، متعلقہ بیلیف ایم ڈی پی میں تمام عقیدے کی ریاستیں تمام اعمال کی اجازت دیتی ہیں، کیونکہ آپ (تقریبا) ہمیشہ یہ یقین کرنے کا کچھ امکان رکھتے ہیں کہ آپ کسی بھی (اصل) حالت میں ہیں۔ اس طرح، کسی بھی عقیدے کے لیے عمل کی وضاحت کرتا ہے۔ یہاں یہ فرض کیا جاتا ہے کہ مقصد ایک لامحدود افق پر متوقع کل رعایتی انعام کو زیادہ سے زیادہ کرنا ہے۔ جب لاگت کی وضاحت کی جاتی ہے، تو مقصد متوقع لاگت کو کم سے کم کرنا بن جاتا ہے۔ یقین سے شروع ہونے والی پالیسی کے لیے متوقع انعام کی تعریف اس طرح کی جاتی ہے کہ رعایت کا عنصر کہاں ہے۔ زیادہ سے زیادہ پالیسی طویل مدتی انعام کو بہتر بنا کر حاصل کی جاتی ہے۔ ابتدائی عقیدہ کہاں ہے؟ زیادہ سے زیادہ پالیسی، جس کی طرف اشارہ کیا گیا ہے، ہر عقیدے کی ریاست کے لیے سب سے زیادہ متوقع انعامی قیمت حاصل کرتی ہے، جس کی نمائندگی زیادہ سے زیادہ قدر فنکشن کے ذریعے کی جاتی ہے۔ یہ ویلیو فنکشن بیل مین آپٹیمیلیٹی مساوات کا حل ہے: محدود افقی پی او ایم ڈی پیز کے لیے، آپٹیمل ویلیو فنکشن پیس وائز لکیری اور کنویکس ہے۔ اسے ویکٹروں کے ایک محدود سیٹ کے طور پر پیش کیا جا سکتا ہے۔ لامحدود افق کی تشکیل میں، ایک محدود ویکٹر سیٹ من مانی طور پر قریب سے اندازہ لگا سکتا ہے، جس کی شکل کنویکس رہتی ہے۔ ویلیو ایٹریشن ڈائنامک پروگرامنگ اپ ڈیٹ کا اطلاق کرتا ہے تاکہ قدر کو بتدریج بہتر بنایا جا سکے جب تک کہ ایک بہترین ویلیو فنکشن میں کنورجنس نہ ہو جائے، اور اس کی پیس وائز لینیرٹی اور کنویکسٹی کو محفوظ رکھتا ہے۔ قدر کو بہتر بنانے سے پالیسی میں واضح طور پر بہتری آتی ہے۔ ایک اور متحرک پروگرامنگ تکنیک جسے پالیسی تکرار کہا جاتا ہے اس کے بجائے واضح طور پر پالیسی کی نمائندگی کرتی ہے اور اسے بہتر بناتی ہے۔ عملی طور پر، پی او ایم ڈی پیز اکثر کمپیوٹیشنل طور پر درست طریقے سے حل کرنے کے قابل نہیں ہوتے ہیں، اس لیے کمپیوٹر سائنس دانوں نے ایسے طریقے تیار کیے ہیں جو پی او ایم ڈی پیز کے لیے حل کا تخمینہ لگاتے ہیں۔ گرڈ پر مبنی الگورتھم ایک تخمینی حل کی تکنیک پر مشتمل ہے۔ اس نقطہ نظر میں، ویلیو فنکشن کا حساب عقیدے کی جگہ میں پوائنٹس کے ایک سیٹ کے لیے کیا جاتا ہے، اور انٹرپولیشن کا استعمال ان دیگر عقائد کی حالتوں کے لیے زیادہ سے زیادہ کارروائی کا تعین کرنے کے لیے کیا جاتا ہے جن کا سامنا کرنا پڑتا ہے جو گرڈ پوائنٹس کے سیٹ میں نہیں ہیں۔ مزید حالیہ کام نمونے لینے کی تکنیکوں، عمومی کاری کی تکنیکوں اور مسئلہ کے ڈھانچے کے استحصال کا استعمال کرتا ہے، اور پی او ایم ڈی پی کو لاکھوں ریاستوں کے ساتھ بڑے ڈومینز میں توسیع دی ہے۔ مثال کے طور پر، اڈیپٹو گرڈ اور پوائنٹ پر مبنی طریقے بے ترتیب قابل رسائی عقیدے کے نکات کا نمونہ لیتے ہیں تاکہ یقین کی جگہ میں متعلقہ شعبوں میں منصوبہ بندی کو محدود کیا جا سکے۔ پی سی اے کا استعمال کرتے ہوئے جہتی کمی کی بھی کھوج کی گئی ہے۔ پی او ایم ڈی پیز کو حل کرنے کے لیے تخمینی حل کی تکنیکوں کی ایک اور لائن پچھلے مشاہدات، اعمال اور انعامات کی تاریخ (کے ذیلی سیٹ) کو موجودہ وقت کے مرحلے تک ایک فرضی ریاست کے طور پر استعمال کرنے پر انحصار کرتی ہے۔ ان فرضی ریاستوں کی بنیاد پر ایم ڈی پیز کو حل کرنے کے لیے عام تکنیکیں پھر استعمال کی جا سکتی ہیں (مثال کے طور پر۔ ق-لرننگ)۔ مثالی طور پر فرضی ریاستوں کو پوری تاریخ کی سب سے اہم معلومات پر مشتمل ہونا چاہیے (تعصب کو کم کرنے کے لیے) جبکہ جتنا ممکن ہو اتنا کمپریسڈ ہونا چاہیے (اوورفٹنگ کو کم کرنے کے لیے)۔ پی او ایم ڈی پی میں پی او ایم ڈی پی تھیوری پلاننگ عام طور پر ناقابل فیصلہ ہے۔ تاہم، کچھ ترتیبات کی نشاندہی فیصلہ کن ہونے کے لیے کی گئی ہے (ٹیبل 2 میں دیکھیں، نیچے دوبارہ پیش کیا گیا ہے)۔ مختلف مقاصد پر غور کیا گیا ہے۔ بوچی کے مقاصد کی وضاحت بوچی آٹومیٹا کے ذریعے کی جاتی ہے۔ رسائی بوچی حالت کی ایک مثال ہے (مثال کے طور پر، ایک اچھی حالت میں پہنچنا جس میں تمام روبوٹ گھر پر ہوں)۔ کوبوچی کے مقاصد ان نشانات سے مطابقت رکھتے ہیں جو کسی دی گئی بوچی حالت کو پورا نہیں کرتے ہیں (مثال کے طور پر، ایسی خراب حالت میں نہیں پہنچنا جس میں کچھ روبوٹ مر گیا ہو)۔ برابری کے مقاصد کی تعریف برابری کے کھیلوں کے ذریعے کی جاتی ہے۔ وہ پیچیدہ مقاصد کی وضاحت کرنے کے قابل بناتے ہیں جیسے کہ ہر 10 ٹائم اسٹیپس پر ایک اچھی حالت تک پہنچنا۔ مقصد کو پورا کیا جا سکتا ہے: تقریبا یقینی طور پر، یعنی مقصد کو پورا کرنے کا امکان 1 ہے ؛ مثبت، یعنی مقصد کو پورا کرنے کا امکان 0 سے سختی سے زیادہ ہے ؛ مقداری، یعنی مقصد کو پورا کرنے کا امکان دی گئی حد سے زیادہ ہے۔ ہم محدود میموری کیس پر بھی غور کرتے ہیں جس میں ایجنٹ ایک محدود ریاستی مشین ہے، اور عام کیس جس میں ایجنٹ کی لامحدود میموری ہوتی ہے۔ ایپلی کیشنز پی او ایم ڈی پیز کو کئی قسم کے حقیقی دنیا کے مسائل کے نمونے بنانے کے لیے استعمال کیا جا سکتا ہے۔ قابل ذکر ایپلی کیشنز میں اسکیمک دل کی بیماری کے مریضوں کے انتظام میں پی او ایم ڈی پی کا استعمال، ڈیمینشیا کے شکار افراد کے لیے معاون ٹیکنالوجی، انتہائی خطرے سے دوچار اور سماتران شیروں کا پتہ لگانا مشکل ہے اور ہوائی جہاز کے تصادم سے بچنا شامل ہیں۔ ایک درخواست ایک تدریسی معاملہ ہے، ایک بچے کے رونے کا مسئلہ، جہاں والدین کو ترتیب وار فیصلہ کرنے کی ضرورت ہوتی ہے کہ بچے کو دودھ پلانا ہے یا نہیں اس مشاہدے کی بنیاد پر کہ آیا بچہ رو رہا ہے یا نہیں، جو کہ بچے کی بھوک کی اصل حالت کی نامکمل نمائندگی ہے۔ حوالہ جات بیرونی روابط اے پی پی ایل، ایک تیز پوائنٹ پر مبنی پی او ایم ڈی پی حل کرنے والا فائنائٹ اسٹیٹ کنٹرولر جو برانچ اینڈ باؤنڈ این ایکزیکٹ پی او ایم ڈی پی حل کرنے والا باؤنڈڈ سائز کی پالیسیوں کے لیے استعمال کرتا ہے۔ پی او ایم ڈی پی: جزوی طور پر قابل مشاہدہ مارکوف فیصلہ کے عمل کے لیے انفراسٹرکچر (پی او ایم ڈی پی) ایک آر پیکیج جس میں ٹونی کیسینڈرا کے پی او ایم ڈی پی حل پروگرام کا انٹرفیس شامل ہے۔ POMDPs.jl، جولیا اور ازگر میں مختلف قسم کے حل کاروں کے ساتھ ایم ڈی پیز اور پی او ایم ڈی پیز کی وضاحت اور حل کرنے کے لیے ایک انٹرفیس ہے۔ پائپو ایم ڈی پی، ایک (پی او) ایم ڈی پی ٹول باکس (سمیلیٹر، سولور، لرنر، فائل ریڈر) از اولیور اسٹولمین اور باسٹین مگ زیڈ ایم ڈی پی، ٹری اسمتھ ڈائنامک پروگرامنگ مارکوف کا ایک پی او ایم ڈی پی سولور، اسٹاکسٹک کنٹرول پر کارروائی کرتا ہے۔