MixedComplementarityProblems.jl: A Fast, Batched, Open-Source Interior Point Solver for Mixed Complementarity Problems
यह शोध पत्र MixedComplementarityProblems.jl को प्रस्तुत करता है, जो मिश्रित पूरकता समस्याओं (mixed complementarity problems) के लिए एक ओपन-सोर्स जूलिया (Julia) सॉल्वर है, जो क्लोज्ड-सोर्स PATH सॉल्वर की विश्वसनीयता से मेल खाता है और साथ ही CPU एवं GPU पर बैच किए गए, समानांतर प्रसंस्करण (parallel processing) के नेटिव सपोर्ट और कुशल ऑटोमैटिक डिफरेंशिएशन (automatic differentiation) के माध्यम से काफी तेज़ प्रदर्शन प्रदान करता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
एक ऐसी दुनिया की कल्पना करें जहाँ रोबोट, सेल्फ-ड्राइविंग कारें और ड्रोन केवल एक स्क्रिप्ट का पालन नहीं करते, बल्कि आपस में टकराने से बचने के लिए एक उच्च-दांव वाला शतरंज का खेल खेलते हैं। यह मल्टी-एजेंट रोबोटिक्स का क्षेत्र है, जहाँ हर रोबोट एक खिलाड़ी है जो दूसरों से टकराने से बचते हुए अपनी खुद की दौड़ जीतने की कोशिश कर रहा है। इन निर्णयों को वास्तविक समय (real-time) में लेने के लिए, इंजीनियर एक गणितीय उपकरण का उपयोग करते हैं जिसे "मिक्स्ड कॉम्प्लीमेंटैरिटी प्रॉब्लम" (Mixed Complementarity Problem - MCP) कहा जाता है। एक MCP को एक विशाल, जटिल नियम पुस्तिका के रूप में सोचें जो बिल्कुल यह बताती है कि प्रत्येक खिलाड़ी को कैसे कार्य करना चाहिए ताकि एक पूर्ण संतुलन तक पहुँचा जा सके जहाँ कोई भी अकेले अपना अगला कदम बदलकर अपनी स्थिति में सुधार नहीं कर सकता। वर्षों तक, इस नियम पुस्तिका को पढ़ने का एकमात्र तरीका PATH नामक एक बहुत ही शक्तिशाली, लेकिन बंद-दरवाजे वाला सॉफ़्टवेयर था। यह ऐसा था जैसे आपके पास एक मास्टर शेफ हो जो एक आदर्श भोजन बना सकता है, लेकिन आपको रेसिपी देखने की अनुमति नहीं थी, आप सामग्री को बदल नहीं सकते थे, और आपको अगला खाना शुरू करने से पहले एक समय में केवल एक ही भोजन पकने का इंतज़ार करना पड़ता था।
अब, एक नई टीम के शोधकर्ताओं ने एक नया, ओपन-सोर्स किचन बनाया है जिसे MixedComplementarityProblems.jl कहा जाता है। एक समय में एक भोजन बनाने के बजाय, उन्होंने यह पता लगा लिया है कि कैसे सैकड़ों भोजन एक साथ बनाए जा सकते हैं, चाहे वे एक मानक चूल्हे (कंप्यूटर का CPU) का उपयोग कर रहे हों या एक सुपर-फास्ट इंडस्ट्रियल ओवन (ग्राफिक्स कार्ड या GPU) का। उनकी बड़ी खोज क्या है? बैचों में खाना बनाकर, वे इन जटिल रोबोट खेलों को पुराने तरीके की तुलना में लगभग 100 गुना तेज़ी से हल कर सकते हैं, और वे इसे विशेष, महंगे हार्डवेयर की आवश्यकता के बिना सामान्य कंप्यूटरों पर भी कर सकते हैं। उन्होंने इसे भी संभव बना दिया है कि वे चलते-फिरते रेसिपी में बदलाव कर सकें, जो रोबोट को उनकी गलतियों से सीखने में मदद करने के लिए महत्वपूर्ण है।
समस्या: रोबोट का ट्रैफिक जाम
रोबोटिक्स की दुनिया में, चीजें तब जटिल हो जाती हैं जब कई एजेंट—जैसे हाईवे पर कारें या गोदाम में ड्रोन—एक ही समय में चलने की कोशिश करते हैं। प्रत्येक एजेंट अपने गंतव्य तक जितनी जल्दी हो सके पहुँचना चाहता है, लेकिन उन्हें सड़क के नियमों का सम्मान करना होता है और एक-दूसरे से टकराने से बचना होता है। गणितीय रूप से, यह एक "नॉनकोऑपरेटिव गेम" (noncooperative game) है। इस खेल का समाधान चालों का एक विशिष्ट सेट है जहाँ हर कोई अपने पथ से खुश होता है, बशर्ते वह दूसरों के कार्यों को ध्यान में रखे।
इस समाधान को खोजने के लिए, रोबोट्स को एक मिक्स्ड कॉम्प्लीमेंटैरिटी प्रॉब्लम (MCP) को हल करने की आवश्यकता होती है। आप एक MCP को समीकरणों की एक विशाल, उलझी हुई गांठ के रूप में देख सकते हैं। गांठ के कुछ हिस्से कहते हैं, "यदि आप लेन के बीच में हैं, तो आपकी गति शून्य होनी चाहिए।" अन्य भाग कहते हैं, "यदि आप दीवार से टकराते हैं, तो आपको रुकना होगा।" जब आप इसमें एक "पैरामीटर" जोड़ते हैं, जैसे कार की शुरुआती स्थिति बदलना या गति सीमा बदलना, तो यह गांठ और भी जटिल हो जाती है। रोब 받았 में, आपको विभिन्न परिदृश्यों (जैसे, "क्या होगा यदि कार यहाँ से शुरू होती है? क्या होगा यदि वह वहाँ से शुरू होती है?") की योजना बनाने के लिए एक साथ हजारों इन गांठों को हल करने की आवश्यकता होती है।
लंबे समय तक, इन गांठों को सुलझाने के लिए उद्योग का मानक PATH नामक एक प्रोग्राम था। यह विश्वसनीय और मजबूत है, लेकिन इसमें तीन बड़े दोष हैं:
- यह क्लोज्ड-सोर्स है, जिसका अर्थ है कि डेवलपर्स इसे ठीक करने या अपने विशिष्ट रोबोट के लिए अनुकूलित करने के लिए इसके अंदर झाँक नहीं सकते।
- यह समस्याओं को एक-एक करके हल करता है। यदि आपके पास 1,000 परिदृश्य हैं, तो यह उन्हें क्रमिक रूप से करता है, जिसमें बहुत समय लगता है।
- यह मशीन लर्निंग के साथ अच्छी तरह से काम नहीं करता है। आधुनिक AI को अक्सर यह जानने की आवश्यकता होती है कि यदि आप इनपुट को थोड़ा बदलते हैं तो समाधान कैसे बदलता है (जिसे डिफरेंशिएशन कहा जाता है), लेकिन PATH इसे बहुत कठिन बना देता है।
समाधान: बैच वाला किचन
इस पेपर के लेखक, जिन्होंने MixedComplementarityProblems.jl बनाया है, एक पूरी तरह से जूलिया (Julia) प्रोग्रामिंग भाषा में लिखा गया नया सॉल्वर है। उनका दृष्टिकोण एक समय में एक व्यंजन बनाने वाले एकल शेफ से लेकर एक विशाल किचन ब्रिगेड तक अपग्रेड करने जैसा है जो एक साथ पूरा भोज तैयार कर सकती है।
यहाँ उन्होंने यह किया है:
1. "बैच" का जादू
एक रोबोट गेम को हल करने के बाद, फिर दूसरा, फिर तीसरा करने के बजाय, नया सॉल्वर खेलों का एक पूरा "बैच" लेता है—मान लीजिए, 1,024 अलग-अलग ट्रैफिक परिदृश्य—और उन सभी को एक साथ हल करता है।
- CPU (कंप्यूटर प्रोसेसर) पर: वे कंप्यूटर के कई कोर का उपयोग करते हैं (जैसे समानांतर में काम करने वाले 32 शेफ होना)।
- GPU (ग्राफिक्स कार्ड) पर: वे ग्राफिक्स कार्ड के हजारों छोटे कोर का उपयोग करते हैं (जैसे एक सुपर-फास्ट असेंबली लाइन)।
चतुर हिस्सा यह है कि इन सभी खेलों का मूल ढांचा एक ही होता है (वही "गांठ" का आकार), भले ही उनके अंदर की संख्याएँ अलग हों। सॉल्वर इसे पहचान लेता है और काम को दोबारा उपयोग करता है, केवल प्रत्येक परिदृश्य के लिए विशिष्ट संख्याओं को बदलता है।
2. "ओपन-सोर्स" रेसिपी
क्योंकि कोड ओपन-सोर्स है और जूलिया में लिखा गया है, इसलिए कोई भी इसे देख सकता है, बदल सकता है, या इसे अपने स्वयं के रोबोट सॉफ्टवेयर में प्लग कर सकता है। यह ऑटोमैटिक डिफरेंशिएशन का भी समर्थन करता है, जिसका अर्थ है कि सॉल्वर तुरंत आपको बता सकता है, "यदि मैं कार के शुरुआती स्थान को एक इंच खिसकाता हूँ, तो पूरा ट्रैफिक पैटर्न कितना बदल जाएगा।" यह AI रोबोट को प्रशिक्षित करने के लिए एक सुपरपावर है।
3. "स्मार्ट पॉज़" (Smart Pause)
बैच सॉल्विंग में सबसे बड़ी चुनौतियों में से एक यह है कि कुछ समस्याएं आसान होती हैं, कुछ कठिन, और कुछ असंभव। यदि आप सबसे कठिन समस्या के खत्म होने का इंतज़ार करते हैं, तो आसान वाली बस इंतज़ार करती रह जाती हैं।
नया सॉल्वर इतना स्मार्ट है कि वह पहचान सकता है कि कोई विशिष्ट परिदृश्य फंस गया है या असंभव है। यह उस समस्या को "फ्रीज" कर देता है और उस पर समय बर्बाद करना बंद कर देता है, जिससे बाकी का बैच आगे बढ़ता रहता है। यह एक जिद्दी समस्या को पूरे समूह को धीमा करने से रोकता है।
परिणाम: कितनी तेज़ है तेज़?
शोधकर्ताओं ने पुराने मानक (PATH) के विरुद्ध दो प्रकार की समस्याओं का उपयोग करके अपने नए सॉल्वर का परीक्षण किया: रैंडम मैथ पजल्स (Quadratic Programs) और एक वास्तविक "लेन-चेंज" गेम जहाँ दो कारें बिना टकराए लेन बदलने की कोशिश करती हैं।
- विश्वसनीयता: सबसे पहले, उन्होंने जांचा कि क्या नया सॉल्वर पुराने वाले जितना अच्छा है। यह वैसा ही था। इसने PATH के समान संख्या में समस्याओं को हल किया, जिससे साबित हुआ कि यह केवल तेज़ ही नहीं, बल्कि सटीक भी है।
- गति: फिर, उन्होंने गति को मापा।
- लेन-चेंज गेम के लिए, नए सॉल्वर ने 1,024 परिदृश्यों के बैच को लगभग 0.44 सेकंड में पूरा किया। पुराने PATH तरीके ने 46.4 सेकंड लिए। यह 105x की स्पीडअप है।
- कंप्यूटर के CPU (32 थ्रेड्स का उपयोग करके) पर भी, नया सॉल्वर PATH को एक-एक करके चलाने की तुलना में 100 गुना तेज़ था।
- GPU (ग्राफिक्स कार्ड) भी अविश्वसनीय रूप से तेज़ था, लेकिन दिलचस्प बात यह है कि यह हमेशा विजेता नहीं था।
ट्विस्ट: जब GPU जीतता है (और जब वह नहीं जीतता)
पेपर में एक आश्चर्यजनक विवरण मिला कि किस हार्डवेयर का उपयोग कब किया जाए।
- CPU किंग: लेन-चेंज गेम के लिए, CPU (32 थ्रेड्स के साथ) वास्तव में GPU से तेज़ था। क्यों? क्योंकि लेन-चेंज गेम के लिए गणित "स्पार्स" (ज्यादातर खाली जगह) है। CPU स्मार्ट है और खाली हिस्सों को छोड़ देता है और केवल सक्रिय समस्याओं पर काम करता है। इसके विपरीत, GPU एक साथ पूरे बैच को प्रोसेस करने की कोशिश करता है, यहाँ तक कि उन हिस्सों को भी जो फ्रीज या खत्म हो चुके हैं, जिससे ऊर्जा बर्बाद होती है।
- GPU चैंपियन: GPU केवल तभी आगे निकला जब समस्याएं बहुत बड़ी और "डेंस" (संख्याओं से भरी) हो गईं। उदाहरण के लिए, जब उन्होंने रैंडम मैथ पजल्स का आकार बढ़ाया, तो GPU, CPU की तुलना में 3 गुना तेज़ हो गया।
यह हमें सिखाता है कि कोई एक "सर्वश्रेष्ठ" मशीन नहीं है। यदि आपकी रोबोट समस्या छोटी और स्पार्स है, तो कई कोर वाला एक मानक कंप्यूटर सबसे अच्छा है। यदि आपकी समस्याएँ विशाल और जटिल हैं, तो ग्राफिक्स कार्ड बाजी मार लेता है।
यह क्यों मायने रखता है
यह पेपर केवल एक तेज़ कैलकुलेटर नहीं दे रहा है; यह सोचने का एक नया तरीका दे रहा है। यह दिखाकर कि हम ओपन-सोर्स टूल्स का उपयोग करके पलक झपकते ही हजारों रोबोट परिदृश्यों को हल कर सकते हैं, यह रोबोटिक्स में एक बड़ी बाधा को दूर करता है।
- रियल-टाइम प्लानिंग: रोबोट अब कई "क्या होगा अगर" वाले परिदृश्यों की तुरंत योजना बना सकते हैं, जिससे वे अधिक सुरक्षित और अनुकूलन योग्य बन जाते हैं।
- लर्निंग (सीखना): क्योंकि सॉल्वर डिफरेंशिएट कर सकता है, इंजीनियर अब इन खेलों से सीधे बेहतर रणनीतियाँ सीखने के लिए रोबोट को प्रशिक्षित कर सकते हैं।
- पहुंच (Accessibility): चूंकि यह ओपन-सोर्स है, इसलिए दुनिया भर के शोधकर्ता महंगे लाइसेंस के लिए भुगतान किए बिना या अगला काम शुरू करने से पहले एक समस्या के खत्म होने का इंतज़ार किए बिना इन उपकरणों का उपयोग कर सकते हैं।
संक्षेप में, लेखक ने जटिल गणित और वास्तविक दुनिया के रोबोटिक्स के बीच एक पुल बनाया है, यह साबित करते हुए कि सही बैच-प्रोसेसिंग रणनीति के साथ, हम मल्टी-एजेंट रोबोट्स के अराजक नृत्य को पहले से कहीं अधिक तेज़ी से हल कर सकते हैं।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।