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

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

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

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

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

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

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