पदानुक्रमित कार्य नेटवर्क नियोजन

पदानुक्रमित कार्य नेटवर्क (HTN) नियोजन समस्याओं को लक्ष्य स्थिति तक पहुँचने के लिए आदिम क्रियाओं पर सीधे खोज करने के बजाय, विधियों की एक लाइब्रेरी का उपयोग करके उच्च-स्तरीय कार्यों को उप-कार्यों में पुनरावर्ती रूप से विघटित करके हल करता है।

Definition

HTN नियोजन एक समस्या को निष्पादित किए जाने वाले कार्यों के एक प्रारंभिक नेटवर्क और यौगिक कार्यों को उप-कार्यों में विघटित करने के लिए विधियों के एक सेट के रूप में प्रस्तुत करता है; एक समाधान आदिम, निष्पादन योग्य क्रियाओं में एक विघटन है जो विधियों की बाधाओं का सम्मान करता है।

Scope

यह विषय HTN नियोजन प्रतिमान को शामिल करता है: कार्य (आदिम और यौगिक), वे विधियाँ जो यह निर्दिष्ट करती हैं कि एक यौगिक कार्य को उप-कार्यों में कैसे विघटित किया जाए, और नियोजन प्रक्रिया जो एक प्रारंभिक कार्य नेटवर्क को तब तक परिष्कृत करती है जब तक कि केवल निष्पादन योग्य आदिम क्रियाएँ शेष न रहें। यह शास्त्रीय नियोजन और उल्लेखनीय HTN नियोजकों के सापेक्ष HTN नियोजन की अभिव्यंजकता और जटिलता को संबोधित करता है। शास्त्रीय, लक्ष्य-स्थिति-आधारित नियोजन मॉडल को संबंधित विषयों में माना जाता है; HTN नियोजन इसके बजाय प्रक्रियात्मक डोमेन ज्ञान को एन्कोड करता है।

Core questions

• विधियाँ यौगिक कार्यों को पूरा करने के तरीके के बारे में डोमेन ज्ञान को कैसे एन्कोड करती हैं?
• शास्त्रीय नियोजन में लक्ष्य स्थिति की ओर खोज करने से कार्य विघटन कैसे भिन्न है?
• शास्त्रीय नियोजन की तुलना में HTN नियोजन की अभिव्यंजकता और कम्प्यूटेशनल जटिलता क्या है?
• विघटन के दौरान उप-कार्यों के बीच क्रम और पूर्वशर्त बाधाओं को कैसे संभाला जाता है?

Key concepts

• आदिम और यौगिक कार्य
• विधियाँ और विघटन
• कार्य नेटवर्क
• क्रम बाधाएँ
• प्रक्रियात्मक डोमेन ज्ञान
• HTN अभिव्यंजकता
• क्रमबद्ध कार्य विघटन
• SHOP2

Key theories

विधियों के साथ कार्य विघटन

HTN नियोजन लक्ष्य-निर्देशित खोज को पुनरावर्ती विघटन से प्रतिस्थापित करता है: यौगिक कार्यों को विधियों के माध्यम से उप-कार्यों के नेटवर्क में विस्तारित किया जाता है जब तक कि सभी कार्य आदिम न हो जाएँ, जिससे कार्यों को करने के तरीके के बारे में मानवीय विशेषज्ञता को सीधे एन्कोड किया जा सके।

HTN नियोजन की अभिव्यंजकता और जटिलता

HTN नियोजन शास्त्रीय STRIPS नियोजन से कड़ाई से अधिक अभिव्यंजक है; इसके सामान्य रूप में योजना का अस्तित्व अनिर्णीत हो सकता है, और प्रतिबंधित रूप उच्च जटिलता वर्गों पर कब्जा करते हैं, जो विधि-आधारित विघटन की शक्ति को दर्शाता है।

क्रमबद्ध कार्य विघटन नियोजक

SHOP2 जैसे व्यावहारिक HTN नियोजक कार्यों को उसी क्रम में विघटित करके योजना बनाते हैं जिस क्रम में उन्हें निष्पादित किया जाएगा, जिससे वे पूरी तरह से निर्धारित स्थितियों के खिलाफ पूर्वशर्तों का मूल्यांकन कर सकें और समृद्ध डोमेन ज्ञान को कुशलता से शामिल कर सकें।

Clinical relevance

HTN नियोजन का व्यापक रूप से उपयोग उन जगहों पर किया जाता है जहाँ विशेषज्ञ प्रक्रियाएँ ज्ञात होती हैं और उनका पालन किया जाना चाहिए, जैसे विनिर्माण प्रक्रिया नियोजन, सैन्य और रसद संचालन, वेब-सेवा संरचना, और खेल और कहानी निर्माण, क्योंकि विधियाँ डोमेन विशेषज्ञों को कार्यों को पूरा करने के मानक तरीकों को एन्कोड करने देती हैं।

History

पदानुक्रमित नियोजन 1970 के दशक में सैकरडोटि के NOAH और अमूर्त पदानुक्रमों से जुड़ा है। एरल, हेंडलर और नौ ने 1990 के दशक की शुरुआत में HTN नियोजन को औपचारिक रूप दिया और इसकी जटिलता का विश्लेषण किया, और SHOP और SHOP2 नियोजकों (लगभग 2000-2003) ने क्रमबद्ध HTN नियोजन को एक व्यावहारिक और व्यापक रूप से उपयोग की जाने वाली तकनीक बना दिया।

Key figures

• Dana Nau
• Kutluhan Erol
• James Hendler
• Earl D. Sacerdoti
• Austin Tate

Seminal works

• erol1994
• nau2003

Frequently asked questions

HTN नियोजन शास्त्रीय नियोजन से कैसे भिन्न है?

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

HTN नियोजन अनिर्णीत क्यों हो सकता है?

क्योंकि विधियाँ एक यौगिक कार्य को उन नेटवर्कों में विघटित कर सकती हैं जिनमें आगे यौगिक कार्य शामिल होते हैं, विघटन प्रक्रिया बिना किसी सीमा के पुनरावर्ती हो सकती है, ठीक वैसे ही जैसे एक व्याकरण मनमाने ढंग से लंबे व्युत्पन्न उत्पन्न करता है। इसके सामान्य रूप में, यह तय करना कि एक वैध विघटन मौजूद है या नहीं, इसलिए अनिर्णीत है।