در این مقاله، ما یک الگوریتم پالایش انتزاعی هدایت‌شده (سگار) را برای تحلیل پایداری سیستم‌های ترکیبی چند وجهی ارائه می‌کنیم. نتایج ما بر اساس یک الگوریتم انتزاع گزاره کمی و بررسی مدل برای تجزیه و تحلیل پایداری است که یک مثال متضاد نشان می دهد که دلیل بالقوه ای برای بی ثباتی را نشان می دهد. مشارکت های اصلی این مقاله شامل اعتبار سنجی مثال متقابل و پالایش انتزاع بر اساس تجزیه و تحلیل مثال متقابل است. مثال متقابلی که توسط تحلیل انتزاعی گزاره کمی برگردانده می‌شود، چرخه‌ای است که حاصل ضرب وزنهای لبه‌های آن بیشتر از 1 است. اعتبارسنجی شامل بررسی وجود یک اجرای واگرای نامتناهی است که چرخه را بی‌نهایت چندین بار دنبال می‌کند. برخلاف مورد Cegar برای ایمنی، مشکل اعتبارسنجی یک مشکل بررسی مدل محدود نیست. با استفاده از بینش های جدید، ما یک توصیف ساده برای وجود یک اجرای واگرای نامتناهی از نظر رضایت از یک فرمول منطقی مرتبه اول ارائه می کنیم که می تواند به طور موثر حل شود. به طور مشابه، پالایش بیشتر درگیر است، زیرا، پیشینی هیچ محدودیتی در تعداد مراحل محاسباتی پیشین وجود ندارد که باید انجام شود تا مثال متقابل انتزاعی را باطل کند. ما استراتژی هایی را برای اصلاح بر اساس بینش های مرحله اعتبار سنجی ارائه می کنیم. ما الگوریتم‌های اعتبارسنجی و اصلاح را پیاده‌سازی کرده‌ایم و از ابزار تأیید پایداری Averist در انتهای پشتی برای انجام انتزاع و بررسی مدل استفاده می‌کنیم. ما الگوریتم Cegar را با Averist مقایسه می‌کنیم و نتایج تجربی را گزارش می‌کنیم که مزایای پالایش هدایت‌شده به‌عنوان مثال متقابل را نشان می‌دهد.
کلید واژه ها
- نمونه انتزاعی
- الگوریتم سیگار
- پارتیشن چند وجهی
- سیستم های هیبریدی سوئیچ شده
- ایالات چاقو
این کلمات کلیدی توسط ماشین اضافه شده اند و نه توسط نویسندگان. این فرآیند آزمایشی است و ممکن است با بهبود الگوریتم یادگیری، کلمات کلیدی به روز شوند.
دانلود مقاله کنفرانس به صورت PDF
1. مقدمه
سیستم های ترکیبی به سیستمهایی که دارای رفتارهای مداوم گسسته هستند ، اشاره می کنند. این موارد به طور طبیعی در سیستم های کنترل تعبیه شده به عنوان یک نتیجه از تعامل نرم افزار تعبیه شده ، که در مراحل گسسته اجرا می شود ، با سیستم های فیزیکی ، که به طور مداوم در زمان واقعی متراکم تکامل می یابند ، آشکار می شوند. به طور خاص ، ما سیستم های ترکیبی سوئیچ شده را در نظر می گیریم [13] که در آن حالت مداوم در حین تعویض حالت تغییر نمی کند. اینها برای مدل سازی کنترل نظارتی مناسب هستند ، که در آن یک سرپرست به طور مداوم وضعیت گیاه را حس می کند و بر اساس آن تصمیمات را تغییر می دهد.
در این مقاله ، ما بر تجزیه و تحلیل پایداری خودکار سیستم های ترکیبی سوئیچ شده تمرکز می کنیم. ثبات یک خاصیت اساسی در طراحی سیستم کنترل است و استحکام سیستم را با توجه به حالت های اولیه یا ورودی ها ضبط می کند. ما یک مفهوم کلاسیک از ثبات ، یعنی ثبات لیاپونوف را با توجه به یک نقطه تعادل در نظر می گیریم - وضعیتی از سیستم که با تکامل زمان تغییر نمی کند. به طور شهودی ، اگر اعدام هایی که در یک محله کوچک از نقطه تعادل شروع می شود ، یک نقطه تعادل پایدار است.
روشهای کلاسیک برای تجزیه و تحلیل پایداری مبتنی بر نمایش تابعی از فضای وضعیت به واقعیت های غیر منفی به نام یک تابع Lyapunov است (به عنوان مثال ، [11] را ببینید) ، که تضمین می کند که مقدار عملکرد در طول هر اجرا کاهش می یابداز سیستمروشهای خودکار برای تجزیه و تحلیل پایداری به جستجوی الگوی مبتنی بر یک عملکرد Lyapunov متکی هستند. به عنوان مثال ، یک عملکرد چند جمله ای با ضرایب به عنوان پارامترها به عنوان یک عملکرد کاندیدای لیاپونوف انتخاب می شود. پارامترها با حل نابرابری های ماتریس خطی یا جمع آوری تعداد مربعات [17] محاسبه می شوند که هنگام رمزگذاری محدودیت های عملکرد لیاپونف بوجود می آیند.
یکی از چالش های روشهای مبتنی بر لیاپونوف ، نبوغ کاربر مورد نیاز در انتخاب الگوهای مناسب است. یک جستجوی جامع در تمام الگوها (به عنوان مثال ، چند جمله ای از افزایش درجه ها) برای درجات کوچک چند جمله ای قابل کنترل نیست. در [20 ، 21] ، نویسندگان یک روش تجزیه و تحلیل پایداری متناوب را بر اساس انتزاع برای زیر کلاس سیستم های ترکیبی به نام سیستم های ترکیبی چند قطبی ارائه می دهند. سیستم های ترکیبی چند قطبی یک کلاس جالب از سیستم ها هستند که می توانند برای انتزاع سیستم های ترکیبی خطی و غیر خطی استفاده شوند [3 ، 12]. نویسندگان یک روش انتزاع محمول کمی را پیشنهاد می کنند که یک نمودار وزنی محدود را ایجاد می کند ، و دومی را برای وجود چرخه ها با محصول وزنه های لبه \ (\ ge \) تجزیه و تحلیل می کند. پیشنهاد می شود با انتخاب مجموعه ای بزرگتر از پیش بینی ها ، انتزاع بهتری را می توان بدست آورد. با این حال ، هیچ استراتژی کارآمد برای انتخاب همان مورد بحث نیست. در اینجا ما تجزیه و تحلیل کمی مبتنی بر انتزاع محمول کمی را انجام می دهیم و در مورد استراتژی های پالایش بر اساس اعتبار سنجی ضد نمونه بحث می کنیم. این مورد به عنوان Cegar (پالایش انتزاع هدایت شده با مثال) گفته می شود [6]).
The main contributions of the paper are the validation and refinement algorithms. Validation consists of checking if an abstract counterexample actually corresponds to a concrete counterexample. In the context of safety analysis [6], an abstract counterexample typically consists of a finite sequence of abstract states or nodes in a finite graph from the initial state to an unsafe state. Validation consists of checking if there exists a finite execution of the system which follows the sequence of abstract states. However, the validation problem we encounter is not a bounded model-checking problem as above. Instead, it consists of checking if there exists an infinite diverging trajectory that follows the cycle infinitely many times. This property cannot, as is, be encoded as the satisfiability of a formula in a finitary logic. We provide a novel characterization of the existence of an infinite diverging execution in terms of the existence of a finite execution that follows the cycle once from a continuous state x to a continuous state y such that \(y = \alpha x\) for some \(\alpha >1 \). این یک روش الگوریتمی برای انجام اعتبار سنجی ارائه می دهد ، زیرا ، دومی می تواند به عنوان مشکل رضایت بخش یک فرمول منطق مرتبه اول رمزگذاری شود و به طور مؤثر حل شود.
پالایش در تجزیه و تحلیل ایمنی شامل محاسبات ، به طور تکراری ، زیر مجموعه های حالت های بتونی مربوط به حالت های انتزاعی است که می توانند به حالت های ناامن برسند. اگر نمونه ضد نمونه ای جالب باشد ، یکی از مجموعه های محاسبه شده خالی است ، که به آن نقطه پالایش گفته می شود و با بررسی برخی از حالت های انتزاعی محلی در اطراف این نقطه از پالایش ، پالایش صورت می گیرد. از آنجا که ، نمونه ضد بتن مورد نیاز برای اعتبار سنجی دارای طول محدود M ، بالایی است که با طول ضد نمونه انتزاعی محدود شده است ، نقطه پالایش در مراحل M می رسد. در مورد پالایش برای ثبات ، ما نشان می دهیم که اگرچه پیشینی چنین محدودیتی در مورد پالایش وجود ندارد ، اگر نمونه ضد نمونه ای جالب باشد ، اما قطعاً به آن رسیده است.
ما دو استراتژی پالایش را پیشنهاد می کنیم - با این حال ، یکی از آنها همیشه کاربردی است ، اما بخش بزرگی از نمونه های متضاد را از بین نمی برد. مورد دیگر فقط در موارد خاص قابل استفاده است ، اما بخش بزرگی از نمونه های ضد را از بین می برد. اگر روش اعتبار سنجی به این نتیجه برسد که نمونه ضد نمونه نه تنها اجرای واگرایی نامحدود مربوط به آن را ندارد ، بلکه هیچ اعدام بی نهایت مربوط به آن را ندارد. سپس الگوریتم های پالایش ما وزن لبه را نادیده می گیرند و هدف آن "از بین بردن" چرخه است. در غیر این صورت ، وزن را در نظر می گیرد و فقط هدف آن کاهش وزن در چرخه است.
ما الگوریتم Cegar را اجرا کرده ایم که از Averist در پس زمینه استفاده می کند تا مراحل انتزاع و بررسی مدل Cegar را انجام دهد. ما مقایسه های تجربی بین الگوریتم Cegar و الگوریتم Averist را گزارش می کنیم. برای دومی ، ما پالایش را بر اساس استراتژی ساده لوحانه برای اضافه کردن یکنواخت پیش بینی های جدید در نظر می گیریم. نتایج تجربی ما مزایای Cegar را از نظر کاهش زمان محاسبه و انتزاع های کوچکتر نشان می دهد که نتیجه پالایش دقیق در هر تکرار است. کار آینده شامل گسترش چارچوب Cegar برای تجزیه و تحلیل پایداری به کلاسهای عمومی تر سیستم های ترکیبی و مفاهیم مرتبط با آن مانند ثبات بدون علامت خواهد بود.
کار مرتبط. ما به طور خلاصه در مورد کار مرتبط بحث می کنیم. یک کار بزرگ در مورد تجزیه و تحلیل پایداری مبتنی بر عملکرد Lyapunov برای سیستم های ترکیبی خطی و غیر خطی وجود دارد ، به نظرسنجی ها مراجعه کنید [4 ، 14]. برخی از کارها در مورد تأیید خودکار پایداری سیستم های خطی با پالایش مکرر پارتیشن ها وجود دارد [15 ، 16 ، 24] ، با این حال ، این یک رویکرد مبتنی بر انتزاع نیست و پالایش ها با تجزیه و تحلیل های ضد نمونه هدایت نمی شوند. Cegar برای تأیید ایمنی سیستم های ترکیبی [2 ، 5 ، 18] و تجزیه و تحلیل پایداری منطقه مورد بررسی قرار گرفته است [8]. با این حال ، بر خلاف لیاپونوف و پایداری بدون علامت ، ایمنی و پایداری منطقه خصوصیات متغیر بی سیمین هستند. اخیراً ، برخی از کارها در مورد یادگیری الگوهای مربوط به توابع Lyapunov وجود دارد [10].
2 Polyhedral Switched System ( \(>\) )
A hybrid automaton [1] is a popular formalism for modeling mixed discrete-continuous behaviors. It extends the finite state automaton model for discrete dynamics by annotating the modes with differential equations or inclusions for modeling the physical systems. In addition, invariants on the modes and guards on the edges provides constraints that need to be satisfied during evolution and mode switching, respectively. A polyhedral switched system \(>\ ، \) نوع خاصی از اتوماتیک ترکیبی است که در آن هر حالت با یک گنجاندن دیفرانسیل چند قطبی همراه است و متغیرها و نگهبانان با محدودیت های خطی مشخص می شوند.
تعریف 1
A n -dimensional polyhedral switched system ( \(>\)) یک tuple \ (\ mathcal = (\ textit ، \ textit ، x ، \) \ (\ textit ، \ textit ، \ textit) \) است:
\ (\ textit \) مجموعه ای محدود از مکان ها است.
\ (\ textit \ subeTeq \ textit \ times \ textit \) مجموعه ای محدود از لبه ها است.
\ (x = \ mathbb ^n \) فضای مداوم حالت است.
\ (\ textit: \ textit \ RightArrow \ textit (n) \) تابع جریان است.
\ (\ textit: \ textit \ RightArrow \ textit (n) \) عملکرد ثابت است. وت
\ (\ textit: \ textit \ RightArrow \ textit (n) \) تابع نگهبان است.
که در آن \ (\ textit (x) \) مجموعه ای از همه زیر مجموعه های چند قطبی محدب x را نشان می دهد ، و \ (\ textit (x) \) مجموعه ای از مجموعه های چندجمله محدب جمع و جور را نشان می دهد.
نشانه گذاری
From now on, we will denote each of the elements in a \(>\) \ (\ mathcal \) ، با \ (\ mathcal \) به عنوان یک اشتراک ، به عنوان مثال ، عملکرد ثابت به عنوان \ (\ textit_ نامیده می شود.<\mathcal>\) .
مثال
شکل 1 یک سیستم سوئیچی شده چند بعدی 3 بعدی را در امتداد صفحه \ (x-y \) نشان می دهد که مقدار در امتداد Z-axis به عنوان 1 باشد. در اصل ، مجموعه های چند قطبی از A تا F هرم هستند که در \ متمرکز شده اند (x = 0، y = 0 \).\ (v_a \) از طریق \ (v_f \) نشان دهنده polyhedra در اجزاء دیفرانسیل چند قطبی مربوط به مناطق a تا f. ما فرض می کنیم که \ (\ dot = 1 \) در همه جا. اجرای نمونه سیستم با استفاده از دنباله ای از خطوط نازک هدایت شده نشان داده شده است.
A switched system starts evolving in a mode \(q \in \textit\) and a continuous state x . In this mode q , the continuous state evolves inside \(\textit(q)\) such that the differential of the evolution at any time lies within \(\textit(q)\) . If \((q_1, q_2)\) is an edge of the system and the continuous state satisfies the guard, a switch from \(q_1\) to \(q_2\) can occur. The continuous state does not change during the mode switching. The semantics of a \(>\) \ (\ Mathcal \) توسط مجموعه اعدام های نمایش داده شده توسط سیستم ارائه شده است.
تعریف 2
An execution \(\sigma \) of a \(>\) ابعاد n یک سه گانه است (((<\iota >، \ eta ، \ gamma) \) ، جایی که \ (<\iota >\) دنباله ای از فواصل زمانی \ (I_0 ، I_1 ، \ ldots \) است که به زمان های صرف شده توسط اجرای در یک مکان خاص اشاره دارد ، \ (\ eta: \ mathcal (<\iota >) \ Rightarrow x \) ، جایی که \ (\ mathcal (<\iota >) = \ cup _i<\iota >(i) \) ، وضعیت مداوم را در همه زمان ها نشان می دهد ، و \ (\ gamma \) نقشه های من را به محل اعدام در فاصله \ (i_i \) تبدیل می کند.
اعدام \ (\ sigma = (<\iota >، \ eta ، \ gamma) \) از \ (\ mathcal \) گفته می شود اگر \ (\ mathcal (\ mathcal (\ mathcal) کامل باشد<\iota >) \) \ ([0 ، \ infty) \) ؛در غیر این صورت ، آن را محدود می نامند. مجموعه همه اعدام های \ (\ Mathcal \) توسط \ (\ textit (\ mathcal) \) و مجموعه ای از همه اعدام های کامل توسط \ (\ textit (\ mathcal) \) مشخص می شود.
(سمت چپ) سیستم سوئیچی شده چند قطبی (راست) نمونه ضد انتزاعی
2. 1 روابط قابل دسترسی
We introduce certain predicates related to reachability which we will need in the sequel. Let us fix an n -dimensional \(>\) \ (\ mathcal \) ، دو مکان \ (q_1 \) و \ (q_2 \) در \ (\ textit_<\mathcal>\) ، و سه مجموعه چند قطبی \ (p_1 \) ، \ (p_2 \) و p بیش از \ (\ mathbb ^n \) برای بقیه بخش.
It captures the set of points \((x, y) \in P_1 \times P_2\) such that there exists an execution which starts at \((q_1, x)\) and ends at \((q_2, y)\) and remains in P at all intermediate time points. It is shown in [21] that the \(\textit_\mathcal\) is computable and can be represented as a 2 n -dimensional polyhedral set. Next, we define the predecessor and successor operators denoted by \(>_<\mathcal>\) and \(>_<\mathcal>\) , and their weighted counter-parts \(>_\mathcal\) and \(>به ترتیب _ \ Mathcal \).
در اینجا ، W یک عدد واقعی مثبت است و e \ (|| \ cdot || \) هنجار بی نهایت یک عنصر را در \ (\ Mathbb ^n \) نشان می دهد.
3 پایداری
در این بخش ، ما یک مفهوم کلاسیک از ثبات در تئوری کنترل ، یعنی ثبات لیاپونوف را تعریف می کنیم. ما ثبات سیستم را با توجه به مبدا \ (\ bar \) در نظر می گیریم ، که تصور می کنیم یک نقطه تعادل است. به طور شهودی ، پایداری لیاپونوف این مفهوم را ضبط می کند که اعدام که از نزدیک به نقطه تعادل شروع می شود ، نزدیک به آن باقی مانده است. le \ (_ \ epsilon (\ bar) \) یک توپ باز از شعاع \ (\ epsilon \) در اطراف \ (\ bar \) باشد ، که نشانگر \ (\\) است.
تعریف 3
A \(>\) \(\mathcal\) is said to be Lyapunov stable , if for every \(\epsilon > 0\) , there exists a \(\delta >0 \) به گونه ای که برای هر اعدام \ (\ sigma = (<\iota >، \ eta ، \ gamma) \ in \ textit (\ mathcal) \) با \ (\ eta (0) \ in _ \ delta (\ bar) \) ، \ (\ eta (t) \ in _ \ epsilon (\ bar) \) برای هر \ (t \ in \ mathcal (<\iota >)\) .
Observe that Lyapunov is a local property whose satisfaction depends on the behaviors of the system in a small neighborhood around the origin. Hence, the only polyhedral sets of the \(>\) which play a role in stability analysis are those which contain the \(\bar\) . Therefore, we will assume without loss of generality that the \(>\) به صورت عادی است [20 ، 21].
تعریف 4
A polyhedral set P is closed under positive scaling if for every \(x \in P\) and \(\alpha >0 \) ، \ (\ alpha x \ in p \).
تعریف 5
A \(>\) \ (\ mathcal \) اگر برای هر \ (q \ in \ textit \) و برای هر \ (e \ in \ textit \) ، \ (\ textit_ \ mathcal (q) \) و \(\ textit_ \ mathcal (e) \) مقیاس مثبت بسته هستند.
4 پالایش انتزاع هدایت شده به عنوان مثال
در این بخش ، چارچوب Cegar را برای تجزیه و تحلیل پایداری ارائه می دهیم. این الگوریتم در الگوریتم 1 خلاصه شده است. اول ، ما به طور خلاصه الگوریتم های انتزاع و بررسی مدل را برای تجزیه و تحلیل پایداری سیستم های سوئیچی شده چند قطبی از [21] مرور می کنیم. سپس ، ما الگوریتم های اعتبار سنجی و پالایش جدید را ارائه می دهیم.
4. 1 انتزاع
روش انتزاع ، اصلاح انتزاع محمول استاندارد است [9] که یک سیستم حالت محدود را با استفاده از یک مجموعه محدود از پیش بینی ها ، که سیستم بتونی را شبیه سازی می کند ، ایجاد می کند. در [19] نشان داده شد که ثبات با شبیه سازی حفظ نمی شود و در عوض مفاهیم قوی تر که باعث تقویت رابطه شبیه سازی با شرایط تداوم می شوند ، لازم است. از این رو ، روش انتزاع در [20] یک نمودار وزنی محدود را همانطور که در شکل 1 نشان داده شده است ، ساخت. در صورت وجود اعدام از یک جفت مکان و جنبه به دیگری با باقی ماندن در منطقه مشترک جنبه ها ، یک لبه بین دو راس وجود دارد. علاوه بر این ، وزنهای موجود در لبه ها اطلاعات کمی را ذخیره می کنند ، که هنگام رسیدن به جنبه هدف نسبت به جایی که در جنبه منبع شروع می شود ، از چه عاملی به منشأ نزدیک می شود. در مرحله بعد ، ما ساخت رسمی سیستم انتزاعی را ارائه می دهیم ، برای آنچه ما برخی از تعاریف کمکی را معرفی می کنیم.
تعریف 6
یک پارتیشن چند قطبی \ (\ mathcal \) از \ (x \ subeeteq \ mathbb ^n \) یک مجموعه محدود از مجموعه های چند قطبی محدب بسته ، \ (\
The elements of a polyhedral partition are referred to as regions. A polyhedral partition is said to respect a \(>\) \ (\ mathcal \) اگر برای هر \ (p \ in \ mathcal \) ، \ (q \ in \ textit_ \ mathcal \) و \ (e \ in \ textit_ \ mathcal \) ، یا \ (p \ (p \ (subeetq \ textit_<\mathcal>. ه) = \ vacyset \).
تعریف 7
یک پارتیشن جنبه \ (\ mathcal \) یک پارتیشن چند قطبی \ (\ mathcal \) یک پارتیشن چند قطبی از \ (\ cup _ است
\ جزئی (p) \) ، که در آن \ (\ جزئی (p) \) مرز ص است.
تعریف 8
Let us fix a concrete \(>\) \ (\ Mathcal \). بگذارید \ (\ mathcal \) یک پارتیشن چند قطبی از \ (x \) باشد و \ (\ mathcal \) یک پارتیشن جنبه ای از \ (\ mathcal \) باشد. سیستم انتزاعی نمودار وزنی محدود است (\ textit (\ mathcal ، \ mathcal ، \ mathcal) = (v ، e ، w) \) تعریف شده به شرح زیر است.
\ (v = \ textit \ times \ mathcal \).
\ (W: E \ Rightarrow \ Mathbb _<\ge 0>\ فنجان \<\infty \>\) ، به گونه ای که برای \ (e = ((q_1 ، f_1) ، p ، (q_2 ، f_2)) \ in e \) ،
محاسبه وزن در لبه های نمودار انتزاعی را می توان با حل یک مشکل بهینه سازی در مجموعه چند قطبی رابطه قابلیت دسترسی ساخت [20 ، 21].
4. 2 تولید مدل و ضد نمونه
برای هر اجرای سیستم بتونی ، مسیری در نمودار وزنی وجود دارد به گونه ای که محصول وزنهای لبه های آن محدوده بالایی در مقیاس بندی اعدام است - نسبت فاصله فاصله نقطه انتهایی آن از مبدا تافاصله نقطه شروع آن از مبدا. بنابراین ، قضیه زیر شرایط کافی را در نمودار وزنی محدود فراهم می کند که حاکی از پایداری سیستم بتونی است. ما می گوییم که اگر یک اعدام وجود داشته باشد که همیشه در منطقه باقی بماند و واگرایی داشته باشد (به طور دلخواه از منشأ دور می رود) در \ (\ mathcal \) منفجر می شود. یک پارتیشن \ (\ mathcal \) را در نظر بگیرید که به \ (\ mathcal \) احترام می گذارد ، سپس برای هر منطقه \ (p \ in \ mathcal \) وجود دارد \ (q \ in \ textit_ \ mathcal \) به گونه ای که \ (p \subeetq \ textit_<\mathcal>(س) \). منطقه P در مورد \ (p \ cap \ textit_ \ mathcal (q) \ ne \ vetyset \) در \ (\ mathcal \) منفجر می شود. با توجه به یک مسیر \ (\ pi \) ، اجازه دهید \ (w (\ pi) \) محصول وزنهای موجود در لبه های \ (\ pi \) را نشان دهد.
قضیه 1
[21]. Let \(\mathcal\) be a \(>\) , \(\mathcal\) be a polyhedral partition respecting \(\mathcal\) and \(\mathcal \) be a facet partition of \(\mathcal\) . Then, the \(>\) \ (\ mathcal \) اگر برای هر چرخه ساده \ (\ pi \) ، \ (w (\ pi) \ le 1 \) پایدار باشد و هیچ منطقه ای در \ (\ mathcal \) وجود ندارد که در آن منفجر شود.\ (\ Mathcal \).
The conditions on the abstract system can be efficiently checked [20, 21]. The model-checking procedure will either return that \(\mathcal\) is stable or in the case that the abstract system does not satisfy the conditions of Theorem 1 return an abstract counterexample in the form of a simple cycle with weight >1 یا بگویید که این سیستم دارای یک منطقه منفجر شده است. در مورد اول ، ما می دانیم که سیستم پایدار است و در مورد سوم ، ناپایدار است. برای مورد دوم ، الگوریتم Cegar به مرحله اعتبار سنجی ادامه می یابد.
مثال
Consider the 3-dimensional \(>\) نشان داده شده در شکل 1 (سمت چپ). اکنون ، تصویر در سمت راست بخشی از سیستم انتزاعی را نشان می دهد. گره ها بر روی جنبه هایی که نشان می دهند قرار گرفته اند و لبه ها وجود اعدام بین چنین جنبه هایی را نشان می دهد که از طریق مجموعه چند قطبی مشترک در حال تحول هستند. به عنوان مثال ، ما مشاهده می کنیم که اعدام از Facet \ (F_1 \) به \ (F_2 \) در حال تحول از طریق Polyhedron c وجود دارد. چرخه نشان داده شده یک نمونه ضد انتزاعی است زیرا وزن مرتبط با آن بیشتر از 1 است. اعتبار سنجی بررسی می کند که آیا یک اجرای واقعی در طول چرخه وجود دارد که می تواند شاهد بی ثباتی باشد.
نکته 1
The conditions in Theorem 1 are, in fact, both necessary and sufficient in the case of 2-dimensional \(>\) S [23] ، با این حال ، فقط در 3 یا بیشتر ابعاد کافی است. دو دلیل برای محافظه کارانه وجود دارد. اول ، لبه ها به صورت روحی بسته نمی شوند ، زیرا با توجه به اعدام های موجود در سیستم بتونی وجود دارند. به طور دقیق تر ، وجود اعدام از یک جنبه \ (f_1 \) به \ (f_2 \) و اجرای از \ (f_2 \) تا \ (f_3 \) به معنای این نیست که یک اعدام واحد وجود دارد که از \ (می رود (()f_1 \) به \ (f_2 \) به \ (f_3 \). ثانیا ، ممکن است یک انتقال مشابه بر وزن نباشد. فرض کنید که وزن در لبه از \ (f_1 \) تا \ (f_2 \) \ (w_1 \) است و از \ (f_2 \) تا \ (f_3 \) \ (w_2 \) است. اعدام از برخی از نقاط در \ (f_1 \) تا جایی در \ (f_2 \) با مقیاس گذاری \ (w_1 \) و اجرای از برخی از نقطه در \ (f_2 \) تا یک نقطه در \ (f_3 \) وجود دارد. با وزن \ (W_2 \). با این وجود ، ممکن است یک اعدام واحد از \ (f_1 \) تا \ (f_3 \) از طریق \ (f_2 \) وجود نداشته باشد به گونه ای که مقیاس بندی مربوط به پیشوند از \ (f_1 \) تا \ (f_2 \) \ ((f_2 \) است ((f_1 \)w_1 \) ، در حالی که از \ (f_2 \) تا \ (f_3 \) \ (w_2 \) است.
اعتبار سنجی 4. 3
ما برخی از مقدمات را ارائه می دهیم و مشکل اعتبار سنجی را تعریف می کنیم. در مرحله بعد ، روش اعتبار سنجی و مبنای نظری آن ارائه شده است.
تعریف 9
A simple cycle \(\pi \) in \(\textit(\mathcal,\mathcal,\mathcal )\) is an abstract counterexample if \(W(\pi ) >1 \).
الف) مشکل اعتبار سنجی. اعتبار سنجی شامل بررسی اینکه آیا نمونه ضد انتزاعی با نقض ثبات در سیستم بتونی مطابقت دارد یا خیر. بگذارید یک نمونه متقابل \ (\ pi = (q_0 ، f_0) ، p_0 ، (q_1 ، f_1) ، p_1 ، \ ldots ، (q_ ، f_) ، p _ ، (q_0 ، f_0) \) از \ (\ mathcal = اصلاح کنیم.\ textit (\ mathcal ، \ mathcal ، \ mathcal) \). تعریف زیر ارتباط بین نمونه ضد انتزاعی و اعدام های موجود در سیستم بتونی را بیان می کند.
تعریف 10
مفهوم زیر نقض پایداری لیاپانوف را در امتداد \(\pi \) نشان می‌دهد. مثال متقابل انتزاعی \(\pi \) شاهد نقض پایداری لیاپانوف توسط سیستم بتنی \(\mathcal\) است اگر اجراهایی با مقیاس‌بندی دلخواه وجود داشته باشد که از چرخه مربوط به وزن‌ها پیروی می‌کنند.
$$\begin
$$\begin
گزاره بعدی بیان می کند که شرط فوق در واقع به این معنی است که یک اجرای کامل در امتداد \(\pi \) وجود دارد.
گزاره 1
شرط (C1) معادل وجود یک اجرای کامل \(\sigma \) \(\mathcal\) است به طوری که \(\sigma \mathop<\leadsto >\limits ^ \pi \) .
در حالی که (C1) را می توان دقیقاً اعتبارسنجی کرد، یک اصلاح مربوط به (C1) سعی می کند فقط اجراهایی را که دقیقاً وزن های لبه های \(\pi \) را دنبال می کنند حذف کند. به منظور تسریع پیشرفت در تکرارهای Cegar، ما یک مشکل اعتبارسنجی قوی‌تر را در نظر می‌گیریم، که در آن نیازی به دنبال کردن وزن‌ها از اجرا نداریم، اما همچنان واگرا هستیم.
تعریف 11
اگر یک اجرای کامل واگرا \(\sigma \) وجود نداشته باشد به یک مثال انتزاعی \(\pi \) گفته می‌شود که \(\sigma \leadsto \pi \) وجود نداشته باشد.
مشکل اعتبارسنجی:با توجه به مثال انتزاعی \(\pi \) آیا \(\pi \) جعلی است؟
ب. رویه اعتبار سنجی. اصل رویه اعتبارسنجی این است که مشکل بررسی وجود بی‌نهایت اجرا را به اجراهای محدود تقلیل دهیم. از این رو، برای \( m \in \ mathbb _<\ge 0>\) یک گزاره تعریف می کنیم \(\psi _<\pi >(m)\) که مجموعه نقاط \(x_0,\dots , x_k\) را می گیرد به طوری که با دنبال کردن چرخه یک بار می توان به \(x_k\) از \(x_0\) رسید و \(x_k = mx_0\).
در مرحله بعد، قضیه اصلی را برای اعتبار سنجی بیان می کنیم.
قضیه 2
موارد زیر برای مثال انتزاعی \(\pi \) صادق است:
\(\exists m>1 : \psi _<\pi >(m)\) \(\Rightarrow \exists \sigma \in \textit(\mathcal) : \sigma \leadsto \pi \wedge \sigma \, \mathrm \) .
\(\عدم \وجود m: \psi _<\pi >(m)\) \(\Rightarrow \) \(
ot \exists \sigma \in \textit(\mathcal) : \sigma \leadsto \pi \) .<\pi >(m) \wedge \not \exists m>\(\وجود m:\) \(\psi _<\pi >1 : \psi _
(m)\) \(\پیکان راست \)<\leadsto >\limits ^ \pi \) .
ot \exists \sigma \in \textit(\mathcal) : \sigma \mathop
Condition V1 implies that when there exists \(m>\limits ^ \pi \) .
تبصره 2
1 \) به گونه ای که \ (\ psi _ \ pi (m) \) نگه دارد ، سیستم ناپایدار است. شرط V2 اظهار می دارد که وقتی به هیچ وجه \ (m \) وجود ندارد به گونه ای که \ (\ psi _ \ pi (m) \) صحیح است ، پس از آن ، نمونه متقابل هیچ اعدام کاملی در پی آن ندارد ، و از این رو ، فریبنده است. شرط V3 دلالت بر این دارد که هیچ اجرای کامل به دنبال \ (\ pi \) وجود ندارد که به وزن احترام می گذارد ، با این حال ، اجرای کامل (واگرایی یا نه) وجود دارد.< (s, s'): s' \in H(s)\>قضیه 3
(قضیه نقطه ثابت کاکوتانی). بگذارید \ (s \ subeTeq \ Mathbb ^n \) یک مجموعه غیر خالی ، جمع و جور و محدب باشد. بگذارید \ (H: S \ RightArrow 2^ \) یک تابع با ارزش باشد که نمودار آن \ (\
\) یک مجموعه بسته است ، و برای همه \ (s \ in s \) ، \ (h (s) \ ne \ vetyset \) و محدب. سپس \ (H \) یک نقطه ثابت دارد ، به این معنی که \ (\ وجود S^ \ in s: s^ \ in h (s^) \).
وجود چنین نوع نقطه ثابت استراتژی را برای اثبات نتیجه بعدی برای ما فراهم می کند.<\leadsto >گزاره 2<\pi >اگر وجود داشته باشد \ (\ sigma \ in \ textit (\ mathcal) \) به گونه ای که \ (\ sigma \ mathop
\ محدود ^ \ pi \) ، سپس یک مقدار \ (m \) بیشتر از 1 وجود دارد به گونه ای که \ (\ psi _
(م) \) نگه می دارد.<\leadsto >اثبات<\leadsto >\limits ^ \pi \>\) .
\(\textit(\pi )\) is a closed convex set which is positive scaling closed. This follows from the following facts. Firstly, the facet \(f_0\) is closed, convex and positive scaling closed, since it is a facet from a polyhedral partition respecting a \(>\) \(\mathcal\) in normal form. Next, the set \(\textit(\pi )\) is the intersection of \(>فرض کنید \ (\ sigma \ in \ textit (\ mathcal) \) به گونه ای که \ (\ sigma \ mathopk = 0> >^i(f_0)\) has the property that \(Z \subseteq >^k(Z)\) ). Finally, the \(>\ محدود ^ \ pi \). بگذارید ابتدا مجموعه ای از نقاط شروع را برای اعدام های واگرا به دنبال \ (\ pi \) با احترام به وزن ها تعریف کنیم.\ (\ textit (\ pi) = \ ، \ eta ، \ gamma) \ in \ textit (\ mathcal): \ eta (0) = x ، \ sigma \ mathop
Consider a set-valued function G from \(f_0\) to \(f_0\) which maps \(x_0\in f_0\) to the set \(>^k(x_0)\) . Define \(S = \(\pi )\>^i (f_0) \) برای \ (i \ geqslant 0 \) که یک چند k است ، طول counterexample \ (\ pi \).(این بستگی به این واقعیت دارد که مجموعه \ (z = \ bigcap _
Define K as an upper bound for the scaling of the executions following \(\pi \) for one iteration and respecting the weights, so the ones from \(f_0\) to \(>^k(f_0)\) , being k the length of \(\pi \) . Define the set valued function H from S to \(2^S\) , which maps \(x \in S\) to the set \(\ \,|\, y \in G(x)\>\) .
\) و عملیات تقاطع ، بسته بودن ، محدب و خاصیت مقیاس مثبت را حفظ می کند.<(x, y) \,|\, y \in G(x)\>\)از آنجا که \ (\ textit (\ pi) \) غیر خالی ، محدب ، بسته و بسته تحت مقیاس مثبت است ، ما به دست می آوریم که S غیر خالی ، جمع و جور و محدب است. فشردگی از این فرض پیروی می کند که \ (\ textit (\ pi) \) بسته شده و مجموعه \ (|| x || \ le 1 \) جمع و جور است ، و از این رو ، تقاطع آنها جمع و جور است. محدب S از این واقعیت پیروی می کند که این تقاطع مجموعه \ (\ textit (\ pi) \) و مجموعه \ (|| x || \ le 1 \) است که هر دو محدب هستند.
توجه داشته باشید که نمودار \ (\<\pi >(K)\) , and \(K>1\) because it is an upper bound on the \(W(\pi )\) and \(\pi \) is a counterexample, and \(K^s^* \in >\) یک مجموعه بسته است. دنباله ای از نقاط \ ((x_0 ، y_0) ، (x_i ، y_i) ، \ ldots \) را در نظر بگیرید که متعلق به نمودار هستند و به (x ، y) همگرا می شوند. سپس X به دلیل بسته بودن \ (F_0 \) در دامنه نمودار قرار خواهد گرفت. و \ (y \ in g (x) \) به دلیل فشرده سازی و خطی بودن هر مجموعه چند قطبی \ (\ textit (q) \) برای \ (q \ in \ textit \) که نشان دهنده پویایی است.
در مرحله بعد ، ما نشان می دهیم که H یک نقطه ثابت دارد. برای این کار ، ما قضیه نقطه ثابت کاکوتانی را اعمال می کنیم. از آنجا که H در بالا فرضیه قضیه Kakutani را برآورده می کند ، وجود دارد (S^* \ در S \) به گونه ای که \ (S^* \ in H (S^*) \). سپس ، توجه داشته باشید که \ (s^* \ in \ frac \) ، آن \ (ks^* \ in g (s^*) \) است. سپس دنباله نقاط \ (s^*، k s^*، k^2 s^*، \ ldots \) دارای \ (\ psi _
Suppose there exists \(m>^k (k^js^*) \) برای هر \ (j \ geqslant 0 \).\(\مربع \)< k\) , \(x_i \in f_i\) and \((x_i ,x_) \in \textit((q_i,f_i),P_i,(q_f_))\) , and \(x_ = mx_0\) . Then consider the infinite execution \(\nu = x_0, \ldots , x_, mx_0, \ldots , mx_,\) \( m^2 x_0,\) \( \ldots , m^2 x_, \ldots \) such that \((m^j x_i ,m^j x_) \in \textit((q_i,f_i),\) \(P_i,(q_f_))\) for every \(j \geqslant 0\) because of linearity of the flows. Construct with such points and \(\pi \) an execution \(\sigma \) such that \(\sigma \leadsto \pi \) . Note that \(\sigma \) diverges, since \(m>1 \).
It can show by using a similar argument that in the proof of Proposition 2 but defining \(\textit(\pi )\) as \(\,\eta ,\gamma ) \in \textit(\mathcal):\eta (0)=x, \sigma \leadsto \pi \>\) .
1 \) و \ (x_0 ، \ ldots ، x_k \ in \ mathbb ^n \) به گونه ای که برای همه \ (0 \ le i< m\leqslant 1\) and \(x_0, \ldots , x_k \in \mathbb ^n\) such that for all \(0 \le i < k\) , \(x_i \in f_i\) and \((x_i ,x_) \in \textit((q_i,f_i),P_i,(q_f_))\) , and \(x_ = mx_0\) . Then consider the infinite execution \(\nu = x_0, \ldots , x_, mx_0, \ldots , mx_, m^2 x_0,\) \( \ldots , m^2 x_, \ldots \) . Construct with such points and \(\pi \) an execution \(\sigma \) such that \(\sigma \leadsto \pi \) . Note that there does not exist \(\sigma \) respecting the weights in \(\pi \) because in case of existence we would get a contradiction due to Proposition 2. \(\square \)
1 \).
فرض کنید وجود دارد \ (0
4. 4 پالایش
اول ، ما مشکل پالایش را رسمی می کنیم. سپس ، ما استراتژی های مختلفی را برای پالایش ارائه می دهیم با در نظر گرفتن دلیل تحریک نمونه ضد انتزاعی.
الف) مشکل پالایش. ما ابتدا مفهوم پالایش را معرفی می کنیم.
