तकनीकी सारांश: कई ओमेगा-रेगुलर (Omega-Regular) उद्देश्यों के लिए डीकप्ल्ड प्लानिंग (Decoupled Planning)

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

यह शोध पत्र एक परिमित निर्देशित ग्राफ (finite directed graph) पर ऐसे पथ (paths) उत्पन्न करने की समस्या को संबोधित करता है जो $\omega$-रेगुलर उद्देश्यों ($\phi_1, \dots, \phi_N$) के एक संग्रह को संतुष्ट करते हैं। पारंपरिक दृष्टिकोण सभी उद्देश्यों के संयोजन (conjunction) के लिए एक एकल, मोनोलिथिक पॉलिसी (monolithic policy) की गणना करके इसे हल करते हैं। यह कार्य एक डीकप्ल्ड फ्रेमवर्क (decoupled framework) प्रस्तावित करता है जहाँ $N$ स्वतंत्र एजेंटों को व्यक्तिगत उद्देश्यों के लिए सौंपा जाता है। प्रत्येक एजेंट $i$ अन्य एजेंटों के उद्देश्यों या नीतियों के ज्ञान के बिना $\phi_i$ को संतुष्ट करने के लिए एक स्थानीय नीति $\pi_i$ का चयन करता है। एक शेड्यूलर $\sigma$, जो ग्राफ संरचना और विशिष्ट उद्देश्यों से अनभिज्ञ है, अगले चरण में किस एजेंट द्वारा अगले वर्टेक्स (vertex) को निर्धारित किया जाएगा, इसका चयन करके इन नीतियों को गतिशील रूप से संयोजित करता है।

मुख्य चुनौती यह निर्धारित करना है कि किन परिस्थितियों में, एक शेड्यूलर द्वारा निर्देशित स्वतंत्र स्थानीय नीतियों का संयोजन, सभी उद्देश्यों के संयोजन ($\bigwedge \phi_i$) को लगभग-निश्चित रूप से (almost-surely) संतुष्ट करता है, यह मानते हुए कि ऐसा एक पथ मौजूद है। यह फ्रेमवर्क अधिकतम मॉडुलैरिटी (एजेंट स्वतंत्र रूप से नीतियां डिजाइन करते हैं) प्राप्त करने का लक्ष्य रखता है जबकि शुद्धता (correctness) सुनिश्चित करता है।

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

डीकप्ल्ड फ्रेमवर्क (The Decoupled Framework)

सिस्टम में शामिल हैं:

1. एजेंट (Agents): $N$ एजेंट, जिनमें से प्रत्येक एक उद्देश्य $\phi_i$ के लिए जिम्मेदार है।
2. नीतियां (Policies): एजेंट शेड्यूलिंग प्रक्रिया के बारे में अपने ज्ञान के आधार पर विशिष्ट वर्गों से नीतियां चुनते हैं:
   • पाथ-अवेयर (Path-aware): पारंपरिक नीतियां जो केवल पथ के इतिहास पर निर्भर करती हैं।
   • शेड्यूल-अवेयर (Scheduled-aware): वे नीतियां जिन्हें पता होता है कि पिछले चरणों में उन्हें शेड्यूल किया गया था या नहीं।
   • फुल हिस्ट्री-अवेयर (Full history-aware): वे नीतियां जिन्हें सटीक रूप से पता होता है कि प्रत्येक पिछले चरण में किस एजेंट को शेड्यूल किया गया था।
3. शेड्यूलर (Scheduler): एक स्टोकेस्टिक शेड्यूलर $\sigma$ जो प्रत्येक चरण पर एक एजेंट का चयन करता है। पेपर तर्क देता है कि नियत (deterministic) शेड्यूलर (अत्यधिक निष्पक्ष होने के बावजूद) सार्वभौमिक संयोजन के लिए अपर्याप्त हैं, जिसके लिए संभावabilistic निष्पक्षता गुणों वाले स्टोकेस्टिक शेड्यूलर की आवश्यकता होती है।

उद्देश्यों का अपघटन (Decomposition of Objectives)

लेखक $\omega$-रेगुलर उद्देश्यों को सेफ्टी (safety) और लाइवनेस (liveness) घटकों ($\phi = \phi_{safe} \cap \phi_{live}$) में विभाजित करते हैं।

• सेफ्टी (Safety): असुरक्षित अवस्थाओं (unsafe states) से बचने की आवश्यकता होती है। पेपर प्रदर्शित करता है कि बिना संचार के स्टोकेस्टिक शेड्यूलिंग के तहत सुरक्षा सुनिश्चित नहीं की जा सकती है। वे एक शील्डेड कंपोजिशन (shielded composition) प्रोटोकॉल पेश करते हैं जहाँ एजेंट प्रत्येक चरण में सुरक्षित क्रियाओं के सेट (अधिकतम परमिसिव नीतियां) का आदान-प्रदान करते हैं। निर्धारित एजेंट को सभी एजेंटों के सुरक्षित सेट्स के प्रतिच्छेदन (intersection) से एक क्रिया चुननी चाहिए। पारस्परिक सुरक्षा-समापन (mutual safety-closure) (प्रत्येक पथ का प्रीफिक्स जो व्यक्तिगत सुरक्षा बाधाओं को संतुष्ट करता है, उसे सभी को संतुष्ट करने के लिए विस्तारित किया जा सकता है) के अनुमान के तहत, यह प्रोटोकॉल सुरक्षा सुनिश्चित करता है।
• लाइवनेस (Liveness): अच्छे राज्यों पर अनंत बार या अंततः जाने की आवश्यकता होती है। एक बार जब सुरक्षा लागू हो जाती है (ग्राफ को सुरक्षित सबग्राफ तक सीमित करना), तो ध्यान लाइवनेस उद्देश्यों को संतुष्ट करने पर केंद्रित हो जाता है।

कन्वेंशन (Conventions)

चूंकि असंबद्ध (uncoordinated) नीतियां सरल उद्देश्यों (जैसे, स्ट्रॉन्गली कनेक्टेड ग्राफ में बुची (Büchi) उद्देश्य) के लिए भी विफल हो सकती हैं, इसलिए पेपर कन्वेंशन (conventions) पेश करता है। एक कन्वेंशन उद्देश्य वर्गों से पॉलिसी प्रकारों (जैसे, मेमोरी बाउंड्स, शेड्यूलिंग अवेयरनेस) पर प्रतिबंधों का एक मैपिंग है जिसे ग्राफ या उद्देश्यों के प्रकट होने से पहले पूर्व में सहमति दी गई है। यदि सभी एजेंट कन्वेंशन का पालन करते हैं, तो संयोजन लगभग-निश्चित रूप से सभी उद्देश्यों को संतुष्ट करने की गारंटी देता है।

मुख्य योगदान और परिणाम (Key Contributions and Results)

1. सार्वभौमिक नियत और असंबद्ध स्टोकेस्टिक शेड्यूलर की असंभवता

• नियत शेड्यूलर (Deterministic Schedulers): पेपर सिद्ध करता है कि कोई भी नियत शेड्यूलर सार्वभौमिक नहीं है। अत्यधिक निष्पक्षता (प्रत्येक एजेंट को अनंत बार शेड्यूल किया जाता है) के साथ भी, ऐसे ग्राफ और नीतियां मौजूद हैं जहाँ संयोजन उद्देश्यों को संतुष्ट करने में विफल रहता है (उदाहरण 1, प्रमेय 1)।
• असंबद्ध स्टोकेस्टिक शेड्यूलर (Uncoordinated Stochastic Schedulers): बुची उद्देश्यों के लिए, यदि एजेंट मनमानी नीतियों का उपयोग करते हैं तो स्टोकेस्टिक शेड्यूलर भी विफल हो जाते हैं। लेखक एक परिदृश्य का निर्माण करते हैं जहाँ एजेंट तेजी से बढ़ते "वेटिंग टाइम" वाली नीतियां उपयोग करते हैं (उदाहरण 2, प्रमेय 3)। एक स्टोकेस्टिक शेड्यूलर उस संभावना को दूर नहीं कर सकता जहाँ एजेंट एक-दूसरे के महत्वपूर्ण विंडोज़ (critical windows) को मिस कर देते हैं, जिससे संयोजन को लगभग-निश्चित रूप से संतुष्ट करने में विफलता होती है। यह रीचेबिलिटी (reachability) उद्देश्यों तक विस्तृत है (उपप्रमेय 1)।

2. शील्डेड कंपोजिशन के माध्यम से सेफ्टी (Safety via Shielded Composition)

पेपर स्थापित करता है कि सुरक्षा के लिए संचार की आवश्यकता होती है। वे एक प्रोटोकॉल प्रस्तावित करते हैं जहाँ एजेंट अपने सुरक्षित उत्तराधिकारियों (successors) के सेट प्रसारित करते हैं। निर्धारित एजेंट इन सेट्स के प्रतिच्छेदन से एक क्रिया चुनता है। प्रमेय 2 सिद्ध करता है कि यदि उद्देश्य पारस्परिक रूप से सुरक्षा-समापित (safety-closed) हैं, तो यह शील्डेड कंपोजिशन सुरक्षा घटक को लगभग-निश्चित रूप से संतुष्ट करता है, जिससे समस्या सुरक्षित सबग्राफ पर लाइवनेस में बदल जाती है।

3. लाइवनेस उद्देश्यों के लिए कन्वेंशन (Conventions for Liveness Objectives)

पेपर $\omega$-रेगुलर उद्देश्यों के प्रमुख उप-वर्गों के लिए न्यूनतम प्रतिबंधात्मक कन्वेंशन को स्पष्ट करता है:

• बुची उद्देश्य (Büchi Objectives):

  • कन्वेंशन: एजेंट फिनिट-मेमोरी पॉलिसीज (finite-memory policies) का उपयोग करते हैं (विशेष रूप से, लक्ष्य सेट के लिए समान रूप से सीमित अपेक्षित हिटिंग टाइम वाली नीतियां)।
  • परिणाम: प्रमेय 4 दिखाता है कि यदि सभी एजेंट ऐसी नीतियों का उपयोग करते हैं, तो एक स्टोकेस्टिक शेड्यूलर उन्हें सभी बुची उद्देश्यों को लगभग-निश्चित रूप से संतुष्ट करने के लिए संयोजित करता है। इसके लिए रनटाइम समन्वय या अन्य एजेंटों के ज्ञान की आवश्यकता नहीं है।

• को-बुची उद्देश्य (Co-Büchi Objectives):

  • चुनौती: सरल फिनिट-मेमोरी नीतियां अपर्याप्त हैं (प्रमेय 5)। एजेंटों को अंततः एक सामान्य चक्र (common cycle) पर अभिसरण (converge) करना होगा।
  • कन्वेंशन: एजेंट शेड्यूल-अवेयर नीतियां उपयोग करते हैं जो एक लासो-आकार के पथ (lasso-shaped path - एक अच्छे चक्र की ओर जाने वाला पथ) का "अनुमान" बनाए रखते हैं।
  • तंत्र: यदि एक एजेंट शेड्यूल नहीं किया गया है और अपने वर्तमान अनुमान के विपरीत एक ट्रांज़िशन देखता है, तो वह अनुमान को त्याग देता है और एक नया लासो पथ चुनता है।
  • परिणाम: प्रमेय 6 सिद्ध करता है कि यह प्रोटोकॉल लगभग-निश्चित रूप से एक सामान्य लासो पथ पर सहमति की ओर ले जाता है, जिससे सभी को-बुची उद्देश्यों को संतुष्ट किया जाता है।

• पैरिटी उद्देश्य (Parity Objectives):

  • चुनौती: पैरिटी उद्देश्य अधिक जटिल हैं; एक एकल सरल चक्र पर्याप्त नहीं हो सकता (लेम्मा 1)।
  • कन्वेंशन: एजेंट फुल हिस्ट्री-अवेयर नीतियां उपयोग करते हैं। प्रत्येक एजेंट आंतरिक मेमोरीलेस नीतियों के टुपल (tuple) को बनाए रखता है, जो स्वयं सहित प्रत्येक अन्य एजेंट की नीति का अनुमान लगाता है।
  • तंत्र: यदि एक एजेंट दूसरे एजेंट की नीति के अपने अनुमान के विपरीत ट्रांज़िशन देखता है, तो वह यादृच्छिक रूप से नीतियों के एक नए टुपल का चयन करता है।
  • परिणाम: प्रमेय 7 सिद्ध करता है कि यह प्रक्रिया एक सहमति अवस्था (consensus state) की ओर अभिसरित होती है जहाँ सभी एजेंट नीतियों के एक सेट पर सहमत होते हैं जो पैरिटी उद्देश्यों को लगभग-निश्चित रूप से संतुष्ट करते हैं।

महत्व और दावे (Significance and Claims)

पेपर दावा करता है कि यह $\omega$-रेगुलर निर्णय लेने के लिए प्रथम-प्रकार के मॉड्यूलर डिजाइन फ्रेमवर्क की नींव स्थापित करता है। इसका महत्व निम्नलिखित में निहित है:

1. मॉड्यूलरिटी और मजबूती (Modularity and Robustness): यह पॉलिसी डिजाइन के लिए 'सेपरेशन ऑफ कंसर्न' (separation of concerns) को सक्षम बनाता है। यदि एजेंट तय किए गए कन्वेंशन का पालन करते हैं, तो पूरे सिस्टम को पुन: कंप्यूट किए बिना स्वतंत्र रूप से नीतियां डिजाइन की जा सकती हैं, जोड़ी जा सकती हैं, हटाई जा सकती हैं या संशोधित की जा सकती हैं।
2. लाइटवेट रनटाइम (Lightweight Runtime): शेड्यूलर सरल और स्टोकेस्टिक हैं, जो सीमित प्रसंस्करण क्षमता वाले उपकरणों (जैसे रोबोट, ड्रोन) के लिए उपयुक्त हैं।
3. सैद्धांतिक सीमाएं (Theoretical Limits): यह उद्देश्य वर्ग की जटिलता और एजेंटों के बीच आवश्यक समन्वय (शेड्यूलर अवेयरनेस) के बीच के ट्रेड-ऑफ को कठोरता से परिभाषित करता है।
   • बुची: केवल पाथ-अवेयर नीतियों की आवश्यकता है।
   • को-बुची: शेड्यूलिंग स्थिति के ज्ञान (शेड्यूल-अवेयर) की आवश्यकता है।
   • पैरिटी: किस एजेंट को शेड्यूल किया गया था, इसके ज्ञान (फुल हिस्ट्री-अवेयर) की आवश्यकता है।
4. सेफ्टी बनाम लाइवनेस (Safety vs. Liveness): यह स्पष्ट करता है कि जबकि लाइवनेस को कन्वेंशन के माध्यम से संभावabilistic अभिसरण (probabilistic convergence) द्वारा प्राप्त किया जा सकता है, सुरक्षा के लिए प्रत्येक पथ पर नियत शुद्धता सुनिश्चित करने के लिए मौलिक रूप से एक संचार प्रोटोकॉल (शील्डेड कंपोजिशन) की आवश्यकता होती है।

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