🤖 AI

Infinite Trace Objectives with Finite Trace Techniques: Translating LTL to LTLf+

यह शोध पत्र लीनियर टेम्पोरल लॉजिक (LTL) से LTLf+ में प्रथम अनुवाद प्रस्तुत करता है, जो मानक LTL-टू-ऑटोमेटा पाइपलाइन की एसिम्प्टोटिक जटिलता को बढ़ाए बिना अनंत-ट्रेस (infinite-trace) AI समस्याओं के लिए कुशल परिमित-ट्रेस (finite-trace) ऑटोमेटा तकनीकों के अनुप्रयोग को सक्षम बनाता है।

मूल लेखक: Christoph Weinhuber, Maximilian Prokop, Giuseppe De Giacomo, Moshe Y. Vardi

प्रकाशित 2026-08-04

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

CC BY 4.0

मूल लेखक: Christoph Weinhuber, Maximilian Prokop, Giuseppe De Giacomo, Moshe Y. Vardi

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

समय-यात्रा करने वाला रोबोट और अनंत लूप (The Time-Traveling Robot and the Infinite Loop)

कल्पना कीजिए कि आप एक रोबोट को शहर की खोज करने के लिए प्रोग्राम कर रहे हैं। आप उसे ऐसे निर्देशों का एक सेट देना चाहते हैं जो न केवल यह बताएं कि अभी क्या करना है, बल्कि यह भी कि हमेशा के लिए क्या करना है। "हमेशा लाल बत्तियों पर रुकें," "अंततः पार्क जाएँ," या "यदि बारिश होती है, तो हमेशा के लिए आश्रय की तलाश जारी रखें।" यह लीनियर टेम्पोरल लॉजिक (LTL) नामक एक विशेष भाषा का काम है। यह समय के लिए एक अति-सटीक रेसिपी की तरह है, जिसका उपयोग वैज्ञानिक और इंजीनियर कंप्यूटर, रोबोट और एआई (AI) को यह बताने के लिए करते हैं कि उन्हें अनंत भविष्य में वास्तव में कैसे व्यवहार करना चाहिए।

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

हाल ही में, एक नई, सरल भाषा LTLf+ का आविष्कार किया गया। यह समय के परिमित टुकड़ों (जैसे एक छोटी वीडियो क्लिप) को देखने और फिर उन्हें आपस में जोड़ने के विचार पर आधारित है। यह नई भाषा कंप्यूटर के लिए संभालना बहुत आसान है क्योंकि यह "परिमित मानचित्रों" (finite maps) का उपयोग करती है जो छोटे, व्यवस्थित और अपने सबसे सरल रूप में सिकोड़ने में आसान होते हैं। लेकिन एक पहेली का हिस्सा गायब था: कोई नहीं जानता था कि पुराने, जटिल अनंत नियमों (LL) को इस नए, आसानी से उपयोग करने योग्य भाषा (LTLf+) में कैसे अनुवादित किया जाए बिना कंप्यूटर के काम को पहले से अधिक कठिन बनाए। अब तक, ऐसा नहीं था।

महान अनुवाद: अनंत अराजकता को परिमित व्यवस्था में बदलना (The Great Translation: Turning Infinite Chaos into Finite Order)

इस शोध पत्र में, लेखकों—क्रिस्टोफ़ वेइनहुबर, मैक्सिमिलियन प्रोकोप, ग्यूसेप डे गियाकोमो और मोशे वाई. वर्डी—ने अंततः वह पुल बना लिया है। उन्होंने यह पता लगा लिया है कि किसी भी जटिल, अनंत-समय के निर्देश (LTL) को नई, आसानी से संभालने वाली भाषा (LTLf+) में कैसे अनुवादित किया जाए।

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

लेखकों की नई विधि उस उलझे हुए अनंत धागे को यह समझने जैसी है कि वह वास्तव में कुछ सरल, दोहराते पैटर्न से बना है। वे पहले अनंत निर्देशों को एक मानक "आकार" (एक प्रक्रिया जिसे सामान्यीकरण या normalization कहा जाता है) में व्यवस्थित करते हैं। यह सॉर्टिंग चरण सबसे भारी काम है: सबसे खराब स्थिति में, यह निर्देशों को घातीय रूप से (exponentially) बड़ा बना सकता है। हालाँकि, एक बार जब निर्देश इस व्यवस्थित आकार में आ जाते हैं, तो उन्हें नई भाषा (LTLf+) में अनुवादित करना लगभग तुरंत होता है—जैसे एक जटिल वाक्य को सरल बुलेट पॉइंट्स की सूची में बदलना। यह विशिष्ट अनुवाद चरण रैखिक (linear) है, जिसका अर्थ है कि यह पहले से सॉर्ट किए गए निर्देशों के आकार के साथ पूरी तरह से स्केल करता है।

यहाँ वह जादुई ट्रिक है जो उन्होंने खोजी है:

आकार परिवर्तन (The Shape Shift): वे अव्यवस्थित, अनंत नियमों को एक विशिष्ट प्रारूप में व्यवस्थित करते हैं जो "सुरक्षा" नियमों (ऐसी चीजें जो कभी नहीं होनी चाहिए) को "गारंटी" नियमों (ऐसी चीजें जो अंततः होनी चाहिए) से अलग करती हैं। जबकि यह संगठन चरण निर्देशों के आकार को घातीय रूप से बढ़ा सकता है, यह एक आवश्यक सेटअप है।
परिमित लेंस (The Finite Lens): वे फिर इन व्यवस्थित नियमों को एक "परिमित लेंस" के माध्यम से देखते हैं। यह पूछने के बजाय कि, "क्या यह हमेशा के लिए होगा?" वे पूछते हैं, "क्या यह समय के एक छोटे, परिमित क्लिप में होता है?"
स्टिचिंग (The Stitching): वे इन छोटे क्लिप्स को वापस जोड़ने के लिए विशेष "क्वांटिफायर्स" (जैसे, "सभी क्लिप्स के लिए" या "कुछ क्लिप्स के लिए") का उपयोग करते हैं। यह कंप्यूटर को अनंत समय के बारे में मूल रूप से समस्याओं को हल करने के लिए नए, आसान उपकरणों का उपयोग करने की अनुमति देता है जो परिमित समय के लिए डिज़ाइन किए गए हैं।

बिना थके क्यों यह महत्वपूर्ण है (Why This Matters - Without Breaking a Sweat)

इस खोज का सबसे रोमांचक हिस्सा यह है कि यह आज हमारे पास मौजूद सर्वोत्तम तरीकों से समग्र समस्या को कठिन नहीं बनाता है। कंप्यूटर विज्ञान की दुनिया में, एक नया चरण जोड़ने से अक्सर गणित का आकार विस्फोट की तरह बढ़ जाता है, जिससे एक प्रबंधनीय कार्य असंभव में बदल जाता है। लेखकों ने सिद्ध किया है कि भले ही प्रारंभिक सॉर्टिंग चरण निर्देशों को घातीय रूप से बड़ा बना सकता है, लेकिन इन अनंत समस्याओं को हल करने का कुल प्रयास (मूल LTL फॉर्मूला से लेकर अंतिम कंप्यूटर मानचित्र तक) आज के सर्वोत्तम तरीकों के समान स्तर पर रहता है। यह एक शॉर्टकट खोजने जैसा है जो आपका समय बचाता है लेकिन इसके लिए आपको पहले से अधिक भारी बैकपैक ले जाने की आवश्यकता नहीं होती।

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

यह शोध पत्र केवल यह सुझाव नहीं देता कि यह काम कर सकता है; उन्होंने गणितीय प्रमाण प्रदान किया है कि अनुवाद सही है और जटिलता समान रहती है। उन्होंने मौजूदा सॉफ़्टवेयर लाइब्रेरीज़ का उपयोग करके इस अनुवादक का एक कामकाजी संस्करण भी बनाया है, जो यह दर्शाता है कि यह केवल एक सिद्धांत नहीं है बल्कि उपयोग के लिए तैयार एक व्यावहारिक उपकरण है।

संक्षेप में, उन्होंने एक ऐसी समस्या को हल कर दिया है जो अनंत तक गिनने की कोशिश करने जैसी महसूस होती थी और इसे बार-बार दस तक गिनने के खेल में बदल दिया है। और सबसे अच्छी बात? कंप्यूटर अंतर को महसूस भी नहीं करता है।

तकनीकी सारांश: परिमित ट्रेस तकनीकों के साथ अनंत ट्रेस उद्देश्य (Infinite Trace Objectives with Finite Trace Techniques)

समस्या विवरण
लीनियर टेम्पोरल लॉजिक (LTL) AI में टेम्पोरल उद्देश्यों को निर्दिष्ट करने के लिए एक मानक भाषा है, जो रिएक्टिव सिंथेसिस से लेकर मार्कोव डिसीजन प्रोसेस में प्लानिंग तक विस्तृत है। हालाँकि, LTL-आधारित समस्याओं को हल करने के लिए पारंपरिक रूप से LTL फॉर्मूला को अनंत शब्दों (infinite words) पर नॉन-डिटरमिनिस्टिक ऑटोमेटा में अनुवादित करने और उसके बाद उसे डिटरमिनाइज़ (determinize) करने की आवश्यकता होती है। यह डिटरमिनाइजेशन चरण सैद्धांतिक और व्यावहारिक दोनों रूप से अत्यंत कठिन है, जो स्केलेबिलिटी के लिए एक महत्वपूर्ण बाधा उत्पन्न करता है। जबकि हालिया LTL सिंथेसिस प्रगति में एक सामान्य रूप (Manna-Pnueli सेफ्टी-प्रोग्रेस पदानुक्रम पर आधारित) का उपयोग किया जाता है ताकि फॉर्मूला को डिटरमिनिस्टिक घटकों में विभाजित किया जा सके, LTL से डिटरमिनिस्टिक ऑटोटा में अनुवाद प्रक्रिया 'डबली एक्सपोनेंशियल' (doubly exponential) बनी रहती है।

इसके साथ ही, LTLf (परिमित ट्रेस पर LTL) ने अपनी दक्षता के कारण लोकप्रियता हासिल की है, क्योंकि इसे डिटर्मिनिस्टिक फाइनाइट ऑटोमेटा (DFA) में कुशलतापूर्वक अनुवादित किया जा सकता है, जो मिनिमाइजेशन (minimization) का समर्थन करता है। LTLf+ को हाल ही में LTLf को अनंत ट्रेस तक ले जाने के लिए पेश किया गया है, जो प्रिफिक्स (prefix) पर क्वांटिफिकेशन (quantification) करता है और Manna-Pnueli पदानुक्रम वर्गों से मेल खाता है। हालाँकि LTLf+ में LTL के समान अभिव्यंजक शक्ति (expressive power) है, लेकिन सामान्य LTL से LTLf+ तक एक कंस्ट्रक्टिव ट्रांसलेशन (constructive translation) पहले अनुपलब्ध था, जिससे मानक LTL स्पेसिफिकेशन के लिए DFA-आधारित तकनीकों (जैसे मिनिमाइजेशन) का अनुप्रयोग सीमित था।

कार्यप्रणाली (Methodology)
यह शोध पत्र किसी भी LTL फॉर्मूला को लीनियर समय में LTLf+ में अनुवादित करने के लिए एक कंस्ट्रक्टिव ट्रांसलेशन प्रस्तुत करता है, यह मानते हुए कि LTL फॉर्मूला पहले नॉर्मलाइज्ड (normalized) है। कार्यप्रणाली तीन मुख्य चरणों में आगे बढ़ती है:

$\Delta_2$ नॉर्मल फॉर्म में नॉर्मलाइजेशन:
लेखक किसी भी LTL फॉर्मूला को $\Delta_2$ (रिएक्टिविटी) नॉर्मल फॉर्म में अनुवादित करने के लिए एक शुद्ध फॉर्म रीराइटिंग सिस्टम (Esparza, Rubio, और Sickert 2024 पर आधारित) का उपयोग करते हैं। यह रूप फॉर्मूला को टर्म्स के डिसजंक्शन (disjunction) में विभाजित करता है, जहाँ प्रत्येक टर्म एक विशिष्ट "लिमिट-बिहेवियर" $(M, N)$ का प्रतिनिधित्व करता है। प्रत्येक टर्म में शामिल है:
- एक सरल $\Sigma_2$ बॉडी फॉर्मूला ( $\phi[M, N]$ )।
- पुनरावृत्ति (recurrence) के लिए $\Pi_2$ चेक ( $\bigwedge GF(\psi[N]_\mu)$ )।
- निरंतरता (persistence) के लिए $\Sigma_2$ चेक ( $\bigwedge FG(\psi[M]_\nu)$ )।
  यह नॉर्मलाइजेशन मूल फॉर्मूला के आकार के सापेक्ष सिंगल एक्सपोनेंशियल है।
लिमिट-बिहेवियर ब्लॉक्स का अनुवाद:
पेपर लिमिट-बिहेवियर चेक्स के लिए विशिष्ट अनुवादों को परिभाषित करता है:
- पुनरावृत्ति ( $\Pi_2$ ): $GF(\sigma_1)$ (जहाँ $\sigma_1 \in \Sigma_1$ ) जैसे फॉर्मूला को $\forall\exists(F(\text{tight}(\text{finX}(\sigma_1))))$ में अनुवादित किया जाता है। लेखक एक "टाइट कंप्लीशन" (tight completion) अवधारणा पेश करते हैं जो एक chop ऑपरेटर का उपयोग करती है ताकि यह सुनिश्चित किया जा सके कि फॉर्मूला की संतुष्टि प्रिफिक्स के अंत से जुड़ी हो, जिससे अनंत प्रिफिक्स पर स्प्यूरियस (spurious) संतुष्टि को रोका जा सके।
- निरंतरता ( $\Sigma_2$ ): $FG(\pi_1)$ (जहाँ $\pi_1 \in \Pi_1$ ) जैसे फॉर्मूला को $\exists\forall(G(\neg\text{tight}(\neg\text{finX}(\pi_1))))$ में अनुवादित किया जाता है।
- फाइनाइट रीइंटरप्रिटेशन (Finite Reinterpretation): लेखक finX और tight ऑपरेटर्स को परिभाषित करते हैं जो परिमित ट्रेस पर LTL ऑपरेटर्स को फिर से व्याख्यायित करते हैं, जो संदर्भ (सेफ्टी बनाम को-सेफ्टी फ्रेगमेंट) के आधार पर स्ट्रॉन्ग और वीक 'नेक्स्ट' ऑपरेटर्स के बीच अंतर करते हैं।
$\Sigma_2$ बॉडीज का अनुवाद:
नॉर्मलाइज्ड फॉर्मूला की मुख्य बॉडी ( $\phi[M, N]$ ) के लिए, लेखक इस तथ्य का लाभ उठाते हैं कि एक निश्चित लिमिट-बिहेवियर $(M, N)$ के तहत, सभी सेफ्टी लीव्स (G-फॉर्मूला) अंततः हमेशा सत्य होते हैं। इन सेफ्टी लीव्स को प्रोजेक्ट करके (उन्हें tt से बदलकर), बॉडी फॉर्मूला प्रभावी रूप से एक $\Sigma_1$ (को-सेफ्टी) फॉर्मूला में बदल जाता है। लेखक सिद्ध करते हैं कि विशिष्ट लिमिट-बिहेवियर प्रदर्शित करने वाले ट्रेसेस के लिए, बॉडी "कन्वर्जेंट" (convergent) है, जिसका अर्थ है कि इसकी अनंत ट्रेस पर संतुष्टि, सभी लेकिन कुछ परिमित प्रिफिक्स पर इसके फाइनाइट रीइंटरप्रिटेशन की संतुष्टि के समान है। यह बॉडी को $\exists\forall(\text{finX}(\phi[M, N]))$ का उपयोग करके अनुवादित करने की अनुमति देता है।

मुख्य योगदान

कंस्ट्रक्टिव ट्रांसलेशन: यह पेपर सामान्य LTL से LTLf+ तक पहला कंस्ट्रक्टिव ट्रांसलेशन प्रदान करता है, जो Aminof et al. (2025) के अस्तित्व संबंधी परिणाम और एक व्यावहारिक एल्गोरिदम के बीच के अंतर को पाटता है।
लीनियर ट्रांसलेशन कॉम्प्लेक्सिटी: नॉर्मलाइज्ड LTL फॉर्मूला के आकार के सापेक्ष LTLf+ में ट्रांसलेशन लीनियर है।
कॉम्प्लेक्सिटी का संरक्षण: यह पेपर प्रदर्शित करता है कि यह ट्रांसलेशन पाइपलाइन (LTL $\to$ Normal Form $\to$ LTLf+ $\to$ DFA) मूल LTL के आकार के संबंध में 'डबली एक्सपोनेंशियल' बनी रहती है। यह सीधे LTL-टू-ऑटोमेटा ट्रांसलेशन के स्टेट-ऑफ-द-आर्ट की तुलना में कोई अतिरिक्त एक्सपोनेंशियल उछाल (exponential blow-up) उत्पन्न नहीं करता है।
DFA तकनीकों को सक्षम बनाना: यह ट्रांसलेशन DFA-आधारित तकनीकों, जैसे ऑटोमेटा मिनिमाइजेशन को लागू करने में सक्षम बनाता है, जो मूल रूप से LTL द्वारा फॉर्म्युलेट की गई समस्याओं के लिए महत्वपूर्ण है। यह महत्वपूर्ण है क्योंकि DFAs को कुशलतापूर्वक मिनिमाइज किया जा सकता है, जबकि नॉन-डिटरमिनिस्टिक बुची ऑटोमेटा को मिनिमाइज करना PSPACE-कम्पलीट है।

परिणाम
लेखक सिद्ध करते हैं कि प्रत्येक LTL फॉर्मूला $\phi$ और अनंत ट्रेस $w$ के लिए, $w \models_{inf} \phi$ यदि और केवल यदि $w \models_{inf} \text{Translation}(\phi)$ । परिणामी LTLf+ फॉर्मूला प्रिफिक्स क्वांटिफायर्स ( $\forall, \exists, \forall\exists, \exists\forall$ ) को मूल सब-फॉर्मूला के फाइनाइट-ट्रेस रीइंटरप्रिटेशन पर लागू करने वाले लीफ फॉर्मूला का एक बूलियन कॉम्बिनेशन है। अनुवादित फॉर्मूला की लंबाई $2^{O(|\phi|)}$ द्वारा सीमित है, जो मध्यवर्ती $\Delta_2$ नॉर्मल फॉर्म के आकार से मेल खाती है।

महत्व
यह पेपर LTLf+ को मनमाने LTL स्पेसिफिकेशन के लिए एक व्यावहारिक इंटरमीडिएट लैंग्वेज के रूप में स्थापित करता है। LTL को LTLf में अनुवादित करके, परिमित-ट्रेस लॉजिक के लिए विकसित कुशल DFA-आधारित तकनीकों का बढ़ता पारिस्थितिकी तंत्र अब अनंत-ट्रेस समस्याओं के लिए उपलब्ध हो जाता है। इसमें शामिल हैं:

रिएक्टिव सिंथेसिस: सिंथेसिस को तेज करने के लिए DFA मिनिमाइजेशन का उपयोग करने की अनुमति देना, जो पहले केवल फाइनाइट-होराइजन स्पेसिफिकेशन तक सीमित था।
प्लानिंग और लर्निंग: मार्कोव डिसीजन प्रोसेस, स्टोकेस्टिक प्लानिंग और रिइन्फोर्समेंट लर्निंग में, जहाँ LTL उद्देश्यों का उपयोग किया जाता है, इन तकनीकों की प्रयोज्यता का विस्तार करना।

लेखक उल्लेख करते हैं कि उन्होंने SPOT लाइब्रेरी के ऊपर इस ट्रांसलेशन को लागू किया है, जिसमें ऑब्लिगेशन्स (obligations) जैसे विशिष्ट फ्रेगमेंट के लिए अनुकूलन शामिल है, जो नॉर्मलाइजेशन और टाइट कंप्लीशन को पूरी तरह से छोड़ सकते हैं। यह कार्य LTLf+ को न केवल एक सैद्धांतिक विस्तार, बल्कि AI में LTL-आधारित रीजनिंग की स्केलेबिलिटी में सुधार के लिए एक व्यवहार्य इंजीनियरिंग मार्ग के रूप में स्थापित करता है।

समय-यात्रा करने वाला रोबोट और अनंत लूप (The Time-Traveling Robot and the Infinite Loop)

महान अनुवाद: अनंत अराजकता को परिमित व्यवस्था में बदलना (The Great Translation: Turning Infinite Chaos into Finite Order)

बिना थके क्यों यह महत्वपूर्ण है (Why This Matters - Without Breaking a Sweat)

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