2025-11-23T10:46:16.032830

Strategy Templates for Almost-Sure and Positive Winning of Stochastic Parity Games towards Permissive and Resilient Control

Phalakarn, Pruekprasert, Hasuo
Stochastic games are fundamental in various applications, including the control of cyber-physical systems (CPS), where both controller and environment are modeled as players. Traditional algorithms typically aim to determine a single winning strategy to develop a controller. However, in CPS control and other domains, permissive controllers are essential, as they enable the system to adapt when additional constraints arise and remain resilient to runtime changes. This work generalizes the concept of (permissive winning) strategy templates, originally introduced by Anand et al. at TACAS and CAV 2023 for deterministic games, to incorporate stochastic games. These templates capture an infinite number of winning strategies, allowing for efficient strategy adaptation to system changes. We focus on two winning criteria (almost-sure and positive winning) and five winning objectives (safety, reachability, Büchi, co-Büchi, and parity). Our contributions include algorithms for constructing templates for each winning criterion and objective and a novel approach for extracting a winning strategy from a given template. Discussions on comparisons between templates and between strategy extraction methods are provided.
academic

स्टोकेस्टिक पैरिटी गेम्स के लिए लगभग-निश्चित और सकारात्मक जीत की रणनीति टेम्पलेट: अनुमतिशील और लचीले नियंत्रण की ओर

मूल जानकारी

  • पेपर ID: 2409.08607
  • शीर्षक: Strategy Templates for Almost-Sure and Positive Winning of Stochastic Parity Games towards Permissive and Resilient Control
  • लेखक: Kittiphon Phalakarn, Sasinee Pruekprasert, Ichiro Hasuo
  • वर्गीकरण: eess.SY cs.LO cs.SY
  • प्रकाशन समय: सितंबर 2024 (arXiv v2: 16 अक्टूबर 2025)
  • पेपर लिंक: https://arxiv.org/abs/2409.08607

सारांश

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

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या पृष्ठभूमि

  1. पारंपरिक विधि की सीमाएं: पारंपरिक गेम समाधान एल्गोरिदम आमतौर पर केवल एकल जीत रणनीति खोजते हैं, रणनीति की अनुमतिशीलता (permissiveness) पर विचार नहीं करते
  2. व्यावहारिक अनुप्रयोग की आवश्यकता: साइबर-फिजिकल सिस्टम नियंत्रण में, अतिरिक्त बाधाओं को अनुकूलित करने और रनटाइम परिवर्तनों को संभालने के लिए अनुमतिशील नियंत्रकों की आवश्यकता होती है
  3. लचीले नियंत्रण की आवश्यकता: सिस्टम को विफलताओं या पर्यावरणीय परिवर्तनों का सामना करते समय मजबूत रहने की आवश्यकता है

अनुसंधान प्रेरणा

  • मौजूदा रणनीति टेम्पलेट अवधारणा केवल नियतात्मक गेम्स पर लागू होती है, स्टोकेस्टिक गेम्स के लिए समर्थन की कमी है
  • अनंत संख्या में जीत रणनीतियों को पकड़ने में सक्षम ढांचे की आवश्यकता है, जो तेजी से रणनीति अनुकूलन का समर्थन करे
  • CPS नियंत्रण जैसे व्यावहारिक अनुप्रयोगों में, अनुमतिशीलता और लचीलापन मुख्य आवश्यकताएं हैं

मुख्य योगदान

  1. लगभग निश्चित जीत रणनीति टेम्पलेट एल्गोरिदम: पांच जीत उद्देश्यों (सुरक्षा, पहुंच, Büchi, co-Büchi, समता) के लिए लगभग निश्चित जीत रणनीति टेम्पलेट निर्माण एल्गोरिदम प्रस्तावित किए
  2. सकारात्मक संभावना जीत रणनीति टेम्पलेट: सकारात्मक संभावना जीत मानदंड के तहत रणनीति टेम्पलेट निर्माण और संयोजन एल्गोरिदम विकसित किए
  3. रणनीति टेम्पलेट तुलना ढांचा: अनुमतिशीलता और आकार के आधार पर टेम्पलेट तुलना के लिए चर्चा प्रदान की
  4. रणनीति निष्कर्षण विधि: दिए गए टेम्पलेट से जीत रणनीति निकालने के लिए नई विधि प्रस्तावित की, जो जीत उद्देश्य और अनुमतिशीलता को संतुलित करती है

विधि विवरण

कार्य परिभाषा

स्टोकेस्टिक गेम परिभाषा: स्टोकेस्टिक गेम G = (V, E, (V□, V○, V△)), जहां:

  • V शीर्ष समुच्चय है, E किनारा समुच्चय है
  • V□, V○, V△ क्रमशः Even खिलाड़ी, Odd खिलाड़ी और Random खिलाड़ी के शीर्षों को दर्शाते हैं
  • इसे "2.5" खिलाड़ी गेम कहा जाता है, जिसमें दो मुख्य खिलाड़ी और एक यादृच्छिक खिलाड़ी होते हैं

रणनीति टेम्पलेट परिभाषा: T = (P, L, C), जहां:

  • P ⊆ E□ निषिद्ध किनारों का समुच्चय है
  • L ⊆ 2^E□ सक्रिय समूहों का समुच्चय है
  • C ⊆ E□ सह-सक्रिय किनारों का समुच्चय है

मॉडल आर्किटेक्चर

1. लगभग निश्चित जीत रणनीति टेम्पलेट निर्माण

सुरक्षा उद्देश्य (G X):

SafetyTemplate(G, X):
1. W□ ← νY.(X ∩ (Pre□(Y) ∪ Pre(Y)))
2. P ← Edges□(W□, V \ W□)
3. return (P, ∅, ∅)

पहुंच उद्देश्य (F X):

ReachabilityTemplate(G, X):
1. A ← Attr'(X)
2. W□ ← Attr'□(A)
3. P ← Edges□(W□, V \ W□)
4. C ← Edges□(W□ \ A, W□ \ A)
5. return (P, ∅, C)

Büchi उद्देश्य (GF X): LiveGroups फ़ंक्शन के माध्यम से सक्रिय समूहों का निर्माण, यह सुनिश्चित करते हुए कि पथ लक्ष्य समुच्चय को अनंत बार देखते हैं।

समता उद्देश्य:

  1. स्टोकेस्टिक गेम को नियतात्मक गेम में कम करें (Reduce एल्गोरिदम का उपयोग करके)
  2. नियतात्मक गेम की रणनीति टेम्पलेट का निर्माण करें
  3. स्टोकेस्टिक गेम की टेम्पलेट में वापस रूपांतरित करें

2. सकारात्मक संभावना जीत रणनीति टेम्पलेट निर्माण

PositiveTemplate(G, φ):
1. W□, W○ और लगभग निश्चित जीत टेम्पलेट T^(a) की गणना करें
2. W? ← V \ (W□ ∪ W○)
3. P^(p) ← P^(a) ∪ Edges□(W?, W○)
4. C^(p) ← C^(a) ∪ Edges□(W?, W?)
5. return T^(p) = (P^(p), L^(p), C^(p))

तकनीकी नवाचार बिंदु

  1. समुच्चय संचालन विस्तार: Random खिलाड़ी पर विचार करने वाले नए समुच्चय संचालक परिचय, जैसे Pre△(X', X) और Attr'□(X)
  2. टेम्पलेट संयोजन एल्गोरिदम: संघर्ष पहचान तंत्र प्रस्तावित किया, जब टेम्पलेट संघर्ष करते हैं तो पुनः गणना करें
  3. पैरामीटरीकृत रणनीति निष्कर्षण: अनुमतिशीलता और लक्ष्य प्राप्ति गति को संतुलित करने के लिए पैरामीटर α और β का उपयोग करें
  4. सकारात्मक संभावना जीत विस्तार: पहली बार रणनीति टेम्पलेट को सकारात्मक संभावना जीत मानदंड तक विस्तारित किया

प्रायोगिक सेटअप

सैद्धांतिक सत्यापन

पेपर मुख्य रूप से सैद्धांतिक प्रमाण के माध्यम से एल्गोरिदम की सही्ता को सत्यापित करता है, जिसमें शामिल हैं:

  • विभिन्न टेम्पलेट निर्माण एल्गोरिदम की सही्ता प्रमेय
  • रणनीति निष्कर्षण विधि की अनुमतिशीलता प्रमेय
  • टेम्पलेट संयोजन एल्गोरिदम की सही्ता प्रमाण

जटिलता विश्लेषण

  • रणनीति निर्माण एल्गोरिदम का सबसे खराब स्थिति रनटाइम मानक एल्गोरिदम से मेल खाता है
  • टेम्पलेट संयोजन और रणनीति निष्कर्षण रनटाइम पर कुशलतापूर्वक निष्पादित किए जा सकते हैं

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

सैद्धांतिक परिणाम

प्रमेय 10-14: विभिन्न जीत उद्देश्यों के लिए रणनीति टेम्पलेट निर्माण एल्गोरिदम की सही्ता प्रमाणित की

  • SafetyTemplate द्वारा निर्मित टेम्पलेट G X के लिए लगभग निश्चित रूप से जीत है
  • ReachabilityTemplate द्वारा निर्मित टेम्पलेट F X के लिए लगभग निश्चित रूप से जीत है
  • इसी तरह अन्य उद्देश्यों पर लागू होता है

प्रमेय 18: PositiveTemplate द्वारा निर्मित टेम्पलेट लगभग निश्चित रूप से जीत और सकारात्मक संभावना जीत दोनों है

प्रमेय 27: पैरामीटरीकृत निष्कर्षण विधि मूल Extract विधि की तुलना में अधिक अनुमतिशील है

अनुमतिशीलता विश्लेषण

प्रस्ताव 22: यदि P ⊇ P', L ⊇ L', C ⊇ C', तो T, T' से अधिक अनुमतिशील नहीं है

प्रस्ताव 23: यदि T, T' से अधिक अनुमतिशील नहीं है और T' जीत है, तो T भी जीत है

व्यावहारिक अनुप्रयोग क्षमता

पेपर इंगित करता है कि नियतात्मक गेम्स के आधार पर प्रायोगिक परिणामों के अनुसार, रणनीति टेम्पलेट वृद्धिशील संश्लेषण में कम से कम 2 गुना त्वरण प्राप्त कर सकते हैं, और सहनशील नियंत्रण में यहां तक कि 30% विकल्पों के निषिद्ध होने पर भी पुनः गणना को प्रभावी ढंग से कम कर सकते हैं।

संबंधित कार्य

शास्त्रीय अनुमतिशीलता सिद्धांत

  • Ramadge और Wonham (1987) ने पर्यवेक्षी नियंत्रण में अनुमतिशीलता अवधारणा को औपचारिक रूप से प्रस्तुत किया
  • Bernet आदि ने समता गेम्स में अधिकतम अनुमतिशील रणनीति के अस्तित्व को प्रमाणित किया

रणनीति टेम्पलेट विकास

  • Anand आदि ने TACAS और CAV 2023 में नियतात्मक गेम्स के लिए रणनीति टेम्पलेट प्रस्तुत किए
  • यह कार्य रणनीति टेम्पलेट को स्टोकेस्टिक गेम्स तक विस्तारित करने वाला पहला अनुसंधान है

स्टोकेस्टिक गेम्स समाधान

  • Chatterjee आदि की स्टोकेस्टिक समता गेम्स कमी विधि
  • Banerjee आदि द्वारा स्टोकेस्टिक गेम्स के लिए समुच्चय संचालक

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. रणनीति टेम्पलेट अवधारणा को नियतात्मक गेम्स से स्टोकेस्टिक गेम्स तक सफलतापूर्वक विस्तारित किया
  2. पूर्ण एल्गोरिदम ढांचा प्रदान किया, जो दो जीत मानदंड और पांच जीत उद्देश्यों को कवर करता है
  3. नई रणनीति निष्कर्षण विधि सही्ता की गारंटी देते हुए अनुमतिशीलता में सुधार करती है

सीमाएं

  1. सकारात्मक संभावना जीत रणनीति इष्टतम संभावना की गारंटी नहीं देती
  2. एल्गोरिदम कार्यान्वयन और प्रायोगिक सत्यापन अभी बाकी है
  3. केवल परिमित अवस्था गेम्स पर विचार किया गया है

भविष्य की दिशाएं

  1. समान अनुमतिशीलता बनाए रखते हुए छोटे टेम्पलेट का निर्माण
  2. मेट्रिक समय तर्क (MTL) सूत्रों द्वारा परिभाषित उद्देश्यों तक विस्तार
  3. वास्तविक समय प्रणालियों पर अनुप्रयोग

गहन मूल्यांकन

लाभ

  1. महत्वपूर्ण सैद्धांतिक योगदान: पहली बार रणनीति टेम्पलेट को स्टोकेस्टिक गेम्स तक विस्तारित किया, सैद्धांतिक ढांचा संपूर्ण है
  2. उचित एल्गोरिदम डिजाइन: मौजूदा समुच्चय संचालन और कमी तकनीकों का कुशलतापूर्वक उपयोग
  3. व्यापक अनुप्रयोग संभावनाएं: साइबर-फिजिकल सिस्टम नियंत्रण के लिए महत्वपूर्ण व्यावहारिक महत्व
  4. गणितीय कठोरता: पूर्ण सही्ता प्रमाण प्रदान किए

कमियां

  1. प्रायोगिक सत्यापन की कमी: मुख्य रूप से सैद्धांतिक कार्य, वास्तविक कार्यान्वयन और प्रदर्शन मूल्यांकन की कमी
  2. इष्टतमता समस्या: सकारात्मक संभावना जीत रणनीति इष्टतमता की गारंटी नहीं देती
  3. अपर्याप्त जटिलता विश्लेषण: वास्तविक कम्प्यूटेशनल जटिलता का विश्लेषण अपेक्षाकृत संक्षिप्त है

प्रभाव

  1. शैक्षणिक मूल्य: स्टोकेस्टिक गेम्स सिद्धांत के लिए नई उपकरण और विधियां प्रदान करता है
  2. व्यावहारिक मूल्य: अनुमतिशील नियंत्रक डिजाइन के लिए सैद्धांतिक आधार प्रदान करता है
  3. विस्तारशीलता: भविष्य के अनुसंधान के लिए अच्छा आधार ढांचा प्रदान करता है

लागू परिदृश्य

  1. साइबर-फिजिकल सिस्टम का मजबूत नियंत्रण
  2. अनुकूलन की आवश्यकता वाली स्वचालित प्रणालियां
  3. बहु-उद्देश्य अनुकूलन नियंत्रण प्रणाली डिजाइन
  4. सहनशील नियंत्रण प्रणालियां

संदर्भ

पेपर 35 संबंधित संदर्भों का हवाला देता है, मुख्य रूप से शामिल हैं:

  • गेम सिद्धांत मूल साहित्य
  • पर्यवेक्षी नियंत्रण सिद्धांत
  • रणनीति टेम्पलेट संबंधित कार्य
  • स्टोकेस्टिक गेम्स समाधान एल्गोरिदम
  • रैखिक समय तर्क और मॉडल जांच

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