دسته بندی:
رباتیک - robotic
سال انتشار:
2018
ترجمه فارسی عنوان مقاله:
بدیههسازی کنترل واکنشی
عنوان انگلیسی مقاله:
Reactive Control Improvisation
منبع:
CAV 2018, LNCS 10981, pp: 307–326, 2018
نویسنده:
Daniel J: Fremont(B) and Sanjit A: Seshia
چکیده انگلیسی:
Reactive synthesis is a paradigm for automatically building correct-by-construction systems that interact with an unknown or adversarial environment. We study how to do reactive synthesis when part of the specification of the system is that its behavior should be random. Randomness can be useful, for example, in a network protocol fuzz tester whose output should be varied, or a planner for a surveillance robot whose route should be unpredictable. However, existing reactive synthesis techniques do not provide a way to ensure random behavior while maintaining functional correctness. Towards this end, we generalize the recently-proposed framework of control improvisation (CI) to add reactivity. The resulting framework of reactive control improvisation provides a natural way to integrate a randomness requirement with the usual functional specifications of reactive synthesis over a finite window. We theoretically characterize when such problems are realizable, and give a general method for solving them. For specifications given by reachability or safety games or by deterministic finite automata, our method yields a polynomial-time synthesis algorithm. For various other types of specifications including temporal logic formulas, we obtain a polynomial-space algorithm and prove matching PSPACE-hardness results. We show that all of these randomized variants of reactive synthesis are no harder in a complexity-theoretic sense than their non-randomized counterparts.
چکیده فارسی:
سنتز واکنشی نوعی الگو برای ساخت اتوماتیک سیستمهای "صحیح در حین ساخت" است که با یک محیط ناشناخته یا خصمانه تعامل دارند. ما بررسی کردیم زمانیکه بخشی از مشخصات سیستم این است که بایستی رفتارش، تصادفی باشد، سنتز واکنشی را به چه نحو انجام دهیم. ممکن است تصادفی بودن، مفید باشد، برای مثال در تستکنندهی فازی پروتکل شبکه که بایستی خروجی آن تغییر کند، یا یک برنامهریز برای یک ربات نظارتی که بایستی مسیر آن غیر قابل پیشبینی باشد. بااینحال، روشهای موجود برای سنتز واکنشی، راهی برای اطمینان از رفتار تصادفی و در عین حال حفظ صحت عملکرد فراهم نمیآورند. بدین منظور، چارچوب بدیههسازی کنترلی (CI) را که به تازگی ارائه شده است را برای افزایش واکنشپذیری، تعمیم دادیم. چارچوب حاصله برای بدیههسازی کنترل واکنشی، راهی طبیعی برای یکپارچهسازی الزامات تصادفی بودن با مشخصات عملیاتی متداول سنتز واکنشی در یک پنجرهی محدود فراهم میآورد. ما به لحاظ نظری بررسی کردیم چه هنگام چنین مسائلی تحقق مییابند، و یک روش کلی برای حل و فصل آنها ارائه نمودیم. برای مشخصات ارائهشده توسط قابلیت دسترسی یا بازیهای ایمنی یا با اتوماتای محدود قطعی، روش ما به یک الگوریتم سنتز زمان چندجملهای دست یافت. برای دیگر انواع مشخصات شامل فرمولهای منطق زمانی، به الگوریتم فضای چندجملهای رسیدیم و انطباق نتایج سختی-PSPACE را اثبات نمودیم. ما نشان دادیم تمامی این گونههای تصادفی سنتز واکنشی به لحاظ نظریهی پیچیدگی از همتایان غیرتصادفی خود، سختتر نیستند.
حجم فایل: 525 کیلوبایت
قیمت: 56160 تومان
توضیحات اضافی:
تعداد نظرات : 0