क्लासिकल प्लानिंग और स्ट्रिप्स

क्लासिकल प्लानिंग एक नियतात्मक, पूर्णतः अवलोकनीय, स्थिर वातावरण में एक लक्ष्य तक पहुँचने के लिए क्रियाओं के अनुक्रम को खोजने की समस्या का समाधान करती है, जिसमें पूर्व-शर्तों और प्रभावों द्वारा क्रियाओं के कारक STRIPS-शैली प्रतिनिधित्व का उपयोग किया जाता है।

Definition

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

Scope

यह विषय क्लासिकल प्लानिंग मॉडल और उसकी मान्यताओं (नियतात्मक क्रियाएँ, पूर्ण अवलोकनशीलता, एक एकल एजेंट, परमाणु समय), राज्यों और क्रियाओं के STRIPS और ADL/PDDL प्रतिनिधित्व, फॉरवर्ड (प्रोग्रेशन) और बैकवर्ड (रिग्रेशन) स्टेट-स्पेस सर्च और पार्शियल-ऑर्डर प्लानिंग की बुनियादी समाधान विधियों, और प्रोपोज़िशनल प्लानिंग की कम्प्यूटेशनल जटिलता को शामिल करता है। ह्यूरिस्टिक मार्गदर्शन और प्लानिंग ग्राफ़ संबंधित विषय में वर्णित हैं, और गैर-नियतात्मक या संभाव्य वेरिएंट दायरे से बाहर हैं।

Core questions

• क्लासिकल प्लानिंग मॉडल को कौन सी मान्यताएँ परिभाषित करती हैं, और वे कब उपयुक्त होती हैं?
• STRIPS प्रतिनिधित्व एक स्थिति को प्रस्तावों में और एक क्रिया को पूर्व-शर्तों और जोड़ें/हटाएँ प्रभावों में कैसे कारक बनाता है?
• प्लानिंग रणनीतियों के रूप में प्रोग्रेशन और रिग्रेशन सर्च में क्या अंतर है?
• सामान्य तौर पर क्लासिकल प्लानिंग कम्प्यूटेशनल रूप से कितनी कठिन है?

Key concepts

• नियतात्मक, पूर्णतः अवलोकनीय मॉडल
• STRIPS पूर्व-शर्तें और प्रभाव
• जोड़ें और हटाएँ सूचियाँ
• PDDL और ADL
• प्रोग्रेशन (फॉरवर्ड) सर्च
• रिग्रेशन (बैकवर्ड) सर्च
• पार्शियल-ऑर्डर प्लानिंग
• योजना अस्तित्व जटिलता

Key theories

STRIPS प्रतिनिधित्व

STRIPS दुनिया को सत्य प्रस्तावों के एक सेट के रूप में और प्रत्येक क्रिया को एक पूर्व-शर्त सूची के साथ-साथ जोड़ें और हटाएँ सूचियों द्वारा वर्णित करता है, ताकि एक क्रिया को लागू करने से केवल प्रस्ताव जुड़ते और हटते हैं; यह कारक मॉडल लगभग सभी क्लासिकल प्लानर्स का आधार है।

प्रोग्रेशन और रिग्रेशन सर्च

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

प्लानिंग की जटिलता

यह तय करना कि क्या एक प्रोपोज़िशनल STRIPS योजना मौजूद है, सामान्य तौर पर PSPACE-पूर्ण है, जो औपचारिक रूप से बताता है कि प्लानिंग कठिन क्यों है और इसे व्यावहारिक बनाने के लिए ह्यूरिस्टिक और संरचनात्मक तरीकों को प्रेरित करता है।

Clinical relevance

क्लासिकल प्लानिंग प्रतिनिधित्व रोबोट कार्य योजना, स्वचालित असेंबली और लॉजिस्टिक्स, और किसी भी ऐसे अनुप्रयोग के लिए सामान्य इंटरफ़ेस हैं जहाँ एक लक्ष्य तक पहुँचने के लिए नियतात्मक क्रियाओं को अनुक्रमित किया जाना चाहिए; PDDL-आधारित क्लासिकल प्लानर इस क्षेत्र और अंतर्राष्ट्रीय प्लानिंग प्रतियोगिताओं के मुख्य कार्यवाहक हैं।

History

STRIPS को 1971 के आसपास SRI में शेकी रोबोट को नियंत्रित करने के लिए विकसित किया गया था, जिसमें पूर्व-शर्त/प्रभाव क्रिया मॉडल पेश किया गया था जो क्लासिकल प्लानिंग को परिभाषित करता है। पार्शियल-ऑर्डर प्लानिंग 1970-80 के दशक में परिपक्व हुई, बायलैंडर ने 1994 में प्रोपोज़िशनल प्लानिंग की PSPACE-पूर्णता स्थापित की, और PDDL मानक ने बाद में क्षेत्र के बेंचमार्क को एकीकृत किया।

Key figures

• Richard E. Fikes
• Nils J. Nilsson
• Tom Bylander
• Earl D. Sacerdoti

Seminal works

• fikes1971
• bylander1994

Frequently asked questions

क्लासिकल प्लानिंग की मान्यताएँ क्या हैं?

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

STRIPS की जोड़ें सूची और हटाएँ सूची का क्या अर्थ है?

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