वृद्धिशील अनुमानी खोज (इन्क्रीमेंटल ह्यूरिस्टिक सर्च) कृत्रिम बुद्धिमत्ता में एल्गोरिदम का एक परिवार है जो ग्राफ में पथ खोजने की समस्या का समाधान करता है जब ग्राफ समय के साथ बदलता है। शास्त्रीय अनुमानी खोज विधियों जैसे कि A* के विपरीत, जो पर्यावरण में प्रत्येक परिवर्तन पर शुरू से पूर्ण समाधान की पुनर्गणना करते हैं, वृद्धिशील अनुमानी खोज एल्गोरिदम पिछले खोज प्रयासों से अधिकतम जानकारी का पुन: उपयोग करते हैं। यह पुन: उपयोग गतिशील या आंशिक रूप से ज्ञात वातावरण में कम्प्यूटेशनल लागत को नाटकीय रूप से कम कर सकता है, जिससे वे रोबोट नेविगेशन, वीडियो गेम पाथफाइंडिंग और स्वायत्त वाहन रूटिंग जैसे अनुप्रयोगों के लिए विशेष रूप से मूल्यवान बन जाते हैं।
मूल विचार एक अनुमानी फलन और एक खोज वृक्ष को बनाए रखना है जो किनारे की लागत में परिवर्तन या नई बाधाओं की खोज होने पर वृद्धिशील रूप से अद्यतन होते हैं। जब कोई परिवर्तन होता है, तो एल्गोरिदम पहचानता है कि पिछली खोज के कौन से भाग अभी भी मान्य हैं और किन्हें संशोधित करने की आवश्यकता है, फिर आवश्यक अद्यतनों का प्रसार करता है। यह दृष्टिकोण शास्त्रीय अनुमानी खोज (जो एक स्थिर ग्राफ मानता है) और बिना अनुमानी के वृद्धिशील खोज (जो पथों का पुन: उपयोग कर सकता है लेकिन अनुमानी के मार्गदर्शन की कमी रखता है) दोनों के विपरीत है।
ऐतिहासिक विकास
वृद्धिशील अनुमानी खोज की नींव 1990 के दशक के अंत और 2000 के दशक की शुरुआत में रखी गई थी। सबसे प्रभावशाली एल्गोरिदम, D लाइट, 2002 में स्वेन कोएनिग और मैक्सिम लिखाचेव द्वारा प्रस्तुत किया गया था। D लाइट 1994 में एंथनी स्टेंट्ज़ द्वारा विकसित पहले D एल्गोरिदम पर आधारित है, जिसे मोबाइल रोबोट नेविगेशन के लिए डिज़ाइन किया गया था। D लाइट मूल D* को सरल बनाता है जबकि इसकी दक्षता बनाए रखता है, और यह क्षेत्र में एक मानक संदर्भ बन गया है।
एक अन्य प्रमुख एल्गोरिदम लाइफलॉन्ग प्लानिंग A (LPA) है, जिसे 2001 में कोएनिग और लिखाचेव द्वारा भी प्रस्तुत किया गया था। LPA किनारे की लागत में परिवर्तन को संभालता है जबकि अनुमानी को सुसंगत रखता है, और यह D लाइट का आधार बनाता है। तब से क्षेत्र का विस्तार जनरलाइज्ड एडेप्टिव A (GAA) और एनीटाइम D* जैसे विविधताओं के साथ हुआ है, जो समाधान गुणवत्ता को गणना समय के लिए व्यापार करते हैं।
एल्गोरिदमिक सिद्धांत
वृद्धिशील अनुमानी खोज एल्गोरिदम आमतौर पर प्रत्येक नोड के लिए दो प्रकार के मान बनाए रखते हैं: एक g-मान (शुरुआत से सबसे अच्छे ज्ञात पथ की लागत) और एक h-मान (लक्ष्य के लिए अनुमानी अनुमान)। वे यह भी ट्रैक करते हैं कि कोई नोड सुसंगत है या नहीं, जिसका अर्थ है कि इसका g-मान इसके पूर्ववर्तियों पर न्यूनतम के बराबर है। जब किनारे की लागत बदलती है, तो एल्गोरिदम प्रभावित नोड्स के g-मानों को अद्यतन करता है और f = g + h द्वारा क्रमित प्राथमिकता कतार का उपयोग करके खोज वृक्ष के माध्यम से परिवर्तनों का प्रसार करता है।
मुख्य नवाचार LPA और D लाइट में "rhs-मान" (दाएं हाथ की ओर मान) का उपयोग है, जो पूर्ववर्तियों के g-मानों के न्यूनतम और किनारे की लागत का प्रतिनिधित्व करता है। एक नोड स्थानीय रूप से सुसंगत है यदि इसका g-मान इसके rhs-मान के बराबर है। एल्गोरिदम स्थानीय रूप से असंगत नोड्स की एक सूची बनाए रखता है और उन्हें उनकी कुंजी के क्रम में संसाधित करता है, जो एक जोड़ी (min(g, rhs) + h, min(g, rhs)) है। यह सुनिश्चित करता है कि खोज के केवल आवश्यक भागों की पुनर्गणना की जाती है।
रोबोटिक्स और एआई में अनुप्रयोग
वृद्धिशील अनुमानी खोज का व्यापक रूप से रोबोटिक्स में अज्ञात या बदलते वातावरण में पथ योजना के लिए उपयोग किया जाता है। उदाहरण के लिए, एक रोबोट इमारत की खोज करते समय शुरू में एक नक्शे के आधार पर पथ की योजना बना सकता है, लेकिन जैसे ही यह नई बाधाओं (जैसे, बंद दरवाजे) की खोज करता है, यह पुनः आरंभ किए बिना अपनी योजना को वृद्धिशील रूप से अद्यतन कर सकता है। यह वास्तविक समय नेविगेशन के लिए महत्वपूर्ण है जहां गणना समय सीमित है।
वीडियो गेम में, गैर-खिलाड़ी पात्रों (NPCs) को अक्सर चलती बाधाओं या बदलते लक्ष्यों के साथ गतिशील इलाकों में नेविगेट करने की आवश्यकता होती है। वृद्धिशील अनुमानी खोज कुशल पुनर्नियोजन को सक्षम बनाती है, जिससे गेम की प्रतिक्रियाशीलता में सुधार होता है। यह तकनीक लॉजिस्टिक्स में भी लागू होती है, जहां डिलीवरी मार्गों को यातायात स्थितियों के अनुकूल होना चाहिए, और नेटवर्क रूटिंग में, जहां लिंक लागत में उतार-चढ़ाव होता है।
अन्य खोज विधियों के साथ तुलना
शास्त्रीय A खोज स्थिर ग्राफ के लिए इष्टतम और पूर्ण है, लेकिन यह गतिशील सेटिंग्स में अक्षम है क्योंकि यह ग्राफ बदलने पर सभी पिछले कार्य को त्याग देता है। वृद्धिशील अनुमानी खोज A की इष्टतमता गारंटी को बरकरार रखती है जबकि पिछली गणनाओं का पुन: उपयोग करती है। हालांकि, इसे खोज वृक्ष और स्थिरता जानकारी संग्रहीत करने के लिए अतिरिक्त मेमोरी की आवश्यकता होती है।
एक और संबंधित दृष्टिकोण एनीटाइम खोज है, जिसका उद्देश्य जल्दी से एक अच्छा समाधान ढूंढना और फिर अधिक समय दिए जाने पर इसे सुधारना है। कुछ वृद्धिशील एल्गोरिदम, जैसे एनीटाइम D*, दोनों गुणों को जोड़ते हैं: वे जल्दी से एक उप-इष्टतम समाधान लौटा सकते हैं और समय अनुमति देने पर इसे परिष्कृत कर सकते हैं। यह समय-महत्वपूर्ण अनुप्रयोगों में विशेष रूप से उपयोगी है।
वर्तमान अनुसंधान और भविष्य की दिशाएं
वृद्धिशील अनुमानी खोज में हालिया शोध बहुत बड़े ग्राफों पर स्केलिंग, निरंतर राज्य स्थानों को संभालने और मशीन लर्निंग के साथ एकीकरण पर केंद्रित है। उदाहरण के लिए, प्रारंभिक h-मानों को बेहतर बनाने के लिए सीखने-आधारित अनुमानी का उपयोग किया जा सकता है, जिससे विस्तार की संख्या कम हो जाती है। मल्टी-कोर प्रोसेसर के लिए वृद्धिशील खोज को समानांतर करने और उच्च-आयामी समस्याओं के लिए RRT* जैसे नमूना-आधारित योजनाकारों के साथ संयोजन पर भी काम चल रहा है।
आधुनिक Artificial intelligence प्रणालियों के संदर्भ में, वृद्धिशील अनुमानी खोज मूर्त एजेंटों के लिए प्रासंगिक बनी हुई है, जैसे कि Waymo स्वायत्त वाहनों या Tesla प्रणालियों में, जहां वास्तविक समय पुनर्नियोजन आवश्यक है। सिद्धांत Machine learning और Deep learning में खोज सीखने के लिए अनुसंधान को भी प्रभावित करते हैं, हालांकि शास्त्रीय एल्गोरिदम गारंटीकृत इष्टतमता के लिए मानक बने हुए हैं।
यह भी देखें
संदर्भ
- कोएनिग, एस., और लिखाचेव, एम. (2002). D* लाइट. राष्ट्रीय कृत्रिम बुद्धिमत्ता सम्मेलन की कार्यवाही.
- कोएनिग, एस., और लिखाचेव, एम. (2001). लाइफलॉन्ग प्लानिंग A*. कृत्रिम बुद्धिमत्ता.
- स्टेंट्ज़, ए. (1994). आंशिक रूप से ज्ञात वातावरण के लिए इष्टतम और कुशल पथ योजना. आईईईई अंतर्राष्ट्रीय रोबोटिक्स और स्वचालन सम्मेलन.