⚡ electrical engineering

Accelerated consensus in multi-agent networks via memory of local averages

यह शोध पत्र एक संशोधित मल्टी-एजेंट कंसेंसस मॉडल प्रस्तावित करता है जो वर्तमान और पिछले दोनों अवस्थाओं पर डीग्रूट अपडेट लागू करने से पहले उन्हें संयोजित करता है, यह प्रदर्शित करते हुए कि यह दृष्टिकोण आवधिक नेटवर्क (periodic networks) में अभिसरण (convergence) को सक्षम बनाता है और शास्त्रीय डीग्रूट एवं पूर्ववर्ती त्वरित औसत मॉडलों की तुलना में तेज़ अभिसरण दर प्राप्त करता है।

मूल लेखक: Aditya Bhaskar, Shriya Rangarajan, Vikram Shree, Mark Campbell, Francesca Parise

प्रकाशित 2026-07-22

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

CC BY 4.0

मूल लेखक: Aditya Bhaskar, Shriya Rangarajan, Vikram Shree, Mark Campbell, Francesca Parise

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

कल्पना कीजिए कि दोस्तों का एक समूह रात के खाने के लिए जगह तय करने की कोशिश कर रहा है। वे सभी अलग-अलग कमरों में हैं, लेकिन वे केवल उन लोगों से बात कर सकते हैं जो उनके ठीक बगल में खड़े हैं। यदि हर कोई बस अपने निकटतम पड़ोसियों की बात सुनता है और उनके सुझावों का औसत निकालता है, तो वे अंततः एक बात पर सहमत हो सकते हैं, लेकिन इसमें बहुत लंबा समय लग सकता है। इससे भी बुरा यह है कि यदि दोस्त एक आदर्श घेरे (सर्कल) में व्यवस्थित हैं जहाँ हर कोई केवल अपने बाईं ओर के व्यक्ति से बात करता है, तो वे विचारों को बार-बार बदलने के अंतहीन लूप में फंस सकते हैं, और कभी भी एक अंतिम निर्णय पर नहीं पहुँच पाते। यह "मल्टी-एजेंट नेटवर्क" की दुनिया है, जो एक ऐसा विज्ञान है जो यह अध्ययन करता है कि स्वतंत्र इकाइयों—चाहे वे रोबोट हों, सेंसर हों, या लोग—के समूह जानकारी कैसे साझा करते हैं ताकि एक सामान्य निर्णय पर पहुँचा जा सके। इस मॉडल का क्लासिक तरीका "डीग्रूट मॉडल" (DeGroot model) है, जहाँ हर कोई बस अपने पड़ोसियों द्वारा अभी कही गई बात का भारित औसत (weighted average) लेता है। हालाँकि यह कई स्थितियों में काम करता है, लेकिन इसमें एक निराशाजनक खामी है: कुछ नेटवर्क आकृतियों में, जैसे कि उस आदर्श घेरे में, समूह विचारों के बदलाव के स्थायी नृत्य में फंस सकता है, और बिना किसी अंतिम उत्तर पर पहुँचे हमेशा झूलता (oscillate करता) रह सकता है।

यह शोध पत्र उस पुराने नुस्खे में एक चतुर बदलाव पेश करता है ताकि इस "डांसिंग" की समस्या को ठीक किया जा सके और निर्णय लेने की प्रक्रिया को तेज किया जा सके। लेखक, आदित्य भास्कर और उनके सहयोगी, एक नया तरीका प्रस्तावित करते हैं जिसे "मेमोरी ऑफ लोकल एवरेजज" (MLA) मॉडल कहा जाता है। इसमें एजेंट केवल यह नहीं सुनते कि उनके पड़ोसी अभी क्या कह रहे हैं, बल्कि वे यह भी याद रखते हैं कि उन्होंने पिछली बार क्या गणना की थी। इसे ऐसे समझें जैसे दोस्तों का एक समूह, कोई नया सुझाव देने से पहले, न केवल अपने पड़ोसी के वर्तमान विचार को देखता है, बल्कि यह भी याद रखता है कि पिछले दौर में उसके पड़ोसी ने क्या सुझाव दिया था। इस दो प्रकार की जानकारी—ताज़ा खबर और पुरानी खबर—को एक विशिष्ट तरीके से मिलाकर, समूह उन अंतहीन लूपों से बाहर निकल सकता है और बहुत तेज़ी से एक सहमति तक पहुँच सकता है। यह पेपर गणितीय रूप से सिद्ध करता है कि यह सरल मेमोरी ट्रिक नेटवर्क को उन कठिन, गोलाकार व्यवस्थाओं में भी आम सहमति तक पहुँचने में सक्षम बनाती है जहाँ पुराने तरीके विफल हो जाते हैं, और यह सिमुलेशन के माध्यम से दिखाता है कि कई नेटवर्कों के लिए, यह नया दृष्टिकोण पहले की तुलना में काफी तेज़ी से सबको एक ही पृष्ठ पर ले आता है।

समस्या: अंतहीन नृत्य

नेटवर्क्ड एजेंटों की दुनिया में, लक्ष्य अक्सर "आम सहमति" (consensus) होता है, जहाँ सभी एक ही मान (value) पर समाप्त होते हैं, जो आमतौर पर उनके शुरुआती बिंदुओं का औसत होता है। यह करने का मानक तरीका डीग्रूट मॉडल है। कल्पना कीजिए कि लोगों की एक पंक्ति एक नोट पास कर रही है। प्रत्येक व्यक्ति अपने पड़ोसियों से प्राप्त नोट्स को देखता है, उनका औसत निकालता है, और एक नया नोट लिखता है। यदि नेटवर्क एक सरल, उलझा हुआ जाल है, तो यह ठीक काम करता है। लेकिन यदि नेटवर्क एक पूर्ण रिंग (जैसे दोस्तों का एक घेरा जहाँ हर कोई केवल अपने बाईं ओर के व्यक्ति से बात करता है) है, तो डीग्रूट मॉडल एक बाधा का सामना करता है। मान (values) झूलने (oscillate करने) लग सकते हैं: व्यक्ति A कहता है "हाँ", व्यक्ति B कहता है "नहीं", व्यक्ति A कहता है "नहीं", व्यक्ति B कहता है "हाँ", और वे कभी नहीं रुकते। यह एक पेंडुलम की तरह है जो कभी स्थिर नहीं होता।

इसे ठीक करने का एक पिछला प्रयास, जिसे "एक्सेलेरेटेड एवरेजिंग" (accelerated averaging) कहा गया, मदद करने की कोशिश करता था। यह कुछ ऐसा था जैसे दोस्तों को कहना, "अपने पड़ोसी के वर्तमान विचार का औसत लें, और फिर उस परिणाम को अपने स्वयं के पिछले वोट के साथ मिलाएं।" इसने कुछ मामलों में चीज़ों को तेज़ करने में मदद की, लेकिन लेखकों ने पाया कि उन जिद्दी, गोलाकार नेटवर्कों में, यह विधि अभी भी दोलनों (oscillations) को रोकने में विफल रही। समूह अभी भी उस नृत्य में फंसा हुआ रहता।

समाधान: औसत को याद रखना

लेखक एक अलग रणनीति प्रस्तावित करते हैं। उनके नए MLA मॉडल में, एजेंट केवल अपनी वर्तमान स्थिति को अपनी पिछली स्थिति के साथ नहीं मिलाते हैं। इसके बजाय, वे पहले "स्थानीय औसत" (local average) की गणना करते हैं (जो वे पुराने डीग्रूट नियम का उपयोग करके करते) वर्तमान क्षण और पिछले क्षण दोनों के लिए। फिर, वे उन दोनों औसतों को एक साथ मिलाते हैं।

इसे उपयोग करने के लिए एक उपमा लें: कल्पना कीजिए कि एक समिति एक रंग तय करने की कोशिश कर रही है।

डीग्रूट मॉडल: हर कोई अपने पड़ोसियों के वर्तमान वोटों को देखता है, उनका औसत निकालता है, और एक नया वोट लिखता है।
पुराना एक्सेलेरेटेड मॉडल: हर कोई अपने पड़ोसियों के वर्तमान वोटों को देखता है, उनका औसत निकालता है, और फिर उस परिणाम को अपने स्वयं के पिछले वोट के साथ मिलाता है।
MLA मॉडल (नया विचार): हर कोई अपने पड़ोसियों के वर्तमान वोटों को देखता है और उनका औसत निकालता है। फिर, वे देखते हैं कि उन्होंने पिछली बार क्या गणना की थी (पिछले समय में उनके पड़ोसियों के वोटों का औसत) और वे उन दो संख्याओं को आपस में मिला देते हैं।

यह क्या याद रखा जा रहा है और मिलाया जा रहा है, इसमें सूक्ष्म बदलाव एक गेम-चेंजर साबित होता है।

निष्कर्ष: लूप को तोड़ना और गति बढ़ाना

यह पेपर कठोर गणित का उपयोग यह दिखाने के लिए करता है कि दो मुख्य बातें क्या हैं। पहला, उन नेटवर्कों के लिए जो "आवर्ती" (periodic) हैं (जैसे कि वह पूर्ण रिंग जहाँ डीग्रूट और पुराने एक्सेलेरेटेड मॉडल फंस जाते हैं), MLA मॉडल वास्तव में काम करता है। यह सिद्ध करता है कि सही मिश्रण पैरामीटर (जिसे $\gamma$ कहा जाता है) चुनकर, दोलन कम हो जाते हैं, और समूह एक स्थिर सहमति तक पहुँच जाता है। लेखक दिखाते हैं कि जब तक मिश्रण पैरामीटर 0 और 2 के बीच है (और नेटवर्क की संरचना से संबंधित एक विशिष्ट स्थिति को पूरा करता है), सिस्टम अभिसरण (converge) करेगा। यह एक बड़ी बात है क्योंकि इसका मतलब है कि नेटवर्क उन आकृतियों में भी सहमति बना सकता है जिन्हें पहले इन रैखिक विधियों के लिए असंभव माना जाता था।

दूसरा, यह पेपर जांच करता है कि समूह कितनी तेज़ी से सहमति तक पहुँचता है। वे MLA मॉडल की तुलना डीग्रूट मॉडल और पुराने एक्सेलेरेटेड मॉडल से करते हैं। "एसेंशियल स्पेक्ट्रल रेडियस" (essential spectral radius) की अवधारणा का उपयोग करते हुए (जो मूल रूप रूप से यह मापने का एक तरीका है कि त्रुटियाँ कितनी तेज़ी से कम होती हैं), वे दिखाते हैं कि कई नेटवर्कों के लिए, MLA मॉडल उन त्रुटियों को बहुत तेज़ी से कम करता है। अपने सिमुलेशन में, उन्होंने चार नोड्स वाले एक रिंग नेटवर्क का परीक्षण किया। जब उन्होंने 1,000 अलग-अलग रैंडम शुरुआती बिंदुओं से शुरुआत की, तो डीग्रूट और पुराने एक्सेलेरेटेड मॉडल अनंत काल तक झूलते रहे। हालाँकि, MLA मॉडल एक एकल, स्थिर उत्तर पर स्थिर हो गया।

इसके अलावा, लेखकों ने मिश्रण पैरामीटर $\gamma$ के लिए एक "स्वीट स्पॉट" (sweet spot) पाया। यदि आप इस संख्या को ठीक से ट्यून करते हैं, तो MLA मॉडल क्लासिक डीग्रूट मॉडल और पिछले एक्सेलेरेटेड मॉडल दोनों की तुलना में काफी तेज़ी से अभिसरण कर सकता है। उन्होंने इसे एक विशिष्ट उदाहरण के साथ प्रदर्शित किया: एक रिंग नेटवर्क जहाँ कुछ छोटे "सेल्फ-लूप्स" (स्वयं से जुड़ाव) जोड़े गए थे। इस सेटअप में, MLA मॉडल अन्य की तुलना में बहुत तेज़ी से आम सहमति तक पहुँचा।

निचोड़

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

तकनीकी सारांश: स्थानीय औसत की स्मृति (Memory of Local Averages) के माध्यम से मल्टी-एजेंट नेटवर्क में त्वरित सर्वसम्मति (Accelerated Consensus)

समस्या विवरण
मल्टी-एजेंट नेटवर्क में, वितरित औसत एल्गोरिदम (distributed averaging algorithms) स्थानीय गणनाओं के माध्यम से वैश्विक सर्वसम्मति (global consensus) तक पहुँचने के लिए आवश्यक हैं। शास्त्रीय डीग्रूट (DeGroote) मॉडल एक एजेंट की स्थिति को उसके पड़ोसियों की वर्तमान स्थितियों के भारित औसत (weighted average) के रूप में अपडेट करता है। हालांकि कई नेटवर्कों के लिए प्रभावी होने के बावजूद, डीग्रूट मॉडल धीमे अभिसरण (convergence) की समस्या से ग्रस्त है और महत्वपूर्ण रूप से, आवधिक नेटवर्कों (periodic networks) में अभिसरण करने में विफल रहता है (जहाँ एजेंट अनिश्चित काल तक दोलन करते रहते हैं)। मुथुकृष्णन और अन्य द्वारा प्रस्तावित एक पूर्व कार्य ने एक "त्वरित औसत" (accelerated averaging) मॉडल का सुझाव दिया था जो स्मृति (memory) को शामिल करने के लिए वर्तमान स्थिति पर डीग्रूट अपडेट करता है और फिर इसे पिछली स्थिति के साथ रैखिक रूप से संयोजित करता है। हालांकि, यह पूर्व मॉडल भी आवधिक नेटवर्कों में अभिसरण करने में विफल रहता है। यह शोध पत्र इन दोनों मॉडलों की सीमाओं को संबोधित करने के लिए एक संशोधन प्रस्तावित करता है जो आवधिक नेटवर्कों में अभिसरण प्राप्त करने और अ-आवधिक (aperiodic) नेटवर्कों में अभिसरण दरों को तेज करने के लिए स्थानीय औसत की स्मृति (MLA) का लाभ उठाता है।

कार्यप्रणाली (Methodology)
लेखक मेमोरी ऑफ लोकल एवरेज (MLA) मॉडल का प्रस्ताव करते हैं। पूर्व त्वरित मॉडल के विपरीत, जो वर्तमान स्थिति को डीग्रूट के माध्यम से अपडेट करता है और फिर इसे पिछली स्थिति के साथ मिलाता है, MLA मॉडल वर्तमान स्थिति $x(k)$ और पिछली स्थिति $x(k-1)$ दोनों पर डीग्रूट अपडेट लागू करता है ताकि मध्यवर्ती अवस्थाएं $z(k)$ और $z(k-1)$ उत्पन्न की जा सकें। अंतिम स्थिति $x(k+1)$ इन दो मध्यवर्ती अवस्थाओं का एक रैखिक संयोजन है:
$x(k+1) = \gamma A x(k) + (1-\gamma) A x(k-1)$
जहाँ $A$ एक रो-स्टोकेस्टिक (row-stochastic) भारित आसन्नता मैट्रिक्स (adjacency matrix) है और $\gamma$ एक वेटिंग पैरामीटर है।

अभिसरण का विश्लेषण करने के लिए, लेखक स्थिति $\hat{x}(k) = [x(k); x(k-1)]^T$ के साथ एक संवर्धित प्रणाली (augmented system) और एक संवर्धित पुनरावृत्ति मैट्रिक्स $\hat{A}$ का निर्माण करते हैं। वे $\hat{A}$ के आइगेनवैल्यू (eigenvalues) और मूल मैट्रिक्स $A$ के आइगेनवैल्यू ( $\lambda$ ) के बीच संबंध को व्युत्पन्न करने के लिए $\hat{A}$ का स्पेक्ट्रल विश्लेषण करते हैं। अभिसरण के गुणों को $\hat{A}$ के स्पेक्ट्रल रेडियस (spectral radius) द्वारा निर्धारित किया जाता है, विशेष रूप से यह सुनिश्चित करना कि प्रमुख आइगेनवैल्यू (जो 1 के बराबर है) को छोड़कर सभी आइगेनवैल्यू यूनिट डिस्क के भीतर हों।

मुख्य योगदान और परिणाम

आवधिक नेटवर्कों में अभिसरण (Convergence in Periodic Networks):
यह शोध पत्र स्थापित करता है कि MLA मॉडल अप्रत्यक्ष (undirected), संकलित (connected) और आवधिक नेटवर्कों में सर्वसम्मति प्राप्त कर सकता है, जो एक ऐसी स्थिति है जहाँ डीग्रूट मॉडल और मुथुकृष्णन और अन्य का त्वरित औसत मॉडल दोनों विफल हो जाते हैं (परिणामस्वरूप निरंतर दोलन होते हैं)।

थ्योरम 3 अर्ध-अभिसरण (semi-convergence) के लिए आवश्यक और पर्याप्त स्थितियाँ प्रदान करता है: $\gamma \in (0, 2)$ और $2\gamma\lambda_n - \lambda_n + 1 > 0$ , जहाँ $\lambda_n$ मैट्रिक्स $A$ का सबसे छोटा आइगेनवैल्यू है।
आवधिक नेटवर्कों के लिए, $\lambda_n = -1$ होता है। MLA मॉडल तब अभिसरण करता है जब $\gamma \in (0, 1)$ हो, जबकि पूर्व त्वरित मॉडल $\lambda_n = -1$ के आइगेनवेक्टर के साथ संरेखित किसी भी प्रारंभिक स्थिति के लिए अपसरण (diverge) करने के लिए सिद्ध होता है (लेम्मा 5)।

अ-आवधिक नेटवर्कों में त्वरित अभिसरण (Accelerated Convergence in Aperiodic Networks):
उन नेटवर्कों के लिए जहाँ तीनों मॉडल अभिसरण करते हैं (प्रिमिटिव, सिमेट्रिक, रो-स्टोकेस्टिक मैट्रिसेस), लेखक उन स्थितियों की पहचान करते हैं जिनमें MLA तेज़ अभिसरण प्रदान करता है।

डीग्रूट के साथ तुलना: लेम्मा 7 दिखाता है कि यदि $\lambda_2 + \lambda_n \neq 0$ है, तो एक ऐसा $\gamma$ मौजूद है जिससे MLA मॉडल का एसेंशियल स्पेक्ट्रल रेडियस (essential spectral radius), डीग्रूट मॉडल की तुलना में स्पष्ट रूप से छोटा है, जिसका अर्थ है तेज़ अभिसरण।
त्वरित औसत के साथ तुलना: थ्योरम 8 एक इष्टतम पैरामीटर $\gamma^*$ व्युत्पन्न करता है जो MLA मॉडल के एसेंशियल स्पेक्ट्रल रेडियस को न्यूनतम करता है। इस स्थिति के तहत कि $\lambda_2 \le |\lambda_n|/3$ और $\lambda_n < 0$ , MLA मॉडल $\rho_{ess}(\hat{A}) = \sqrt{1+\rho_{ess}(A)} - 1$ की दर से अभिसरण प्राप्त करता है। यह दर डीग्रूट मॉडल और इष्टतम रूप से ट्यून किए गए त्वरित औसत मॉडल दोनों की तुलना में स्पष्ट रूप से तेज़ है।

सर्वसम्मति मान (Consensus Value):
लेम्मा 6 प्रदर्शित करता है कि जब अभिसरण मानदंड पूरे होते हैं, तो MLA मॉडल उसी सर्वसम्मति मान पर अभिसरित होता है जिस पर डीग्रूट मॉडल अभिसरित होता है (मैट्रिक्स $A$ के लेफ्ट डोमिनेंट आइगेनवेक्टर द्वारा परिभाषित प्रारंभिक अवस्थाओं का भारित औसत), बशर्ते कि प्रारंभिक स्थितियाँ सुसंगत हों ( $x(0) = x(-1)$ )।

महत्व
यह शोध पत्र दावा करता है कि MLA मॉडल मौजूदा रैखिक सर्वसम्मति योजनाओं में एक सरल लेकिन शक्तिशाली संशोधन है। इसका प्राथमिक महत्व दो क्षेत्रों में है:

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

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

समस्या: अंतहीन नृत्य

समाधान: औसत को याद रखना

निष्कर्ष: लूप को तोड़ना और गति बढ़ाना

निचोड़

इसी तरह के और पेपर