Parallel Branch Model Predictive Control on GPUs

तकनीकी सारांश: GPU पर पैरेलल ब्रांच मॉडल प्रेडिक्टिव कंट्रोल

समस्या विवरण
ब्रांच मॉडल प्रेडिक्टिव कंट्रोल (BMPC) गतिशील वातावरण (जैसे कि ऑटोमेटेड ड्राइविंग) में अनिश्चितता को संभालने के लिए एक शक्तिशाली प्लानिंग फ्रेमवर्क है, जो ऐसे ट्रैजेक्टरी ट्री (trajectory trees) उत्पन्न करता है जहाँ शाखाएँ (branches) विभिन्न अनिश्चितता वास्तविकताओं (uncertainty realizations) के अनुरूप होती हैं। हालाँकि, BMPC का व्यापक प्रसार लंबी प्लानिंग होराइजन और अनेक अनुमानित परिदृश्यों (scenarios) को संभालने की आवश्यकता के कारण होने वाले महत्वपूर्ण कम्प्यूटेशनल बोझ से बाधित है। मौजूदा सॉल्वर अक्सर इन समस्याओं को कुशलतापूर्वक हल करने के लिए अंतर्निहित ट्री संरचना का लाभ उठाने में संघर्ष करते हैं या टेम्पोरल पैरेललिज्म (temporal parallelism) प्राप्त करने में विफल रहते हैं, जिससे वास्तविक समय के अनुप्रयोगों के लिए उनकी उपयुक्तता सीमित हो जाती है। इसके अलावा, पैरेलल हार्डवेयर पर ट्री-स्ट्रक्चर्ड ऑप्टिमल कंट्रोल फ्रेमवर्क के भीतर सामान्य स्टेज-वाइज़ बाधाओं (stage-wise constraints) को संभालना एक चुनौती बनी हुई है।

कार्यप्रणाली (Methodology)
लेखक BMPC के लिए एक GPU-आधारित सॉल्वर का प्रस्ताव करते हैं जो बाधा प्रबंधन (constraint handling) के लिए एक ऑगमेंटेड लैग्रेंजियन (AL) पद्धति के साथ मल्टीपल-शूटिंग फॉर्मूलेशन को एकीकृत करता है। इस दृष्टिकोण का मुख्य आधार दो अनुकूलित इनर लीनियर क्वाड्रेटिक रेगुलेटर (LQR) सॉल्वर हैं जिन्हें ट्री-स्पार्स संरचना का लाभ उठाने के लिए डिज़ाइन किया गया है:

1. पैरेलल ट्री LQR सॉल्वर्स:

   • SLQR (सीनैरियो-लेवल पैरेललिजेशन): यह सॉल्वर लीफ नोड्स से रूट की ओर एक संशोधित रिकाटियन रिकर्सन (Riccate recursion) करता है। यह प्रत्येक स्टेज पर चाइल्ड नोड्स से वैल्यू फंक्शन्स को एकत्रित करता है, जिससे प्रत्येक नोड पर स्वतंत्र मिनिमाइजेशन समस्याओं को समानांतर (parallel) रूप से हल किया जा सकता है। यह दृष्टिकोण कम GPU संसाधनों की मांग करता है और उन परिदृश्यों के लिए उपयुक्त है जहाँ संसाधन सीमित हैं।
   • STLQR (सीनैरियो और टेम्पोरल पैरेललिजेशन): यह सॉल्वर बैकवर्ड (रिकाटियन) और फॉरवर्ड (रोलआउट) दोनों पास में पैरेलल स्कैन एल्गोरिदम का उपयोग करके सीनैरियो-लेवल और टेम्पोरल पैरेललिज्म दोनों का लाभ उठाता है। यह वैल्यू फंक्शन्स और एफ़ाइन कंट्रोल लॉ (affine control laws) की गणना करने के लिए $O(\log N)$ समय जटिलता के साथ कंडीशनल वैल्यू फंक्शन्स (CVFs) और एक ट्री-स्ट्रक्चर्ड कॉम्बिनेशन रूल का उपयोग करता है। यह विधि उच्च पैरेललिज्म प्रदान करती है लेकिन अधिक GPU संसाधनों की मांग करती है।

2. ऑगमेंटेड लैग्रेंजियन के माध्यम से बाधा प्रबंधन:
   सामान्य स्टेज-वाइज़ बाधाओं को संबोधित करने के लिए, लेखक एक ऑगमेंटेड लैग्रेंजियन (AL) पद्धति का उपयोग करते हैं। इनर लूप एक इटरेटिव LQR (iLQR) दृष्टिकोण का उपयोग करता है जहाँ कंस्ट्रेंड समस्या को पॉवेल-हेस्टनेस-रोकफेलर (PHR) पेनल्टी फंक्शन का उपयोग करके एक अनकंस्ट्रेंड ट्री LQR समस्या के रूप में अनुमानित किया जाता है। अनुकूलित परिवर्तनों (optimal perturbations) की गणना के लिए एक लीनियर रोलआउट का उपयोग किया जाता है, जो GPU पर कुशल पैरेललिजेशन को सक्षम बनाता है। आउटर लूप बाधा उल्लंघन के आधार पर लैग्रेंज मल्टीप्लायर्स और पेनल्टी वेट्स को एडैप्टिवली अपडेट करता है, जो BCL नियम का पालन करता है।

3. कार्यान्वयन (Implementation):
   सॉल्वर को JAX में लागू किया गया है, जो इसके ऑटोमैटिक डिफरेंशिएशन और GPU एक्सेलेरेशन के लिए इसके XLA कंपाइलर का उपयोग करता है। यह फ्रेमवर्क सिंगल-प्रिसिजन (FP32) और डबल-प्रिसिजन (FP64) अंकगणित दोनों का समर्थन करता है।

मुख्य योगदान
यह शोध पत्र तीन प्राथमिक योगदानों को रेखांकित करता है:

1. दोहरे पैरेलल सॉल्वर्स: दो पैरेलल ट्री LQR सॉल्वर्स (SLQR और STLQR) का विकास जो विभिन्न स्तरों का पैरेललिज्म प्रदान करते हैं, जिससे उपयोगकर्ताओं को समस्या के आकार और उपलब्ध कम्प्यूटेशनल संसाधनों के आधार पर उपयुक्त विधि चुनने की अनुमति मिलती है।
2. कंस्ट्रेंड नॉनलीन BMPC सॉल्वर: इन ट्री LQR सॉल्वर्स को नॉनलीन BMPC समस्याओं के लिए एक मल्टीपल-शूटिंग इटरेटिव सॉल्वर में एकीकृत करना, जिसमें मजबूत बाधा प्रबंधन और वॉर्म-स्टार्टिंग क्षमताओं के लिए एक ऑगमेंटेड लैग्रेंजियन पद्धति शामिल है।
3. बेंचमार्किंग और ओपन सोर्स: मौजूदा iLQR सॉल्वर्स (TRAJAX, MPX) और एक उच्च-प्रदर्शन वाले CPU-आधारित सॉल्वर (HPIPM) के विरुद्ध प्रस्तावित सॉल्वर का एक व्यापक बेंचमार्किंग, साथ ही एक ओपन-सोर्स कार्यान्वयन का विमोचन।

संख्यात्मक परिणाम (Numerical Results)
लेखकों ने दो अलग-अलग कार्यों पर अपने सॉल्वर का मूल्यांकन किया: अनकंस्ट्रेंड ट्री LQR समस्याएँ और एक यूनिसाइकिल (unicycle) तथा क्वाड-पेंडुलम (quad-pendulum) के लिए कंस्ट्रेंड ट्रैजेक्टरी प्लानिंग।

• Tree LQR पर प्रदर्शन: GPU-आधारित सॉल्वर्स का प्रदर्शन समस्या के आकार और हार्डवेयर पर अत्यधिक निर्भर है। छोटे समस्या आकार (जैसे, $Z = 2$ ट्री पाथ) के लिए, सॉल्वर्स CPU-आधारित HPIPM सॉल्वर की तुलना में काफी धीमे हैं, जहाँ NVIDIA RTX 5060 Ti पर STLQR 5$\times$ से अधिक और SLQR 20$\times$ से अधिक धीमा है, जिसका कारण GPU मेमोरी-एक्सेस लेटेंसी और ओवरहेड है। हालाँकि, बड़े पैमाने के इंस्टेंस में, प्रदर्शन उलट जाता है: SLQR बड़े पैमाने के इंस्टेंस ($Z \ge 128$) के लिए RTX 5060 Ti पर HPIPM से 2$\times$ तक बेहतर प्रदर्शन कर सकता है। इसी तरह, RTX 4090 जैसे हाई-एंड GPUs पर, STLQR मध्यम-से-बड़े ट्री साइज ($Z \ge 16$) के लिए HPIPM पर 1.9$\times$ तक की गति वृद्धि (speedup) प्राप्त करता है।
• बाधा प्रबंधन (Constraint Handling): ट्रैजेक्टरी प्लानिंग कार्यों में, प्रस्तावित सॉल्वर (ILQLJAX) ने अत्याधुनिक CPU सॉल्वर IPOPT के समान अभिसरण व्यवहार (convergence behavior) प्रदर्शित किया, लेकिन काफी कम प्रति-इटरेशन कंप्यूटेशन समय के साथ (उदाहरण के लिए, यूनिसाइकिल के लिए औसत इटरेशन समय को 3.80 ms से घटाकर 1.87 ms करना)। सॉल्वर ने सभी टेस्ट इंस्टेंस को सफलतापूर्वक संभाला, जबकि अन्य GPU-आधारित सॉल्वर (TRAJAX, MPX) चुनौतीपूर्ण इंस्टेंस के साथ संघर्ष करते रहे, जो अक्सर फॉर्मूलेशन सीमाओं या एडैप्टिव अपडेट स्कीम्स की कमी के कारण अभिसरण करने में विफल रहे।

महत्व और दावे
यह शोध पत्र दावा करता है कि प्रस्तावित दृष्टिकोण GPU पर पैरेलल एल्गोरिदम के माध्यम से ट्री संरचना का पूरी तरह से लाभ उठाकर बड़े पैमाने की समस्याओं के लिए रियल-टाइम BMPC की ओर एक व्यवहार्य मार्ग प्रदान करता है। लेखक इस बात पर जोर देते हैं कि उनकी विधि विशेष रूप से उन बड़े पैमाने के इंस्टेंस में उच्च-प्रदर्शन वाले CPU-आधारित सॉल्वर्स की तुलना में बेहतर प्रदर्शन करती है जहाँ ट्री संरचना को प्रभावी ढंग से पैरेलल किया जा सकता है। वे यह भी स्वीकार करते हैं कि पैरेलल स्कैन-आधारित सॉल्वर की उच्च GPU संसाधन मांग होती है, जो संसाधनों के संतृप्त होने पर स्केलेबिलिटी को सीमित कर सकती है, और छोटे समस्या आकार के लिए, CPU-आधारित सॉल्वर अभी भी बेहतर प्रदर्शन कर सकते हैं। यह कार्य कम्प्यूटेशनल दक्षता को बाधाओं और अनिश्चितता के कठोर प्रबंधन के साथ संतुलित करके, जटिल, वास्तविक दुनिया के अनुप्रयोगों के लिए अनिश्चितता-जागरूक (uncertainty-aware) प्लानिंग को संभव बनाने की दिशा में एक कदम है। भविष्य के कार्य के रूप में संसाधन उपयोग को और अधिक अनुकूलित करने के लिए विधि को CUDA C++ में लागू करना और FP32-अनुकूलित हार्डवेयर पर संख्यात्मक स्थिरता में सुधार के लिए मिश्रित-परिशुद्धता (mixed-precision) अंकगणित का पता लगाना पहचाना गया है।