ग्रिड वातावरण में ह्यूरिस्टिक खोज एल्गोरिदम के प्रदर्शन मेट्रिक्स

3 प्रायोगिक वातावरण और प्रदर्शन मीट्रिक्स

ह्यूरिस्टिक सर्च एल्गोरिदम रोबोटिक पाथफाइंडिंग जैसे क्षेत्रों में महत्वपूर्ण भूमिका निभाते हैं, क्योंकि वे एक शुरुआती स्थिति और एक लक्ष्य स्थिति को देखते हुए इष्टतम पथ निर्धारित करते हैं। ग्रिड-आधारित वातावरण का उपयोग आमतौर पर वास्तविक दुनिया के पर्यावरण परिदृश्यों का प्रतिनिधित्व करने के लिए किया जाता है, जहाँ इन एल्गोरिदम को लागू किया जा सकता है, जैसे कि स्वायत्त नेविगेशन और रोबोटिक्स [6] में। इस अध्ययन में, हम विभिन्न ग्रिड वातावरणों में प्रसिद्ध ह्यूरिस्टिक सर्च एल्गोरिदम, अर्थात् D*, D* लाइट, LPA*, LRTA*, RTAA*, और ARA* का व्यापक विश्लेषण करते हैं। हम एल्गोरिदम की खोज का मार्गदर्शन करने के लिए यूक्लिडियन दूरी ह्यूरिस्टिक का उपयोग करते हैं और एल्गोरिदम के प्रदर्शन पर कुछ ग्रिड विशेषताओं, जैसे बाधा घनत्व और ग्रिड आकार के प्रभाव का आकलन करते हैं।

हमारे अध्ययन में, हम ग्रिड-आधारित वातावरण का उपयोग उनकी सरलता और नियंत्रण में आसानी के कारण करते हैं, साथ ही शोध समुदाय में पथ-योजना कार्यों में आमतौर पर उपयोग किए जाने के कारण भी। ग्रिड सफ़ेद कोशिकाओं से बने होते हैं, जो पार करने योग्य स्थितियों का प्रतिनिधित्व करते हैं, जबकि काले रंग की कोशिकाएँ गैर-पार करने योग्य बाधाओं का प्रतिनिधित्व करती हैं। हमारे सिमुलेशन में एजेंट आठ दिशाओं में आगे बढ़ सकता है, जिसकी लागत क्षैतिज और ऊर्ध्वाधर चालों के लिए 1 के बराबर है, और विकर्ण चालों के लिए √ 2 है। हमने दो प्रकार के ग्रिड वातावरण का उपयोग किया: यादृच्छिक रूप से उत्पन्न ग्रिड वातावरण और व्यक्तिगत ग्रिड वातावरण।

यादृच्छिक रूप से उत्पन्न ग्रिड-आधारित वातावरण: ग्रिड तीन मापदंडों द्वारा चिह्नित होते हैं:

ग्रिड आकार (NxN), बाधा घनत्व, तथा आरंभ और लक्ष्य स्थितियों के बीच की दूरी। खोज एल्गोरिदम के प्रदर्शन पर प्रत्येक पैरामीटर के प्रभाव की जांच करने के लिए, हमने अन्य पैरामीटर को स्थिर रखते हुए प्रत्येक पैरामीटर को स्वतंत्र रूप से बदला। विविधताओं में ग्रिड आकार को बदलना, आरंभ से लक्ष्य दूरी को बदलना, तथा बाधा घनत्व को बदलना शामिल था। एक भिन्नता में प्रत्येक ग्रिड के लिए, हमने समान ग्रिड पैरामीटर के दस यादृच्छिक उदाहरण उत्पन्न किए (उदाहरण के लिए, 0.25 बाधा घनत्व वाला ग्रिड, आकार 300x300, तथा आरंभ से लक्ष्य दूरी 140, दस उदाहरण हैं, जो यादृच्छिक रूप से उत्पन्न किए गए थे)।

व्यक्तिगत ग्रिड वातावरण: अधिक विशिष्ट परिदृश्यों का अनुकरण करने के लिए डिज़ाइन किया गया। इन ग्रिडों का आकार निश्चित है (71x31 इकाइयाँ) और आरंभ और लक्ष्य दोनों स्थितियों के लिए एक निश्चित स्थिति है, और उन्हें उनकी बाधा विन्यास के आधार पर दो भागों में विभाजित किया गया है:

• क्षैतिज दीवार विन्यास: इन प्रयोगों के लिए, हम ग्रिड लंबाई की हर 10 इकाइयों पर आधी ग्रिड चौड़ाई की क्षैतिज दीवारें जोड़ते हैं। हमने दीवारों को दो दिशाओं में जोड़ा: एक बार बाएं से दाएं, और एक बार नए बने ग्रिड में दाएं से बाएं।

• क्षैतिज दीवार लंबाई विन्यास: यहां, हम सभी संभावित दीवारों को जोड़ते हैं जिन्हें भीतर रखा जा सकता है

ग्रिड की लम्बाई, और हर बार जब हम एक नया ग्रिड बनाते हैं तो हम सभी दीवारों की लम्बाई को 2 इकाई तक बढ़ा देते हैं।

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

प्रयोगों में प्रयुक्त विभिन्न खोज एल्गोरिदम के प्रदर्शन का मूल्यांकन करने के लिए, हमने निम्नलिखित मेट्रिक्स का चयन किया है:

• पथ लागत: मीट्रिक पथ की लंबाई या शुरुआत से लक्ष्य स्थिति तक निष्पादित क्रियाओं की संख्या को मापता है। यह समाधान की गुणवत्ता को इंगित करता है।

• मेमोरी खपत: यह एल्गोरिदम को समाधान खोजने के लिए आवश्यक मेमोरी की मात्रा को मापता है। एल्गोरिदम की मापनीयता की जांच करना प्रासंगिक है, और इसे (KB) में मापा जाता है।

• समाधान समय: एक एल्गोरिथ्म द्वारा समाधान खोजने में लिया गया कुल समय (एमएस) दर्शाता है, जिसे मिलीसेकंड (एमएस) में मापा जाता है।

हमने अपने प्रयोग 3.30GHz 27 Intel i9 कोर पर किए, जो 250Gb RAM से लैस थे और Ubuntu Linux 22.04 चला रहे थे। निम्नलिखित सेटिंग्स का उपयोग करते हुए: सभी एल्गोरिदम यूक्लिडियन दूरी को ह्यूरिस्टिक फ़ंक्शन के रूप में उपयोग कर रहे थे। LRTA* और RTAA* के लिए, हमने प्रत्येक पुनरावृत्ति के लिए व्यय किए गए नोड्स की संख्या 250 निर्धारित की। ह्यूरिस्टिक के लिए ARA* एल्गोरिदम को 2.5 के भार के साथ चलाया गया। हमने यादृच्छिकता को ध्यान में रखते हुए और परिणामों की विश्वसनीयता सुनिश्चित करने के लिए प्रत्येक ग्रिड पर प्रत्येक एल्गोरिदम को 100 बार चलाया।