एक गोल्फ कोर्स पर सेवा रोबोट नेविगेशन। एक पथ का निर्माण और बाधाओं से बचने

सर्विस रोबोट के लिए बाधाओं को नेविगेट करने और उनसे बचने का सबसे अच्छा तरीका क्या है?

रोबोट मैकेनिकल और सॉफ्टवेयर सिस्टम हैं जो वास्तविक दुनिया के साथ बातचीत करते हैं। सर्विस रोबोट के लिए, अंतरिक्ष में अपनी वर्तमान स्थिति, लक्ष्य की स्थिति और संभावित बाधाओं को दरकिनार करके लक्ष्य के लिए मार्ग बनाने की क्षमता को समझना बेहद महत्वपूर्ण है। हम ड्राइविंग रेंज पर गोल्फ की गेंदों को इकट्ठा करने के लिए एक रोबोट विकसित कर रहे हैं। हमने अपने लिए सबसे अच्छा खोजने के लिए एक मार्ग बनाने के लिए विभिन्न विकल्पों पर विचार किया, शायद यह जानकारी किसी के लिए दिलचस्प होगी।



रोबोट को दो-आयामी अंतरिक्ष में अपने अंतिम लक्ष्य तक पहुंचने का सबसे आसान तरीका। यहां रोवर अपने आप में एक छोटा बिंदु है जिसके सामने कोई बाधा नहीं है। इसलिए, इस स्थिति में रोबोट एक सीधी रेखा में चलता है, और जब यह लक्ष्य तक पहुंचता है तो यह रुक जाता है।

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

लेकिन यह एल्गोरिथ्म लागू नहीं किया जा सकता है अगर रोबोट के सामने अचानक एक बाधा उत्पन्न होती है। एक सीधी रेखा में घूमते हुए, रोवर उसके चारों ओर नहीं जा पाएगा या गुजर नहीं पाएगा। इस संबंध में, वह बस एक बाधा के सामने रुक जाता है और आगे नहीं बढ़ता है।

कैसे एक बाधा के आसपास पाने के लिए? समस्या को हल करने का सबसे आसान तरीका "बाधा से बचना" नामक व्यवहार विकल्प है। व्यवहार में, यह विभिन्न एल्गोरिदम द्वारा दर्शाया गया है।

एल्गोरिथ्म के लिए चलो

यदि लक्ष्य प्राप्त नहीं होता है:

• लक्ष्य की ओर बढ़ें।
• अन्यथा: बंद करो।

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

एक बाधा रोबोट को एक सीधी रेखा में अपने गंतव्य तक पहुंचने की अनुमति नहीं देती है, इस स्थिति में रोवर उसके सामने बस रुक जाता है। इस मामले में, आप "वॉक टू" एल्गोरिथम का उपयोग कर सकते हैं, लेकिन इसे पूरक करने की आवश्यकता है।

बग एल्गोरिदम

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

लक्ष्य की ओर बढ़ते समय रोबोट जो कदम उठाता है (एक बाधा के आसपास चलने सहित) को एक प्रक्षेपवक्र कहा जाता है।



बग एल्गोरिथ्म उन अवधारणाओं के आधार के रूप में कार्य करता है जो अधिक जटिल प्रकार के मार्गों के निर्माण में उपयोग किए जाते हैं। इनमें शामिल हैं:

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

नीति की अवधारणा । यदि बीटल एल्गोरिथ्म का उपयोग करने के लिए आंदोलन के कुछ निर्देश रोबोट को प्रेषित किए जाते हैं, तो मार्ग के निर्माण के इस तरीके को "प्रबंधन नीति" कहा जाता है।

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

हालांकि, इस तरह के एक एल्गोरिथ्म डेवलपर को सीमित करता है, क्योंकि इसकी मदद से एक मार्ग का निर्माण संभव होगा जो आकार में सीमित है। पथ के निर्माण के लिए इस तरह के एक एल्गोरिथ्म का उपयोग करते समय, यह आवश्यक है कि सभी बाधाएं उत्तल बहुभुज का रूप ले लें।

बग एल्गोरिथ्म की सीमाएँ भी हैं:

• बाधाएं एक दूसरे से एक निश्चित दूरी पर होनी चाहिए, यह असंभव है कि उनके पास आम जमीन है;
• बाधाओं की सीमाएं बंद वक्र हैं, जबकि उन्हें ऐसा होना चाहिए कि सीधी रेखा जिसके साथ रोबोट चलता है, उनमें से प्रत्येक को सीमित संख्या के लिए प्रतिच्छेदन;
• एक रोबोट एक बहुत ही छोटा बिंदु है, इसलिए यह उन दोनों के बीच मार्ग की परवाह किए बिना बाधाओं के बीच आगे बढ़ सकता है।

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

CBUG एल्गोरिथम

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

डीजकस्ट्रा का एल्गोरिथम

ग्राफ पर उपयोग किया जाने वाला एल्गोरिथ्म पिछली शताब्दी के उत्तरार्ध में ई। डिज्स्ट्रॉय द्वारा बनाया गया था। इसकी मदद से, ग्राफ के एक कोने से दूसरे तक सबसे छोटा रास्ता निर्धारित करना संभव होगा। ऐसा एल्गोरिथम तब समाप्त होता है जब रोबोट सभी चोटियों का दौरा कर चुका होता है। यदि वे जिनके पास अभी तक सवारी नहीं हुई है, तो न्यूनतम चिह्न वाली चोटी का चयन किया जाता है।

Deister एल्गोरिथ्म के लाभों में शामिल हैं:

• पथ की लंबाई और इसकी लागत पर ध्यान देना;
• यदि अधिक इष्टतम एक पाया जाता है, तो नोड्स को अपडेट किया जाता है।

एक मार्ग के निर्माण की इस पद्धति का नुकसान यह है कि यह केवल उन ग्राफ़ों के लिए उपयुक्त है जहां नकारात्मक भार के कोई किनारे नहीं हैं। यह असुविधाजनक है कि वह चौड़ाई में खोज करते समय खराब उन्मुख है।

बेलमैन-फोर्ड एल्गोरिथम

लेकिन अक्सर ऐसी परिस्थितियां उत्पन्न होती हैं जिनमें एक मार्ग का निर्माण करना आवश्यक होता है जहां नकारात्मक वजन के साथ पसलियां होती हैं। बेलमैन-फोर्ड एल्गोरिदम इस तरह की समस्या को हल करने में मदद करेगा। यदि, परिणामस्वरूप, अंतिम पथ के किनारों के वजन का योग एक नकारात्मक मान लेता है, तो इसे नकारात्मक चक्र कहा जाता है।

जॉनसन एलगोरिदम

यह एल्गोरिथ्म डीबी द्वारा पेश किया गया था जॉनसन एक चोटी से दूसरे तक सभी सबसे छोटे मार्गों की पहचान करने के लिए। इस मामले में, विधि का उपयोग सकारात्मक और नकारात्मक भार दोनों के साथ किनारों के लिए किया जा सकता है। एल्गोरिथ्म का एकमात्र दोष यह है कि कोई नकारात्मक चक्र नहीं हैं।

एल्गोरिथम ए *

ग्राफ़ का उपयोग करके सबसे इष्टतम तरीका खोजने के लिए, आपको ए * एल्गोरिथ्म लागू करने की आवश्यकता है। यह आपको ग्राफ़ पर पहले मैच द्वारा रोबोट से लक्ष्य तक का सबसे अच्छा मार्ग निर्धारित करने की अनुमति देता है। इस एल्गोरिथ्म का आधार अनुमानी सूत्र है, जो इस प्रकार है:

f(n)=g(n)+h(n).
f(n) - , n.
g(n) - n .
h(n) - .

यह एल्गोरिदम आपको लक्ष्य के लिए सबसे छोटा रास्ता खोजने की अनुमति देता है जब तक कि h (n) अधिकतम अनुमत मूल्य नहीं लेता। ए * एल्गोरिथ्म की एक विशेषता इसका लचीलापन है। सबसे अधिक बार, राज्य रोबोट का सेल या स्थान है। लेकिन यह गति या अभिविन्यास भी हो सकता है।

उसी समय, पास के राज्य विशिष्ट मामले के आधार पर भिन्न होते हैं।

एल्गोरिथ्म का लचीलापन इस तथ्य में भी प्रकट होता है कि रोबोट को जिस लक्ष्य को प्राप्त करने की आवश्यकता है वह एक ही बार में कई पदों से मिलकर बन सकता है। ऐसी स्थिति में, सभी उपलब्ध उद्देश्यों के लिए अनुमानी सन्निकटन h (n) तुरंत मान्य होना चाहिए।

एल्गोरिथ्म ए * कितनी अच्छी तरह काम करेगा यह घातांक h (n) पर निर्भर करता है। बेहतर सन्निकटन गुणवत्ता, उच्च दक्षता। इसके अलावा, मुफ्त मेमोरी और प्रोसेसर समय की मात्रा एल्गोरिदम के संचालन को प्रभावित करती है।

तरंग अनुरेखण एल्गोरिथ्म

इसके अलावा, एक तरंग एल्गोरिथ्म अक्सर एक ग्राफ पर एक मार्ग खींचने के लिए उपयोग किया जाता है। इस तरह से एक पथ का निर्माण करते समय, चौड़ाई-पहली खोज विधि का उपयोग किया जाता है।

एल्गोरिथ्म में स्वयं निम्नलिखित चरण शामिल हैं:

1. प्रारंभ;
2. लहर निर्माण;
3. मार्ग की वसूली।

प्रारंभिक चरण में, कई कोशिकाओं की छवि बनाई जाती है, जिनमें से प्रत्येक रोबोट के लिए या तो निष्क्रिय या अगम्य हो जाती है।

रोबोट, एक सेल से दूसरे में जा रहा है, क्रमिक रूप से यह निर्धारित करता है कि क्या इसे पारित करना संभव है और क्या उसने इसे पहले नोट किया है।

उसके बाद, प्रारंभिक सेल से अंतिम एक तक का सबसे छोटा रास्ता जानवर बल द्वारा बनाया गया है, जिसकी उपलब्धि रोवर का उद्देश्य है।

स्पेस एलगोरिदम को अलग करें

1. कॉन्फ़िगरेशन स्पेस में सभी आयामों में एक स्थिर आकार होता है।
2. सभी मापों को विच्छेदित करें ताकि उनके पास कोशिकाओं की एक निरंतर संख्या हो।
3. बाधा के अंदर कॉन्फ़िगरेशन स्थान में स्थित सभी कोशिकाओं को अगम्य के रूप में चिह्नित किया जाना चाहिए।
4. नतीजतन, सभी निष्क्रिय कोशिकाएं नोड्स में बदल गईं।
5. प्रत्येक नोड ग्राफ में सभी पड़ोसियों से जोड़ता है।

यादृच्छिक पथ खोजक

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

संभावित रोड मैप्स एल्गोरिथम

• 1. एक खाली ग्राफ बनाएं G।
• 2. ग्राफ़ में रोबोट के नोड्स और उसके अंतिम लक्ष्य को जोड़ें।
• 3. एकीकरण की एनएचटी संख्या के लिए:
• 1. कॉन्फ़िगरेशन स्थान का एक समान यादृच्छिक नमूना ढूंढें और इसे R नाम दें।
  2. यदि रोबोट आर कॉन्फ़िगरेशन के साथ संघर्ष में है, तो आप जारी रख सकते हैं।
  3. वरना: R को कॉलम G में जोड़ें।
• 4. ग्राफ में सभी नोड्स को पहचानें जो अंक d और R के भीतर स्थित हैं।
• 5. सभी एन नोड्स के लिए जो इस पैरामीटर को फिट करते हैं:

तेजी से अन्वेषण यादृच्छिक वृक्ष एल्गोरिथम

कभी-कभी आपको पिछले नियोजन प्रश्नों को लागू किए बिना एक पथ बनाने की आवश्यकता होती है। ऐसी स्थितियों में, आपको निम्नलिखित विधि का उपयोग करना चाहिए:

1. एक खाली टी। ट्री बनाएँ
2. टी प्रारंभिक रोबोट कॉन्फ़िगरेशन में जोड़ें।
3. लक्ष्य पूरा होने तक:
   1. नोड आर के लिए प्राप्त करें।
   2. टी में परिभाषित करें नोड के निकटतम आर। उसे K नाम दो।
   3. निम्नलिखित स्थिति के पूरा होने तक K से R तक रोबोट को स्थानांतरित करें:
      1. टकराव की स्थिति में, यादृच्छिक नमूने की परिभाषा पर आगे बढ़ें।
      2. अन्यथा: इस कॉन्फ़िगरेशन में T पर एक नया नोड जोड़ें।
      3. यदि d और K के बीच अधिकतम दूरी हो गई है, तो फिर से यादृच्छिक नमूने पर काम करना शुरू करें।
4. समाधान प्राप्त किया जाता है यदि श्रृंखला नोड किसी भी नोड टी से दूरी डी के भीतर स्थित है।

निष्कर्ष

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

चूंकि हमारी बारीकियों में सभी बाधाएं उत्तल हैं, इसलिए हम सबसे सरल बीयूजी एल्गोरिदम का उपयोग करते हैं, और यहां तक ​​कि सरल भी। एक निश्चित "बचकाना" नेविगेशन विधि। जब एक अल्ट्रासाउंड एक बाधा का पता लगाता है, तो रोवर दक्षिणावर्त 90 डिग्री बदल जाता है, 1m गुजरता है, 90 वामावर्त मुड़ता है। यदि रोबोट को 0.5 मीटर पीछे करने से पहले बम्पर द्वारा एक बाधा का पता लगाया जाता है।

योजनाओं

2018 की गर्मियों में परियोजना की शुरुआत के दौरान। बड़ी संख्या में कार्यक्रम हुए। हम अपने प्रोजेक्ट के विकास पर एक पोस्ट तैयार कर रहे हैं। आपका ध्यान के लिए धन्यवाद!

संदर्भ

• गोल्फ गेंदों को इकट्ठा करने के लिए एक रोबोट का विकास
• एक सीमित बजट के साथ एक रोबोट केस बनाने का प्रयास। ग्लास मैट और एपॉक्सी
• सर्विस रोबोट डिजाइन करना। समस्या बयान, समाधान वास्तुकला
• शुरुआती के लिए ArduPilot। स्थापित करें और बीगलबोन ब्लू पर कॉन्फ़िगर करें
• सीमित बजट वाला रोबोट केस बनाना। वैक्यूम बनाने ।