Multi-Objective Kinodynamic Motion Planning with Asymptotic Pareto Optimality

कल्पना कीजिए कि आप एक रोबोट को भूलभुलैया (maze) में नेविगेट करने के लिए प्रोग्राम कर रहे हैं। पुराने दिनों में, इंजीनियर रोबोट को एक ही लक्ष्य देते थे: "जितनी जल्दी हो सके निकास तक पहुँचो।" रोबोट सबसे छोटा रास्ता निकाल लेता था, बाकी सब कुछ अनदेखा करते हुए। लेकिन वास्तविक जीवन अव्यवस्थित है। एक सेल्फ-ड्राइविंग कार केवल तेज़ नहीं होना चाहती; वह सुरक्षित, आरामदायक और ऊर्जा-कुशल भी होना चाहती है। एक डिलीवरी ड्रोन को बैटरी जीवन और पक्षी से टकराने के जोखिम के बीच संतुलन बनाना पड़ सकता है। जब एक रोबोट को कई, अक्सर परस्पर विरोधी लक्ष्यों के बीच सामंजस्य बिठाना होता है, तो वह केवल एक "सर्वश्रेष्ठ" पथ नहीं चुन सकता। इसके बजाय, उसे "सर्वश्रेष्ठ समझौतों" का एक पूरा मेनू खोजना होता है। यह मल्टी-ऑब्जेक्टिव मोशन प्लानिंग की दुनिया है।

इस चुनौती को समझने के लिए, रोबोट के पथ को मानचित्र पर खींची गई एक रेखा के रूप में सोचें। रोबोट के पास कुछ नियम हैं जिनका उसे पालन करना होगा, जैसे दीवारों (बाधाओं) के माध्यम से न जाना और भौतिकी के नियमों का पालन करना (यदि वह बहुत तेज़ गति से चल रहा है, तो वह तुरंत मुड़ नहीं सकता)। इन नियमों को "काइनोडायनामिक बाधाएं" (kinodynamic constraints) कहा जाता है। जब आप कई लक्ष्य जोड़ते हैं—जैसे "समय कम करें" और "सुरक्षा बढ़ाएं"—तो आप अब किसी एक विजेता की तलाश नहीं कर रहे हैं। आप एक "पारेटो फ्रंट" (Pareto front) की तलाश कर रहे हैं, जो एक फैंसी तरीका है यह कहने का कि विकल्पों का एक ऐसा संग्रह जहाँ आप एक लक्ष्य को बेहतर बनाने के लिए दूसरे को खराब किए बिना कुछ नहीं कर सकते। यह एक ऐसे मेनू की तरह है जहाँ हर व्यंजन तीखे और मीठे का एक आदर्श संतुलन है; आप इसे अधिक तीखा बनाए बिना मिठास को कम किए बिना नहीं बना सकते।

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

लक्ष्यों को "मिश्रित" करने की समस्या

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

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

नया दृष्टिकोण: खोजकर्ताओं की एक टीम

लेखकों का समाधान एक मौजूदा एल्गोरिदम पर आधारित है जिसे SST (स्टेबल स्पार्स-आरआरटी) कहा जाता है, जो एक रोबोट की तरह है जो मानचित्र पर डार्ट फेंककर रास्ता खोजता है। आमतौर पर, SST मानचित्र के प्रत्येक छोटे क्षेत्र में केवल एक "सर्वश्रेष्ठ" पथ रखता है। यदि कोई नया पथ थोड़ा बेहतर है, तो यह पुराने को बदल देता है।

लेखकों ने महसूस किया कि कई लक्ष्यों के लिए, केवल एक पथ रखना एक मेनू में केवल एक व्यंजन को देखने जैसा है। इसके बजाय, उन्होंने एल्गोरिदम को प्रत्येक क्षेत्र में एक टीम रखने के लिए बदल दिया। उनके नए ढांचे में, जब भी रोबोट एक पड़ोस (neighborhood) को एक्सप्लोर करता है, तो वह केवल एक विजेता नहीं चुनता; बल्कि वह "स्थानीय रूप से पारेटो-इष्टतम" (locally Pareto-optimal) पथों का एक छोटा समूह रखता है। ये ऐसे पथ हैं जो इतने अच्छे हैं कि आप एक को बेहतर बनाने के लिए दूसरे को नुकसान पहुँचाए बिना नहीं कर सकते।

यह एकल परिवर्तन उन्हें तीन अलग-अलग विशिष्ट रोबोट बनाने की अनुमति देता है, जो सभी एक ही मूल विचार पर आधारित हैं:

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

2. COSST (नियम का पालन करने वाला): यह रोबोट उन स्थितियों को संभालता है जहाँ आपके पास कठिन सीमाएँ होती हैं (जैसे, "गति 50 मील प्रति घंटे से कम होनी चाहिए, लेकिन ईंधन कम से कम करें")। पेपर दिखाता है कि पुराना SST तरीका यहाँ अक्सर विफल हो जाता है क्योंकि यह एक ऐसा पथ चुन सकता है जो तेज़ है लेकिन मुश्किल से गति सीमा के भीतर है, जिससे अचानक बाधा के चारों ओर घूमने के लिए जगह नहीं बचती। COSST उन सभी पथों को रखता है जो नियमों के भीतर रहते हैं, यह सुनिश्चित करता है कि रोबोट गलती से किसी डेड एंड (बंद रास्ते) में न फंस जाए क्योंकि वह बहुत अधिक तेज़ होने पर ध्यान केंद्रित कर रहा था।

3. POSST (मेनू निर्माता): यह सबसे महत्वाकांक्षी रोबोट है। इसका काम "सर्वश्रेष्ठ समझौतों के पूरे मेनू" को खोजना है। एक विजेता चुनने के बजाय, यह पूरे "पारेटो फ्रंट" का मानचित्र बनाता है। यह रोबोट (और मानव डिजाइनर) को हर संभव ट्रेड-ऑफ दिखाता है: "यहाँ एक पथ है जो बहुत तेज़ है लेकिन जोखिम भरा है, यहाँ एक है जो बहुत सुरक्षित है लेकिन धीमा है, और यहाँ बीच के सभी आदर्श संतुलन हैं।"

उन्होंने क्या पाया

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

परिणाम स्पष्ट थे। "कठोर बॉस" परिदृश्य में, पुराने तरीकों ने या तो बहुत जोखिम भरे या बहुत धीमे पथ उत्पन्न किए, जो इस बात पर निर्भर था कि इंजीनियरों ने गणित को कैसे ट्यून किया। LEXSST ने लगातार उन पथों को खोजा जो प्राथमिकता क्रम का पूरी तरह से सम्मान करते थे। "नियम का पालन करने वाले" परिदृश्य में, पुराना तरीका एक कठिन संकीर्ण-मार्ग परीक्षण में 93% रन में विफल रहा, जबकि COSST 100% समय सफल रहा। ऐसा इसलिए हुआ क्योंकि पुराना तरीका बहुत लालची था, एक ऐसा पथ चुन रहा था जो शुरू में अच्छा दिखता था लेकिन काम पूरा नहीं कर सका, जबकि COSST ने पर्याप्त विकल्प खुले रखे ताकि रास्ता मिल सके।

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

निष्कर्ष

यह शोध पत्र केवल एक मामूली बदलाव का सुझाव नहीं देता है; यह इस बारे में सोचने का एक नया तरीका प्रदान करता है कि जब रोबोटों के पास कई, प्रतिस्पर्धी लक्ष्य होते हैं तो वे निर्णय कैसे लेते हैं। यह सिद्ध करके कि सरल गणितीय मिश्रण कुछ समस्याओं के लिए विफल हो जाता है और एक "विजेता" के बजाय एक "टीम" रखने की विधि पेश करके, लेखकों ने एक ऐसा टूलकिट बनाया है जो अधिक विश्वसनीय और कुशल है।

उनका कार्य गणितीय प्रमाणों द्वारा समर्थित है जो गारंटी देते हैं कि रोबोट समाधान खोज लेंगे यदि वे मौजूद हैं (पूर्णता/completeness) और समाधान सर्वोत्तम संभव समाधानों के बहुत करीब होंगे (निकट-इष्टतमता/near-optimality)। हालाँकि पेपर नोट करता है कि कुछ चुनौतियाँ बनी हुई हैं—जैसे कि "कठोर बॉस" परिदृश्य में दो से अधिक लक्ष्यों को कैसे संभालें—उनके नए एल्गोरिदम, LEXSST, COSST और POSST, अगली पीढ़ी के बुद्धिमान, बहु-लक्ष्य रोबोटों के लिए एक मजबूत आधार प्रदान करते हैं। वे दिखाते हैं कि कभी-कभी, सबसे अच्छा पथ खोजने के लिए, आपको एक एकल विजेता की तलाश करना बंद करना होगा और पूरी टीम की सराहना करना शुरू करना होगा।