स्वचालित योजना और शेड्यूलिंग

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

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

अवलोकन
दुनिया के संभावित प्रारंभिक राज्यों, वांछित लक्ष्यों का विवरण, और संभावित कार्यों के एक सेट का वर्णन, योजना की समस्या एक ऐसी योजना को संश्लेषित करना है जो गारंटीकृत है (जब प्रारंभिक राज्यों में लागू होता है) एक ऐसे राज्य को उत्पन्न करने के लिए जिसमें वांछित लक्ष्य शामिल हैं (ऐसे राज्य को लक्ष्य राज्य कहा जाता है)।

नियोजन की कठिनाई नियोजित सरल धारणाओं पर निर्भर है। कई आयामों में समस्याओं के गुणों के आधार पर नियोजन समस्याओं के कई वर्गों की पहचान की जा सकती है।

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

शास्त्रीय योजना समस्या के रूप में जाना जाने वाला सबसे आसान संभव योजना समस्या, इस प्रकार निर्धारित होती है:

एक अद्वितीय ज्ञात प्रारंभिक राज्य,
अवधिहीन क्रियाएं,
निर्धारक कार्रवाई,
जिसे एक समय में केवल एक ही लिया जा सकता है,
और एक एजेंट।

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

इसके अलावा, योजनाओं को कार्यों के अनुक्रम के रूप में परिभाषित किया जा सकता है, क्योंकि यह हमेशा अग्रिम में जाना जाता है कि कार्यों की आवश्यकता होगी।

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

अलग-अलग समय मार्कोव निर्णय प्रक्रियाएं (एमडीपी) इस तरह की योजना बना रही हैं:

अवधिहीन क्रियाएं,
संभावनाओं के साथ nondeterministic कार्रवाई,
पूर्ण अवलोकनता,
इनाम समारोह का अधिकतमकरण,
और एक एजेंट।

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

यदि एक से अधिक एजेंट हैं, तो हमारे पास बहु-एजेंट योजना है, जो गेम सिद्धांत से निकटता से संबंधित है।

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

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

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

योजना के लिए एल्गोरिदम
शास्त्रीय योजना
भविष्य में चेनिंग स्टेट स्पेस सर्च, संभवतः हेरिस्टिक्स के साथ बढ़ाया गया
पिछड़े चेनिंग खोज, संभवतः राज्य की बाधाओं के उपयोग से बढ़ाया गया है (STRIPS, ग्राफप्लान देखें)
आंशिक आदेश योजना

क्लासिक योजना
पारंपरिक योजना दो मान्यताओं पर आधारित है:

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

एन शास्त्रीय नियोजन, यह क्रियाओं के अनुक्रम की तलाश करने का एक प्रश्न है (उदाहरण के लिए, “एक पैन लें”, “पानी डालें”, “पास्ता डालें”, “आग लगाना”, “पहुंचें”, “बाहर निकालने के लिए आग”)। ए * एल्गोरिदम एक शास्त्रीय नियोजन एल्गोरिदम का एक विशिष्ट उदाहरण है, जो अक्सर इसकी सादगी के लिए प्रारंभिक पाठ्यक्रमों में उपयोग किया जाता है। शास्त्रीय योजनाकारों में उपयोग की जाने वाली कुछ एल्गोरिदमिक तकनीकें यहां दी गई हैं:

एक राज्य अंतरिक्ष में आगे की खोज: हेरिस्टिक खोज योजना (एचएसपी) एल्गोरिदम, फास्ट-फॉरवर्ड एल्गोरिदम (एफएफ),
एक राज्य अंतरिक्ष में पिछली खोज,
योजनाओं की एक जगह, ग्राफप्लान में पहले खोज
एक नियोजन समस्या की छूट: एक आराम की समस्या की गणना करना जिसके लिए यह जानना आसान है कि कोई ऐसी योजना है जो प्रारंभिक समस्या को हल करने में मदद करती है
प्रस्तावपरक तर्क के सूत्र की एक संतुष्टि समस्या में परिवर्तन।

बाइलैंडर ने 1 99 4 में प्रदर्शित किया कि परंपरागत योजना PSPACE- पूर्ण है।

अन्य समस्याओं में कमी
प्रस्तावपरक संतुष्टि समस्या (satplan) में कमी।
मॉडल जांच में कमी – दोनों अनिवार्य रूप से राज्य रिक्त स्थानों की समस्याओं की समस्याएं हैं, और शास्त्रीय नियोजन समस्या मॉडल जांच समस्याओं के उप-वर्ग से मेल खाती है।

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

संभाव्य योजना
संभाव्य योजना को पुनरावृत्ति विधियों जैसे मूल्य पुनरावृत्ति और नीति पुनरावृत्ति के साथ हल किया जा सकता है, जब राज्य की जगह पर्याप्त रूप से छोटी होती है। आंशिक अवलोकनता के साथ, संभाव्य योजना को समान रूप से पुनरावृत्तियों के साथ हल किया जाता है, लेकिन राज्यों के बजाय विश्वासों की जगह के लिए परिभाषित मूल्य कार्यों का प्रतिनिधित्व करते हुए।

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

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

एक सशर्त योजनाकार का प्रारंभिक उदाहरण “वारप्लान-सी” है जिसे 1 9 70 के दशक के मध्य में पेश किया गया था। अब तक, प्रश्न का उत्तर नहीं दिया गया था कि सामान्य अनुक्रम और जटिल योजना के बीच क्या अंतर है, जिसमें if-then-statement शामिल हैं। इसे योजना के रनटाइम पर अनिश्चितता के साथ करना है। विचार यह है कि एक योजना सेंसर संकेतों पर प्रतिक्रिया दे सकती है जो योजनाकार के लिए अज्ञात हैं। योजनाकार अग्रिम में दो विकल्प उत्पन्न करता है। उदाहरण के लिए, यदि कोई ऑब्जेक्ट पता चला है, तो क्रिया ए को निष्पादित किया जाता है, यदि कोई ऑब्जेक्ट गुम है, तो क्रिया बी निष्पादित की जाती है। सशर्त योजना का एक बड़ा लाभ आंशिक योजनाओं को संभालने की क्षमता है। एक एजेंट को शुरू से ही खत्म होने तक सब कुछ योजना बनाने के लिए मजबूर नहीं किया जाता है, लेकिन समस्या को टुकड़ों में विभाजित कर सकता है। इससे राज्य की जगह को कम करने में मदद मिलती है और इससे अधिक जटिल समस्याएं हल होती हैं।

योजना प्रणाली की तैनाती
हबल स्पेस टेलीस्कॉप एसपीएसएस नामक शॉर्ट-टर्म सिस्टम और स्पाइक नामक लंबी अवधि की योजना प्रणाली का उपयोग करता है।

अन्य प्रकार की योजना
व्यावहारिक रूप से, यह केवल शास्त्रीय नियोजन की शायद ही कभी धारणाओं की जांच करता है। यही कारण है कि कई एक्सटेंशन उभरे हैं।

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

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

रिंटानेन ने 2004 में प्रदर्शित किया कि यदि शाखाकरण जोड़ा जाता है (आकस्मिक योजना), नियोजन समस्या EXPTIME-पूर्ण हो जाती है। संगत योजना का एक विशेष मामला फॉन्ड की समस्याओं से दर्शाया जाता है – “पूरी तरह से देखने योग्य और गैर-निर्धारिती” के लिए। यदि लक्ष्य एलटीएलएफ (परिमित ट्रेस पर रैखिक अस्थायी तर्क) में निर्दिष्ट है तो समस्या हमेशा एलडीएलएफ में एक उद्देश्य विनिर्देश के लिए पूर्ण 16 और 2EXPTIME पूर्ण हो जाती है।

यदि, इसके अलावा, कोई पारंपरिक नियोजन (यानी अनुपालन योजना) के लिए अनिश्चितता जोड़ता है, तो यह एक्स्प्रेस-अपूर्ण हो जाता है। यदि हम दोनों शाखाओं और अनिश्चितता (अनुपालन और आकस्मिक दोनों की योजना बनाते हैं) जोड़ते हैं, तो यह 2EXPTIME-पूर्ण हो जाता है।

संभाव्य योजना
कुशमेरिक एट अल। संभाव्य योजना की शुरुआत की। उनके काम में, कार्यों के प्रभाव probabilists के साथ वर्णित है। वह निम्नलिखित तरीके से वर्णित ‘रोबोट एक ब्लॉक लेता है’ कार्रवाई का उदाहरण देता है: यदि रोबोट का ग्रिपर सूखा है, तो रोबोट ब्लॉक को संभाव्यता 0.95 के साथ रखता है; अगर क्लैंप गीला है, तो रोबोट ब्लॉक को 0.5 की संभावना के साथ रखता है।

इससे मार्कोव निर्णय प्रक्रिया (एमडीपी) या (सामान्य मामले में) आंशिक रूप से पर्यवेक्षित मार्कोव निर्णय प्रक्रिया (पीओएमडीपी) के लिए नीति उत्पादन (या रणनीति) की समस्या होती है।

Nonlinear योजना
क्लासिक प्लानिंग किसी दिए गए क्रम में उप-लक्ष्यों को हल करती है। समस्या यह है कि यह कभी-कभी जो पहले से ही बनाया गया है उसे नष्ट करने की ओर ले जाता है। इस घटना को सुस्मान विसंगति के रूप में जाना जाता है।

मान लीजिए कि एक व्यक्ति नंगे पैर उसी स्थिति में होना चाहिए क्योंकि वह अपने दाहिने जूते पहन रहा है, उसका बायां जूता, उसका दाहिना साक और उसका बायां साक। यदि वह वचन के क्रम में लक्ष्यों को प्राप्त करना चाहता है, तो वह असफल हो जाएगा।

इस प्रकार की समस्या को हल करने के लिए, कोई आंशिक रूप से आदेशित योजनाओं में जा सकता है जिसमें क्रियाओं के बीच क्रम केवल तभी तय किया जाता है जब आवश्यक हो (नवीनतम या कम से कम प्रतिबद्धता योजना पर वचनबद्धता)।

पिछले उदाहरण में, बाएं जूते डालने के बाद बाएं जूते को रखा जाना चाहिए। दाईं ओर के लिए वही। दूसरी तरफ, बाईं ओर की योजना का निष्पादन दाहिनी ओर निष्पादन से स्वतंत्र है। इसलिए समग्र योजना आंशिक रूप से आदेशित है।

इस श्रेणी की समस्या को संभालने में सक्षम योजनाकार आंशिक आदेश (पीओपी, नोएएच, इत्यादि) कहा जाता है।

पदानुक्रमिक योजना
आम तौर पर, जब योजना बनाते हैं, तो किसी के पास कार्यों पर पदानुक्रमिक जानकारी हो सकती है, यह वर्णन करना है कि जटिल कार्य कैसे विघटित होते हैं। उदाहरण के लिए, “कॉफ़ी की सेवा” जैसी जटिल कार्रवाई को “कॉफी बनाने” और फिर “कॉफी लाने” के दो जटिल कार्यों के अनुक्रम में विभाजित किया जा सकता है। इस प्रकार, योजनाकार हैं, जैसे एबस्ट्रिप्स, जो कार्यों के विवरण के अलावा, कार्यों के पदानुक्रमित विवरण इनपुट के रूप में लेते हैं। उदाहरण के लिए एक उच्च स्तर पर योजना बनाना शुरू कर सकता है, यदि आवश्यक हो तो विवरण में नीचे जाएं (उदाहरण के लिए ABSTRIPS करता है)। उद्देश्य को पदानुक्रमित कार्य नेटवर्क (एचटीएन) का उपयोग करके वर्णित किया गया है।

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

सामान्य योजना
सामान्य नियोजन में ऐसी योजना तैयार करने का समावेश होता है जो कई शुरुआती वातावरण के लिए काम करता है।

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

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

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

उद्देश्य:

ऊपर (ए, बी) Λ ऊपर (बी, सी)
प्रारम्भिक अवस्था :

[ऊपर (ए, टेबल) Λ ऊपर (बी, टेबल) Λ ऊपर (सी, ए) Λ लॉक (ए) Λ लॉक (बी) Λ लॉक (सी) Λ प्रकटीकरण (बी) Λ प्रकटीकरण (सी)]
उपलब्ध कार्य:

ले जाएं (बी, एक्स, वाई)
पूर्व शर्त: ऊपर (बी, एक्स) Λ खुला (बी) Λ खुला (वाई) Λ ब्लॉक (बी) Λ ब्लॉक (वाई) Λ (बी ≠ एक्स) Λ (बी ≠ वाई) Λ (एक्स ≠ वाई)
अतिरिक्त: ऊपर (बी, वाई) Λ पता चला (एक्स)
रद्द करना: ऊपर (बी, एक्स) Λ पता चला (वाई)
Move_tool (बी, एक्स)
अनुदान: ऊपर (बी, एक्स) Λ खुला (बी) Λ खुला (वाई) Λ ब्लॉक (बी) Λ (बी ≠ एक्स)
अतिरिक्त: ऊपर (बी, तालिका) Λ पता चला (एक्स)
रद्द करना: ऊपर (बी, एक्स)

उदाहरण

नियोजन का अनौपचारिक उदाहरण।

लक्ष्य
फ्रिज में कुछ फल और सब्जियां हैं

प्रारम्भिक अवस्था
[घर पर, चप्पल में खाली फ्रिज]

उपलब्ध क्रियाएं (अनियंत्रित सूची)
घर जाओ
जूते पहनो,
कार कुंजी ले लो,
कार द्वारा स्टोर तक पहुंचें,
पैर पर दुकान तक पहुंचें,
वापीस घर जाओ,
फ्रिज में खरीददारी करें,
दुकान में प्रवेश करें,
फल ले लो,
सब्जियां ले लो,
भुगतान करने के लिए।

संभावित समाधान (आदेशित सूची)
[1- जूते पहनें, 2- कार की चाबियाँ लें, 3- घर से बाहर निकलें, 4- कार से स्टोर में जाओ, 5- स्टोर में जाओ, 6- फल लें, 7- सब्जियां लें, 8- वेतन, 9- घर वापस जाओ, फ्रिज में 10- जगह खरीद]

एक और संभावित समाधान (आदेशित सूची):
[1- जूते पहनें, 2- बाहर जाओ, 3- पैर से दुकान में जाओ, 4- दुकान में जाओ, 5- सब्जियां लें, 6- फल लें, 7- वेतन, 8- घर जाओ, 9-जगह खरीद फ्रिज में]

निष्कर्ष
उदाहरण से हम देख सकते हैं कि कैसे:

समाधान कई हो सकते हैं,
वर्तमान कार्य हो सकते हैं जो अनिवार्य रूप से किया जाना चाहिए, अनिवार्य रूप से, दूसरों के बाद (अगर मैं पहले चाबियाँ नहीं लेता तो मैं कार द्वारा स्टोर तक नहीं पहुंच सकता)
ऐसे क्रियाएं हो सकती हैं जो उलटा हो (फल और सब्जियां लें)
यह आवश्यक नहीं है कि अंतिम योजना में कई क्रियाएं या अदला-बदली क्रियाओं के अनुक्रमों (पैर या कार द्वारा दुकान तक पहुंचने) के मामले में सभी कार्य शामिल हैं।