⚡ electrical engineering

Time-Varying Reach-Avoid Control Certificates for Stochastic Systems

यह शोधपत्र निरंतर अवस्था और क्रिया स्थानों वाले डिस्क्रीट-टाइम स्टोकेस्टिक सिस्टम के लिए सुरक्षा को सत्यापित करने और लक्ष्य-प्राप्ति की संभावनाओं को अधिकतम करने हेतु समय-परिवर्ती (time-varying) और समय-अपरिवर्तनीय (time-invariant) रीच-अवॉयड प्रमाणपत्रों (reach-avoid certificates) को संश्लेषित करने के लिए एक सम-ऑफ-स्क्वायर्स (sum-of-squares) अनुकूलन ढांचे को प्रस्तुत करता है।

मूल लेखक: Rayan Mazouz, Luca Laurenti, Morteza Lahijanian

प्रकाशित 2026-03-30

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

CC BY 4.0

मूल लेखक: Rayan Mazouz, Luca Laurenti, Morteza Lahijanian

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

कल्पना कीजिए कि आप एक बहुत ही घबराए हुए, थोड़े नशे में धुत रोबोट को एक भीड़भाड़ वाले, अप्रत्याशित भूलभुलैया (maze) के माध्यम से मार्गदर्शन करने की कोशिश कर रहे हैं। रोबोट का एक लक्ष्य है (एक खजाना), लेकिन वहां खतरनाक गड्ढे (असुरक्षित क्षेत्र) भी हैं जिनसे उसे बचना है। पेच यह है कि रोबोट केवल अपने आप नहीं चलता; फर्श फिसलन भरा है, और हवा के अचानक झोंके (शोर/noise) उसे रास्ते से भटका देते हैं।

आपका काम रोबोट को निर्देशों का एक सेट (एक कंट्रोलर) देना है जो यह गारंटी दे सके कि वह उस सारी उथल-पुथल के बावजूद खजाना ढूंढ लेगा और गड्ढे में नहीं गिरेगा।

यह शोध पत्र (paper) ठीक इसी समस्या को हल करने के लिए एक नया, शक्तिशाली गणितीय उपकरण पेश करता है। यहाँ इसका सरल विवरण दिया गया है:

1. समस्या: "क्या होगा अगर" वाला दुःस्वप्न

वास्तविक दुनिया में, सिस्टम (जैसे सेल्फ-ड्राइविंग कार या ड्रोन) कभी भी पूरी तरह से अनुमानित नहीं होते। वे स्टोकेस्टिक (stochastic) होते हैं, जिसका अर्थ है कि उनमें यादृच्छिकता (randomness) शामिल होती है।

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

2. समाधान: "सुरक्षा प्रमाणपत्र" (Safety Certificate)

एक सर्टिफिकेट को कागज के टुकड़े के रूप में नहीं, बल्कि पूरे भूलभुलैया को कवर करने वाले एक जादुई थर्मामीटर या हाइट मैप (ऊंचाई के मानचित्र) के रूप में सोचें।

लक्ष्य: हम यह सिद्ध करना चाहते हैं कि यदि रोबोट "ग्रीन ज़ोन" (प्रारंभिक सेट) में शुरू होता है, तो वह "रेड ज़ोन" (असुरक्षित) को छुए बिना अंततः "गोल्ड ज़ोन" (लक्ष्य) तक पहुँच जाएगा।
थर्मामीटर कैसे काम करता है:
- यदि रोबोट गोल्ड ज़ोन में है, तो थर्मामीटर उच्च (जैसे 100°C) दिखाएगा।
- यदि रोबोट रेड ज़ोन में है, तो थर्मामीटर निम्न (जैसे 0°C) दिखाएगा।
- यदि रोबोट सुरक्षित मध्य क्षेत्र में है, तो थर्मामीटर एक संख्या देता है जो भविष्यवाणी करती है: "जहाँ आप अभी हैं और हवा के बहने के आधार पर, आपके पास रेड ज़ोन से टकराने से पहले गोल्ड ज़ोन तक पहुँचने की कम से कम 90% संभावना है।"

यदि हम एक ऐसा थर्मामीटर फंक्शन खोज सकते हैं जो इन नियमों का पालन करता है, तो हमने गणितीय रूप से सिद्ध कर दिया है कि रोबोट सुरक्षित है। हमें हर संभावित पथ का सिमुलेशन करने की आवश्यकता नहीं है; थर्मामीटर एक साथ सभी पथों के लिए इसे सिद्ध करता है।

3. सर्टिफिकेट के दो प्रकार

यह पेपर इस थर्मामीटर को बनाने के दो तरीके पेश करता है:

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

पेपर की बड़ी जीत: लेखक दिखाते हैं कि उच्च-आयामी (high-dimensional), जटिल प्रणालियों (जैसे एक 3D ड्रोन) के लिए, टाइम-वेरिंग (समय-परिवर्तित) दृष्टिकोण विजेता है। यह ऐसा है जैसे यह महसूस करना कि एक एकल स्थिर मानचित्र तूफान में नेविगेट करने के लिए बहुत धुंधला है, लेकिन यात्रा के प्रत्येक सेकंड के लिए त्वरित, सरल स्नैपशॉट की एक श्रृंखला आपको एक स्पष्ट तस्वीर देती है।

4. सीक्रेट सॉस: "सम-ऑफ-स्क्वायर्स" (SOS)

हम इन जादुई थर्मामीटरों को वास्तव में कैसे खोजते हैं? यह पेपर सम-ऑफ-स्क्वायर्स (SOS) ऑप्टिमाइज़ेशन नामक एक गणितीय ट्रिक का उपयोग करता है।

उपमा (Analogy): एक ऐसे वक्र (curve) को खोजने की कल्पना करें जो एक निश्चित रेखा से ऊपर रहता है। वक्र का अनुमान लगाने के बजाय, आप इसे मजबूर करते हैं कि यह "वर्गों" (गणितीय रूप से, ऐसी चीजें जो हमेशा सकारात्मक होती हैं) से बना हो।
क्यों महत्वपूर्ण है: यह एक अव्यवस्थित, असंभव दिखने वाली पहेली को एक व्यवस्थित लेगो (Lego) सेट में बदल देता है। आप मानक, शक्तिशाली कंप्यूटर सॉल्वर का उपयोग करके इन टुकड़ों को आपस में जोड़ सकते हैं और तुरंत सटीक सर्टिफिकेट और कंट्रोलर पा सकते हैं। यह "अनुमान लगाने" को "हल करने" में बदल देता है।

5. परिणाम: रोबोट का मस्तिष्क बनाना

यह पेपर केवल यह जाँच नहीं करता कि रोबोट सुरक्षित है या नहीं; यह उसी समय रोबोट का मस्तिष्क (कंट्रोलर) बनाता है।

उन्होंने 1D लाइनों से लेकर 3D एयरक्राफ्ट मॉडल तक सब कुछ पर परीक्षण किया।
परिणाम: उनकी विधि ने सिद्ध किया कि रोबोट हवा और शोर के बावजूद 99% निश्चितता (या उससे अधिक) के साथ अपने लक्ष्यों तक पहुँच सकते हैं।
तुलना: जब उन्होंने अपने "टाइम-वेरिंग" तरीके की तुलना पुराने "टाइम-इनवेरिएंट" तरीकों से की, तो उनका नया तरीका एक साइकिल से स्पोर्ट्स कार में अपग्रेड करने जैसा था। इसने उन सुरक्षित रास्तों को खोज निकाला जहाँ पुराने तरीकों ने हार मान ली थी या कहा था कि "मुझे नहीं पता।"

सारांश

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

यह यह सब करता है:

एक गतिशील सुरक्षा स्कोर (सर्टिफिकेट) बनाकर जो समय के साथ बदलता है।
गणितीय लेगो ब्लॉक्स (SOS) का उपयोग करके इसे कुशलतापूर्वक हल करना।
यह सिद्ध करना कि जटिल, वास्तविक दुनिया की प्रणालियों के लिए, एक-एक कदम भविष्य की ओर देखना (टाइम-वेरिंग) एक एकल स्थिर नियम का उपयोग करने की तुलना में बहुत बेहतर है।

यह अंधेरे जंगल में आपके बचने की उम्मीद करने और एक चमकते हुए, रियल-टाइम GPS होने के बीच का अंतर है जो गारंटी देता है कि आप बाहर निकलने का रास्ता ढूंढ लेंगे।

यहाँ शोध पत्र "Time-Varying Reach-Avoid Control Certificates for Stochastic Systems" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र बहुपद गतिकी (polynomial dynamics) वाले डिस्क्रीट-टाइम, कंटीन्यूअस-स्पेस स्टोकेस्टिक सिस्टम्स के लिए रीच-अवॉयड (Reach-Avoid) समस्या का समाधान करता है। सिस्टम को इस प्रकार परिभाषित किया गया है:
$x_{k+1} = f(x_k, u_k, w_k)$
जहाँ $x$ अवस्था (state) है, $u$ नियंत्रण इनपुट (control input) है, और $w$ एक i.i.d. स्टोकेस्टिक विक्षोभ (stochastic disturbance) है।

उद्देश्य यह सुनिश्चित करना है कि $X_0$ के प्रारंभिक सेट से शुरू होने वाले प्रक्षेपवक्र (trajectories) एक क्षितिज (horizon) $H$ (परिमित या अनंत) के भीतर लक्ष्य सेट $X_r$ तक पहुँचें, जबकि एक असुरक्षित सेट $X_u$ (जहाँ $X_u = X \setminus X_s$ , और $X_s$ सुरक्षित सेट है) से बचते रहें।

यह शोध पत्र दो विशिष्ट समस्याओं पर काम करता है:

सत्यापन (Verification): एक नियंत्रक (controller) $\pi$ दिए जाने पर, यह सत्यापित करना कि रीच-अवॉयड गुण को संतुष्ट करने की प्रायिकता (probability) एक थ्रेशोल्ड $\delta$ से कम नहीं है।
नियंत्रण संश्लेषण (Control Synthesis): एक फीडबैक नियंत्रक $\pi^*$ को संश्लेषित करना जो रीच-अवॉयड प्रायिकता के निचले स्तर (lower bound) को अधिकतम करता है।

चुनौतियाँ: निरंतर अवस्था/क्रिया स्थानों (continuous state/action spaces), गैर-रेखीय गतिकी, स्टोकेस्टिक अनिश्चितता, और सुरक्षा एवं पहुँच (reachability) के बारे में एक साथ तर्क करने की आवश्यकता के कारण यह समस्या गणनात्मक रूप से अव्यवहार्य (intractable) है। मौजूदा विधियाँ अक्सर परिमित एब्स्ट्रैक्शन (finite abstractions) पर निर्भर करती हैं (जो 'कर्स ऑफ डायमेंशनलिटी' से ग्रस्त होती हैं) या डीप लर्निंग (जिसमें औपचारिक गारंटी का अभाव होता है) पर निर्भर करती हैं।

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

लेखक एक प्रमाण-आधारित ढांचा (certificate-based framework) प्रस्तावित करते हैं जो डायनेमिक प्रोग्रामिंग (DP) और सम-ऑफ-स्क्वायर्स (SOS) ऑप्टिमाइज़ेशन पर आधारित है।

A. रीच-अवॉयड प्रमाणपत्र (Reach-Avoid Certificates)

सटीक वैल्यू फंक्शन (value function) की गणना करने के बजाय (जो अव्यवहार्य है), लेखक वास्तविक-मान वाले फलनों (प्रमाणपत्रों) को पेश करते हैं जो रीच-अवॉयड प्रायिकता का एक रूढ़िवादी निचला स्तर (conservative lower bound) प्रदान करते हैं। वे दो स्वरूप प्रस्तावित करते हैं:

समय-परिवर्ती प्रमाणपत्र (Time-Varying Certificates - $R(x, k)$ ):
- यह परिमित और अनंत दोनों क्षितिजों के लिए लागू है।
- प्रमाणपत्र समय चरणों $k$ के साथ विकसित होता है।
- शर्तें: फलन को $X_r$ (लक्ष्य), $X_u$ (असुरक्षित), और $X_0$ (प्रारंभिक) पर सीमा शर्तों (boundary conditions) के साथ-साथ अगले चरण के अपेक्षित मान (expected value) से जुड़ी एक पुनरावर्ती असमानता (recursive inequality) को संतुष्ट करना चाहिए।
- रिलैक्सेशन (Relaxation): निरंतर बहुपदों के साथ सटीक इंडिकेटर फंक्शन (0 या 1) को लागू करने की कठिनाई को संभालने के लिए, लेखक बाधाओं को शिथिल करने के लिए स्लैक वेरिएबल्स ( $\alpha, \beta$ ) पेश करते हैं। यह सुनिश्चित करता है कि अनुकूलन समस्या व्यवहार्य (feasible) बनी रहे।
- परिणाम: प्रायिकता $\gamma - (\alpha_H + \sum \beta_i)$ द्वारा निम्न-बद्ध (lower-bounded) है।
समय-अपरिवर्तित प्रमाणपत्र (Time-Invariant Certificates - $R(x)$ ):
- सभी समय चरणों के लिए एक ही फलन का उपयोग करता है।
- गणनात्मक रूप से सरल लेकिन संभावित रूप से अधिक रूढ़िवादी।
- अनंत क्षितिज के लिए, यह सुपरमार्टिंगेल-जैसे गुणों पर निर्भर करता है।
- परिणाम: प्रायिकता $\gamma - \alpha - H\beta$ (परिमित) या $\gamma - \alpha$ (अनंत) द्वारा निम्न-बद्ध है।

B. SOS ऑप्टिमाइज़ेशन ढांचा

कार्यात्मक अनुकूलन को व्यावहारिक बनाने के लिए, लेखक प्रमाणपत्रों (और नियंत्रकों) को बहुपद फलनों (polynomial functions) तक सीमित करते हैं।

सत्यापन: प्रमाणपत्रों की शर्तों को SOS रिलैक्सेशन और पुटिनार के पॉजिटिवस्टेलनेस्टज़ (Putinar's Positivstellensatz) का उपयोग करके सेमीडेफिनेट प्रोग्रामिंग (SDP) बाधाओं में अनुवादित किया जाता है। यह समस्या को एक अभेद्य (convex) अनुकूलन समस्या में बदल देता है।
संयुक्त संश्लेषण (Joint Synthesis): नियंत्रक संश्लेषण के लिए, लेखक एक मिन-मैक्स समस्या (नियंत्रक मापदंडों पर न्यूनतम करना, सबसे खराब स्थिति वाले राज्यों पर अधिकतम करना) तैयार करते हैं। वे एक ड्यूल SOS रिलैक्सेशन (मोमेंट मैट्रिसेस पर आधारित) का उपयोग करते हैं ताकि इस गैर-कॉन्वेक्स मिन-मैक्स समस्या को एक कॉन्वेक्स SOS प्रोग्राम में बदला जा सके। यह इष्टतम नियंत्रक और उसके प्रमाणपत्र के सह-संश्लेषण (simultaneous synthesis) की अनुमति देता है।

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

एकीकृत प्रमाणपत्र ढांचा: स्टोकेस्टिक सिस्टम के लिए रीच-अवॉयड प्रमाणपत्रों का एक नवीन प्रारूप जो समय-परिवर्ती (time-varying) और समय-अपरिवर्तित (time-invariant) दोनों मामलों को कवर करता है, और परिमित एवं अनंत क्षितिज के लिए लागू है।
कॉन्वेक्स संश्लेषण: SOS ऑप्टिमाइज़ेशन का उपयोग करके फीडबैक नियंत्रक और प्रमाणपत्र को संयुक्त रूप से संश्लेषित करने की एक विधि, जो गैर-कॉन्वेक्स ह्यूरिस्टिक्स या डीप लर्निंग की आवश्यकता को समाप्त करती है।
रिलैक्सेशन के माध्यम से बेहतर बाउंड्स: स्लैक वेरिएबल्स ( $\alpha, \beta$ ) का परिचय व्यवहार्य SOS फॉर्मुलेशन की अनुमति देता है जो पिछले सख्त बैरियर फंक्शन दृष्टिकोणों (जैसे [8], [19]) की तुलना में कम रूढ़िवादी हैं।
स्केलेबिलिटी विश्लेषण: शोध पत्र यह प्रदर्शित करता है कि जबकि समय-अपरिवर्तित प्रमाणपत्र प्रति चरण गणनात्मक रूप से सस्ते होते हैं, समय-परिवर्ती प्रमाणपत्र कई समय चरणों में कम-डिग्री वाले बहुपदों का उपयोग करके उच्च-आयामी प्रणालियों के लिए काफी बेहतर (tighter) प्रायिकता बाउंड और बेहतर स्केलेबिलिटी प्रदान करते हैं।

4. प्रयोगात्मक परिणाम (Experimental Results)

इस ढांचे को 1D/2D/3D लीनियर सिस्टम, कॉन्ट्रैक्शन मैप्स, एक एयरक्राफ्ट मॉडल और रूम टेम्परेचर सिस्टम सहित कई बेंचमार्क पर सत्यापित किया गया।

स्टेट-ऑफ-द-आर्ट के साथ तुलना:
- [8] (समय-अपरिवर्तित, अनंत क्षितिज) के विरुद्ध: प्रस्तावित विधि ने काफी उच्च प्रायिकता बाउंड प्राप्त किए (उदाहरण के लिए, 1D लीनियर सिस्टम में 0.96 बनाम 0.16) और उन मामलों में भी सफल रही जहाँ [8] विफल रहा।
- [19] (परिमित क्षितिज) के विरुद्ध: प्रस्तावित समय-परिवर्ती प्रारूप ने कम बहुपद डिग्री पर काफी बेहतर (tighter) बाउंड प्रदान किए।
समय-परिवर्ती बनाम समय-अपरिवर्तित:
- समय-परिवर्ती: लगातार उच्च निचली-बद्ध प्रायिकताएँ (higher lower-bound probabilities) प्रदान कीं। उच्च-आयामी प्रणालियों (जैसे 3D एयरक्राफ्ट) के लिए, डिग्री 6 के समय-परिवर्ती प्रमाणपत्र ने 0.98 का बाउंड प्राप्त किया, जबकि समय-अपरिवर्तित दृष्टिकोण को एक गैर-तुच्छ बाउंड प्राप्त करने के लिए डिग्री 24 की आवश्यकता थी।
- ट्रेड-ऑफ (Trade-off): समय-परिवर्ती प्रमाणपत्रों में समय चरणों की संख्या के कारण उच्च गणना लागत आती है, लेकिन वे उच्च-डिग्री बहुपदों से जुड़े चर के घातीय विस्फोट (exponential explosion) से बचते हैं।
नियंत्रण संश्लेषण: संयुक्त संश्लेषण ने सफलतापूर्वक ऐसे नियंत्रक डिजाइन किए जिन्होंने विभिन्न परिदृश्यों में रीच प्रायिकता को लगभग शून्य (ओपन-लूप) से बढ़ाकर >0.95 कर दिया।

5. महत्व (Significance)

यह कार्य निरंतर स्थानों वाले स्टोकेस्टिक सिस्टम के लिए औपचारिक सत्यापन (formal verification) और नियंत्रण संश्लेषण (control synthesis) के बीच के अंतर को पाटता है।

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

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