मोशन प्लानिंग

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

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

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

अवधारणाएं

File:Motion planning workspace 1.svg

कार्यक्षेत्र का उदाहरण।

File:Motion planning workspace 1 configuration space 1.svg

एक बिंदु के आकार के रोबोट का विन्यास स्थान। सफेद = सी_free, ग्रे = सी_obs.

Error creating thumbnail:

एक आयताकार अनुवाद करने वाले रोबोट के लिए विन्यास स्थान (चित्रित लाल)। सफेद = सी_free, ग्रे = सी_obs, जहां डार्क ग्रे = ऑब्जेक्ट्स, लाइट ग्रे = कॉन्फ़िगरेशन जहां रोबोट किसी ऑब्जेक्ट को छूएगा या वर्कस्पेस छोड़ देगा।

File:Motion planning configuration space curved valid path.svg

एक मान्य पथ का उदाहरण।

Error creating thumbnail:

अमान्य पथ का उदाहरण.

File:Motion planning configuration space road map path.svg

रोड मैप का उदाहरण।

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

कॉन्फ़िगरेशन स्थान

एक कॉन्फ़िगरेशन रोबोट की मुद्रा का वर्णन करता है, और कॉन्फ़िगरेशन स्पेस (भौतिकी) सी सभी संभावित कॉन्फ़िगरेशन का सेट है। उदाहरण के लिए:

• यदि रोबोट एक एकल बिंदु (शून्य-आकार) है जो 2-आयामी विमान (कार्यक्षेत्र) में अनुवाद कर रहा है, तो C एक विमान है, और दो मापदंडों (x, y) का उपयोग करके एक कॉन्फ़िगरेशन का प्रतिनिधित्व किया जा सकता है।
• यदि रोबोट एक 2D आकार है जो अनुवाद और घुमा सकता है, तो कार्यक्षेत्र अभी भी 2-आयामी है। हालाँकि, C विशेष यूक्लिडियन समूह SE(2) = R है^{2</उप> $\times$ SO(2) (जहाँ SO(2) 2D घुमावों का विशेष ऑर्थोगोनल समूह है), और एक विन्यास को 3 मापदंडों (x, y, θ) का उपयोग करके दर्शाया जा सकता है।}
• यदि रोबोट एक ठोस 3D आकार है जो अनुवाद और घुमा सकता है, तो कार्यक्षेत्र 3-आयामी है, लेकिन C विशेष यूक्लिडियन समूह SE(3) = R है^{3</उप> $\times$ SO(3), और एक कॉन्फ़िगरेशन के लिए 6 पैरामीटर की आवश्यकता होती है: (x, y, z) अनुवाद के लिए, और यूलर कोण (α, β, γ)।}
• यदि रोबोट एन उल्टे जोड़ों (और कोई बंद-लूप नहीं) के साथ एक निश्चित-बेस मैनिपुलेटर है, तो सी एन-डायमेंशनल है।

मुक्त स्थान

विन्यासों का वह समुच्चय जो बाधाओं से टकराने से बचाता है मुक्त स्थान C कहलाता है_free. C का पूरक_free सी में बाधा या वर्जित क्षेत्र कहा जाता है।

अक्सर, सी के आकार की स्पष्ट रूप से गणना करना निषेधात्मक रूप से कठिन होता है_free. हालाँकि, परीक्षण करना कि क्या दिया गया कॉन्फ़िगरेशन C में है_free कुशल है। सबसे पहले, आगे कीनेमेटीक्स रोबोट की ज्यामिति की स्थिति निर्धारित करती है, और यदि रोबोट की ज्यामिति पर्यावरण की ज्यामिति से टकराती है तो टकराव का पता लगाने का परीक्षण करती है।

लक्ष्य स्थान

लक्ष्य स्थान मुक्त स्थान का एक उप-स्थान है जो दर्शाता है कि हम रोबोट को कहाँ ले जाना चाहते हैं। ग्लोबल मोशन प्लानिंग में, लक्ष्य स्थान को रोबोट के सेंसर द्वारा देखा जा सकता है। हालाँकि, स्थानीय गति नियोजन में, रोबोट कुछ राज्यों में लक्ष्य स्थान का निरीक्षण नहीं कर सकता है। इस समस्या को हल करने के लिए, रोबोट कई वर्चुअल टारगेट स्पेस से गुज़रता है, जिनमें से प्रत्येक ऑब्जर्वेबल एरिया (रोबोट के आसपास) में स्थित है। वर्चुअल टारगेट स्पेस को सब-गोल कहा जाता है।

बाधा स्थान

बाधा स्थान एक ऐसा स्थान है जहां रोबोट नहीं जा सकता। बाधा स्थान मुक्त स्थान के विपरीत नहीं है।

एल्गोरिदम

कम-आयामी समस्याओं को ग्रिड-आधारित एल्गोरिदम के साथ हल किया जा सकता है जो कॉन्फ़िगरेशन स्पेस के शीर्ष पर ग्रिड को ओवरले करता है, या ज्यामितीय एल्गोरिदम जो सी के आकार और कनेक्टिविटी की गणना करता है_free.

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

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

ग्रिड-आधारित खोज

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

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

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

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

अंतराल आधारित खोज

ये दृष्टिकोण ग्रिड-आधारित खोज दृष्टिकोणों के समान हैं, सिवाय इसके कि वे ग्रिड के बजाय पूरी तरह से कॉन्फ़िगरेशन स्थान को कवर करने वाले फ़र्श उत्पन्न करते हैं। फ़र्श को दो सबपाविंग्स X में विघटित किया जाता है⁻, एक्स⁺ ऐसे बक्सों से बनाया गया है कि X⁻ ⊂ सी_free ⊂ एक्स⁺. विशेषता सी_free एक सेट व्युत्क्रम को हल करने के बराबर है। अंतराल अंकगणित इस प्रकार इस्तेमाल किया जा सकता है जब सी_free गारंटीकृत संलग्नक होने के लिए रैखिक असमानताओं द्वारा वर्णित नहीं किया जा सकता है।

इस प्रकार रोबोट को X में स्वतंत्र रूप से चलने की अनुमति है⁻, और X से बाहर नहीं जा सकते⁺. दोनों सबपाविंग्स के लिए, एक पड़ोसी ग्राफ बनाया गया है और डायजस्ट्रा के एल्गोरिदम या एए * खोज एल्गोरिदम|ए* जैसे एल्गोरिदम का उपयोग करके पथ पाया जा सकता है। जब एक्स में एक पथ संभव है⁻, यह C में भी संभव है_free. जब X में कोई पथ मौजूद नहीं है⁺ एक प्रारंभिक कॉन्फ़िगरेशन से लक्ष्य तक, हमारे पास गारंटी है कि C में कोई व्यवहार्य पथ मौजूद नहीं है_free. ग्रिड-आधारित दृष्टिकोण के लिए, उच्च-आयामी समस्याओं के लिए अंतराल दृष्टिकोण अनुपयुक्त है, इस तथ्य के कारण कि उत्पन्न होने वाले बक्से की संख्या विन्यास स्थान के आयाम के संबंध में तेजी से बढ़ती है।

An illustration is provided by the three figures on the right where a hook with two degrees of freedom has to move from the left to the right, avoiding two horizontal small segments.

File:Graph2displaycolor.jpg

दो बाधाओं (लाल खंडों) से बचते हुए, प्रारंभिक विन्यास (नीला) से हुक के अंतिम विन्यास तक गति। हुक के बाएँ-निचले कोने को क्षैतिज रेखा पर रहना पड़ता है, जो हुक को स्वतंत्रता की दो डिग्री बनाता है।

Error creating thumbnail:

विन्यास स्थान को कवर करने वाले बक्सों के साथ अपघटन: सबपाविंग एक्स⁻ सभी लाल बक्सों और सबपाविंग X का मिलन है⁺ लाल और हरे बॉक्स का मिलन है। पथ ऊपर दर्शाई गई गति से मेल खाता है।

File:Graph3cameleon.jpg

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

निकोलस डेलानोउ ने दिखाया है कि अंतराल विश्लेषण का उपयोग करते हुए सबपाविंग्स के साथ अपघटन भी सी की टोपोलॉजी को चिह्नित करना संभव बनाता है_free जैसे कि इसके जुड़े हुए घटकों की संख्या की गणना करना।

ज्यामितीय एल्गोरिदम

बहुभुज बाधाओं के बीच रोबोटों को इंगित करें

• दृश्यता ग्राफ
• Boustrophedon सेल अपघटन

बाधाओं के बीच वस्तुओं का अनुवाद करना

• मिन्कोव्स्की योग

एक इमारत से बाहर निकलने का रास्ता ढूँढना

• सबसे दूर की किरण का निशान

वर्तमान स्थिति के चारों ओर किरणों के एक बंडल को दीवार से टकराने वाली उनकी लंबाई के साथ जिम्मेदार ठहराया जाता है, जब तक कि एक दरवाजे की पहचान नहीं हो जाती, तब तक रोबोट सबसे लंबी किरण की दिशा में चला जाता है। इस तरह के एक एल्गोरिथ्म का उपयोग इमारतों से आपातकालीन निकासी के मॉडलिंग के लिए किया गया था।

कृत्रिम संभावित क्षेत्र

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

नमूना-आधारित एल्गोरिदम

सैंपलिंग-आधारित एल्गोरिदम कॉन्फ़िगरेशन स्पेस को सैंपल कॉन्फ़िगरेशन के रोडमैप के साथ दर्शाते हैं। एक मूल एल्गोरिथ्म C में N कॉन्फ़िगरेशन का नमूना लेता है, और C में उन्हें बनाए रखता है_free मील के पत्थर के रूप में उपयोग करने के लिए। एक रोडमैप तब बनाया जाता है जो दो मील के पत्थर P और Q को जोड़ता है यदि रेखा खंड PQ पूरी तरह से C में है_free. फिर से, टकराव का पता लगाने का उपयोग सी में समावेशन का परीक्षण करने के लिए किया जाता है_free. S और G को जोड़ने वाले पथ को खोजने के लिए, उन्हें रोडमैप में जोड़ा जाता है। यदि रोडमैप में पथ एस और जी को जोड़ता है, तो योजनाकार सफल होता है और उस पथ को वापस करता है। यदि नहीं, तो कारण निश्चित नहीं है: या तो C में कोई रास्ता नहीं है_free, या योजनाकार ने पर्याप्त मील के पत्थर का नमूना नहीं लिया।

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

सी पर बुनियादी दृश्यता की स्थिति को देखते हुए_free, यह सिद्ध हो चुका है कि जैसे-जैसे विन्यास N की संख्या अधिक होती है, संभावना है कि उपरोक्त एल्गोरिथ्म एक समाधान पाता है जो घातीय रूप से 1 तक पहुंचता है। दृश्यता स्पष्ट रूप से C के आयाम पर निर्भर नहीं है; अच्छी दृश्यता वाला उच्च-आयामी स्थान या खराब दृश्यता वाला निम्न-आयामी स्थान होना संभव है। नमूना-आधारित विधियों की प्रायोगिक सफलता बताती है कि आमतौर पर देखे जाने वाले स्थानों में अच्छी दृश्यता होती है।

इस मूल योजना के कई रूप हैं:

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

उल्लेखनीय एल्गोरिदम की सूची

• ए* सर्च एल्गोरिद्म|ए*
• डी*
• तेजी से यादृच्छिक पेड़ की खोज
• संभाव्य रोडमैप

पूर्णता और प्रदर्शन

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

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

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

रिज़ॉल्यूशन पूर्णता वह संपत्ति है जिसकी योजनाकार को एक पथ खोजने की गारंटी दी जाती है यदि अंतर्निहित ग्रिड का रिज़ॉल्यूशन पर्याप्त रूप से ठीक है। अधिकांश रिज़ॉल्यूशन पूर्ण योजनाकार ग्रिड-आधारित या अंतराल-आधारित होते हैं। संकल्प पूर्ण योजनाकारों की कम्प्यूटेशनल जटिलता अंतर्निहित ग्रिड में बिंदुओं की संख्या पर निर्भर है, जो ओ (1/एच) है^d), जहां h रेजोल्यूशन (ग्रिड सेल के एक तरफ की लंबाई) है और d कॉन्फ़िगरेशन स्पेस डायमेंशन है।

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

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

समस्या प्रकार

इस बुनियादी समस्या के वेरिएंट को संभालने के लिए कई एल्गोरिदम विकसित किए गए हैं।

विभेदक बाधाएं

होलोनोमिक बाधाएं

• मैनिपुलेटर हथियार (गतिकी के साथ)

नॉनहोलोनोमिक

• ड्रोन
• कारें
• यूनीसाइकिलें
• विमान
• त्वरण बाध्य प्रणाली
• चलती बाधाएं (समय पीछे नहीं जा सकता)
• बेवल-टिप चलाने योग्य सुई
• डिफरेंशियल ड्राइव रोबोट

हाइब्रिड सिस्टम

हाइब्रिड सिस्टम वे हैं जो असतत और निरंतर व्यवहार को मिलाते हैं। ऐसी प्रणालियों के उदाहरण हैं:

• रोबोटिक्स
• विधानसभा के लिए डिजाइन
• लेग्ड रोबोट लोकोमोशन
• स्व-पुनर्गठन मॉड्यूलर रोबोटिक्स

अनिश्चितता

• मोशन अनिश्चितता
• गयाब सूचना
• सक्रिय संवेदन
• सेंसरलेस प्लानिंग
• नेटवर्क नियंत्रण प्रणाली

पर्यावरण की कमी

• गतिकी के मानचित्र

अनुप्रयोग

• रोबोट नेविगेशन
• स्वचालन
• चालक रहित कार
• रोबोटिक सर्जरी
• कंप्यूटर एनीमेशन
• प्रोटीन की तह
• कंप्यूटर एडेड वास्तुशिल्प डिजाइन में सुरक्षा और पहुंच

यह भी देखें

• जिम्बल ताला - मैकेनिकल इंजीनियरिंग में समान पारंपरिक मुद्दा
• किनोडायनामिक योजना
• पर्वतारोहण की समस्या
• OMPL - द ओपन मोशन प्लानिंग लाइब्रेरी
• पथ खोज
• कंकड़ गति की समस्या - मल्टी-रोबोट मोशन प्लानिंग
• सबसे छोटा रास्ता समस्या
• वेग बाधा

अग्रिम पठन

• Latombe, Jean-Claude (2012). Robot Motion Planning. Springer Science & Business Media. ISBN 978-1-4615-4022-9.
• Planning Algorithms, Steven M. LaValle, 2006, Cambridge University Press, ISBN 0-521-86205-1.
• Principles of Robot Motion: Theory, Algorithms, and Implementation, H. Choset, W. Burgard, S. Hutchinson, G. Kantor, L. E. Kavraki, K. Lynch, and S. Thrun, MIT Press, April 2005.
• Mark de Berg; Marc van Kreveld; Mark Overmars & Otfried Schwarzkopf (2000). Computational Geometry (2nd revised ed.). Springer-Verlag. ISBN 978-3-540-65620-3. Chapter 13: Robot Motion Planning: pp. 267–290.

बाहरी संबंध

• "Open Robotics Automation Virtual Environment", http://openrave.org/
• Jean-Claude Latombe talks about his work with robots and motion planning, 5 April 2000
• "Open Motion Planning Library (OMPL)", http://ompl.kavrakilab.org
• "Motion Strategy Library", http://msl.cs.uiuc.edu/msl/
• "Motion Planning Kit", https://ai.stanford.edu/~mitul/mpk
• "Simox", http://simox.sourceforge.net
• "Robot Motion Planning and Control", http://www.laas.fr/%7Ejpl/book.html