संभाव्य रोडमैप

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

कई बहुभुज बाधाओं के आसपास संभावित पथों की खोज करने वाले संभाव्य यादृच्छिक मानचित्र एल्गोरिदम का एक उदाहरण।

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

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

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

पीआरएम पद्धति के आविष्कार का श्रेय लिडिया कावराकी|लिडिया ई. कावराकी को दिया जाता है। बुनियादी पीआरएम पद्धति के कई प्रकार हैं, कुछ काफी परिष्कृत हैं, जो तेज प्रदर्शन प्राप्त करने के लिए नमूनाकरण रणनीति और कनेक्शन रणनीति को बदलते हैं। उदाहरण देखें Geraerts & Overmars (2002) चर्चा के लिए.