💻 computer science

Verification of Robust Multi-Agent Systems

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

मूल लेखक: Raphaël Berthon, Joost-Pieter Katoen, Munyque Mittelmann, Aniello Murano

प्रकाशित 2026-02-17

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

CC BY 4.0

मूल लेखक: Raphaël Berthon, Joost-Pieter Katoen, Munyque Mittelmann, Aniello Murano

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

कल्पना कीजिए कि आप स्वायत्त डिलीवरी ड्रोन (autonomous delivery drones) के एक बेड़े के कप्तान हैं। आपका लक्ष्य पैकेज को उनके गंतव्य तक कुशलतापूर्वक और सुरक्षित रूप से पहुँचाना है। आपके पास ड्रोनों की एक टीम है (एक मल्टी-एजेंट सिस्टम) जिन्हें मिलकर काम करने की आवश्यकता है, कभी वे एक-दूसरे के साथ सहयोग करते हैं, तो कभी एक-दूसरे के साथ प्रतिस्पर्धा करते हैं।

हालाँकि, एक पेच है: आपके पास एक सटीक मानचित्र (map) नहीं है।

वास्तविक दुनिया अव्यवस्थित होती है। हवा आपके सेंसर द्वारा बताई गई तुलना में अधिक तेज़ हो सकती है, बैटरी उम्मीद से अधिक तेज़ी से खत्म हो सकती है, या कोई ट्रैफिक लाइट खराब हो सकती है। कंप्यूटर विज्ञान के शब्दों में, आगे क्या होगा इसकी "संभावनाएं" (जैसे, "आगे बढ़ने की 80% संभावना") केवल अनुमान मात्र हैं। वे अनिश्चित (uncertain) हैं।

यह शोध पत्र इन ड्रोन टीमों को मजबूत योजनाएं (robust plans) बनाना सिखाने के बारे में है—ऐसी योजनाएं जो तब भी काम करती हैं जब दुनिया ठीक वैसी नहीं होती जैसी भविष्यवाणी की गई थी।

यहाँ सरल उपमाओं का उपयोग करके इस शोध पत्र के विचारों का विवरण दिया गया है:

1. समस्या: "धुंधला" मानचित्र (The "Foggy" Map)

आमतौर पर, जब हम रोबोट को प्रोग्राम करते हैं, तो हम मान लेते हैं कि हम नियमों को पूरी तरह से जानते हैं। "यदि मैं बटन A दबाता हूँ, तो 90% संभावना है कि मैं आगे बढ़ूँगा।"
लेकिन वास्तव में, वह 90% वास्तव में 85% या 95% हो सकता है क्योंकि डेटा खराब है या पर्यावरणीय शोर (noise) है। यदि आपके रोबोट की योजना उस सटीक 90% पर निर्भर करती है, और वास्तविक दुनिया 85% है, तो आपकी योजना विफल हो सकती है।

लेखक पूछते हैं: हम एक ऐसी रणनीति कैसे लिखें जो तब भी काम करे जब संख्याएँ थोड़ी गलत हों?

2. समाधान: "बाउंडेड मेमोरी" (The Short-Term Planner)

इसे हल करने के लिए, रोबोटों को अच्छे निर्णय लेने के लिए यह याद रखने की आवश्यकता है कि हाल ही में क्या हुआ था।

अनंत स्मृति (Infinite Memory): एक ऐसे रोबट की कल्पना करें जो अपने निर्माण के समय से अब तक हुई हर एक चीज़ को याद रखता है। यह उसके मस्तिष्क (कंप्यूटेशनल रूप से) के लिए बहुत भारी है और अक्सर अनावश्यक होता है।
कोई स्मृति नहीं (No Memory): एक ऐसे रोबोट की कल्पना करें जो केवल उसी पर प्रतिक्रिया देता है जो वह अभी देख रहा है, बाकी सब कुछ भूल जाता है। यह बहुत सरल है और अक्सर लूप में फंसने का कारण बनता है।
बाउंडेड मेमोरी (Bounded Memory - द स्वीट स्पॉट): यह एक ऐसे रोबोट की तरह है जो पिछले 5 कदमों को याद रखता है या हाल की घटनाओं का एक छोटा "चीट शीट" रखता है। यह तत्काल अतीत से सीखने के लिए पर्याप्त स्मार्ट है लेकिन एक मानक कंप्यूटर चिप पर चलने के लिए पर्याप्त हल्का भी है।

यह शोध पत्र सिद्ध करता है कि इस "लघु-कालिक स्मृति" का उपयोग करना मजबूत निर्णय लेने के लिए एक आदर्श संतुलन है।

3. "धुंध" के तीन प्रकार (Perturbations)

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

"छोटी हलचल" ( $\epsilon$ -perturbation): कल्पना कीजिए कि हवा थोड़ी सी अलग है। शायद आगे बढ़ने की संभावना केवल 5% कम या ज्यादा है। रणनीति को तब भी काम करना चाहिए जब हवा उम्मीद से थोड़ी तेज़ या धीमी हो।
"निश्चित चर" (Fixed Parameters): कल्पना कीजिए कि मौसम कुछ विशिष्ट बटनों (जैसे "आर्द्रता" और "तापमान") पर निर्भर करता है। हमें उन बटनों की सटीक सेटिंग का पता नहीं है, लेकिन हम जानते हैं कि केवल कुछ ही हैं। रणनीति को इन कुछ बटनों के किसी भी सेटिंग के लिए काम करना चाहिए।
"अनंत चर" (Unbounded Parameters): कल्पना कीजिए कि मौसम अनंत सूक्ष्म, अज्ञात कारकों पर निर्भर है। यह सबसे कठिन परिदृश्य है, जैसे बिना किसी डेटा के मौसम की भविष्यवाणी करने की कोशिश करना। शोध पत्र दिखाता है कि हालांकि इसे हल करना संभव है, लेकिन इसके लिए अन्य दो की तुलना में बहुत अधिक "मस्तिष्क शक्ति" (कंप्यूटेशनल जटिलता) की आवश्यकता होती है।

4. "कोलिशन" (गठबंधन) का खेल

एक मल्टी-एजेंट सिस्टम में, एजेंट मित्र या शत्रु हो सकते हैं।

सहयोग (Cooperation): दो ड्रोनों को मिलकर एक भारी पैकेज पकड़ने की आवश्यकता हो सकती है।
प्रतिस्पर्धा (Competition): एक ड्रोन "विरोधी" (जैसे एक हैकर या प्रतिद्वंद्वी कंपनी) हो सकता है जो दूसरों को रोकने की कोशिश कर रहा है।

यह शोध पत्र एक विशेष तर्क (जिसे PATL कहा जाता है) का उपयोग करके प्रश्न पूछता है जैसे: "क्या ड्रोनों की एक टीम यह गारंटी दे सकती है कि वे कम से कम 90% सफलता दर के साथ गंतव्य तक पहुँचेंगे, भले ही हवा बदल जाए और एक प्रतिद्वंद्वी ड्रोन उन्हें रोकने की कोशिश करे?"

5. बड़ी खोज

लेखकों ने यह देखने के लिए गणित किया कि "पूरी तरह से मजबूत" योजनाएं खोजना कितना कठिन है।

अच्छी खबर: अधिकांश वास्तविक परिदृश्यों (छोटी हलचल या कुछ अज्ञात चर) के लिए, हम इन योजनाओं का उपयोग मौजूदा कंप्यूटरों का उपयोग करके कर सकते हैं। यह एक जटिल सुडोकू पहेली को हल करने जैसा है; इसमें समय लगता है, लेकिन यह संभव है।
चेतावनी: यदि अनिश्चितता बहुत अधिक अनियंत्रित है (अनंत अज्ञात चर), तो समस्या अविश्वसनीय रूप से कठिन हो जाती है, जो वर्तमान कंप्यूटरों के लिए इसे जल्दी से हल करना लगभग असंभव है।

यह क्यों मायने रखता है?

स्मार्ट शहरों या स्व-चालित कारों (Self-Driving Cars) के बारे में सोचें।

यदि एक सेल्फ-ड्राइविंग कार का सॉफ़्टवेयर यह मानता है कि सड़क सूखी है, लेकिन वास्तव में बारिश हो रही है (अनिश्चितता), और कार के पास एक "मजबूत" योजना नहीं है, तो दुर्घटना हो सकती है।
यदि बिजली संयंत्रों का एक स्मार्ट ग्रिड ऊर्जा को संतुलित करने का प्रयास करता है लेकिन सौर पैनल अनुमान से कम कुशल हैं, तो पूरे शहर की बिजली जा सकती है।

यह शोध पत्र उन AI प्रणालियों के निर्माण के लिए गणितीय "ब्लूप्रिंट" प्रदान करता है जो कहते हैं: "मैं जानता हूँ कि दुनिया अव्यवस्थित है और मेरा डेटा पूर्ण नहीं है, लेकिन मेरे पास एक ऐसी योजना है जो इन सीमाओं के भीतर कुछ भी होने पर भी हमें सुरक्षित रखेगी।"

संक्षेप में: यह शोध पत्र हमें ऐसी AI टीमों को बनाना सिखाता है जो लचीली (resilient), हाल के अतीत को याद रखने के लिए पर्याप्त स्मार्ट, और अप्रत्याशित के लिए तैयार होती हैं, जिससे यह सुनिश्चित होता है कि जब वास्तविकता सिमुलेशन से मेल नहीं खाती, तो वे क्रैश न हों।

यहाँ रैफ़ाएल बर्थोन (Raphaël Berthon) और अन्य द्वारा लिखित शोध पत्र "Verification of Robust Multi-Agent Systems" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र स्टोकेस्टिक मल्टी-एजेंट सिस्टम (Stochastic Multi-Agent Systems - MAS) के सत्यापन (verification) को संबोधित करता है, जहाँ संक्रमण की संभावनाएँ (transition probabilities) स्थिर नहीं होती हैं, बल्कि अनिश्चितता या विक्षोभ (perturbations) के अधीन होती हैं। वास्तविक दुनिया के अनुप्रयोगों (जैसे रोबोटिक्स, साइबर-फिजिकल सिस्टम, सुदृढीकरण शिक्षण/reinforcement learning) में, संक्रमण मॉडल अक्सर डेटा से अनुमानित किए जाते हैं, जिससे संभावित त्रुटियाँ या भिन्नताएँ उत्पन्न हो सकती हैं।

पहचाने गए मुख्य चुनौतियाँ हैं:

अनिश्चितता (Uncertainty): पर्यावरणीय शोर या अनुमान संबंधी त्रुटियों के कारण संक्रमण की संभावनाएँ नाममात्र (nominal) मानों से विचलित हो सकती हैं।
अपूर्ण सूचना (Imperfect Information): एजेंटों के पास अक्सर सिस्टम की स्थिति का आंशिक अवलोकन (partial observability) होता है।
रणनीतिक जटिलता (Strategic Complexity): एजेंटों को प्रतिकूल एजेंटों और अनिश्चित गतिकी (dynamics) के साथ काम करते हुए टेम्पोरल लक्ष्यों को प्राप्त करने के लिए गठबंधन (coalitions) बनाने होते हैं।
मेमोरी सीमाएँ (Memory Constraints): जबकि अनंत-मेमोरी रणनीतियाँ सैद्धांतिक रूप से शक्तिशाली होती हैं, वे अक्सर अपूर्ण सूचना सेटिंग्स में कम्प्यूटेशनल रूप से अव्यवहार्य या अनिर्णायक (undecidable) होती हैं। लेखक बाउंडेड-मेमोरी रणनीतियों (जिन्हें परिमित ऑटोमेटा द्वारा दर्शाया जाता है) पर ध्यान केंद्रित करते हैं, जो अभिव्यक्ति (expressivity) और कम्प्यूटेशनल लागत के बीच एक व्यावहारिक संतुलन प्रदान करती हैं।

विशिष्ट समस्या यह निर्धारित करना है कि क्या एजेंटों के एक गठबंधन के पास एक रोबस्ट रणनीति (robust strategy) है—एक ऐसी रणनीति जो एक परिभाषित विक्षोभ सीमा (perturbation bound) के भीतर संक्रमण की संभावनाएँ कैसे भी बदलें, एक संभावabilistic टेम्पोरल स्पेसिफिकेशन (प्रोबबिलिस्टिक अल्टरनेटिंग-टाइम टेम्पोरल लॉजिक, PATL में) को संतुष्ट करती है।

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

लेखक एक ऐसा ढांचा प्रस्तावित करते हैं जो तीन अलग-अलग प्रकार के विक्षोभ (perturbation) के तहत मजबूती (robustness) को संभालने के लिए प्रोबबिलिस्टिक अल्टरनेटिंग-टाइम टेम्पोरल लॉजिक (PATL) का विस्तार करता है:

$\epsilon$ -विक्षोभ ( $\epsilon$ -Perturbations): प्रत्येक संक्रमण की संभावना नाममात्र मान से अधिकतम $\epsilon$ तक विचलित हो सकती है। यह इंटरवल मार्कोव डिसीजन प्रोसेस (IMDPs) का सामान्यीकरण है।
फिक्स्ड-पैरामीटर विक्षोभ (Fixed-Parameter Perturbations): संक्रमण की संभावनाएँ निश्चित, छोटी संख्या में पैरामीटर्स के तर्कसंगत फलनों (rational functions) के रूप में होती हैं। यह संक्रमणों के बीच निर्भरता को दर्शाता है (जैसे, यदि एक संभावना बढ़ती है, तो दूसरी घटनी चाहिए)।
अनबाउंडेड-पैरामीटर विक्षोभ (Unbounded-Parameter Perturbations): संक्रमण की संभावनाएँ अनिश्चित (अनबाउंडेड) संख्या में पैरामीटर्स पर निर्भर करती हैं।

प्रमुख कार्यप्रणाली नवाचार:

ऑटोमेटा-आधारित रणनीतियाँ (Automata-Based Strategies): बाउंडेड मेमोरी को केवल पिछले $k$ राज्यों को याद रखने (sequential strategies) के रूप में परिभाषित करने के बजाय, लेखक रणनीतियों को फिनिट-स्टेट शेड्यूलर्स (ऑटोमेटा) का उपयोग करके परिभाषित करते हैं। वे सिद्ध करते हैं कि यह परिभाषा $k$ -सिक्वेंशियल रणनीतियों की तुलना में अधिक अभिव्यंजक है, जबकि मॉडल चेकिंग के लिए समान 'वर्स्ट-केस' जटिलता बनाए रखती है।
पैरामेट्रिक सिस्टम (Parametric Systems): सिस्टम को एक पैरामेट्रिक स्टोकेस्टिक सिस्टम के रूप में मॉडल किया गया है जहाँ संक्रमण की संभावनाएँ चर $X$ के ऊपर तर्कसंगत फलन हैं। मजबूती का सत्यापन यह जाँचकर किया जाता है कि क्या इन पैरामीटर्स के सभी वैध मानों (valuations) के लिए एक गुण सत्य है।
लॉजिक विस्तार (Logic Extension): यह शोध पत्र PATL के लिए एक रोबस्ट मॉडल-चेकिंग समस्या को परिभाषित करता है, जहाँ संतुष्टि संबंध (satisfaction relation) के लिए एक ऐसी रणनीति का अस्तित्व आवश्यक है जो अनिश्चित पैरामीटर्स के सभी वैध इंस्टेंशिएशन के लिए कार्य करती है।

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

स्टोकेस्टिक MAS के लिए प्रथम रोबस्ट वेरिफिकेशन (PATL के साथ): यह PATL उद्देश्यों वाले स्टोकेस्टिक MAS में रोबस्ट रणनीतियों का अध्ययन करने वाला पहला कार्य है, जिसमें पूर्ण और अपूर्ण सूचना दोनों सेटिंग्स शामिल हैं।
सामान्यीकृत बाउंडेड मेमोरी (Generalized Bounded Memory): लेखक क्लासिकल $k$ -रिकॉल रणनीतियों का विस्तार करने वाले शेड्यूलर-आधारित बाउंडेड मेमोरी परिभाषा को पेश करते हैं। वे प्रदर्शित करते हैं कि यह बढ़ी हुई अभिव्यक्ति मॉडल चेकिंग की कम्प्यूटेशनल जटिलता को नहीं बढ़ाती है।
जटिलता लक्षण वर्णन (Complexity Characterization): यह शोध पत्र विभिन्न विक्षोभ मॉडलों और रणनीति प्रकारों (डिटरमिनिस्टिक बनाम रैंडमाइज्ड) के तहत रोबस्ट मॉडल-चेकिंग समस्या का व्यापक जटिलता विश्लेषण प्रदान करता है।
निर्णय क्षमता (Decidability): अपूर्ण सूचना, स्टोकेस्टिसिटी और पैरामेट्रिक अनिश्चितता के संयोजन के बावजूद, लेखक दिखाते हैं कि बाउंडेड-मेमोरी रणनीतियों के लिए यह समस्या निर्णय योग्य (decidable) बनी रहती है।

4. मुख्य परिणाम (जटिलता विश्लेषण) [Main Results (Complexity Analysis)]

जटिलता के परिणाम विक्षोभ के प्रकार और रणनीतियों की प्रकृति (डिटरमिनिस्टिक बनाम रैंडमाइज्ड) पर निर्भर करते हैं। परिणामों को शोध पत्र की तालिका 1 में संक्षेपित किया गया है:

विक्षोभ प्रकार (Perturbation Type)	रणनीति प्रकार (Strategy Type)	जटिलता वर्ग (Complexity Class)
$\epsilon$ -विक्षोभ	डिटरमिनिस्टिक (गठबंधन) / रैंडमाइज्ड (अन्य)	$\Sigma^P_2$ (NP $^{NP}$ )
निश्चित संख्या में पैरामीटर्स	डिटरमिनिस्टिक (गठबंधन) / रैंडमाइज्ड (अन्य)	$\Sigma^P_2$ (NP $^{NP}$ )
अनबाउंडेड पैरामीटर्स	रैंडमाइज्ड (सामान्य)	$\Sigma^R_3$ (रील्स पर Existential-Universal-Existential)
यूनिवर्सल रीचेबिलिटी (बेस केस)	रैंडमाइज्ड	P ( $\epsilon$ ), NP $\cap$ co-NP (फिक्स्ड पैरामीटर्स), $\forall\mathbb{R}$ (अनबाउंडेड पैरामीटर्स)

$\epsilon$ -विक्षोभ और फिक्स्ड पैरामीटर्स: यह समस्या $\Sigma^P_2$ में है। इसे गठबंधन (रणनीति चुनते हुए) और वातावरण (सबसे खराब स्थिति वाला पैरामीटर वैल्यूएशन चुनते हुए) के बीच एक खेल (game) में बदलकर प्राप्त किया गया है।
अनबाउंडेड पैरामीटर्स: जटिलता बढ़कर $\Sigma^R_3$ (रीयल हाइरार्की का तीसरा स्तर) हो जाती है। यह अनबाउंडेड संख्या में रियल-वैल्यूड पैरामीटर्स पर क्वांटिफिकेशन (quantification) की कठिनाई को दर्शाता है।
रीचेबिलिटी बनाम सामान्य PATL: लेखक पहले सरल "यूनिवर्सल रीचेबिलिटी" समस्या को हल करते हैं (यह जाँचना कि क्या एक लक्ष्य सभी रणनीतियों के लिए प्रायिकता $\ge d$ के साथ सुलभ है) ताकि बिल्डिंग ब्लॉक्स स्थापित किए जा सकें। इसके बाद वे इन परिणामों को पूर्ण PATL फॉर्मूला (टेम्पोरल ऑपरेटर्स जैसे Until, Release और गठबंधन नेस्टिंग सहित) तक विस्तारित करते हैं।

5. महत्व और अनुप्रयोग (Significance and Applications)

सैद्धांतिक प्रभाव (Theoretical Impact): यह कार्य रणनीतिक तर्क (ATL), संभाव्यता सत्यापन (PATL), और रोबस्ट कंट्रोल (पैरामेट्रिक/इंटरवल मॉडल) के बीच के अंतर को पाटता है। यह मल्टी-एजेंट सत्यापन में मजबूती जोड़ने की कम्प्यूटेशनल लागत को स्पष्ट करता है।
व्यावहारिक प्रासंगिकता (Practical Relevance): यह ढांचा साइबर-फिजिकल सिस्टम्स (CPS) जैसे स्मार्ट सिटी, स्वायत्त परिवहन और औद्योगिक स्वचालन के लिए लागू करने योग्य है।
- उदाहरण: एक स्मार्ट सिटी में, इमारतों (एजेंटों) को ऊर्जा उपयोग के लिए समन्वय करना होगा। मॉडल यह सत्यापित करता है कि क्या इमारतों का एक गठबंधन एक निश्चित ऊर्जा स्तर की गारंटी दे सकता है, भले ही सौर पैनल दक्षता या हीटिंग मांग की भविष्यवाणियाँ ज्ञात त्रुटि मार्जिन के भीतर भिन्न हों।
- सुरक्षा (Security): यह सत्यापित कर सकता है कि एक हमलावर उच्च प्रायिकता के साथ अनधिकृत पहुंच प्राप्त नहीं कर सकता, भले ही रक्षा प्रणाली की पहचान दर (detection rates) उतार-चढ़ाव का शिकार हो।
व्यवहार्यता (Feasibility): बाउंडेड-मेमोरी रणनीतियों पर ध्यान केंद्रित करके, लेखक यह सुनिश्चित करते हैं कि सत्यापन विधियाँ उन वास्तविक प्रणालियों के लिए कम्प्यूटेशनल रूप से व्यवहार्य हैं जहाँ एजेंटों के पास सीमित प्रोसेसिंग पावर और मेमोरी होती है।

निष्कर्ष (Conclusion)

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