तेजी की खोज यादृच्छिक पेड़

Question

http://msl.cs.uiuc.edu/rrt/

किसी को भी कैसे आर आर टी सरल शब्दों समझने में आसान है कि साथ काम करता है व्याख्या कर सकते हैं? मैंने साइट और विकिपीडिया में विवरण पढ़ा।

क्यों आर आर टी बढ़ने करता बाहर सिर्फ केंद्र के चारों ओर बहुत घने बढ़ रही के बजाय:

मैं देखना चाहेंगे क्या, एक आर आर टी या निम्न बात का पूरी तरह से व्याख्या की एक छोटी कार्यान्वयन है? यह एक बेवकूफ यादृच्छिक पेड़ से अलग कैसे है?

अगला नया वर्टेक्स जिसे हम उठाए जाने का प्रयास करते हैं?

मुझे पता है कि एक मोशन स्ट्रैटेजी लाइब्रेरी है जिसे मैं डाउनलोड कर सकता हूं लेकिन मैं दूसरे तरीके के बजाय कोड में जाने से पहले विचार को समझूंगा।

Answer 1

सबसे आसान संभव आरआरटी ​​एल्गोरिदम इतना सफल रहा है क्योंकि इसे लागू करना बहुत आसान है। हालात जटिल पाने के लिए जब आप करते हैं:

• जरूरत से ज्यादा दो आयामों में योजना बना अवधारणाओं कल्पना करने के लिए
• नियोजन से सम्बन्धित मूल शब्दों से अपरिचित हैं, और;
• साहित्य में वर्णित आरआरटी ​​की बड़ी संख्या में वर्णित हैं। एक खाली खोज के पेड़ के साथ

  1. प्रारंभ

  2. खोज करने के लिए अपने प्रारंभिक स्थान (विन्यास) जोड़ें:

छद्म कोड

बुनियादी एल्गोरिथ्म कुछ इस तरह दिखता पेड़

जबकि आपका खोज पेड़ लक्ष्य तक नहीं पहुंच पाया है (और आप समय से बाहर नहीं हुए हैं)

3.1। एक स्थान (कॉन्फ़िगरेशन), q_r चुनें, (कुछ नमूना रणनीति के साथ)

3.2। उस यादृच्छिक बिंदु के निकट खोज पेड़ में कशेरुका पाएं, q_n

3.3। q_n और q_r के बीच पेड़ में किनारे (पथ) जोड़ने का प्रयास करें, यदि आप टकराव के बिना उन्हें लिंक कर सकते हैं।

हालांकि कि वर्णन पर्याप्त है, कुछ समय बाद इस क्षेत्र में काम कर रहे, मैं वास्तव में pseudocode of figure 5.16 on RRT/RDT स्टीवन LaValle की पुस्तक "योजना एल्गोरिदम" में पसंद करते हैं।

ट्री स्ट्रक्चर

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

सैम्पलिंग रणनीति

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

पुस्तकालय

MSL library एक अच्छा प्रारंभिक बिंदु यदि आप वास्तव में कार्यान्वयन पर अटक कर रहे है, लेकिन यह सक्रिय रूप से के बाद से 2003 एक और अधिक अप-टू-डेट पुस्तकालय Open Motion Planning Library (OMPL) है नहीं रखा गया है। आपको एक अच्छी टक्कर पहचान पुस्तकालय की भी आवश्यकता होगी।

योजना शब्दावली & सलाह

देखने के एक शब्दावली बिंदु से, कठिन सा एहसास है कि हालांकि चित्र आप आर आर टी पर (के प्रारंभिक वर्षों) प्रकाशनों में देखने की बहुत सारी दो आयामों में कर रहे हैं (है पेड़ जो 2 डी अंक लिंक करते हैं), कि यह पूर्ण सरलतम मामला है।

आमतौर पर, जटिल शारीरिक स्थितियों का वर्णन करने के लिए गणितीय रूप से कठोर तरीका आवश्यक है। इसका एक अच्छा उदाहरण एन-लिंकेज के साथ रोबोट बांह की योजना बना रहा है। इस तरह के हाथ के अंत का वर्णन करने के लिए न्यूनतम n संयुक्त कोण की आवश्यकता होती है। किसी स्थिति का वर्णन करने के लिए न्यूनतम पैरामीटर का यह सेट कॉन्फ़िगरेशन (या कुछ प्रकाशन राज्य) है। एक एकल विन्यास अक्सर q

सभी संभव विन्यास (या उसके एक सबसेट) कि प्राप्त किया जा सकता का संयोजन निरूपित किया जाता है एक विन्यास अंतरिक्ष (या राज्य अंतरिक्ष) बनाते हैं। यह विमान में एक बिंदु के लिए एक unbounded 2 डी विमान के रूप में, या अन्य मानकों की श्रृंखला के अविश्वसनीय रूप से जटिल संयोजन के रूप में सरल हो सकता है।