योजना ग्राफ़ और अनुमानी (Heuristics)

योजना ग्राफ़ और डोमेन-स्वतंत्र अनुमानी वे तकनीकें हैं जिन्होंने पहुंच-योग्यता का संक्षिप्त विश्लेषण करके और किसी स्थिति से लक्ष्य तक की दूरी का स्वचालित रूप से अनुमान लगाकर शास्त्रीय योजना को तीव्र बनाया है।

Definition

एक योजना ग्राफ़ एक स्तरित संरचना है जो पहुंच-योग्यता का अनुमान लगाने के लिए प्रस्ताव और क्रिया स्तरों को म्यूटेक्स बाधाओं के साथ जोड़ता है; योजना अनुमानी ऐसे कार्य हैं, जिनकी गणना अक्सर ऐसी संरचनाओं या विलोपन-शिथिल समस्याओं से की जाती है, जो किसी स्थिति से लक्ष्य तक पहुंचने की लागत का अनुमान लगाते हैं।

Scope

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

Core questions

• एक योजना ग्राफ़ स्तर-दर-स्तर पहुंच-योग्य प्रस्तावों और क्रियाओं का प्रतिनिधित्व कैसे करता है?
• म्यूटेक्स संबंध क्या हैं, और वे तथ्यों और क्रियाओं के बीच असंगति को कैसे दर्शाते हैं?
• स्वीकार्य या सूचनात्मक योजना अनुमानी प्राप्त करने के लिए विलोपन-शिथिलीकरण का उपयोग कैसे किया जाता है?
• ये अनुमानी योजना को कुशल अनुमानी खोज में कैसे बदलते हैं?

Key concepts

• योजना ग्राफ़
• प्रस्ताव और क्रिया स्तर
• पारस्परिक अपवर्जन (म्यूटेक्स)
• ग्राफ़प्लान
• विलोपन-शिथिलीकरण
• h-max और h-add अनुमानी
• एफएफ अनुमानी और शिथिल योजनाएं
• अनुमानी फॉरवर्ड सर्च

Key theories

योजना ग्राफ़ और ग्राफ़प्लान

ग्राफ़प्लान एक योजना ग्राफ़ बनाता है जो संक्षिप्त रूप से यह एन्कोड करता है कि कौन से प्रस्ताव और क्रियाएं प्रत्येक स्तर पर पहुंच-योग्य हैं और कौन से जोड़े पारस्परिक रूप से अनन्य हैं, फिर इस संरचना के माध्यम से पीछे की ओर खोज करके एक योजना निकालता है, जिससे योजना की गति नाटकीय रूप से बढ़ जाती है।

विलोपन-शिथिलीकरण अनुमानी

क्रियाओं के विलोपन प्रभावों को अनदेखा करने से एक शिथिल योजना समस्या उत्पन्न होती है जिसे हल करना बहुत आसान होता है; इस शिथिलीकरण को हल करने की लागत सूचनात्मक, अक्सर स्वीकार्य अनुमानी (जैसे h-max और h-add और FF अनुमानी) प्रदान करती है जो फॉरवर्ड सर्च को निर्देशित करती है।

अनुमानी खोज योजना

अत्याधुनिक शास्त्रीय योजनाकार स्वचालित रूप से प्राप्त अनुमानी को बेस्ट-फर्स्ट या ग्रीडी सर्च और पसंदीदा ऑपरेटरों जैसे संवर्द्धन के साथ जोड़ते हैं, जिससे विविध डोमेन में मजबूत सामान्य-उद्देश्य प्रदर्शन प्राप्त होता है।

Clinical relevance

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

History

ब्लम और फर्स्ट के ग्राफ़प्लान (1995, जर्नल संस्करण 1997) ने योजना ग्राफ़ की शुरुआत की और योजना की गति में क्रांति ला दी। 1990 के दशक के अंत और 2000 के दशक में विलोपन-शिथिलीकरण अनुमानी का उदय हुआ, जिसमें एफएफ प्लानर (हॉफमैन और नेबेल, 2001) और बाद में फास्ट डाउनवर्ड (हेल्मर्ट, 2006) ने अनुमानी फॉरवर्ड सर्च को प्रमुख दृष्टिकोण के रूप में स्थापित किया।

Key figures

• Avrim L. Blum
• Merrick L. Furst
• Jörg Hoffmann
• Bernhard Nebel
• Malte Helmert

Seminal works

• blum1997
• hoffmann2001

Frequently asked questions

योजना ग्राफ़ में म्यूटेक्स क्या है?

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

विलोपन प्रभावों को अनदेखा करने से एक उपयोगी अनुमानी क्यों मिलता है?

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