स्वचालित योजना और शेड्यूलिंग
| Part of a series on |
| Artificial intelligence |
|---|
 |
स्वचालित योजना और शेड्यूलिंग, जिसे कभी-कभी केवल एआई योजना के रूप में दर्शाया जाता है,[1] कृत्रिम बुद्धि की एक शाखा है जो विशेष रूप से बुद्धिमान एजेंट, स्वायत्त रोबोट और मानव रहित वाहन द्वारा निष्पादन के लिए रणनीति या कार्रवाई अनुक्रमों की प्राप्ति से संबंधित है। मौलिक नियंत्रण प्रणाली और सांख्यिकीय वर्गीकरण समस्याओं के विपरीत, समाधान जटिल हैं और इन्हें बहुआयामी स्थान में खोजा और अनुकूलित किया जाना चाहिए। नियोजन निर्णय सिद्धांत से भी संबंधित है।
ज्ञात परिवेशों में उपलब्ध मॉडलों के साथ नियोजन ऑफ़लाइन किया जा सकता है। निष्पादन से पहले समाधान खोजे और उनका मूल्यांकन किया जा सकता है। गतिशील रूप से अज्ञात परिवेशों में, रणनीति को अधिकांशतः ऑनलाइन संशोधित करने की आवश्यकता होती है। मॉडल और नीतियों को अनुकूलित किया जाना चाहिए। समाधान सामान्यतः पुनरावृत्त परीक्षण और त्रुटि प्रक्रियाओं का सहारा लेते हैं जो सामान्यतः कृत्रिम बुद्धिमत्ता में देखी जाती हैं। इनमें गतिशील प्रोग्रामिंग सुदृढीकरण सीखना और संयोजन अनुकूलन सम्मिलित हैं। नियोजन और शेड्यूलिंग का वर्णन करने के लिए उपयोग की जाने वाली भाषाओं को अधिकांशतः क्रियात्मक भाषाएँ कहा जाता है।
अवलोकन
दुनिया के संभावित प्रारंभिक अवस्थाओ का वर्णन वांछित लक्ष्यों का विवरण और संभावित कार्यों के एक समूह का वर्णन, नियोजन समस्या आश्वस्त योजना को संश्लेषित करना है (जब प्रारंभिक अवस्थाओ में से किसी पर प्रयुक्त किया जाता है) एक ऐसा अवस्था उत्पन्न करना जिसमें वांछित लक्ष्य हों (ऐसे अवस्था को लक्ष्य अवस्था कहा जाता है)।
नियोजन की कठिनाई नियोजित सरलीकृत धारणाओं पर निर्भर है। कई आयामों में समस्याओं के गुणों के आधार पर नियोजन समस्याओं के कई वर्गों की पहचान की जा सकती है।
- क्या क्रियाएं नियतात्मक या गैर-नियतात्मक हैं? गैर-नियतात्मक क्रियाओं के लिए, क्या संबंधित संभावनाएँ उपलब्ध हैं?
- क्या अवस्था चर असतत या निरंतर हैं? यदि वे असतत हैं, तो क्या उनके पास संभव मानों की सीमित संख्या है?
- क्या वर्तमान स्थिति को स्पष्ट रूप से देखा जा सकता है? पूर्ण अवलोकन और आंशिक अवलोकन हो सकता है।
- कितनी प्रारंभिक अवस्थाएँ हैं, परिमित या इच्छानुसार से कई?
- क्या कर्मों की कोई अवधि होती है?
- क्या एक साथ कई क्रियाएं की जा सकती हैं, या एक समय में केवल एक ही क्रिया संभव है?
- क्या किसी योजना का उद्देश्य निर्दिष्ट लक्ष्य स्थिति तक पहुँचना है, या किसी इनाम कार्य को अधिकतम करना है?
- एजेंट एक ही होता है या कई एजेंट होते हैं? क्या एजेंट सहकारी या स्वार्थी हैं? क्या सभी एजेंट अलग-अलग अपनी योजनाएँ बनाते हैं, या योजनाएँ सभी एजेंटों के लिए केंद्रीय रूप से निर्मित होती हैं?
सरलतम संभव नियोजन समस्या जिसे मौलिक योजना समस्या के रूप में जाना जाता है, द्वारा निर्धारित किया जाता है:
- एक अद्वितीय ज्ञात प्रारंभिक अवस्था,
- अवधिहीन क्रियाएं,
- नियतात्मक क्रियाएं,
- जो एक बार में एक ही लिया जा सकता है,
- और एक एजेंट।
चूंकि प्रारंभिक अवस्था स्पष्ट रूप से जानी जाती है और सभी क्रियाएं नियतात्मक होती हैं, क्रियाओं के किसी भी क्रम के बाद दुनिया की स्थिति का स्पष्ट अनुमान लगाया जा सकता है, और मौलिक योजना के लिए पर्यवेक्षणीयता का प्रश्न अप्रासंगिक है।
इसके अतिरिक्त योजनाओं को कार्यों के अनुक्रम के रूप में परिभाषित किया जा सकता है, क्योंकि यह सदैव पहले से ज्ञात होता है कि किन कार्यों की आवश्यकता होगी।
एजेंट के नियंत्रण से बाहर गैर-निर्धारिती क्रियाओं या अन्य घटनाओं के साथ संभावित निष्पादन एक पेड़ बनाते हैं और योजनाओं को पेड़ के प्रत्येक नोड के लिए उपयुक्त कार्यों का निर्धारण करना होता है।
असतत-समय मार्कोव निर्णय प्रक्रिया (एमडीपी) के साथ समस्याओं की योजना बना रहे हैं:
- अवधिहीन क्रियाएं,
- संभावनाओं के साथ गैर नियतात्मक क्रियाएं,
- पूर्ण अवलोकन,
- एक इनाम कार्य का अधिकतमकरण,
- और एक एजेंट।
जब पूर्ण पर्यवेक्षणीयता को आंशिक अवलोकनीयता से बदल दिया जाता है, तो योजना आंशिक रूप से अवलोकनीय मार्कोव निर्णय प्रक्रिया (पीओएमडीपी) से मेल खाती है।
यदि एक से अधिक एजेंट हैं, तो हमारे पास बहु-एजेंट योजना है, जो गेम सिद्धांत से निकटता से संबंधित है।
डोमेन स्वतंत्र योजना
एआई योजना में, नियोजक सामान्यतः एक डोमेन मॉडल (संभावित कार्यों के एक समूह का विवरण जो डोमेन को मॉडल करते हैं) के साथ-साथ प्रारंभिक स्थिति और लक्ष्य द्वारा निर्दिष्ट विशिष्ट समस्या को हल करने के लिए इनपुट करते हैं, इसके विपरीत जिसमें कोई नहीं है इनपुट डोमेन निर्दिष्ट इस तरह के योजनाकारों को इस तथ्य पर जोर देने के लिए डोमेन स्वतंत्र कहा जाता है कि वे डोमेन की एक विस्तृत श्रृंखला से नियोजन समस्याओं को हल कर सकते हैं। डोमेन के विशिष्ट उदाहरण ब्लॉक-स्टैकिंग, लॉजिस्टिक्स, वर्कफ्लो मैनेजमेंट और रोबोट टास्क प्लानिंग हैं। इसलिए इन सभी विभिन्न डोमेनों में नियोजन समस्याओं को हल करने के लिए एक एकल डोमेन-स्वतंत्र योजनाकार का उपयोग किया जा सकता है। दूसरी ओर, एक रूट प्लानर डोमेन-विशिष्ट प्लानर के लिए विशिष्ट है।
डोमेन मॉडलिंग भाषाओं की योजना बनाना
नियोजन डोमेन और विशिष्ट नियोजन समस्याओं का प्रतिनिधित्व करने के लिए सबसे अधिक उपयोग की जाने वाली भाषाएं जैसे कि स्टैनफोर्ड रिसर्च इंस्टीट्यूट प्रॉब्लम सॉल्वर और योजना डोमेन परिभाषा भाषा फॉर क्लासिकल प्लानिंग, स्टेट वेरिएबल्स पर आधारित हैं। दुनिया की प्रत्येक संभावित स्थिति अवस्था चर के मानो का एक असाइनमेंट है, और क्रियाएं यह निर्धारित करती हैं कि जब कार्रवाई की जाती है तो अवस्था चर के मान कैसे बदलते हैं। चूंकि अवस्था चर का एक समूह एक अवस्था स्थान को प्रेरित करता है जिसका आकार समूह में घातीय है, नियोजन इसी तरह कई अन्य कम्प्यूटेशनल समस्याओं के लिए आयामीता के अभिशाप और दहनशील विस्फोट से ग्रस्त है।
नियोजन समस्याओं का वर्णन करने के लिए एक वैकल्पिक भाषा पदानुक्रमित कार्य नेटवर्क है जिसमें कार्यों का एक समूह दिया गया है और प्रत्येक कार्य या तो एक आदिम क्रिया द्वारा अनुभव किया जा सकता है या अन्य कार्यों के एक समूह में विघटित हो सकता है। इसमें आवश्यक रूप से अवस्था चर सम्मिलित नहीं हैं चूँकि अधिक यथार्थवादी अनुप्रयोगों में अवस्था चर कार्य नेटवर्क के विवरण को सरल बनाते हैं।
नियोजन के लिए एल्गोरिदम
मौलिक योजना
- आगे श्रृंखलन अवस्था स्थान खोज , संभवतः ह्यूरिस्टिक (कंप्यूटर साइंस) के साथ बढ़ाया गया
- बैकवर्ड चेनिंग सर्च, संभवतः अवस्था की बाधाओं के उपयोग से बढ़ाया गया (देखें स्टैनफोर्ड रिसर्च इंस्टीट्यूट प्रॉब्लम सॉल्वर, ग्राफ़प्लान )
- आंशिक आदेश योजना
अन्य समस्याओं में कमी
- प्रस्तावित संतुष्टि समस्या (विमान बैठ गया) में कमी।
- मॉडल की जाँच में कमी - दोनों अनिवार्य रूप से स्टेट स्पेस को पार करने की समस्याएँ हैं और क्लासिकल प्लानिंग समस्या मॉडल चेकिंग समस्याओं के एक उपवर्ग से मेल खाती है।
टेम्पोरल प्लानिंग
मौलिक योजना के समान विधि से अस्थायी योजना को हल किया जा सकता है। मुख्य अंतर यह है कि कई की संभावना के कारण अस्थायी रूप से अतिव्यापी क्रियाएं एक अवधि के साथ समवर्ती रूप से ली जा रही हैं, कि एक अवस्था की परिभाषा में वर्तमान निरपेक्ष समय के बारे में जानकारी सम्मिलित है और प्रत्येक सक्रिय क्रिया का निष्पादन कितनी दूर तक आगे बढ़ा है। इसके अतिरिक्त तर्कसंगत या वास्तविक समय के साथ योजना बनाने में, मौलिक योजना या पूर्णांक समय के साथ योजना के विपरीत, अवस्था का स्थान अनंत हो सकता है। टेम्पोरल प्लानिंग अनिश्चितता से जुड़े होने पर अनुसूची बनाना समस्याओं से निकटता से संबंधित है और इसे समयबद्ध ऑटोमेटन के संदर्भ में भी समझा जा सकता है। अनिश्चितता के साथ सरल टेम्पोरल नेटवर्क (एसटीएनयू) एक शेड्यूलिंग समस्या है जिसमें नियंत्रणीय क्रियाएं, अनिश्चित घटनाएं और अस्थायी बाधाएं सम्मिलित हैं। ऐसी समस्याओं के लिए गतिशील नियंत्रणीयता एक प्रकार का समय-निर्धारण है जिसके लिए नियंत्रणीय क्रियाओं को प्रतिक्रियात्मक रूप से सक्रिय करने के लिए एक अस्थायी योजना रणनीति की आवश्यकता होती है क्योंकि अनिश्चित घटनाएं देखी जाती हैं जिससे सभी बाधाओं को संतुष्ट होने की आश्वासन दी जा सकती है। [2]
संभाव्य योजना
जब अवस्था का स्थान पर्याप्त रूप से छोटा हो, तो मान पुनरावृत्ति और नीति पुनरावृत्ति जैसे पुनरावृत्त विधि से संभाव्य नियोजन को हल किया जा सकता है।
आंशिक पर्यवेक्षणीयता के साथ संभाव्यतापूर्ण योजना समान रूप से पुनरावृत्त विधि से हल की जाती है किंतु अवस्थाओ के अतिरिक्त विश्वासों के स्थान के लिए परिभाषित मान कार्यों के प्रतिनिधित्व का उपयोग करते हुए।
वरीयता-आधारित योजना
वरीयता-आधारित योजना में उद्देश्य न केवल एक योजना तैयार करना है किंतु उपयोगकर्ता द्वारा निर्दिष्ट प्राथमिकताओं को पूरा करना भी है। अधिक सामान्य इनाम-आधारित योजना में अंतर, उदाहरण के लिए एमडी पी एस के अनुरूप, वरीयताएँ आवश्यक रूप से स्पष्ट संख्यात्मक मान नहीं रखती हैं।
नियमावली योजना
नियतात्मक नियोजन को स्टैनफोर्ड रिसर्च इंस्टीट्यूट प्रॉब्लम सॉल्वर प्लानिंग प्रणाली के साथ प्रस्तुत किया गया था जो एक श्रेणीबद्ध योजनाकार है। कार्रवाई के नाम एक क्रम में दिए गए हैं और यह रोबोट के लिए एक योजना है। पदानुक्रमित योजना की तुलना एक स्वचालित उत्पन्न व्यवहार वृक्ष (कृत्रिम बुद्धिमत्ता, रोबोटिक्स और नियंत्रण) से की जा सकती है।[3] इसका हानि यह है कि एक सामान्य व्यवहार ट्री कंप्यूटर प्रोग्राम की तरह अभिव्यंजक नहीं होता है। इसका अर्थ है एक व्यवहार ग्राफ के अंकन में एक्शन कमांड होते हैं, किंतु कोई लूप (कंप्यूटिंग) या इफ-डेन-स्टेटमेंट नहीं होते हैं। नियमावली योजना अड़चन पर नियंत्रण पाती है और एक विस्तृत संकेतन प्रस्तुत करती है जो एक नियंत्रण प्रवाह के समान है, जिसे पास्कल (प्रोग्रामिंग भाषा) जैसी अन्य प्रोग्रामिंग भाषाओं से जाना जाता है। यह कार्यक्रम संश्लेषण के समान है, जिसका अर्थ है कि एक योजनाकार स्रोत कोड उत्पन्न करता है जिसे दुभाषिया द्वारा निष्पादित किया जा सकता है।[4]
नियमावली योजनाकार का एक प्रारंभिक उदाहरण "वारप्लान-सी" है जिसे 1970 के दशक के मध्य में प्रस्तुत किया गया था।[5] एक सामान्य अनुक्रम और एक जटिल योजना के बीच क्या अंतर है, जिसमें अगर-तो-कथन सम्मिलित हैं? यह किसी योजना के रन टाइम (कार्यक्रम जीवनचक्र चरण) पर अनिश्चितता से संबंधित है। विचार यह है कि एक योजना शीतल संवेदक पर प्रतिक्रिया कर सकती है जो योजनाकार के लिए अज्ञात है। योजनाकार पहले से दो विकल्प उत्पन्न करता है। उदाहरण के लिए, यदि किसी वस्तु का पता चला है, तो क्रिया A को निष्पादित किया जाता है, यदि कोई वस्तु विलुप्त है तो क्रिया B को निष्पादित किया जाता है।[6] नियमावली नियोजन का एक प्रमुख लाभ आंशिक-आदेश नियोजन को संभालने की क्षमता है।[7] एक एजेंट को प्रारंभ से अंत तक सब कुछ योजना बनाने के लिए विवश नहीं किया जाता है, किंतु समस्या को चंकिंग (कम्प्यूटेशनल भाषाविज्ञान) में विभाजित कर सकता है। यह अवस्था के स्थान को कम करने में सहायता करता है और अधिक जटिल समस्याओं को हल करता है।
आकस्मिक योजना
हम आकस्मिक योजना की बात करते हैं जब सेंसर के माध्यम से पर्यावरण को देखा जा सकता है, जो दोषपूर्ण हो सकता है। इस प्रकार यह एक ऐसी स्थिति है जहाँ नियोजन एजेंट अधूरी जानकारी के तहत कार्य करता है। एक आकस्मिक नियोजन समस्या के लिए एक योजना अब क्रियाओं का एक क्रम नहीं है किंतु एक निर्णय वृक्ष है क्योंकि योजना के प्रत्येक चरण को अवस्थाओ के एक समूह द्वारा दर्शाया गया है न कि एक पूरी तरह से अवलोकन योग्य अवस्था के रूप में जैसा कि मौलिक योजना के स्थिति में है।[8] चयनित क्रियाएं प्रणाली की स्थिति पर निर्भर करती हैं। उदाहरण के लिए यदि बारिश होती है तो एजेंट छाता लेना चुनता है और यदि नहीं तो वे इसे नहीं लेने का विकल्प चुन सकते हैं।
माइकल एल. लिटमैन ने 1998 में दिखाया कि ब्रांचिंग क्रियाओं के साथ, नियोजन समस्या एक्सपटाइम-पूर्ण हो जाती है।[9][10] पूरी तरह से देखे जाने योग्य और गैर-नियतात्मक के लिए - सन्निहित नियोजन का एक विशेष स्थिति प्रिय समस्याओं द्वारा दर्शाया गया है। यदि लक्ष्य एलटीएलएफ (सीमित ट्रेस पर रैखिक समय तर्क) में निर्दिष्ट है तो समस्या सदैव एक्सपटाइम-पूर्ण होती है[11] और 2एक्सपटाइम-पूर्ण यदि लक्ष्य एलडीएलएफ के साथ निर्दिष्ट किया गया है।
अनुरूप योजना
अनुरूप नियोजन तब होता है जब एजेंट प्रणाली की स्थिति के बारे में अनिश्चित होता है, और यह कोई अवलोकन नहीं कर सकता है। एजेंट को तब वास्तविक दुनिया के बारे में विश्वास होता है, किंतु उदाहरण के लिए संवेदन क्रियाओं के साथ उन्हें सत्यापित नहीं कर सकता है। इन समस्याओं को मौलिक योजना के समान विधियों द्वारा हल किया जाता है,[12][13] किंतु जहां वर्तमान स्थिति के बारे में अनिश्चितता के कारण अवस्था का स्थान समस्या के आकार में घातीय है। एक अनुरूप नियोजन समस्या का समाधान क्रियाओं का एक क्रम है। हसलम और जॉनसन ने प्रदर्शित किया है कि अनुरूप योजना की समस्या एक्सपस्पेस-पूर्ण है,[14] और 2एक्सपटाइम-पूर्ण जब प्रारंभिक स्थिति अनिश्चित होती है, और क्रियाओं के परिणामों में गैर-निर्धारणा होती है।[10]
नियोजन प्रणालियों की तैनाती
- हबल स्थान सूक्ष्मदर्शी SPSS नामक एक अल्पकालिक प्रणाली का उपयोग करता है और एक लंबी-अवधि नियोजन प्रणाली जिसे Spike कहा जाता है .
यह भी देखें
- क्रिया विवरण भाषा
- अभिनेता मॉडल
- आर्टिफिशियल इंटेलिजेंस के अनुप्रयोग
- बाधा संतुष्टि समस्या
- प्रतिक्रियाशील योजना
- निर्धारण (कंप्यूटिंग)
- रणनीति (खेल सिद्धांत)
- सूचियों
- श्रीमती सॉल्वरों की सूची
- बाधा प्रोग्रामिंग भाषाओं की सूची
- उभरती प्रौद्योगिकियों की सूची
- कृत्रिम बुद्धि की रूपरेखा
संदर्भ
- ↑ Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004), Automated Planning: Theory and Practice, Morgan Kaufmann, ISBN 1-55860-856-7, archived from the original on 2009-08-24, retrieved 2008-08-20
- ↑ Vidal, Thierry (January 1999). "Handling contingency in temporal constraint networks: from consistency to controllabilities". Journal of Experimental & Theoretical Artificial Intelligence. 11 (1): 23--45. CiteSeerX 10.1.1.107.1065. doi:10.1080/095281399146607.
- ↑ Neufeld, Xenija and Mostaghim, Sanaz and Sancho-Pradel, Dario and Brand, Sandy (2017). "Building a Planner: A Survey of Planning Systems Used in Commercial Video Games". IEEE Transactions on Games. IEEE.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - ↑ Sanelli, Valerio and Cashmore, Michael and Magazzeni, Daniele and Iocchi, Luca (2017). सशर्त योजना और निष्पादन के माध्यम से अल्पकालिक मानव रोबोट परस्पर क्रिया. Proc. of International Conference on Automated Planning and Scheduling (ICAPS). Archived from the original on 2019-08-16. Retrieved 2019-08-16.
{{cite conference}}: CS1 maint: multiple names: authors list (link) - ↑ Peot, Mark A and Smith, David E (1992). सशर्त गैर रेखीय योजना (PDF). Artificial Intelligence Planning Systems. Elsevier. pp. 189–197.
{{cite conference}}: CS1 maint: multiple names: authors list (link) - ↑ Karlsson, Lars (2001). अनिश्चितता के तहत सशर्त प्रगतिशील योजना. IJCAI. pp. 431–438.
- ↑ Liu, Daphne Hao (2008). A survey of planning in intelligent agents: from externally motivated to internally motivated systems (Technical report). Technical Report TR-2008-936, Department of Computer Science, University of Rochester. Archived from the original on 2023-03-15. Retrieved 2019-08-16.
- ↑ Alexandre Albore; Hector Palacios; Hector Geffner (2009). आकस्मिक योजना के लिए एक अनुवाद-आधारित दृष्टिकोण. International Joint Conference of Artificial Intelligence (IJCAI). Pasadena, CA: AAAI. Archived from the original on 2019-07-03. Retrieved 2019-07-03.
- ↑ Littman, Michael L. (1997). Probabilistic Propositional Planning: Representations and Complexity. Fourteenth National Conference on Artificial Intelligence. MIT Press. pp. 748–754. Archived from the original on 2019-02-12. Retrieved 2019-02-10.
- ↑ 10.0 10.1 Jussi Rintanen (2004). आंशिक पर्यवेक्षणीयता के साथ नियोजन की जटिलता (PDF). Int. Conf. Automated Planning and Scheduling. AAAI. Archived (PDF) from the original on 2020-10-31. Retrieved 2019-07-03.
- ↑ De Giacomo, Giuseppe; Rubin, Sasha (2018). LTLf और LDLf लक्ष्यों के लिए शौकीन योजना के ऑटोमेटा-सैद्धांतिक नींव. IJCAI. Archived from the original on 2018-07-17. Retrieved 2018-07-17.
- ↑ Palacios, Hector; Geffner, Hector (2009). "परिबद्ध चौड़ाई के साथ अनुरूप योजना समस्याओं में अनिश्चितता को दूर करना". Journal of Artificial Intelligence Research. 35: 623–675. doi:10.1613/jair.2708. Archived from the original on 2020-04-27. Retrieved 2019-08-16.
- ↑ Albore, Alexandre; Ramírez, Miquel; Geffner, Hector (2011). अधूरी जानकारी के साथ नियोजन के लिए प्रभावी अनुमान और विश्वास ट्रैकिंग. Twenty-First International Conference on Automated Planning and Scheduling (ICAPS). Archived from the original on 2017-07-06. Retrieved 2019-08-16.
- ↑ Haslum, Patrik; Jonsson, Peter (2000). "अधूरी जानकारी के साथ नियोजन की जटिलता पर कुछ परिणाम". Recent Advances in AI Planning. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 1809: 308–318. doi:10.1007/10720246_24. ISBN 9783540446576.
अग्रिम पठन
- Vlahavas, I. "Planning and Scheduling". EETN. Archived from the original on 2013-12-22.
