کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952227 | 1442020 | 2017 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Symbolic optimal expected time reachability computation and controller synthesis for probabilistic timed automata
ترجمه فارسی عنوان
محاسبه قابلیت دستیابی زمان انتظار بهینه و سنتز کنترل کننده برای اتوماتای زمانبندی احتمالی بهینه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
اتوماتای زمانبندی احتمالی، سنتز کنترل کننده، تأیید احتمالاتی، بررسی مدل نمادین،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper we consider the problem of computing the optimal (minimum or maximum) expected time to reach a target and the synthesis of an optimal controller for a probabilistic timed automaton (PTA). Although this problem admits solutions that employ the digital clocks abstraction or statistical model checking, symbolic methods based on zones and priced zones fail due to the difficulty of incorporating probabilistic branching in the context of dense time. We work in a generalisation of the setting introduced by Asarin and Maler for the corresponding problem for timed automata, where simple and nice functions are introduced to ensure finiteness of the dense-time representation. We find restrictions sufficient for value iteration to converge to the optimal expected time on the uncountable Markov decision process representing the semantics of a PTA. We formulate Bellman operators on the backwards zone graph of a PTA and prove that value iteration using these operators equals that computed over the PTA's semantics. This enables us to extract an ε-optimal controller from value iteration in the standard way.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 669, 22 March 2017, Pages 1-21
Journal: Theoretical Computer Science - Volume 669, 22 March 2017, Pages 1-21
نویسندگان
Aleksandra JovanoviÄ, Marta Kwiatkowska, Gethin Norman, Quentin Peyras,