💻 computer science

Efficiently Solving Mixed-Hierarchy Games with Quasi-Policy Approximations

यह शोध पत्र N-रोबोट वन-संरचित मिश्रित-पदानुक्रमित खेलों (N-robot forest-structured mixed-hierarchy games) को कुशलतापूर्वक हल करने के लिए एक अर्ध-नीति सन्निकटन (quasi-policy approximation) और एक अनिश्चित न्यूटन पद्धति (inexact Newton method) प्रस्तुत करता है, जो मानक KKT स्थितियों में उच्च-क्रम डेरिवेटिव की जटिलता को दूर करते हुए सिमुलेशन और हार्डवेयर प्रयोगों दोनों में स्थानीय घातांकीय अभिसरण (local exponential convergence) और वास्तविक समय प्रदर्शन प्राप्त करता है।

मूल लेखक: Hamzah Khan, Dong Ho Lee, Jingqi Li, Tianyu Qiu, Christian Ellis, Jesse Milzman, Wesley Suttle, David Fridovich-Keil

प्रकाशित 2026-05-18

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Hamzah Khan, Dong Ho Lee, Jingqi Li, Tianyu Qiu, Christian Ellis, Jesse Milzman, Wesley Suttle, David Fridovich-Keil

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

एक व्यस्त हाईवे की कल्पना करें जहाँ कई कारों को एक ही लेन में मर्ज (merge) होना है। कुछ कारें एक काफिले (convoy) में चल रही हैं, जो एक साथ आगे बढ़ रही हैं, जबकि कुछ कारें उनके बीच में घुसने की कोशिश कर रही हैं। वास्तविक दुनिया में ये कारें केवल बेतरतीब ढंग से नहीं चलतीं; वे इस आधार पर निर्णय लेती हैं कि उन्हें लगता है कि दूसरी कारें क्या करेंगी।

यह शोध पत्र (paper) पेश करता है कि कैसे रोबोट्स (या सेल्फ-ड्राइविंग कारें) इन जटिल स्थितियों के लिए एक आदर्श योजना कैसे बना सकते हैं। यहाँ सरल उपमाओं (analogies) का उपयोग करके इसका विवरण दिया गया है:

समस्या: बॉस और साथियों का एक उलझा हुआ मिश्रण

आमतौर पर, गेम थ्योरी (रणनीति का गणित) दो प्रकार के संबंधों को संभालती है:

"बॉस" (स्टैकेलबर्ग - Stackelberg): एक रोबोट लीडर होता है, और अन्य फॉलोअर्स होते हैं। लीडर पहले चलता है, और फॉलोअर्स उसकी प्रतिक्रिया देते हैं। यह एक जनरल द्वारा सैनिकों को आदेश देने जैसा है।
"साथी" (नैश - Nash): सभी एक ही समय में चलते हैं, और यह अनुमान लगाने की कोशिश करते हैं कि दूसरे क्या करेंगे। यह दोस्तों के एक समूह द्वारा रात के खाने के लिए जगह तय करने जैसा है; कोई भी प्रभारी नहीं है, वे बस आपस में तालमेल बिठाते हैं।

चुनौती: वास्तविक जीवन जटिल होता है। कभी-कभी इसमें मिश्रण होता है। पेपर के उदाहरण में, कार 1, कार 2 का "बॉस" है, लेकिन कार 2 और कार 3 एक ही समय में "साथी" के रूप में बातचीत कर रहे हैं। मौजूदा गणितीय उपकरण इस विशिष्ट "मिश्रित" संरचना को संभालने के लिए बहुत धीमे या कठोर थे, विशेष रूप से जब कारों की भौतिकी (physics) जटिल हो (जैसे कि वे तुरंत मुड़ नहीं सकतीं) और उनके लक्ष्य गैर-रेखीय (non-linear) हों (जैसे कि केवल दूरी कम करने के बजाय टक्कर से बचना)।

समाधान: "क्वासी-पॉलिसी" (Quasi-Policy) का शॉर्टकट

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

ट्रिक: लेखकों ने एक "क्वासी-पॉलिसी एप्रोक्सिमेशन" (Quasi-Policy Approximation) का आविष्कार किया।

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

इंजन: "इनएक्सैक्ट न्यूटन" (Inexact Newton) विधि

एक बार जब उन्होंने शॉर्टकट का उपयोग करके गणित को सरल बना दिया, तो उन्हें वास्तव में समीकरणों को हल करने के लिए एक तरीके की आवश्यकता थी। उन्होंने "इनएक्सैक्ट न्यूटन मेथड" नामक विधि का उपयोग किया।

उपमा: कल्पना करें कि आप कोहरे में एक घाटी के निचले हिस्से को खोजने की कोशिश कर रहे हैं। एक पूर्ण विधि के लिए आपको आगे बढ़ने से पहले घाटी के हर इंच का मानचित्रण करने की आवश्यकता होगी। "इनएक्सैक्ट" विधि उस ढलान के आधार पर एक आत्मविश्वासपूर्ण कदम उठाने जैसी है जो आप अभी देख पा रहे हैं। यदि आप बिल्कुल नीचे नहीं पहुँचे हैं, तो आप एक और कदम उठाते हैं।
यह क्यों काम करता है: पेपर यह सिद्ध करता है कि भले ही वे "अनुमानित" (approximate) कदम उठा रहे हों (क्योंकि उन्होंने शॉर्टकट का उपयोग किया है), एक बार जब वे करीब पहुँच जाते हैं तो वे बहुत तेज़ी से (exponentially fast) सटीक समाधान की ओर बढ़ेंगे।

प्रमाण: वास्तविक रोबोट और सिमुलेशन

टीम ने केवल सिद्धांत नहीं लिखा; उन्होंने एक सॉफ्टवेयर लाइब्रेरी बनाई (जो 'जूलिया' नामक भाषा में लिखी गई है) और उसका परीक्षण किया:

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

सारांश

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

तकनीकी सारांश: क्वासी-पॉलिसी सन्निकटन के साथ मिश्रित-पदानुक्रमित खेलों को कुशलतापूर्वक हल करना

समस्या विवरण

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

गैर-रैखिक बाधाएं (जैसे, गैर-रैखिक गति गतिकी से उत्पन्न)।
गैर-द्विघाती उद्देश्य (सरल द्विघाती लागतों से परे जटिल कार्यों को एनकोड करना)।
वन-संरचित (Forest-structured) सूचना पैटर्न, जहाँ रोबोट लीडर-फॉलोअर श्रृंखलाओं (वृक्षों) के रूप में बनते हैं जो विभिन्न शाखाओं में नाश संतुलन के माध्यम से परस्पर क्रिया करते हैं।

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

कार्यप्रणाली

लेखक उच्च-क्रम डेरिवेटिव गणनाओं से बचने के लिए अनुकूलता स्थितियों को अनुमानित करने के लिए एक ढांचा प्रस्तावित करते हैं।

1. समस्या निरूपण

खेल को एक निर्देशित अचक्रीय ग्राफ $G$ के रूप में मॉडल किया गया है जहाँ नोड्स रोबोटों का प्रतिनिधित्व करते हैं और किनारे लीडर-फॉलोअर संबंधों का प्रतिनिधित्व करते हैं। लेखक मानते हैं कि $G$ एक वन (forest) है (विच्छेदित वृक्षों का एक संघ), जो यह सुनिश्चित करता है कि प्रत्येक रोब of कम से कम एक सीधा लीडर हो।

रणनीतियाँ: प्रत्येक रोबोट $i$ एक उद्देश्य $J_i(z)$ को समानता बाधाओं $g_i(z_i)=0$ (जैसे, गतिकी) के अधीन न्यूनतम करता है।
संतुलन परिभाषा: एक मिश्रित-पदानुक्रमित संतुलन के लिए आवश्यक है कि प्रत्येक रोबोट संतुष्ट करे:
- स्टैकेलबर्ग स्थितियां: अपनी रणनीति और लीडर्स की रणनीतियों को देखते हुए अपने सबट्री (उप-वृक्ष) की रणनीतियों को अनुकूलित करना।
- नाश स्थितियां: अन्य शाखाओं के रोबोटों (नाश रिश्तेदारों) की रणनीतियों को देखते हुए अपनी रणनीति को अनुकूलित करना जिन्हें वह प्रभावित नहीं कर सकता।

2. क्वासी-पॉलिसी सन्निकटन (Quasi-Policy Approximation)

उच्च-क्रम डेरिवेटिव्स की जटिलता से बचने के लिए, लेखक एक क्वासी-पॉलिसी सन्निकटन पेश करते हैं:

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

3. इनएक्सैक्ट न्यूटन सॉल्वर

लेखक परिणामी अनुमानित KKT सिस्टम को हल करने के लिए एक इनएक्सैक्ट न्यूटन विधि विकसित करते हैं:

एल्गोरिदम: सॉल्वर प्रत्येक रोबोट के लिए अनुमानित KKT स्थितियों का निर्माण करने के लिए रिवर्स टोपोलॉजिकल ऑर्डर में पुनरावृत्ति करता है। फिर यह एक अनुमानित जैकोबियन (जहाँ उच्च-क्रम पदों को शून्य कर दिया जाता है) का उपयोग करके एक सर्च डायरेक्शन निर्धारित करने के लिए एक लीनियर सिस्टम को हल करता है।
अभिसरण (Convergence): पेपर गैर-द्विघाती उद्देश्यों और गैर-रैखिक बाधाओं वाले खेलों के लिए स्थानीय घातीय अभिसरण (local exponential convergence) का सैद्धांतिक प्रमाण प्रदान करता है, बशर्ते कि उच्च-क्रम पॉलिसी संवेदनशीलताशीलता प्रथम-क्रम ग्रेडिएंट्स के सापेक्ष छोटी हो (एक स्थिति जो मजबूत रेगुलाइजेशन वाले कंट्रोल समस्याओं में अक्सर मिलती है)।

मुख्य योगदान

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

प्रयोगात्मक परिणाम

दृढ़तापूर्वक मूल्यांकन हार्डवेयर और सिमुलेशन दोनों में किया गया:

हार्डवेयर (टारगेट गार्डिंग): एक तीन-रोबोट प्रयोग जिसमें एक पर्स्यूटर (पीछा करने वाला), एक गार्ड और एक टारगेट शामिल है। गार्ड टारगेट का नेतृत्व करता है, जबकि दोनों का पर्स्यूटर के साथ नाश संबंध है। मानक CPU पर सॉल्वर रियल-टाइम (औसत 13.6 ms प्रति कॉल) में चला, जिसने टारगेट-गार्डिंग उद्देश्य को प्राप्त करने के लिए रोबोटों को सफलतापूर्वक समन्वयित किया।
सिमुलेशन (कॉन्वॉय मर्जिंग): चार अलग-अलग पदानुक्रम संरचनाओं के तहत एक चार-वाहन मर्जिंग परिदृश्य का परीक्षण किया गया: शुद्ध नाश, दो मिश्रित पदानुक्रम, और एक शुद्ध स्टैकेलबर्ग चेन।
- सॉल्वर ने प्रदर्शित किया कि पदानुक्रम संरचना बदलने से विशिष्ट, व्याख्या योग्य व्यवहार (जैसे, स्थिति बनाए रखने के लिए त्वरण लेने वाला बनाम रास्ता देने वाला लीडर वाहन) उत्पन्न होते हैं।
- सभी परिणामी संतुलन सुरक्षित इंटरैक्शन सुनिश्चित करते हैं।
- अनुभवजन्य परिणामों ने मेरिट फंक्शन के मोनोटोन डिके (monotone decay) और संतुलन के पास स्थानीय घातीय अभिसरण की पुष्टि की, जो थ्योरम 1 को मान्य करता है।

महत्व और दावे

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

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

लेखक निष्कर्ष निकालते हैं कि हालांकि वन संरचना धारणा (Assumption 2) वर्तमान में एकल-लीडर वृक्षों तक इसके दायरे को सीमित करती है, प्रस्तावित क्वासी-पॉलिसी दृष्टिकोण रोबोटिक्स में जटिल, असममित सूचना खेलों को हल करने के लिए एक मजबूत आधार प्रदान करता है। भविष्य के कार्य का लक्ष्य मल्टी-लीडर संरचनाओं को अनुमति देने के लिए इस धारणा को शिथिल करना और असमानता बाधाओं (inequality constraints) को शामिल करना है।