Dynamic Adversarial Resource Allocation: the dDAB Game

यहाँ शोध पत्र "Dynamic Adversarial Resource Allocation: The DDAB Game" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या का निरूपण (Problem Formulation)

यह शोध पत्र डायनेमिक डिफेंडर-अटैकर ब्लोटो (dDAB) गेम पेश करता है, जो क्लासिकल स्टैटिक कर्नल ब्लोटो गेम का एक नवीन विस्तार है, जिसे डायनेमिक और ग्राफ-प्रतिबंधित सेटिंग में लाया गया है।

• वातावरण (Environment): यह खेल एक निर्देशित, स्ट्रॉन्गली कनेक्टेड ग्राफ $G=(V, E)$ पर खेला जाता है जहाँ नोड्स भौतिक स्थानों का प्रतिनिधित्व करते हैं और एडजेस (edges) आवाजाही (traversability) का प्रतिनिधित्व करते हैं।
• खिलाड़ी (Players): दो खिलाड़ी, एक डिफेंडर (ब्लू) और एक अटैकर (रेड), की-नोड्स ($V_{key}$) के एक उपसमूह पर नियंत्रण के लिए प्रतिस्पर्धा करते हैं।
• संसाधन (Resources): खिलाड़ियों के पास निरंतर (continuous) या असतत (discrete) संसाधन (जैसे कि रोबोट्स) होते हैं जिनकी कुल मात्रा क्रमशः $X$ और $Y$ होती है।
• गतिशीलता (Dynamics): खेल डिस्क्रीट टाइम स्टेप्स में आगे बढ़ता है। स्टैटिक ब्लोटो गेम्स के विपरीत, जहाँ आवंटन तात्कालिक होता है, यहाँ संसाधनों को एडजेस (edges) के माध्यम से पार करना होता है। प्रत्येक चरण में:
  1. डिफेंडर वर्तमान स्थिति (ट्रांजिशन मैट्रिक्स $K_t$) के आधार पर संसाधनों को स्थानांतरित करता है।
  2. अटैकर, डिफेंडर की नई स्थिति को देखता है और संसाधनों को स्थानांतरित करता है (ट्रांजिशन मैट्रिक्स $F_t$)।
  3. जीत की शर्त (Winning Condition): अटैकर तब जीतता है यदि किसी भी की-नोड $i$ पर, अटैकर की संसाधन संख्या डिफेंडर की संख्या से अधिक हो जाए ($[y_t]_i > [x_t]_i$)। डिफेंडर तब जीतता है यदि वह एक निर्दिष्ट होराइजन $T$ (या अनिश्चित काल) के लिए इस स्थिति को रोकने में सक्षम होता है।
• उद्देश्य: क्रिटिकल रिसोर्स रेशियो (CRR), $\alpha_T$, निर्धारित करना, जो किसी भी तर्कसंगत अटैकर रणनीति के विरुद्ध जीत सुनिश्चित करने के लिए डिफेंडर हेतु आवश्यक न्यूनतम $X/Y$ अनुपात है, और इसके अनुरूप फीडबैक रणनीतियों को सिंथेसाइज करना है।

2. कार्यप्रणाली (Methodology)

लेखक इस गेम को हल करने के लिए रीचेबिलिटी-आधारित विश्लेषण (reachability-based analysis) को सेट-आधारित डायनेमिक प्रोग्रामिंग के साथ जोड़ते हैं।

A. रीचेबल सेट्स और पॉलीटोप्स (Reachable Sets and Polytopes)

एक्शन स्पेस का सीधे विश्लेषण करने के बजाय, लेखक रीचेबल सेट्स ($R(x_t)$) का विश्लेषण करते हैं, जो एक वर्तमान स्थिति $x_t$ से एक चरण में एक खिलाड़ी द्वारा प्राप्त की जा सकने वाली सभी संभावित स्थितियों का प्रतिनिधित्व करते हैं।

• पॉलीटोप संरचना (Polytope Structure): यह सिद्ध किया गया है कि रीचेबल सेट एक पॉलीटोप (शीर्षों का उत्तल आवरण या convex hull) है।
• एक्सट्रीम एक्शन्स (Extreme Actions): स्वीकार्य कार्यों के सेट को एक्सट्रीम एक्शन्स (एक्शन पॉलीटोप के वर्टिस) द्वारा वर्णित किया गया है, जहाँ संसाधन पूरी तरह से एक पड़ोसी पर चले जाते हैं या वहीं रुक जाते हैं। कोई भी स्वीकार्य कार्य इन एक्सट्रीम एक्शन्स का एक कॉनवेक्स कॉम्बिनेशन (convex combination) होता है।

B. रिक्वायर्ड सेट्स ($P_{req}$)

समय $t+1$ पर रक्षा सुनिश्चित करने के लिए, डिफेंडर को संसाधन इस प्रकार आवंटित करने चाहिए कि वे हर की-नोड पर अटैकर के अधिकतम संभावित आवंटन से अधिक हों।

• रिक्वायर्ड सेट $P_{req}(y_t)$ उन सभी डिफेंडर स्टेट्स $x_{t+1}$ का सेट है जो सभी की-नोड्स के लिए $[x_{t+1}]_i \geq \max_{y' \in R(y_t)} [y']_i$ को संतुष्ट करते हैं।
• यदि डिफेंडर अपनी वर्तमान स्थिति से $P_{req}(y_t)$ तक नहीं पहुँच सकता, तो वह हार जाता है।

C. Q-सेट्स (k-स्टेप सेफ सेट्स)

मल्टी-स्टेप होराइजन को संभालने के लिए, लेखक Q-सेट्स ($Q^{(i)}_k$) को परिभाषित करते हैं, जो डिफेंडर की उन स्टेट्स को दर्शाते हैं जिनसे वे वर्तमान में नोड $i$ पर केंद्रित अटैकर के विरुद्ध $k$ स्टेप्स तक रक्षा सुनिश्चित कर सकते हैं।

• रिकर्सिव परिभाषा (Recursive Definition):
  $$Q^{(i)}_k = \{ x \mid x \in P_{req}(y^{(i)}) \land \forall j \in N_i, R(x) \cap Q^{(j)}_{k-1} \neq \emptyset \}$$
  इसका अर्थ है कि एक स्टेट $k$ स्टेप्स के लिए सुरक्षित है यदि वह वर्तमान स्टेप के लिए सुरक्षित है AND डिफेंडर यह सुनिश्चित कर सकता है कि अटैकर अगले स्टेप में किसी भी पड़ोसी की ओर जाने के बावजूद, डिफेंडर $k-1$ स्टेप्स के लिए सुरक्षित स्टेट तक पहुँच सके।
• अनिश्चित रक्षा (Indefinite Defense): $k \to \infty$ के रूप में सभी $Q^{(i)}_k$ का इंटरसेक्शन अनिश्चित सेफ सेट्स ($Q^{(i)}_\infty$) देता है। यदि ये खाली नहीं हैं, तो अनिश्चित रक्षा संभव है।

D. स्प्लिटिंग रणनीतियों को संभालना (Handling Splitting Strategies)

एक प्रमुख सैद्धांतिक चुनौती यह है कि क्या अटैकर को अपने संसाधनों को कई सब-टीम्स में विभाजित करके लाभ मिलता है।

• सबटीम सुपरपोजिशन (Subteam Superposition): लेखक अटैकर के विभाजन को "सब-टीम्स" के सुपरपोजिशन के रूप में मॉडल करते हैं।
• मुख्य प्रमेय (Key Theorem): वे सिद्ध करते हैं कि यदि डिफेंडर के पास नो-स्प्लिटिंग (केंद्रित) अटैकर के विरुद्ध रक्षा करने के लिए पर्याप्त संसाधन हैं, तो वह किसी भी स्प्लिटिंग रणनीति के विरुद्ध भी रक्षा कर सकता है।
• निहितार्थ (Implication): अटैकर के पास विभाजन (split) करने का कोई प्रोत्साहन नहीं है। नो-स्प्लिटिंग केस के लिए निकाला गया CRR सामान्य केस के लिए पर्याप्त है।

E. एल्गोरिथमिक समाधान (Algorithmic Solution)

• Q-Prop एल्गोरिदम: एक इटरेटिव एल्गोरिदम Q-सेट्स को कंप्यूट करता है जो होराइजन से बाधाओं (constraints) को बैकवर्ड में प्रोपेगेट करता है। यह रीचेबल सेट्स और रिक्वायर्ड सेट्स के इंटरसेक्शन को कुशलतापूर्वक निर्धारित करने के लिए इनवर्स रीचेबल सेट्स (रिवर्स ग्राफ के माध्यम से गणना की गई) का उपयोग करता है।
• एक्शन एक्सट्रैक्शन (Action Extraction): एक बार Q-सेट में टारगेट स्टेट की पहचान हो जाने के बाद, एल्गोरिदम विशिष्ट ट्रांजिशन मैट्रिक्स (एक्शन) खोजने के लिए एक लीनियर प्रोग्राम को हल करता है।

3. मुख्य योगदान (Key Contributions)

1. dDAB का फॉर्मूलेशन: डायनेमिक, ग्राफ-प्रतिबंधित संसाधन मूवमेंट और टर्न-बेस्ड फीडबैक के साथ ब्लोटो गेम का पहला फॉर्मूलेशन।
2. आवश्यक और पर्याप्त शर्तें: क्रिटिकल रिसोर्स रेशियो (CRR) और Q-सेट्स का व्युत्पन्न, जो गारंटीकृत रक्षा के लिए सटीक स्थितियाँ प्रदान करते हैं।
3. नो-स्प्लिटिंग इक्विवेलेंस: यह प्रमाण कि संसाधन विभाजित करना अटैकर को लाभ नहीं पहुँचाता, जिससे रणनीति सिंथेसिस काफी सरल हो जाता है।
4. फीडबैक रणनीतियाँ: दोनों खिलाड़ियों के लिए अनुकूलतम फीडबैक रणनीतियों का संश्लेषण जो प्री-कंप्यूटेड ओपन-लूप प्लान के बजाय वर्तमान स्थिति पर प्रतिक्रिया करती हैं।
5. गैर-पूर्णांक (Non-Integer) CRR: यह प्रदर्शन करना कि फिक्स्ड-होराइजन गेम्स में CRR गैर-पूर्णांक (जैसे 3.5) हो सकता है, जो इस धारणा को चुनौती देता है कि संसाधन अनुपात पूर्णांक होने चाहिए।

4. परिणाम (Results)

• संख्यात्मक सिमुलेशन (Numerical Simulations):
  • विभिन्न ग्राफ टोपोलॉजी (रिंग्स, जनरल डायरेक्टेड ग्राफ्स) पर प्रदर्शित किया गया।
  • दिखाया गया कि एडजेस जोड़ने से हमेशा CRR नहीं बढ़ता; कुछ मामलों में, यह घट जाता है (उदाहरण के लिए, एक सेल्फ-लूप या विशिष्ट द्विदिश एडजेस जोड़ने से डिफेंडर की दक्षता में सुधार हो सकता है)।
  • सत्यापित किया गया कि स्ट्रॉन्गली कनेक्टेड ग्राफ्स के लिए Q-सेट्स एक फिक्स्ड पॉइंट पर अभिसरित (converge) होते हैं, जिससे अनिश्चित रक्षा संभव होती है।
• हार्डवेयर प्रयोग (Robotarium):
  • एल्गोरिदम को एक भौतिक मल्टी-रोबोट टेस्टबेड (जॉर्जिया टेक रोबोटेरियम) पर लागू किया गया।
  • परिदृश्य 1: 7-नोड ग्राफ पर 8 डिफेंडर रोबोट बनाम 2 अटैकर रोबट। डिफेंडर ने की-नोड्स पर संख्यात्मक श्रेष्ठता बनाए रखी।
  • परिदृश्य 2: एक इंडोर सर्विलांस सेटिंग (9 कमरे) में 4 डिफेंडर रोबोट बनाम 1 अटैकर। सिस्टम ने अटैकर की रैंडम मूवमेंट के बावजूद निरंतर निगरानी बनाए रखी।
  • प्रयोगों ने निरंतर (discrete) एलोकेशन रणनीति के साथ कंटीन्यूअस सॉल्यूशन को रैप करके, डिस्क्रीट एम्बोडीड रिसोर्सेज को संभालने की एल्गोरिदम की क्षमता को मान्य किया।

5. महत्व (Significance)

• सैद्धांतिक प्रभाव: यह स्टैटिक गेम थ्योरी (ब्लोटो) और डायनेमिक कंट्रोल (ग्राफ पर पॉपुलेशन डायनेमिक्स) के बीच के अंतर को पाटता है। यह प्रतिकूल अनिश्चितता के तहत सुरक्षा-महत्वपूर्ण संसाधन आवंटन के लिए एक कठोर ढांचा प्रदान करता है।
• व्यावहारिक अनुप्रयोग: यह विवादास्पद वातावरण (जैसे परिधि रक्षा, वाइल्डफायर निगरानी, पावर ग्रिड सुरक्षा) में रोबोटिक सिस्टम को तैनात करने के लिए एक प्रमाणित विधि प्रदान करता है जहाँ संसाधनों को भौतिक रूप से स्थानांतरित होना पड़ता है और मांग गतिशील रूप से बदलती है।
• कंप्यूटेशनल दक्षता: पॉलीटोप ज्योमेट्री और सेट-बेस्ड डायनेमिक प्रोग्रामिंग का उपयोग गेम ट्री से जुड़े "कर्स ऑफ डायमेंशनलिटी" से बचने में मदद करता है, जिससे यह मध्यम आकार के ग्राफों के लिए स्केलेबल बनता है।
• मजबूती (Robustness): व्युत्पन्न रणनीतियाँ वर्स्ट-केस गारंटी (worst-case guarantees) प्रदान करती हैं, जो एक अनुकूल, तर्कसंगत विरोधी के विरुद्ध भी रक्षा सुनिश्चित करती हैं।

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