नियंत्रण अभियांत्रिकी का परिचय: पथ नियोजन — A*, डाइक्स्ट्रा, RRT, RRT*, और PRM

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

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

व्यावहारिक निष्कर्ष

• डाइक्स्ट्रा एक गैर-ऋणात्मक भारित ग्राफ पर सबसे छोटे पथ की गारंटी देता है, लेकिन लक्ष्य से असंबंधित दिशाओं में विस्तार करता है। A* समान इष्टतमता को बनाए रखते हुए एक स्वीकार्य अनुमानी विधि के साथ विस्तार को निर्देशित करता है।

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

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

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

एल्गोरिदम चुनने से पहले मुक्त स्थान परिभाषित करें

मान लीजिए कि स्टेट स्पेस \mathcal X है, ऑब्स्टैकल स्पेस \mathcal X_{obs} है, और मुक्त स्थान \mathcal X_{free}=\mathcal X\setminus\mathcal X_{obs} है। एक पथ \sigma:[0,1]\to\mathcal X_{free}, x_s को x_g से जोड़ता है, जिसमें \sigma(0)=x_s,\sigma(1)=x_g भी शामिल है। 2D में एक पॉइंट रोबोट x=(x,y) का उपयोग करता है; एक वाहन हेडिंग \theta, गति और स्टीयरिंग जोड़ता है; एक मैनिपुलेटर सभी संयुक्त कोणों को शामिल करता है। स्टेट को सरल बनाने से खोज लागत कम हो जाती है, लेकिन इससे ऐसे वक्र बन सकते हैं जिन्हें अनुगामी वाहन प्राप्त नहीं कर सकता।

ऑब्स्टैकल इन्फ्लेशन, बाधाओं का विस्तार करके एक परिमित रोबोट को पॉइंट सर्च में बदल देता है। यहाँ r_{loc} एक निर्दिष्ट अनिश्चितता पद होना चाहिए, जैसे कि एक परिभाषित आत्मविश्वास स्तर के लिए चुनी गई त्रिज्या, न कि एक अनिर्दिष्ट औसत त्रुटि। एक सैद्धांतिक न्यूनतम मान है:

जहाँ r_{robot} पिंड की त्रिज्या है, स्थान निर्धारण अनिश्चितता को पूर्ववर्ती पद द्वारा दर्शाया गया है, और r_{safe} ट्रैकिंग/रोकने का मार्जिन है। वास्तविकता में, मार्जिन मानचित्र रिज़ॉल्यूशन, सेंसर के ब्लाइंड स्पॉट, निकट आ रही वस्तु की गति और ब्रेकिंग क्षमता के साथ बदलता रहता है। बहुत कम मार्जिन होने पर टक्कर हो जाती है; बहुत अधिक मार्जिन होने पर मार्ग असंभव हो जाता है।

आरेख: डस्ककॉइल, मापन के बजाय अवधारणात्मक। सेल का आकार और फुलाव वास्तविक रोबोट फुटप्रिंट, अनिश्चितता और ऑपरेटिंग एनवेलप से प्राप्त किए जाने चाहिए।

ग्रिड खोज: डाइक्स्ट्रा और A*

ग्राफ के लिए G=(V,E) विधि में, गैर-ऋणात्मक किनारे की लागत c(u,v)\ge0 के साथ, डाइक्स्ट्रा विधि में सबसे कम ज्ञात प्रारंभिक लागत g(n) वाले अस्थाई नोड को बार-बार स्थिर किया जाता है और पड़ोसियों को शिथिल किया जाता है। एक बार स्थिर हो जाने पर, इसका g मान सबसे छोटा होता है। बाइनरी हीप के साथ, प्रतिनिधि जटिलता O((|V|+|E|)\log|V|) है। यह सबसे छोटी ग्राफ दूरी की गारंटी देता है, लेकिन लक्ष्य ज्ञान के बिना, व्यापक रूप से विस्तार करने की प्रवृत्ति रखता है।

A* नोड्स को इस प्रकार क्रमबद्ध करता है:

जहाँ h(n) शेष लागत पर एक निचली सीमा है। एक स्वीकार्य अनुमान विधि कभी भी वास्तविक शेष लागत का अधिक अनुमान नहीं लगाती; तब A* इष्टतम बना रहता है। मैनहट्टन दूरी 4-कनेक्टेड ग्रिड के लिए उपयुक्त है, जबकि यूक्लिडियन या चेबीशेव-संबंधित दूरी 8-कनेक्टेड गति के लिए उपयुक्त हो सकती है। एक सुसंगत अनुमान विधि h(n)\le c(n,n')+h(n') को भी संतुष्ट करती है और इसे कम करती है। पुनः विस्तार।

भारित A* इष्टतमता की कीमत पर व्यवहार्य मार्ग को तेजी से खोजने के लिए w>1 द्वारा अनुमानी विधि को स्केल करता है। यदि यह स्पष्ट हो तो यह एक उचित परिचालन समझौता हो सकता है। किनारे की लागत न केवल लंबाई बल्कि बढ़ी हुई बाधा जोखिम, क्लीयरेंस, मोड़, ऊर्जा या भूभाग को भी एन्कोड कर सकती है। आउटपुट न्यूनतम परिभाषित लागत है, न कि न्यूनतम ज्यामितीय लंबाई।

सतत और उच्च-आयामी स्थान: RRT, RRT*, PRM

छह-जोड़ वाले भुजा विन्यास स्थान या वाहन स्थिति स्थान में महीन ग्रिड फैल जाते हैं। RRT मुक्त स्थान से x_{rand} का नमूना लेता है, निकटतम वृक्ष नोड x_{near} का पता लगाता है, उसकी ओर सीमित दूरी तक स्टीयरिंग करता है, टक्कर की जाँच करता है और x_{new} जोड़ता है। यह संभाव्यता की दृष्टि से पूर्ण है: पर्याप्त नमूनों के साथ, व्यवहार्य मार्ग खोजने की संभावना एक के करीब पहुँच जाती है जब ऐसा कोई मार्ग मौजूद होता है। यह एक छोटे पहले मार्ग की गारंटी नहीं देता है।

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

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

आरेख: डस्ककॉइल, सरलीकृत। सैंपलिंग, टकराव जाँच और कनेक्टिविटी प्रदर्शन माप या अंतिम उत्पादन मार्ग नहीं हैं।

पीआरएम | प्रीप्रोसेसिंग प्लस क्वेरी | सैंपलिंग शर्तों के साथ संभाव्यता के अनुसार पूर्ण | स्थैतिक दोहराए गए प्रश्न | गतिशील स्थान में बासी किनारे |

SLAM, Nav2 और स्थानीय नियोजन

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

Nav2 जैसी ROS 2 वास्तुकला में, एक वैश्विक लागत मानचित्र और प्लानर एक बड़े पैमाने का मार्ग चुनते हैं, जबकि एक स्थानीय लागत मानचित्र और नियंत्रक आस-पास की बाधाओं और वेग को संभालते हैं। एक वैश्विक A* एक गलियारा चुन सकता है; स्थानीय परत को किसी व्यक्ति के चारों ओर से रास्ता छोड़ना, रुकना या चक्कर लगाना होगा। एक विशुद्ध रूप से स्थानीय परत एक बंद गली में फंस सकती है। प्लानर, नियंत्रक, पुनर्प्राप्ति, मानचित्र-अद्यतन दरें, समयसीमा और प्राथमिकताओं को स्पष्ट रूप से परिभाषित करें। ROS 2 प्राइमर में वर्णित ROS 2 परिवहन वास्तविक समय या सुरक्षा की गारंटी नहीं देता है।

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

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

कार्यान्वयन चेकलिस्ट और सुरक्षा

1. स्टेट स्पेस, फुटप्रिंट, फ्रेम्स, मैप रिज़ॉल्यूशन और अज्ञात सेल्स का अर्थ परिभाषित करें।

2. इन्फ्लेशन में स्थानीयकरण त्रुटि, गति और स्टॉपिंग दूरी को शामिल करें; वास्तविक संकरे रास्तों का परीक्षण करें।

3. ह्यूरिस्टिक की स्वीकार्यता सत्यापित करें या जानबूझकर शिथिल की गई गारंटी को दस्तावेज़ित करें।

4. सैंपलिंग प्लानर्स के लिए कोलिजन-चेक रिज़ॉल्यूशन, रैंडम सीड, डेडलाइन और नो-सॉल्यूशन व्यवहार को रिकॉर्ड करें।

5. रिलोकेलाइज़ेशन, मैप परिवर्तन, सेंसर ड्रॉपआउट, गतिशील बाधाएं और संचार विलंब को शामिल करें।

6. नो-रूट, स्टेल-मैप और ट्रैकिंग-डेविएशन घटनाओं के लिए एक सुरक्षित स्टॉप और निदान योग्य लॉग पथ सत्यापित करें।

संदर्भ

• हार्ट, निलसन, राफेल, 1968: ए* के लिए एक औपचारिक आधार
• लावेल: रैपिडली-एक्सप्लोरिंग रैंडम ट्रीज़
• करमन और फ्राज़ोली, 2011: आरआरटी*
• Nav2 प्रलेखन