⚡ electrical engineering

On the Computation of Backward Reachable Sets for Max-Plus Linear Systems with Disturbances

यह शोध पत्र एडिटिव डिस्टर्बेंस (additive disturbances) वाले अनसर्टेन मैक्स-प्लस लीनियर सिस्टम्स के लिए वन-स्टेप बैकवर्ड रीचेबल सेट्स को कुशलतापूर्वक गणना करने हेतु ट्रॉपिकल पॉलीहेड्रा पर आधारित एक कम्प्यूटेशनल फ्रेमवर्क प्रस्तुत करता है, जो यह प्रदर्शित करता है कि बैकवर्ड ऑपरेटर्स ट्रॉपिकल-पॉलीहेड्रल संरचना को संरक्षित करते हैं ताकि रचनात्मक सुरक्षा विश्लेषण (constructive safety analysis) सक्षम हो सके।

मूल लेखक: Yuda Li, Xiang Yin

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

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

CC BY 4.0

मूल लेखक: Yuda Li, Xiang Yin

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

कल्पना कीजिए कि आप एक बहुत ही विशेष जहाज के कप्तान हैं जो एक धुंधले, अप्रत्याशित महासागर में यात्रा कर रहे हैं। यह केवल कोई साधारण महासागर नहीं है; यह एक ऐसी दुनिया है जहाँ समय और दूरी अलग तरह से काम करती है, जो मैक्स-प्लस अलजेब्रा (Max-Plus Algebra) नामक नियमों के एक सेट द्वारा नियंत्रित होती है। इस दुनिया में, दो संख्याओं को "जोड़ने" का अर्थ है उनका अधिकतम (maximum) लेना, और "गुणा करने" का अर्थ है उन्हें जोड़ना। यह अजीब लग सकता है, लेकिन यह ट्रैफिक जाम, फैक्ट्री असेंबली लाइनों, या ट्रेन शेड्यूल जैसी चीजों को मॉडल करने के लिए एकदम सही है, जहाँ पूरा सिस्टम अपने सबसे धीमे हिस्से की गति पर निर्भर करता है।

समस्या: धुंधला लक्ष्य (The Foggy Target)

आपका लक्ष्य एक विशिष्ट "सुरक्षित बंदरगाह" (लक्ष्य सेट) तक पहुँचना है। हालाँकि, आपका जहाज विक्षोभों (Disturbances)—अनिश्चित लहरों, हवा या आपके मानचित्र की त्रुटियों—से टकरा रहा है। आप जहाज को दिशा दे सकते हैं (नियंत्रण/Control), लेकिन आप यह नहीं जानते कि लहरें कितनी शक्तिशाली होंगी।

बड़ा सवाल यह है: मानचित्र पर किन शुरुआती बिंदुओं से आप यह गारंटी दे सकते हैं कि, चाहे लहरें कितनी भी ज़ोर से क्यों न टकराएँ, आप एक ही कदम में सुरक्षित बंदरगाह तक पहुँचने के लिए जहाज को मोड़ पाएंगे?

इसे बैकवर्ड रीचेबिलिटी (Backward Reachability) समस्या कहा जाता है। यह पूछने के बजाय कि "मैं यहाँ से कहाँ जा सकता हूँ?", आप पूछ रहे हैं "मुझे कहाँ से शुरू करना चाहिए था ताकि मैं सुरक्षित रूप से वहाँ पहुँच सकूँ?"

पुराना तरीका: एक उलझी हुई गणना

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

नया समाधान: ट्रॉपिकल पॉलीहेड्रा (एक "आकार बदलने वाला" मानचित्र)

इस शोध पत्र के लेखक, यूडा ली और जियांग यिन ने इसे हल करने का एक नया, सुंदर तरीका विकसित किया है। वे ट्रॉपिकल पॉलीहेड्रा (Tropical Polyhedra) की एक अवधारणा का उपयोग करते हैं।

एक ट्रॉपिकल पॉलीहेड्रा को एक कठोर ज्यामितीय आकार के रूप में नहीं, बल्कि एक लचीले, खिंचने वाले जाल (net) के रूप में सोचें।

सामान्य गणित में, यदि आप एक वर्ग को धकेलते हैं, तो वह एक अजीब, टेढ़े-मेढ़े ढेर में बदल सकता है।
इस "मैक्स-प्लस" दुनिया में, इन विशेष जालों के पास एक महाशक्ति है: वे अपना आकार बनाए रखते हैं।

चाहे आप उन्हें कितना भी खींचें, घुमाएँ, या "विक्षोभ लहरों" के माध्यम से धकेलें, वे इन विशेष जालों के रूप में पहचान योग्य बने रहते हैं। यही इस शोध पत्र की सबसे बड़ी सफलता है।

यह कैसे काम करता है: तीन-चरणीय नृत्य (The Three-Step Dance)

सुरक्षित शुरुआती बिंदुओं को खोजने के लिए, लेखक इस समस्या को तीन सरल चालों में तोड़ देते हैं, जो एक नृत्य की दिनचर्या की तरह है:

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

जादुई परिणाम

चूंकि "खिंचने वाले जाल" (ट्रॉपिकल पॉलीहेड्रा) इन तीन चरणों के दौरान अपना आकार कभी नहीं खोते हैं, इसलिए लेखक अंतिम उत्तर को सरल, तेज़ ज्यामितीय नियमों का उपयोग करके निकाल सकते हैं। उन्हें समुद्र के हर बिंदु की जाँच करने की आवश्यकता नहीं है; उन्हें केवल जाल के "कोनों" को ट्रैक करने की आवश्यकता है।

यह क्यों महत्वपूर्ण है

यह केवल एक गणितीय ट्रिक नहीं है। यह वास्तविक दुनिया के लिए एक सुरक्षा उपकरण है।

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

मुख्य निष्कर्ष (The Bottom Line)

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

संक्षेप में: उन्होंने एक "सुरक्षा बुलबुले" को एक अराजक प्रणाली के चारों ओर खींचने का तरीका खोजा है, यह साबित करते हुए कि जब तक आप बुलबुले के अंदर से शुरुआत करते हैं, तो आप तूफान चाहे जो भी हो, अपनी सुरक्षा की राह बना सकते हैं।

यहाँ युदा ली और जियांग यिन के शोध पत्र "On the Computation of Backward Reachable Sets for Max-Plus Linear Systems with Disturbances" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र विक्षोभों (disturbances) के अधीन मैक्स-प्लस लीनियर सिस्टम्स (MPLS) के लिए बैकवर्ड रीचेबिलिटी समस्या (backward reachability problem) को संबोधित करता है।

सिस्टम मॉडल: सिस्टम $x_k = A \otimes x_{k-1} \oplus B \otimes u_k \oplus C \otimes w_k$ के अनुसार विकसित होता है, जहाँ $x$ अवस्था (state) है, $u$ नियंत्रण इनपुट (control input) है, और $w$ विक्षोभ (disturbance) है। सभी संक्रियाएँ मैक्स-प्लस बीजगणित ( $\mathbb{R}_{\max} = \mathbb{R} \cup \{-\infty\}$ , जहाँ $\oplus = \max$ और $\otimes = +$ ) पर परिभाषित हैं।
उद्देश्य: एक लक्ष्य सेट $E$ (जो एक सुरक्षित अवस्था क्षेत्र का प्रतिनिधित्व करता है) दिया गया है, जिससे एक-चरण बैकवर्ड रीचेबल सेट $\Upsilon(E)$ की गणना करना है। इस सेट में वे सभी अवस्थाएँ $x$ शामिल हैं जिनसे एक स्वीकार्य नियंत्रण इनपुट $u$ मौजूद है जिससे, सभी स्वीकार्य विक्षोभों $w$ के लिए, अगली अवस्था $E$ के भीतर रहती है।
चुनौती: विक्षोभ-मुक्त प्रणालियों के विपरीत, विक्षोभों की उपस्थिति अनिश्चितता सेट पर एक यूनिवर्सल क्वांटिफिकेशन ( $\forall w$ ) पेश करती है। मौजूदा विधियाँ (जैसे कि डिफरेंस-बाउंड मैट्रिसेस या DBMs) अक्सर उच्च कम्प्यूटेशनल जटिलता से ग्रस्त होती हैं क्योंकि सिस्टम के आयाम और अनिश्चितता संरचनाएँ बढ़ती जाती हैं। इसके अलावा, यह तुरंत स्पष्ट नहीं है कि बैकवर्ड रीचेबल सेट मैक्स-प्लस संक्रियाओं के तहत प्रारंभिक सेटों की ज्यामितीय संरचना को संरक्षित करता है या नहीं।

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

लेखक ट्रॉपिकल कॉनवेक्सिटी (Tropical Convexity) और ट्रॉपिकल पॉलीहेड्रा (Tropical Polyhedra) पर आधारित एक कम्प्यूटेशनल फ्रेमवर्क प्रस्तावित करते हैं।

A. गणितीय ढांचा (Mathematical Framework)

प्रतिनिधित्व: लक्ष्य सेट $E$ , नियंत्रण सेट $U$ , और विक्षोभ सेट $W$ , सभी को ट्रॉपिकल पॉलीहेड्रा के रूप में मॉडल किया गया है। एक ट्रॉपिकल पॉलीहेड्रोन को परिमित कई ट्रॉपिकल हाफ-स्पेस के प्रतिच्छेदन (Outer/M-form) या सदिशों के एक परिमित सेट के मैक्स-प्लस स्पैन (Inner/V-form) के रूप में परिभाषित किया जाता है।
ऑपरेटर अपघटन (Operator Decomposition): बैकवर्ड रीचेबिलिटी ऑपरेटर $\Upsilon$ $Υ$ को तीन मौलिक सेट-वैल्यूड ऑपरेटरों में विभाजित किया गया है:
1. इनवर्स ऑपरेटर ( $A^{-1}$ ): स्वायत्त सिस्टम डायनेमिक्स को संभालता है।
2. यूनिवर्सल इनवर्स ऑपरेटर ( $\phi_W$ ): विक्षोभों पर यूनिवर्सल क्वांटिफिकेशन को संभालता है (सबसे चुनौतीपूर्ण भाग)।
3. एक्ज़िस्टेंशियल इनवर्स ऑपरेटर ( $\gamma_U$ ): नियंत्रण इनपुट पर एक्ज़िस्टेंशियल क्वांटिफिकेशन को संभालता है।
- संयोजन है $\Upsilon = A^{-1} \circ \gamma_U \circ \phi_W$ ।

B. मुख्य कम्प्यूटेशनल चरण (Key Computational Steps)

संरचना का संरक्षण (Preservation of Structure): शोध पत्र सिद्ध करता है कि यदि इनपुट सेट ट्रॉपिकल पॉलीहेड्रा हैं, तो $A^{-1}$ और $\gamma_U$ के तहत इमेज भी ट्रॉपिकल पॉलीहेड्रा ही रहते हैं। यह एक एकीकृत ज्यामितीय ढांचे के उपयोग की अनुमति देता है।
विक्षोभों को संभालना ( $\phi_W$ ):
- अपघटन: विक्षोभ सेट $W$ को एक रिसेशन कोन $R$ और एक बाउंडेड पॉलीहेड्रोन $P$ में विभाजित किया गया है ( $W = R \oplus P$ )। लेखक दिखाते हैं कि यदि $R$ लक्ष्य सेट के रिसेशन कोन के भीतर है, तो समस्या $\phi_P(Z)$ की गणना करने तक सीमित हो जाती है।
- स्यूडो हाफ-स्पेस (Pseudo Half-Spaces): सेट $\phi_P(Z)$ को "स्यूडो हाफ-स्पेस" के प्रतिच्छेदन के रूप में वर्णित किया गया है। एक स्यूडो हाफ-स्पेस को विक्षोभ कोन के जनरेटिंग सेट पर यूनिवर्सल क्वांटिफिकेशन द्वारा परिभाषित किया जाता है।
- रिकर्सिव जनरेशन: लेखक परिणामी सेट (V-form) के जनरेटिंग सेट की गणना करने के लिए एक एल्गोरिदम विकसित करते हैं। वे एक प्रमेय का उपयोग करते है जो मिंकोव्स्की-कैराथियोडोरॉय प्रमेय के समान है, जो बताता है कि एक ट्रॉपिकल कोन और एक स्यूडो हाफ-स्पेस का प्रतिच्छेदन निम्नलिखित द्वारा जनरेट किया जा सकता है:
  - मूल सेट के वे सदिश जो बाधा (constraint) को संतुष्ट करते हैं।
  - एक "संतुष्ट करने वाले" सदिश और एक "उल्लंघन करने वाले" सदिश को एक विशिष्ट थ्रेशोल्ड $\rho$ (वह अधिकतम स्केलर $\lambda$ जिससे संयोजन सेट में रहता है) पर संयोजित करके बनाए गए नए सदिश।
अनुकूलन (Optimization): प्रत्येक पुनरावृत्ति (iteration) में जनरेटिंग सेट से गैर-चरम बिंदुओं (non-extremal points) को हटाने के लिए एक एक्सट्रीमल पॉइंट्स फिल्टरिंग प्रक्रिया का सुझाव दिया गया है।

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

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

4. परिणाम (Results)

सैद्धांतिक सत्यापन: शोध पत्र प्रस्तावित ऑपरेटरों के ट्रॉपिकल पॉलीहेड्रल संरचना को संरक्षित करने का प्रदर्शन करने वाले कठोर प्रमाण (लेम्मा 1-3, प्रमेय 1) प्रदान करता है।
केस स्टडी: एक विशिष्ट विक्षोभ सेट और सुरक्षा लक्ष्य के साथ 2-आयामी MPLS (सेक्शन VII) को शामिल करते हुए एक संख्यात्मक उदाहरण प्रस्तुत किया गया है।
- लेखक $\phi_W(S)$ , $\gamma_U(\cdot)$ , और $A^{-1}(\cdot)$ की गणना को मैन्युअल रूप से ट्रेस करते हैं।
- उदाहरण स्यूडो हाफ-स्पेस के प्रतिच्छेदन और अंतिम बैकवर्ड रीचेबल सेट के लिए जनरेटिंग वेक्टर्स की गणना को प्रदर्शित करता है।
- ज्यामितीय विज़ुअलाइज़ेशन (चित्र 1 और 2) सेट्स के रूपांतरण को दर्शाते हैं, जो जटिल अनिश्चितता संरचनाओं को संभालने की विधि की क्षमता की पुष्टि करते हैं।

5. महत्व (Significance)

सुरक्षा सत्यापन (Safety Verification): यह विधि उन डिस्क्रीट-इवेंट सिस्टम्स (जैसे विनिर्माण, परिवहन, शेड्यूलिंग) में सुरक्षा विश्लेषण और नियंत्रित इनवेरियंस के लिए एक कठोर उपकरण प्रदान करती है जहाँ समय संबंधी अनिश्चितताएं (timing uncertainties) महत्वपूर्ण हैं।
संभाव्यता मॉडलों से परे: स्टोकेस्टिक दृष्टिकोणों के विपरीत जो संभाव्यता वितरणों पर निर्भर करते हैं, यह नियतवादी (deterministic) दृष्टिकोण उन परिदृश्यों के लिए उपयुक्त है जहाँ अनिश्चितताएं सीमित हैं लेकिन उनका वितरण अज्ञात या नॉन-गॉसियन है।
स्केलेबिलिटी क्षमता: ट्रॉपिकल पॉलीहेड्रा के बीजगणितीय गुणों का लाभ उठाकर, प्रस्तावित विधि DBM-आधारित दृष्टिकोणों के लिए एक संभावित विकल्प प्रदान करती है, जो आयाम बढ़ने के साथ कम्प्यूटेशनल रूप से महंगे हो सकते हैं। एक्सट्रीमल पॉइंट फिल्टरिंग का उपयोग बड़े सिस्टम को संभालने के मार्ग का सुझाव देता है।
मौलिक कार्य: यह कार्य ट्रॉपिकल कॉनवेक्सिटी सिद्धांत को नियंत्रण सिद्धांत (control theory) के साथ जोड़ता है, जो अनिश्चित मैक्स-प्लस सिस्टम के विश्लेषण के लिए नए रास्ते खोलता है।

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