⚡ electrical engineering

Ternary Logic Encodings of Temporal Behavior Trees with Application to Control Synthesis

यह शोध पत्र टेम्पोरल बिहेवियर ट्रीज़ के लिए एक टर्नरी-वैल्यूड सिग्नल टेम्पोरल लॉजिक फ्रेमवर्क प्रस्तावित करता है जो मिक्स्ड-इंटीजर लीनियर एनकोडिंग्स के माध्यम से लीनियर डायनामिकल सिस्टम्स के लिए करेक्ट-बाय-कंस्ट्रक्शन कंट्रोल स्ट्रैटेजीज़ के संश्लेषण को सक्षम बनाता है, जो ऑनलाइन कंट्रोल जनरेशन का समर्थन करने के लिए पिछले ऑफलाइन विश्लेषण की सीमाओं से आगे बढ़ता है।

मूल लेखक: Ryan Matheu, John S. Baras, Calin Belta

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

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

CC BY 4.0

मूल लेखक: Ryan Matheu, John S. Baras, Calin Belta

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

कल्पना कीजिए कि आप एक रोबोट सॉकर टीम के कोच हैं। आप चाहते हैं कि आपके रोबोट स्मार्ट, सुरक्षित और अप्रत्याशित समस्याओं (जैसे टायर का पंचर होना या अचानक बारिश होना) को संभालने में सक्षम हों।

लंबे समय तक, कोचों के पास दो मुख्य उपकरण थे:

सख्त नियम पुस्तिकाएं (तर्क/Logic): बहुत सटीक, लेकिन जटिल खेलों के लिए इन्हें लिखना कठिन है। यदि आप एक छोटा सा विवरण भी छोड़ देते हैं, तो रोबोट भ्रमित हो जाता है।
फ्लोचार्ट (व्यवहार वृक्ष/Behavior Trees): ये निर्णय लेने वाले पेड़ों की तरह होते हैं। "यदि गेंद यहाँ है, तो उसे किक मारो। यदि बैटरी कम है, तो चार्जर के पास जाओ।" ये इंसानों के समझने और बनाने में आसान हैं, लेकिन गणितीय रूप से यह सिद्ध करना कठिन है कि वे "सुरक्षित" या "सही" हैं।

यह शोध पत्र दोनों दुनियाओं के सर्वश्रेष्ठ गुणों को मिलाने का एक नया तरीका पेश करता है। यह आसानी से पढ़े जाने वाले फ्लोचार्ट को एक सख्त गणितीय भाषा में बदल देता है जिसका उपयोग कंप्यूटर एक आदर्श रोबोटिक चाल को स्वचालित रूप से डिजाइन करने के लिए कर सकता है।

यहाँ सरल उपमाओं का उपयोग करके इसका विवरण दिया गया है:

1. समस्या: "शायद" की स्थिति (The "Maybe" State)

वास्तविक दुनिया में, चीजें हमेशा ब्लैक एंड व्हाइट (सही/गलत) नहीं होतीं।

पुराना तरीका: एक रोबोट का तर्क आमतौर पर केवल हाँ (सफलता) या नहीं (विफलता) जानता था।
नया तरीका: लेखक एक तीसरा विकल्प पेश करते हैं: "अज्ञात" (शायद)।

उपमा: कल्पना कीजिए कि आप बस का इंतजार कर रहे हैं।

सत्य (True): बस यहाँ है।
असत्य (False): बस निश्चित रूप से नहीं आ रही है (इसे रद्द कर दिया गया है)।
अज्ञात (Unknown): बस देर से चल रही है, या ट्रैफिक खराब है। आपको अभी तक नहीं पता कि वह आ रही है या नहीं।

अतीत में, यदि किसी रोबोट को नहीं पता होता था कि कोई स्थिति पूरी हुई है या नहीं, तो वह क्रैश हो जाता या रुक जाता। यह शोध पत्र रोबोट को सिखाता है कि बिना घबराए कैसे कहें, "मुझे अभी पक्का नहीं पता, लेकिन मैं देखते रहूँगा।" इसे टर्नरी लॉजिक (Ternary Logic) कहा जाता है।

2. उपकरण: "जादुई फ्लोचार्ट" (Behavior Trees)

यह शोध पत्र बिहेवियर ट्रीज़ (BTs) का उपयोग करता है। इन्हें रोबोट के मस्तिष्क के लिए एक फ्लोचार्ट की तरह समझें।

अनुक्रम (Sequence →): A करें, फिर B करें, फिर C करें। (एक रेसिपी की तरह)।
सेलेक्टर (Selector ?): A को आजमाएं। यदि A विफल हो जाता है, तो B को आजमाएं। यदि B विफल हो जाता है, तो C को आजमाएं। (एक बैकअप प्लान की तरह)।

लेखकों ने इन फ्लोचार्ट्स को गणितीय समीकरणों में अनुवाद करने का तरीका खोज निकाला है जिन्हें एक कंप्यूटर सॉल्वर पढ़ सके।

3. समाधान: "गणितीय अनुवादक" (The "Math Translator")

इस शोध पत्र का मूल आधार एक अनुवादक है। यह रोबोट के फ्लोचार्ट (इसके "हाँ," "नहीं," और "शायद" अवस्थाओं के साथ) को लेता है और इसे एक विशाल पहेली में बदल देता है जिसे मिक्स्ड-इंटिजर लीनियर प्रोग्राम (MILP) कहा जाता है।

उपमा: कल्पना कीजिए कि आप एक आदर्श रोड ट्रिप की योजना बना रहे हैं।

लक्ष्य: बिंदु A से बिंदु B तक पहुँचना।
नियम: टैंक 10% से कम होने से पहले आपको एक गैस स्टेशन पर रुकना होगा। आपको उस सड़क से बचना होगा जो बंद है।
पहेली: कंप्यूटर को हर मोड़, गति और स्टॉप की गणना करनी होगी ताकि वह वह एक आदर्श रास्ता खोज सके जो सभी नियमों का पालन करता है और कम से कम ईंधन का उपयोग करता है।

क्योंकि लेखकों ने "अज्ञात" (टर्नरी) तर्क को जोड़ा है, कंप्यूटर उन स्थितियों को संभाल सकता है जहाँ परिस्थितियाँ पूरी तरह से ज्ञात नहीं हैं। यह कह सकता है, "यदि सड़क साफ है, तो बाईं ओर जाओ। यदि ब्लॉक है, तो दाईं ओर जाओ। यदि मुझे अभी नहीं पता, तो मैं देखूँगा और इंतज़ार करूँगा।"

4. परिणाम: वे रोबोट जो आगे की सोचते हैं

लेखकों ने इसे दो उदाहरणों के साथ परखा:

एकल रोबोट (Solo Robot): एक रोबोट जिसे तीन स्थानों (A, B और C) पर जाना है।
- ट्विस्ट: यह अपनी बैटरी की जांच करता है। यदि बैटरी अधिक (>80%) है, तो यह A → B जाता है। यदि बैटरी कम है, तो यह A → C (चार्ज करने के लिए) → B जाता है।
- परिणाम: कंप्यूटर ने दोनों परिदृश्यों के लिए आदर्श पथ स्वचालित रूप से बनाया, जिससे यह सुनिश्चित हुआ कि रोबोट कभी भी बिजली खत्म होने की स्थिति में न आए।
रोबोट दस्ता (Robot Squad): तीन रोबोट जो बाधाओं वाले भूलभुलैया (maze) से गुजरने की कोशिश कर रहे हैं।
- ट्विस्ट: उन्हें एक-दूसरे से दूर रहना होगा (टकराव से बचने के लिए) और दीवारों से बचना होगा।
- परिणाम: कंप्यूटर ने निष्कर्ष निकाला कि टकराव से बचने के लिए रोबोट को संकीले गलियारों से गुजरने के लिए बारी-बारी से निकलना चाहिए, जैसे कि फोर-वे स्टॉप पर कारें चलती हैं।

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

इस शोध पत्र से पहले, यदि आप चाहते थे कि एक रोबोट जटिल फ्लोचार्ट का पालन करे, तो आपको चालों का अनुमान लगाना पड़ता था या विफल होने के बाद उन्हें ठीक करना पड़ता था (post-hoc analysis)।

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

यहाँ मैथ्यू, बारस और बेल्टा के शोध पत्र "Ternary Logic Encodings of Temporal Behavior Trees with Application to Control Synthesis" का विस्तृत तकनीकी सारांश दिया गया है।

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

स्वायत्त प्रणालियों (Autonomous systems) को कार्य मॉडलिंग और नियंत्रण संश्लेषण (control synthesis) के लिए मजबूत तरीकों की आवश्यकता होती है। जबकि सिग्नल टेम्पोरल लॉजिक (STL) स्थानिक-कालिक व्यवहारों को निर्दिष्ट करने के लिए समृद्ध अभिव्यक्ति प्रदान करता है, इसे दीर्घ-अवधि नियोजन (long-horizon planning) और जटिल फॉलबैक तंत्र (जैसे, "यदि कार्य A विफल होता है, तो B को आज़माएँ") के लिए संघर्ष करना पड़ता है। बिहेवियर ट्रीज़ (BTs) ऐसे पदानुक्रमित रणनीतियों के लिए एक सहज, मॉड्यूलर ग्राफिकल इंटरफ़ेस प्रदान करते हैं, लेकिन उनमें करेक्ट-बाय-कंस्ट्रक्शन कंट्रोल सिंथेसिस के लिए कठोर औपचारिक मॉडल की कमी है।

BTs को औपचारिक बनाने के मौजूदा दृष्टिकोण (Temporal Behavior Trees या TBTs) ऑफलाइन पोस्ट-हॉक विश्लेषण या बूलियन तर्क का उपयोग करके ट्रेस रिपेयर पर निर्भर करते हैं। ये विधियाँ BT निष्पादन की गतिशील प्रकृति, विशेष रूप से "रनिंग" (Running) अवस्था को पकड़ने में विफल रहती हैं, जहाँ कोई कार्य न तो पूरी तरह से संतुष्ट होता है और न ही विफल। इसके अलावा, नियंत्रण संश्लेषण के लिए मानक STL एनकोडिंग अक्सर अनंत प्रक्षेप पथ (infinite trajectories) मानती हैं या यह आवश्यक मानती हैं कि पूरा क्षितिज (horizon) ज्ञात हो, जो आंशिक प्रक्षेप पथ विश्लेषण या अनिश्चितता वाले सिस्टम के लिए अनुपयुक्त है।

मुख्य चुनौती: बिहेवियर ट्रीज़ और उनके टेम्पोरल ऑपरेटर्स को एक ऐसे गणितीय ढांचे में औपचारिक रूप से कैसे एनकोड किया जाए जो मिक्स्ड-इंटीजर ऑप्टिमाइज़ेशन (कंट्रोल सिंथेसिस) के अनुकूल हो और निम्नलिखित को ध्यान में रखे:

BTs का तीन-अवस्था वाला तर्क (Success, Failure, Running)।
आंशिक प्रक्षेप पथ (partial trajectories) जहाँ भविष्य अज्ञात है।
सिस्टम अनिश्चितता (ऐसे माप जो स्पष्ट रूप से सत्य या असत्य नहीं हैं)।

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

लेखक एक ढांचा प्रस्तावित करते हैं जो TBTs को क्लेनी के स्ट्रॉन्ग लॉजिक ( $K_3$ ), एक टर्नरी लॉजिक सिस्टम, का उपयोग करके पुनर्गठित करता है और इन सिमेंटिक्स को मिक्सड-इंटीजर लीनियर प्रोग्रामिंग (MILP) बाधाओं में एनकोड करता है।

A. टर्नरी लॉजिक फाउंडेशन ( $K_3$ )

मानक बूलियन लॉजिक (True/False) के बजाय, लेखक एक तीसरा मान, अननोन (Unknown - $U$ ) पेश करते हैं, जो BT नोड की "रनिंग" अवस्था या अनिश्चित सिस्टम मापों का प्रतिनिधित्व करता है।

सत्य मान (Truth Values): $\{F, U, T\}$ जो $\{-1, 0, +1\}$ के अनुरूप हैं।
लॉजिक ऑपरेशन्स: क्लेनी बीजगणित तालिकाओं के माध्यम से परिभाषित (जैसे, $T \land U = U$ , $F \lor U = U$ )।
महत्व: यह सिस्टम को ऐसे मामलों को संभालने की अनुमति देता है जहाँ एक प्रक्षेप पथ ने अभी तक विशिष्टताओं को संतुष्ट या उल्लंघन नहीं किया है, जिससे आंशिक प्रक्षेप पथों पर तर्क करने में सक्षम बनाया जा सके।

B. टर्नरी सिग्नल टेम्पोरल लॉजिक (STL)

लेखक $K_3$ पर संचालित होने वाले और आंशिक प्रक्षेप पथों (परिमित समय क्षितिज $t_2$ ) के लिए STL सिमेंटिक्स का विस्तार करते हैं।

सिग्नल प्रेडिकेट्स: इन्हें एक अनिश्चितता थ्रेशोल्ड $\delta$ के साथ परिभाषित किया गया है। यदि $f(x_t) \ge \delta$ , तो मान $T$ है; यदि $f(x_t) \le -\delta$ , तो मान $F$ है; यदि $-\delta < f(x_t) < \delta$ , तो मान $U$ है।
टेम्पोरल ऑपरेटर्स: "ऑलवेज" ( $\square$ $□$ ) और "इवेंचुअली" ( $\diamond$ $⋄$ ) ऑपरेटर्स को सर्च विंडो (ऑपरेटर द्वारा आवश्यक समय अंतराल) और पार्शियल होराइजन (ज्ञात प्रक्षेप पथ की वर्तमान लंबाई) के बीच संबंध को संभालने के लिए पुनर्व्याख्यायित किया गया है।
- यदि सर्च विंडो क्षितिज के भीतर है, तो मानक तर्क लागू होता है।
- यदि विंडो क्षितिज से बाहर निकल जाती है, तो परिणाम $U$ (Unknown) होता है, जब तक कि कोई "शॉर्ट-सर्किट" न हो (जैसे, एक कंजंक्शन में तुरंत $F$ मिल जाता है, जिससे पूरा व्यंजक $F$ हो जाता है, भले ही भविष्य अज्ञात हो)।

C. मिक्स्ड-इंटीजर एनकोडिंग्स

पेपर एक विशिष्ट एनकोडिंग विकसित करता है जो इन टर्नरी लॉजिक नियमों को मिक्स्ड-इंटीजर क्वाड्रेटिक प्रोग्राम (MIQP) के लिए बाधाओं में अनुवादित करती है।

डिसीजन वेरिएबल्स: टर्नरी इंटीजर्स $z \in \{-1, 0, +1\}$ जो एक विशिष्ट समय चरण पर एक फॉर्मूला की संतुष्टि का प्रतिनिधित्व करते हैं।
एनकोडिंग रणनीति:
- प्रेडिकेट्स: अवस्था $x_t$ को $\delta$ के सापेक्ष एनफोर्स करने के लिए बाइनरी वेरिएबल्स का उपयोग किया जाता है।
- लॉजिकल कनेक्टिव्स: टर्नरी सेट पर $\land$ (min) और $\lor$ (max) को एनकोड करने के लिए min/max ऑपरेशन्स का उपयोग किया जाता है।
- TBT ऑपरेटर्स (Seq/Sel):
  - सीक्वेंस ( $\rightarrow$ ): इसके लिए उप-फॉर्मुलों का क्रमिक रूप से संतुष्ट होना आवश्यक है। एनकोडिंग एक स्प्लिट पॉइंट $\tau$ की खोज करती है जहाँ पहला भाग $\phi_1$ को संतुष्ट करता है और शेष भाग $\phi_2$ को संतुष्ट करता है।
  - सेलेक्टर ( $?$ ): इसके लिए कम से कम एक उप-फॉर्मूला का संतुष्ट होना आवश्यक है। एनकोडिंग एक ऐसा स्प्लिट पॉइंट खोजती है जहाँ या तो पहला भाग $\phi_1$ को संतुष्ट करता है OR शेष भाग $\phi_2$ को संतुष्ट करता है।
जटिलता: लेखक उल्लेख करते हैं कि जबकि मानक STL एनकोडिंग में समय जटिलता $O(T)$ रैखिक होती है, TBT एनकोडिंग जिसमें $k$ उप-फॉर्मूले शामिल हैं, समय विभाजन (time splits) के नेस्टेड सर्च के कारण $O(T^{k+1})$ के रूप में स्केल करती है।

D. कंट्रोल सिंथेसिस समस्या

फ्रेमवर्क लीनियर डिस्क्रीट-टाइम सिस्टम के लिए एक इष्टतम नियंत्रण समस्या को स्वरूपित करता है:
$\min \sum u_t^T R u_t$
विषय (Subject to):

सिस्टम डायनेमिक्स ( $x_{t+1} = Ax_t + Bu_t$ )।
इनपुट बाधाएं (Input constraints)।
TBT संतुष्टि बाधा: सिंथेसाइज किया गया प्रक्षेप पथ समय $t^*$ से $\phi$ वाले TBT फॉर्मूले को संतुष्ट करना चाहिए।

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

$K_3$ में BTs का औपचारिकीकरण: यह पेपर $K_3$ का उपयोग करके बिहेवियर ट्रीज़ के औपचारिकीकरण को ठोस रूप देता है, जो स्पष्ट रूप से "रनिंग" अवस्था को "अननोन" सत्य मान से जोड़ता है।
टर्नरी STL सिमेंटिक्स: यह आंशिक प्रक्षेप पथों पर $K_3$ का उपयोग करके STL सिमेंटिक्स को परिभाषित करता है, जिससे पूर्ण क्षितिज ज्ञात न होने या माप अनिश्चित होने पर भी फॉर्मूलों का मूल्यांकन संभव होता है।
मिक्स्ड-इंटीजर एनकोडिंग्स: लेखक टर्नरी लॉजिक पर TBT ऑपरेटर्स (Sequence और Selector) के लिए पहले मिक्स्ड-इंटीजर लीनियर एनकोडिंग प्रदान करते हैं, जो करेक्ट-बाय-कंस्ट्रक्शन कंट्रोल सिंथेसिस को सक्षम बनाता है।
उपयोगिता का प्रदर्शन: फ्रेमवर्क को दो केस स्टडीज के माध्यम से मान्य किया गया है जो लीनियर डायनेमिकल सिस्टम्स के लिए ऑप्टिमल कंट्रोल प्रॉब्लम्स को हल करते हैं, यह सिद्ध करता है कि BTs जटिल फॉलबैक लॉजिक को संभालने वाले व्यवहार्य और इष्टतम प्रक्षेप पथ उत्पन्न कर सकते हैं।

4. परिणाम और केस स्टडीज (Results and Case Studies)

लेखकों ने Gurobi सॉल्वर का उपयोग करके दो परिदृश्यों में अपने ढांचे को मान्य किया:

केस स्टडी 1: डिस्क्रीट-टाइम डबल इंटीग्रेटर (मोबाइल रोबोट)
- कार्य: लक्ष्य A तक नेविगेट करें, फिर बैटरी की जांच करें। यदि $\ge 80\%$ है, तो लक्ष्य B पर जाएँ; अन्यथा, लक्ष्य C (चार्जर) फिर लक्ष्य B पर जाएँ।
- परिणाम: सॉल्वर ने दो अलग-अलग प्रारंभिक बैटरी अवस्थाओं के लिए प्रक्षेप पथ सफलतापूर्वक सिंथेसाइज किए।
  - उच्च बैटरी: रोबोट A $\to$ B गया।
  - कम बैटरी: रोबोट A $\to$ C $\to$ B गया।
- प्रदर्शन: 25-स्टेप होराइजन के लिए ~97 सेकंड में ग्लोबल ऑप्टिमलिटी तक हल किया गया।
केस स्टडी 2: मल्टी-एजेंट प्लानिंग
- कार्य: तीन एजेंटों को सुरक्षा बाधाओं से बचते हुए और न्यूनतम अलगाव दूरी बनाए रखते हुए क्रमवार विशिष्ट लक्ष्यों तक पहुँचना होगा।
- परिणाम: सिस्टम ने ऐसे प्रक्षेप पथ सिंथेसाइज किए जहाँ एजेंटों ने सुरक्षा बाधाओं को संतुष्ट करने के लिए संकीर्ण बाधा गलियारों (narrow obstacle corridors) से गुजरने के लिए स्वाभाविक रूप से कतार (queue) बनाई।
- प्रदर्शन: 3 एजेंटों के लिए 20-स्टेप होराइजन पर ~307 सेकंड में हल किया गया।

5. महत्व और प्रभाव (Significance and Impact)

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

संक्षेप में, यह पेपर उच्च-स्तरीय, मॉड्यूलर बिहेवियर ट्री विशिष्टताओं को ऑप्टिमाइज़ेशन समस्याओं में अनुवादित करने के लिए एक गणितीय रूप से कठोर तरीका प्रस्तुत करता है, जिससे स्वायत्त प्रणालियों को इष्टतम, सुरक्षित और मजबूत नियंत्रण रणनीतियाँ उत्पन्न करने में सक्षम बनाया जा सके जो विफलताओं और अनिश्चितताओं के अनुकूल हो सकें।