Automated planning and scheduling
स्वचालित योजना और समय-निर्धारण, जिसे कभी-कभी केवल ए. आई. योजना के रूप में दर्शाया जाता है, कृत्रिम बुद्धिमत्ता की एक शाखा है जो रणनीतियों या कार्य अनुक्रमों की प्राप्ति से संबंधित है, आमतौर पर बुद्धिमान एजेंटों, स्वायत्त रोबोटों और मानव रहित वाहनों द्वारा निष्पादन के लिए। शास्त्रीय नियंत्रण और वर्गीकरण समस्याओं के विपरीत, समाधान जटिल हैं और बहुआयामी स्थान में खोजे और अनुकूलित किए जाने चाहिए। योजना निर्णय सिद्धांत से भी संबंधित है। उपलब्ध मॉडलों के साथ ज्ञात वातावरण में, योजना ऑफ़लाइन की जा सकती है। निष्पादन से पहले समाधान खोजे जा सकते हैं और उनका मूल्यांकन किया जा सकता है। गतिशील रूप से अज्ञात वातावरण में, रणनीति को अक्सर ऑनलाइन संशोधित करने की आवश्यकता होती है। मॉडल और नीतियों को अनुकूलित किया जाना चाहिए। समाधान आमतौर पर कृत्रिम बुद्धिमत्ता में आमतौर पर देखे जाने वाले पुनरावृत्ति परीक्षण और त्रुटि प्रक्रियाओं का सहारा लेते हैं। इनमें डायनेमिक प्रोग्रामिंग, रीइनफोर्समेंट लर्निंग और कॉम्बिनेटोरियल ऑप्टिमाइजेशन शामिल हैं। योजना और समय-निर्धारण का वर्णन करने के लिए उपयोग की जाने वाली भाषाओं को अक्सर क्रिया भाषा कहा जाता है। दुनिया की संभावित प्रारंभिक अवस्थाओं के विवरण, वांछित लक्ष्यों के विवरण और संभावित कार्यों के एक समूह के विवरण को देखते हुए, योजना की समस्या एक ऐसी योजना को संश्लेषित करना है जिसकी गारंटी (जब प्रारंभिक अवस्थाओं में से किसी पर भी लागू की जाती है) एक ऐसी स्थिति उत्पन्न करने के लिए जिसमें वांछित लक्ष्य होते हैं (ऐसे राज्य को लक्ष्य स्थिति कहा जाता है)। नियोजन की कठिनाई नियोजित सरल धारणाओं पर निर्भर करती है। योजना समस्याओं के कई वर्गों की पहचान उन गुणों के आधार पर की जा सकती है जो समस्याओं के कई आयामों में हैं। क्या क्रियाएँ नियतात्मक हैं या गैर-नियतात्मक? गैर-निर्धारक कार्यों के लिए, क्या संबंधित संभावनाएं उपलब्ध हैं? क्या अवस्था चर असतत हैं या निरंतर हैं? यदि वे असतत हैं, तो क्या उनके पास संभावित मूल्यों की केवल एक सीमित संख्या है? क्या वर्तमान स्थिति को स्पष्ट रूप से देखा जा सकता है? पूर्ण अवलोकन और आंशिक अवलोकन हो सकता है। कितने प्रारंभिक अवस्थाएँ हैं, परिमित या मनमाने ढंग से कई? क्या कार्यों की कोई अवधि होती है? क्या एक साथ कई कार्रवाई की जा सकती हैं, या एक बार में केवल एक ही कार्रवाई संभव है? क्या किसी योजना का उद्देश्य एक निर्दिष्ट लक्ष्य स्थिति तक पहुँचना है, या एक पुरस्कार कार्य को अधिकतम करना है? क्या केवल एक ही एजेंट है या कई एजेंट हैं? एजेंट सहयोगी हैं या स्वार्थी? क्या सभी एजेंट अलग-अलग अपनी योजनाओं का निर्माण करते हैं, या क्या सभी एजेंटों के लिए योजनाओं का निर्माण केंद्रीय रूप से किया जाता है? सबसे सरल संभव योजना समस्या, जिसे शास्त्रीय योजना समस्या के रूप में जाना जाता है, का निर्धारण इस प्रकार किया जाता हैः एक अद्वितीय ज्ञात प्रारंभिक स्थिति, अवधिहीन कार्य, नियतात्मक कार्य, जो एक समय में केवल एक ही बार किया जा सकता है, और एक ही कारक। चूँकि प्रारंभिक अवस्था को स्पष्ट रूप से जाना जाता है, और सभी क्रियाएँ नियतात्मक होती हैं, इसलिए क्रियाओं के किसी भी क्रम के बाद दुनिया की स्थिति का सटीक अनुमान लगाया जा सकता है, और शास्त्रीय योजना के लिए अवलोकन क्षमता का सवाल अप्रासंगिक है। इसके अलावा, योजनाओं को कार्यों के अनुक्रम के रूप में परिभाषित किया जा सकता है, क्योंकि यह हमेशा पहले से ज्ञात होता है कि किन कार्यों की आवश्यकता होगी। गैर-निर्धारक क्रियाओं या एजेंट के नियंत्रण से बाहर की अन्य घटनाओं के साथ, संभावित निष्पादन एक पेड़ बनाते हैं, और योजनाओं को पेड़ के प्रत्येक नोड के लिए उपयुक्त कार्यों को निर्धारित करना होता है। डिस्क्रीट-टाइम मार्कोव निर्णय प्रक्रियाएँ (एम. डी. पी.) समस्याओं की योजना बना रही हैंः अवधिहीन क्रियाएँ, संभावनाओं के साथ गैर-निर्धारक क्रियाएँ, पूर्ण अवलोकन, एक पुरस्कार कार्य का अधिकतमकरण, और एक एकल एजेंट। जब पूर्ण अवलोकन क्षमता को आंशिक अवलोकन क्षमता द्वारा प्रतिस्थापित किया जाता है, तो योजना एक आंशिक रूप से अवलोकन योग्य मार्कोव निर्णय प्रक्रिया (पी. ओ. एम. डी. पी.) के अनुरूप होती है। यदि एक से अधिक एजेंट हैं, तो हमारे पास बहु-एजेंट योजना है, जो खेल सिद्धांत से निकटता से संबंधित है। ए. आई. नियोजन में, योजनाकार आम तौर पर एक डोमेन मॉडल (संभावित कार्यों के एक समूह का विवरण जो डोमेन को मॉडल करता है) के साथ-साथ प्रारंभिक स्थिति और लक्ष्य द्वारा निर्दिष्ट की जाने वाली विशिष्ट समस्या को इनपुट करते हैं, इसके विपरीत जिसमें कोई इनपुट डोमेन निर्दिष्ट नहीं है। इस तरह के योजनाकारों को इस तथ्य पर जोर देने के लिए "डोमेन स्वतंत्र" कहा जाता है कि वे डोमेन की एक विस्तृत श्रृंखला से योजना समस्याओं को हल कर सकते हैं। डोमेन के विशिष्ट उदाहरण ब्लॉक-स्टैकिंग, रसद, कार्यप्रवाह प्रबंधन और रोबोट कार्य योजना हैं। इसलिए इन सभी विभिन्न क्षेत्रों में नियोजन समस्याओं को हल करने के लिए एक एकल क्षेत्र-स्वतंत्र योजनाकार का उपयोग किया जा सकता है। दूसरी ओर, एक मार्ग योजनाकार एक विशिष्ट क्षेत्र-विशिष्ट योजनाकार होता है। योजना क्षेत्र प्रतिरूपण भाषाएँ योजना क्षेत्र और विशिष्ट योजना समस्याओं का प्रतिनिधित्व करने के लिए सबसे अधिक उपयोग की जाने वाली भाषाएँ, जैसे कि शास्त्रीय योजना के लिए एसटीआरआईपीएस और पीडीडीएल, राज्य चर पर आधारित हैं। दुनिया की प्रत्येक संभावित स्थिति अवस्था चर के लिए मूल्यों का एक असाइनमेंट है, और क्रियाएं यह निर्धारित करती हैं कि जब वह कार्रवाई की जाती है तो अवस्था चर के मूल्य कैसे बदलते हैं। चूँकि अवस्था चर का एक समूह एक अवस्था स्थान को प्रेरित करता है जिसका आकार सेट में घातीय होता है, योजना, कई अन्य कम्प्यूटेशनल समस्याओं के समान, आयामीता और संयोजन विस्फोट के अभिशाप से पीड़ित होती है। नियोजन समस्याओं का वर्णन करने के लिए एक वैकल्पिक भाषा पदानुक्रमित कार्य नेटवर्क की है, जिसमें कार्यों का एक समूह दिया जाता है, और प्रत्येक कार्य को या तो एक आदिम क्रिया द्वारा प्राप्त किया जा सकता है या अन्य कार्यों के एक समूह में विघटित किया जा सकता है। इसमें आवश्यक रूप से अवस्था चर शामिल नहीं होते हैं, हालांकि अधिक यथार्थवादी अनुप्रयोगों में अवस्था चर कार्य नेटवर्क के विवरण को सरल बनाते हैं। योजना के लिए एल्गोरिदम शास्त्रीय योजना आगे की श्रृंखला राज्य अंतरिक्ष खोज, संभवतः ह्यूरिस्टिक्स बैकवर्ड चेनिंग खोज के साथ बढ़ाया गया, संभवतः राज्य बाधाओं के उपयोग से बढ़ाया गया (एसटीआरआईपीएस, ग्राफप्लान देखें) आंशिक-क्रम योजना अन्य समस्याओं में कमी प्रस्तावक संतोषजनक समस्या (सैटप्लान) में कमी। मॉडल जाँच में कमी-दोनों अनिवार्य रूप से राज्य स्थानों को पार करने की समस्याएं हैं, और शास्त्रीय योजना समस्या मॉडल जाँच समस्याओं के एक उपवर्ग से मेल खाती है। अस्थायी योजना को शास्त्रीय योजना के समान तरीकों से हल किया जा सकता है। मुख्य अंतर यह है कि समवर्ती रूप से की जाने वाली अवधि के साथ कई, अस्थायी रूप से अतिव्यापी कार्यों की संभावना के कारण, एक अवस्था की परिभाषा में वर्तमान निरपेक्ष समय के बारे में जानकारी शामिल होनी चाहिए और प्रत्येक सक्रिय क्रिया का निष्पादन कितना आगे बढ़ा है। इसके अलावा, तर्कसंगत या वास्तविक समय के साथ योजना बनाने में, पूर्णांक समय के साथ शास्त्रीय योजना या योजना के विपरीत, अवस्था स्थान अनंत हो सकता है। अनिश्चित होने पर अस्थायी योजना समय निर्धारण समस्याओं से निकटता से संबंधित होती है और इसे समयबद्ध स्वचालित के संदर्भ में भी समझा जा सकता है। सिम्पल टेम्पोरल नेटवर्क विद अनसर्टेनिटी (एसटीएनयू) एक समयबद्ध समस्या है जिसमें नियंत्रणीय कार्य, अनिश्चित घटनाएं और अस्थायी बाधाएं शामिल हैं। ऐसी समस्याओं के लिए गतिशील नियंत्रणीयता एक प्रकार का समय निर्धारण है जिसके लिए अनिश्चित घटनाओं के रूप में प्रतिक्रियाशील रूप से नियंत्रणीय कार्यों को सक्रिय करने के लिए एक अस्थायी योजना रणनीति की आवश्यकता होती है ताकि सभी बाधाओं को पूरा करने की गारंटी दी जा सके। संभावित योजना संभावित योजना को मूल्य पुनरावृत्ति और नीति पुनरावृत्ति जैसे पुनरावृत्ति विधियों के साथ हल किया जा सकता है, जब राज्य का स्थान पर्याप्त रूप से छोटा होता है। आंशिक अवलोकन के साथ, संभावित योजना को समान रूप से पुनरावृत्ति विधियों के साथ हल किया जाता है, लेकिन अवस्थाओं के बजाय विश्वासों के स्थान के लिए परिभाषित मूल्य कार्यों के प्रतिनिधित्व का उपयोग करके। वरीयता-आधारित योजना वरीयता-आधारित योजना में, उद्देश्य न केवल एक योजना तैयार करना है, बल्कि उपयोगकर्ता-निर्दिष्ट प्राथमिकताओं को संतुष्ट करना भी है। अधिक सामान्य पुरस्कार-आधारित योजना के लिए एक अंतर, उदाहरण के लिए एम. डी. पी. के अनुरूप, प्राथमिकताओं का आवश्यक रूप से एक सटीक संख्यात्मक मूल्य नहीं होता है। सशर्त योजना निर्धारित योजना को एसटीआरआईपीएस योजना प्रणाली के साथ पेश किया गया था, जो एक पदानुक्रमित योजनाकार है। एक्शन नामों को एक क्रम में क्रमबद्ध किया जाता है और यह रोबोट के लिए एक योजना है। पदानुक्रमित योजना की तुलना स्वचालित रूप से उत्पन्न व्यवहार वृक्ष से की जा सकती है। नुकसान यह है कि एक सामान्य व्यवहार वृक्ष कंप्यूटर प्रोग्राम की तरह इतना अभिव्यंजक नहीं है। इसका मतलब है, एक व्यवहार ग्राफ के संकेतन में कार्रवाई आदेश होते हैं, लेकिन कोई लूप या यदि-तब-कथन नहीं होते हैं। सशर्त योजना अड़चन को पार करती है और एक विस्तृत संकेतन पेश करती है जो एक नियंत्रण प्रवाह के समान है, जिसे पास्कल जैसी अन्य प्रोग्रामिंग भाषाओं से जाना जाता है। यह कार्यक्रम संश्लेषण के समान है, जिसका अर्थ है कि एक योजनाकार स्रोत कोड उत्पन्न करता है जिसे एक दुभाषिया द्वारा निष्पादित किया जा सकता है। सशर्त योजनाकार का एक प्रारंभिक उदाहरण "वारप्लान-सी" है जिसे 1970 के दशक के मध्य में पेश किया गया था। एक सामान्य अनुक्रम और एक जटिल योजना के बीच क्या अंतर है, जिसमें यदि-तो-कथन शामिल हैं? इसका संबंध किसी योजना के रनटाइम पर अनिश्चितता से है। विचार यह है कि एक योजना संवेदक संकेतों पर प्रतिक्रिया कर सकती है जो योजनाकार के लिए अज्ञात हैं। योजनाकार अग्रिम रूप से दो विकल्प तैयार करता है। उदाहरण के लिए, यदि किसी वस्तु का पता चला है, तो कार्रवाई ए को निष्पादित किया जाता है, यदि कोई वस्तु गायब है, तो कार्रवाई बी को निष्पादित किया जाता है। सशर्त योजना का एक प्रमुख लाभ आंशिक योजनाओं को संभालने की क्षमता है। एक एजेंट को शुरू से अंत तक हर चीज की योजना बनाने के लिए मजबूर नहीं किया जाता है, लेकिन वह समस्या को टुकड़ों में विभाजित कर सकता है। यह राज्य के स्थान को कम करने में मदद करता है और बहुत अधिक जटिल समस्याओं को हल करता है। आकस्मिक योजना हम "आकस्मिक योजना" की बात करते हैं जब वातावरण संवेदक के माध्यम से अवलोकन योग्य होता है, जो दोषपूर्ण हो सकता है। इस प्रकार यह एक ऐसी स्थिति है जहाँ योजना अभिकर्ता अधूरी जानकारी के तहत कार्य करता है। एक आकस्मिक योजना समस्या के लिए, एक योजना अब कार्यों का एक क्रम नहीं है, बल्कि एक निर्णय वृक्ष है क्योंकि योजना के प्रत्येक चरण को एक पूरी तरह से अवलोकन योग्य स्थिति के बजाय राज्यों के एक समूह द्वारा दर्शाया जाता है, जैसा कि शास्त्रीय योजना के मामले में होता है। चयनित क्रियाएँ प्रणाली की स्थिति पर निर्भर करती हैं। उदाहरण के लिए, यदि बारिश होती है, तो एजेंट छतरी लेने का विकल्प चुनता है, और यदि ऐसा नहीं होता है, तो वे इसे नहीं लेने का विकल्प चुन सकते हैं। माइकल एल. लिटमैन ने 1998 में दिखाया कि शाखाओं के कार्यों के साथ, योजना की समस्या EXPTIME-पूर्ण हो जाती है। सन्निहित योजना के एक विशेष मामले को फॉन्ड समस्याओं द्वारा दर्शाया जाता है-"पूरी तरह से अवलोकन योग्य और गैर-निर्धारक" के लिए। यदि लक्ष्य एल. टी. एल. एफ. (परिमित निशान पर रैखिक समय तर्क) में निर्दिष्ट किया गया है तो समस्या हमेशा एक्स. पी. टी. आई. एम.-पूर्ण और 2. एक्स. पी. टी. आई. एम.-पूर्ण होती है यदि लक्ष्य एल. डी. एल. एफ. के साथ निर्दिष्ट किया गया है। अनुरूप योजना तब होती है जब अभिकर्ता प्रणाली की स्थिति के बारे में अनिश्चित होता है, और वह कोई अवलोकन नहीं कर सकता है। एजेंट को तब वास्तविक दुनिया के बारे में विश्वास होता है, लेकिन उदाहरण के लिए, संवेदन क्रियाओं के साथ उन्हें सत्यापित नहीं कर सकता है। इन समस्याओं को शास्त्रीय योजना के समान तकनीकों द्वारा हल किया जाता है, लेकिन जहां वर्तमान स्थिति के बारे में अनिश्चितता के कारण समस्या के आकार में राज्य स्थान घातीय है। एक अनुरूप योजना समस्या का समाधान कार्यों का एक क्रम है। हैसलम और जॉनसन ने प्रदर्शित किया है कि अनुरूप योजना की समस्या EXPSPACE-पूर्ण है, और 2EXPTIME-पूर्ण है जब प्रारंभिक स्थिति अनिश्चित होती है, और कार्यों के परिणामों में गैर-निर्धारणवाद होता है। योजना प्रणालियों की तैनाती हबल स्पेस टेलीस्कोप एस. पी. एस. एस. नामक एक अल्पकालिक प्रणाली और स्पाइक नामक एक दीर्घकालिक योजना प्रणाली का उपयोग करता है। एक्शन डिस्क्रिप्शन लैंग्वेज ऐक्टर मॉडल एप्लीकेशन ऑफ आर्टिफिशियल इंटेलिजेंस कंस्ट्रेंट सैटिस्फैक्शन प्रॉब्लम रिएक्टिव प्लानिंग शेड्यूलिंग (कंप्यूटिंग) स्ट्रैटेजी (गेम थ्योरी) लिस्ट्स लिस्ट ऑफ एसएमटी सॉल्वर्स लिस्ट ऑफ कंस्ट्रेंट प्रोग्रामिंग लैंग्वेज लिस्ट ऑफ इमर्जिंग टेक्नोलॉजीज आउटलाइन ऑफ आर्टिफिशियल इंटेलिजेंस संदर्भ आगे पढ़ने के लिए बाहरी लिंक स्वचालित योजना और शेड्यूलिंग पर अंतर्राष्ट्रीय सम्मेलन