Partially observable Markov decision process
আংশিকভাবে পর্যবেক্ষণযোগ্য মার্কভ সিদ্ধান্ত প্রক্রিয়া (পি. ও. এম. ডি. পি) হল মার্কভ সিদ্ধান্ত প্রক্রিয়ার (এম. ডি. পি) একটি সাধারণীকরণ। একটি পি. ও. এম. ডি. পি একটি এজেন্ট সিদ্ধান্ত প্রক্রিয়া মডেল করে যেখানে এটি ধরে নেওয়া হয় যে সিস্টেমের গতিশীলতা একটি এম. ডি. পি দ্বারা নির্ধারিত হয়, তবে এজেন্ট সরাসরি অন্তর্নিহিত অবস্থা পর্যবেক্ষণ করতে পারে না। পরিবর্তে, এটিকে অবশ্যই একটি সেন্সর মডেল (অন্তর্নিহিত অবস্থার পরিপ্রেক্ষিতে বিভিন্ন পর্যবেক্ষণের সম্ভাব্যতা বিতরণ) এবং অন্তর্নিহিত এমডিপি বজায় রাখতে হবে। এম. ডি. পি-র নীতিগত কার্যকারিতার বিপরীতে যা ক্রিয়াকলাপের সাথে অন্তর্নিহিত রাজ্যগুলিকে ম্যাপ করে, পি. ও. এম. ডি. পি-র নীতি পর্যবেক্ষণের ইতিহাস (বা বিশ্বাসের অবস্থা) থেকে ক্রিয়াকলাপের একটি ম্যাপিং। পি. ও. এম. ডি. পি কাঠামোটি বাস্তব-বিশ্বের বিভিন্ন ক্রমিক সিদ্ধান্ত প্রক্রিয়ার মডেল তৈরি করার জন্য যথেষ্ট সাধারণ। প্রয়োগগুলির মধ্যে রয়েছে রোবট নেভিগেশন সমস্যা, যন্ত্রের রক্ষণাবেক্ষণ এবং সাধারণভাবে অনিশ্চয়তার মধ্যে পরিকল্পনা। অসম্পূর্ণ তথ্য সহ মার্কভ সিদ্ধান্ত প্রক্রিয়াগুলির সাধারণ কাঠামোটি 1965 সালে কার্ল জোহান অ্যাস্ট্রোম একটি বিচ্ছিন্ন রাষ্ট্র স্থানের ক্ষেত্রে বর্ণনা করেছিলেন এবং এটি অপারেশনস রিসার্চ কমিউনিটিতে আরও অধ্যয়ন করা হয়েছিল যেখানে সংক্ষিপ্ত রূপ পিওএমডিপি তৈরি করা হয়েছিল। এটি পরে লেসলি পি. কেলব্লিং এবং মাইকেল এল. লিটম্যান দ্বারা কৃত্রিম বুদ্ধিমত্তা এবং স্বয়ংক্রিয় পরিকল্পনার সমস্যাগুলির জন্য অভিযোজিত হয়েছিল। পি. ও. এম. ডি. পি-র একটি সঠিক সমাধান বিশ্ব রাষ্ট্রগুলির উপর প্রতিটি সম্ভাব্য বিশ্বাসের জন্য সর্বোত্তম পদক্ষেপ প্রদান করে। সর্বোত্তম পদক্ষেপটি সম্ভবত অসীম দিগন্তের উপর এজেন্টের প্রত্যাশিত পুরস্কারকে সর্বাধিক (বা ব্যয়কে হ্রাস করে) করে। সর্বোত্তম ক্রিয়াকলাপের ক্রমটি তার পরিবেশের সাথে মিথস্ক্রিয়া করার জন্য এজেন্টের সর্বোত্তম নীতি হিসাবে পরিচিত। সংজ্ঞা আনুষ্ঠানিক সংজ্ঞা একটি বিচ্ছিন্ন সময়ের পি. ও. এম. ডি. পি একটি প্রতিনিধি এবং তার পরিবেশের মধ্যে সম্পর্কের মডেল তৈরি করে। আনুষ্ঠানিকভাবে, একটি পি. ও. এম. ডি. পি একটি 7-টুপল, যেখানে অবস্থার একটি সেট, ক্রিয়াগুলির একটি সেট, রাজ্যের মধ্যে শর্তাধীন রূপান্তর সম্ভাবনার একটি সেট, পুরষ্কার ফাংশন। এটি পর্যবেক্ষণের একটি সেট, শর্তাধীন পর্যবেক্ষণ সম্ভাবনার একটি সেট এবং এটি ছাড়ের কারণ। প্রতিটি সময়কালে পরিবেশ কোনও না কোনও অবস্থায় থাকে। এজেন্ট একটি পদক্ষেপ নেয়, যার ফলে পরিবেশটি সম্ভাবনার সাথে পরিবর্তিত হয়। একই সময়ে, এজেন্ট একটি পর্যবেক্ষণ পায় যা নির্ভর করে পরিবেশের নতুন অবস্থার উপর, এবং কেবলমাত্র নেওয়া পদক্ষেপের উপর, সম্ভাব্যতা সহ (বা কখনও কখনও সেন্সর মডেলের উপর নির্ভর করে)। অবশেষে, প্রতিনিধি সমান পুরস্কার পান। তারপর প্রক্রিয়াটি পুনরাবৃত্তি করা হয়। এজেন্টের লক্ষ্য হল প্রতিটি সময়ে এমন পদক্ষেপ বেছে নেওয়া যা তার প্রত্যাশিত ভবিষ্যতের ছাড়ের পুরস্কারকে সর্বাধিক করে তোলেঃ, সেই সময়ে অর্জিত পুরস্কার কোথায়। ডিসকাউন্ট ফ্যাক্টর নির্ধারণ করে যে আরও দূরবর্তী পুরষ্কারের তুলনায় কত তাত্ক্ষণিক পুরষ্কার পছন্দ করা হয়। যখন প্রতিনিধি শুধুমাত্র চিন্তা করে যে কোন পদক্ষেপটি সবচেয়ে বড় প্রত্যাশিত তাৎক্ষণিক পুরস্কার প্রদান করবে; যখন প্রতিনিধি ভবিষ্যতের পুরস্কারের প্রত্যাশিত পরিমাণ সর্বাধিক করার বিষয়ে চিন্তা করে। আলোচনা যেহেতু এজেন্ট সরাসরি পরিবেশের অবস্থা পর্যবেক্ষণ করে না, তাই এজেন্টকে অবশ্যই প্রকৃত পরিবেশের অবস্থার অনিশ্চয়তার মধ্যে সিদ্ধান্ত নিতে হবে। যাইহোক, পরিবেশের সাথে মিথস্ক্রিয়া করে এবং পর্যবেক্ষণগুলি গ্রহণ করে, প্রতিনিধি বর্তমান অবস্থার সম্ভাব্যতা বিতরণ আপডেট করে প্রকৃত অবস্থার প্রতি তার বিশ্বাসকে আপডেট করতে পারে। এই বৈশিষ্ট্যের একটি পরিণতি হল যে সর্বোত্তম আচরণে প্রায়শই (তথ্য সংগ্রহ) এমন পদক্ষেপগুলি অন্তর্ভুক্ত থাকতে পারে যা সম্পূর্ণরূপে নেওয়া হয় কারণ তারা বর্তমান অবস্থা সম্পর্কে এজেন্টের অনুমানকে উন্নত করে, যার ফলে এটি ভবিষ্যতে আরও ভাল সিদ্ধান্ত নিতে সক্ষম হয়। মার্কভ সিদ্ধান্ত প্রক্রিয়ার সংজ্ঞার সঙ্গে উপরের সংজ্ঞাটির তুলনা করা শিক্ষণীয়। একটি এম. ডি. পি পর্যবেক্ষণ সেটকে অন্তর্ভুক্ত করে না, কারণ প্রতিনিধি সর্বদা নিশ্চিতভাবে পরিবেশের বর্তমান অবস্থা জানেন। বিকল্পভাবে, একটি এম. ডি. পি-কে পি. ও. এম. ডি. পি হিসাবে পুনর্বিন্যাস করা যেতে পারে পর্যবেক্ষণ সেটকে অবস্থার সেটের সমান করে এবং পর্যবেক্ষণের শর্তাধীন সম্ভাব্যতাগুলিকে সংজ্ঞায়িত করে যা প্রকৃত অবস্থার সাথে সামঞ্জস্যপূর্ণ পর্যবেক্ষণ নির্বাচন করতে পারে। বিশ্বাসের আপডেট পদক্ষেপ নেওয়ার এবং পর্যবেক্ষণ করার পরে, একজন এজেন্টকে পরিবেশের (বা না) অবস্থার উপর তার বিশ্বাস আপডেট করতে হবে। যেহেতু রাষ্ট্রটি মার্কোভিয়ান (অনুমান দ্বারা), তাই রাজ্যগুলির উপর বিশ্বাস বজায় রাখার জন্য কেবল পূর্ববর্তী বিশ্বাসের অবস্থা, গৃহীত পদক্ষেপ এবং বর্তমান পর্যবেক্ষণ সম্পর্কে জ্ঞান প্রয়োজন। অপারেশন চিহ্নিত করা হয়। নীচে আমরা বর্ণনা করছি কিভাবে এই বিশ্বাসের আপডেট গণনা করা হয়। পৌঁছনোর পর, প্রতিনিধি সম্ভাব্যতা পর্যবেক্ষণ করে। স্টেট স্পেসের উপর একটি সম্ভাব্যতা বন্টন ধরা যাক। পরিবেশের অবস্থা থাকার সম্ভাবনাকে বোঝায়। দেওয়া হয়েছে, তারপর পদক্ষেপ নেওয়ার এবং পর্যবেক্ষণ করার পরে, যেখানে একটি স্বাভাবিককরণ ধ্রুবক রয়েছে। বিশ্বাস এম. ডি. পি একটি মার্কোভিয়ান বিশ্বাস রাষ্ট্র একটি পি. ও. এম. ডি. পি-কে মার্কোভ সিদ্ধান্ত প্রক্রিয়া হিসাবে প্রণয়ন করার অনুমতি দেয় যেখানে প্রতিটি বিশ্বাস একটি রাষ্ট্র। ফলস্বরূপ বিশ্বাস এম. ডি. পি এইভাবে একটি অবিচ্ছিন্ন অবস্থা স্থানের উপর সংজ্ঞায়িত করা হবে (এমনকি যদি "উদ্ভূত" পি. ও. এম. ডি. পি-র একটি সীমাবদ্ধ সংখ্যক অবস্থা থাকেঃ অসীম বিশ্বাসের অবস্থা (ইন) রয়েছে কারণ অবস্থার (এর) উপর অসীম সংখ্যক সম্ভাব্যতা বিতরণ রয়েছে)। আনুষ্ঠানিকভাবে, বিশ্বাস এম. ডি. পি-কে একটি টুপল হিসাবে সংজ্ঞায়িত করা হয় যেখানে পি. ও. এম. ডি. পি-র অবস্থার উপর বিশ্বাসের অবস্থার সেট, মূল পি. ও. এম. ডি. পি-র জন্য একই সীমাবদ্ধ ক্রিয়া, বিশ্বাসের অবস্থা রূপান্তর ফাংশন, বিশ্বাসের অবস্থার উপর পুরস্কার ফাংশন, মূল পি. ও. এম. ডি. পি-র সমান ছাড় ফ্যাক্টর। এর মধ্যে, এবং মূল পি. ও. এম. ডি. পি থেকে উদ্ভূত করা প্রয়োজন। পূর্ববর্তী বিভাগে প্রাপ্ত মূল্য কোথায় এবং বিশ্বাস এমডিপি রিওয়ার্ড ফাংশন () হল বিশ্বাস রাষ্ট্র বিতরণের উপর পিওএমডিপি রিওয়ার্ড ফাংশন থেকে প্রত্যাশিত পুরস্কারঃ এম. ডি. পি বিশ্বাসটি আর আংশিকভাবে পর্যবেক্ষণযোগ্য নয়, কারণ যে কোনও নির্দিষ্ট সময়ে এজেন্ট তার বিশ্বাস এবং সম্প্রসারণের মাধ্যমে এম. ডি. পি বিশ্বাসের অবস্থা জানে। নীতি এবং মূল্য ফাংশন "উৎপত্তির" পি. ও. এম. ডি. পি-র (যেখানে প্রতিটি ক্রিয়া শুধুমাত্র একটি রাজ্য থেকে পাওয়া যায়) বিপরীতে, সংশ্লিষ্ট বিশ্বাস এম. ডি. পি-তে সমস্ত বিশ্বাসের অবস্থা সমস্ত ক্রিয়ার অনুমতি দেয়, কারণ আপনার (প্রায়) সর্বদা বিশ্বাস করার কিছু সম্ভাবনা থাকে যে আপনি যে কোনও (উৎপত্তির) অবস্থায় রয়েছেন। এইভাবে, যে কোনও বিশ্বাসের জন্য একটি ক্রিয়া নির্দিষ্ট করে। এখানে অনুমান করা হয় যে উদ্দেশ্য হল একটি অসীম দিগন্তে প্রত্যাশিত মোট ছাড়ের পুরস্কার সর্বাধিক করা। যখন কোনও খরচের সংজ্ঞা দেওয়া হয়, তখন উদ্দেশ্যটি প্রত্যাশিত খরচের ন্যূনতমকরণ হয়ে ওঠে। বিশ্বাস থেকে শুরু করে পলিসির জন্য প্রত্যাশিত পুরষ্কারটি ডিসকাউন্ট ফ্যাক্টর কোথায় হিসাবে সংজ্ঞায়িত করা হয়। দীর্ঘমেয়াদী পুরস্কারকে অনুকূল করে সর্বোত্তম নীতি পাওয়া যায়। প্রাথমিক বিশ্বাস কোথায়? সর্বোত্তম নীতি, দ্বারা চিহ্নিত, প্রতিটি বিশ্বাস রাষ্ট্রের জন্য সর্বোচ্চ প্রত্যাশিত পুরস্কার মূল্য প্রদান করে, যা সর্বোত্তম মূল্য ফাংশন দ্বারা সংক্ষিপ্তভাবে প্রতিনিধিত্ব করে। এই মান ফাংশনটি বেলম্যান অপ্টিমালিটি সমীকরণের সমাধানঃ সসীম-দিগন্ত পিওএমডিপি-র জন্য, সর্বোত্তম মান ফাংশনটি পিসওয়াইজ-লিনিয়ার এবং উত্তল। এটি ভেক্টরের একটি সীমাবদ্ধ সেট হিসাবে প্রতিনিধিত্ব করা যেতে পারে। অসীম-দিগন্ত গঠনে, একটি সসীম ভেক্টর সেট নির্বিচারে ঘনিষ্ঠভাবে আনুমানিকভাবে অনুমান করতে পারে, যার আকৃতি উত্তল থাকে। মান পুনরাবৃত্তি একটি-সর্বোত্তম মান ফাংশনে রূপান্তর না হওয়া পর্যন্ত মানের ধীরে ধীরে উন্নতির জন্য গতিশীল প্রোগ্রামিং আপডেট প্রয়োগ করে এবং এর পিসওয়াইস রৈখিকতা এবং উত্তলতা সংরক্ষণ করে। মূল্যের উন্নতির মাধ্যমে, নীতিটি অন্তর্নিহিতভাবে উন্নত হয়। নীতি পুনরাবৃত্তি নামে আরেকটি গতিশীল প্রোগ্রামিং কৌশল স্পষ্টভাবে নীতির প্রতিনিধিত্ব করে এবং উন্নত করে। আনুমানিক পি. ও. এম. ডি. পি সমাধান বাস্তবে, পি. ও. এম. ডি. পি প্রায়শই গণনামূলকভাবে সঠিকভাবে সমাধান করা কঠিন, তাই কম্পিউটার বিজ্ঞানীরা এমন পদ্ধতি তৈরি করেছেন যা পি. ও. এম. ডি. পি-র আনুমানিক সমাধান। গ্রিড-ভিত্তিক অ্যালগরিদমগুলি একটি আনুমানিক সমাধান কৌশল নিয়ে গঠিত। এই পদ্ধতিতে, বিশ্বাস স্থানের পয়েন্টগুলির একটি সেটের জন্য মান ফাংশন গণনা করা হয় এবং গ্রিড পয়েন্টগুলির সেটের মধ্যে নেই এমন অন্যান্য বিশ্বাসের অবস্থার জন্য সর্বোত্তম পদক্ষেপ নির্ধারণ করতে ইন্টারপোলেশন ব্যবহার করা হয়। আরও সাম্প্রতিক কাজ নমুনা সংগ্রহ কৌশল, সাধারণীকরণ কৌশল এবং সমস্যা কাঠামোর ব্যবহার করে এবং পিওএমডিপি সমাধানকে লক্ষ লক্ষ রাজ্যের সাথে বড় ডোমেনে প্রসারিত করেছে। উদাহরণস্বরূপ, অভিযোজিত গ্রিড এবং বিন্দু-ভিত্তিক পদ্ধতিগুলি বিশ্বাসের ক্ষেত্রে প্রাসঙ্গিক ক্ষেত্রগুলিতে পরিকল্পনাকে সীমাবদ্ধ করার জন্য এলোমেলোভাবে পৌঁছনো বিশ্বাসের পয়েন্টগুলির নমুনা দেয়। পি. সি. এ ব্যবহার করে মাত্রিকতা হ্রাসও অন্বেষণ করা হয়েছে। পিওএমডিপি সমাধানের জন্য আনুমানিক সমাধান কৌশলগুলির আরেকটি লাইন ছদ্ম-অবস্থা হিসাবে বর্তমান সময় ধাপ পর্যন্ত পূর্ববর্তী পর্যবেক্ষণ, ক্রিয়া এবং পুরষ্কারের ইতিহাস (এর একটি উপসেট) ব্যবহারের উপর নির্ভর করে। এই ছদ্ম-রাষ্ট্রগুলির উপর ভিত্তি করে এম. ডি. পি সমাধানের জন্য সাধারণ কৌশলগুলি তখন ব্যবহার করা যেতে পারে (যেমন। প্রশ্ন-শিক্ষা)। আদর্শভাবে ছদ্ম-রাষ্ট্রগুলিতে সমগ্র ইতিহাস থেকে সবচেয়ে গুরুত্বপূর্ণ তথ্য থাকা উচিত (পক্ষপাত হ্রাস করার জন্য) এবং যতটা সম্ভব সংকুচিত হওয়া উচিত (ওভারফিটিং হ্রাস করার জন্য)। পি. ও. এম. ডি. পি-তে পি. ও. এম. ডি. পি তত্ত্ব পরিকল্পনা সাধারণভাবে অনিশ্চিত। যাইহোক, কিছু সেটিংস নির্ণায়ক হিসাবে চিহ্নিত করা হয়েছে (টেবিল 2 দেখুন, নীচে পুনরুত্পাদন করা হয়েছে)। বিভিন্ন উদ্দেশ্য বিবেচনা করা হয়েছে। বুচির উদ্দেশ্যগুলি বুচি অটোমাটা দ্বারা সংজ্ঞায়িত করা হয়। পৌঁছনোযোগ্যতা একটি বুচি অবস্থার একটি উদাহরণ (উদাহরণস্বরূপ, একটি ভাল অবস্থায় পৌঁছানো যেখানে সমস্ত রোবট বাড়িতে থাকে)। কোবুচির উদ্দেশ্যগুলি এমন ট্রেসগুলির সাথে সামঞ্জস্যপূর্ণ যা একটি প্রদত্ত বুচি অবস্থা সন্তুষ্ট করে না (উদাহরণস্বরূপ, এমন একটি খারাপ অবস্থায় পৌঁছায় না যেখানে কিছু রোবট মারা যায়)। সমতা লক্ষ্যগুলি সমতা খেলার মাধ্যমে সংজ্ঞায়িত করা হয়; তারা জটিল উদ্দেশ্যগুলি সংজ্ঞায়িত করতে সক্ষম করে যেমন প্রতি 10 টি সময় ধাপে একটি ভাল অবস্থায় পৌঁছানো। উদ্দেশ্যটি সন্তুষ্ট করা যেতে পারেঃ প্রায়-নিশ্চিতভাবে, অর্থাৎ উদ্দেশ্যটি সন্তুষ্ট করার সম্ভাবনা হল 1; ধনাত্মক, অর্থাৎ উদ্দেশ্যটি সন্তুষ্ট করার সম্ভাবনা 0-এর চেয়ে কঠোরভাবে বেশি; পরিমাণগত, অর্থাৎ উদ্দেশ্যটি সন্তুষ্ট করার সম্ভাবনা একটি প্রদত্ত প্রান্তিকের চেয়ে বেশি। আমরা সীমাবদ্ধ মেমরি কেসটিও বিবেচনা করি যেখানে এজেন্ট একটি সীমাবদ্ধ-অবস্থা মেশিন, এবং সাধারণ ক্ষেত্রে যেখানে এজেন্টের একটি অসীম মেমরি রয়েছে। পি. ও. এম. ডি. পি অ্যাপ্লিকেশনগুলি বিভিন্ন ধরনের বাস্তব-জগতের সমস্যার মডেল তৈরি করতে ব্যবহার করা যেতে পারে। উল্লেখযোগ্য প্রয়োগগুলির মধ্যে রয়েছে ইস্কেমিক হৃদরোগে আক্রান্ত রোগীদের ব্যবস্থাপনায় পি. ও. এম. ডি. পি-র ব্যবহার, স্মৃতিভ্রংশ রোগে আক্রান্ত ব্যক্তিদের জন্য সহায়ক প্রযুক্তি, গুরুতরভাবে বিপন্ন এবং সুমাত্রার বাঘ সনাক্ত করা কঠিন এবং বিমানের সংঘর্ষ এড়ানো। একটি অ্যাপ্লিকেশন হল একটি টিচিং কেস, একটি কান্নাকাটি শিশুর সমস্যা, যেখানে একজন পিতামাতাকে ক্রমানুসারে সিদ্ধান্ত নিতে হবে যে শিশুটি কাঁদছে কিনা তা পর্যবেক্ষণের ভিত্তিতে শিশুটিকে খাওয়ানো হবে কিনা, যা শিশুর প্রকৃত ক্ষুধার অবস্থার একটি অসম্পূর্ণ উপস্থাপনা। রেফারেন্স এক্সটার্নাল লিঙ্ক এপিপিএল, একটি দ্রুত পয়েন্ট-ভিত্তিক পিওএমডিপি সমাধানকারী ফাইনাইট-স্টেট কন্ট্রোলার যা একটি বাউন্ডেড সাইজ পিওএমডিপির নীতির জন্য শাখা-এবং-বাউন্ড একটি সঠিক পিওএমডিপি সমাধানকারী ব্যবহার করেঃ আংশিকভাবে পর্যবেক্ষণযোগ্য মার্কভ সিদ্ধান্ত প্রক্রিয়াগুলির জন্য পরিকাঠামো (পিওএমডিপি) একটি আর প্যাকেজ যার মধ্যে টনি ক্যাসান্দ্রার পিওএমডিপি-সমাধান প্রোগ্রামের একটি ইন্টারফেস রয়েছে। POMDPs.jl, জুলিয়া এবং পাইথনে বিভিন্ন সমাধানকারীর সাথে এমডিপি এবং পিওএমডিপি সংজ্ঞায়িত এবং সমাধান করার জন্য একটি ইন্টারফেস। পাইপোএমডিপি, অলিভার স্টলম্যান এবং বাস্টিয়ান মিগ জেডএমডিপি দ্বারা পাইথনের জন্য একটি (পিও) এমডিপি টুলবক্স (সিমুলেটর, সলভার, লার্নার, ফাইল রিডার), ট্রে স্মিথ ডায়নামিক প্রোগ্রামিং মার্কভের একটি পিওএমডিপি সলভার স্টোকাস্টিক নিয়ন্ত্রণ প্রক্রিয়া করে