CTL Model Checking of MDPs over Distribution Spaces: Algorithms and Sampling-based Computations
2024 (English)In: HSCC 2024 - Proceedings of the 27th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2024, part of CPS-IoT Week, Association for Computing Machinery (ACM) , 2024, article id 20Conference paper, Published paper (Refereed)
Abstract [en]
This work studies computation tree logic (CTL) model checking for finite-state Markov decision processes (MDPs) over the space of their distributions. Instead of investigating properties over states of the MDP, as encoded by formulae in standard probabilistic CTL (PCTL), the focus of this work is on the associated transition system, which is induced by the MDP, and on its dynamics over the (transient) MDP distributions. CTL is thus used to specify properties over the space of distributions, and is shown to provide an alternative way to express probabilistic specifications or requirements over the given MDP. We discuss the distinctive semantics of CTL formulae over distribution spaces, compare them to existing non-branching logics that reason on probability distributions, and juxtapose them to traditional PCTL specifications. We then propose reachability-based CTL model checking algorithms over distribution spaces, as well as computationally tractable, sampling-based procedures for computing the relevant reachable sets: it is in particular shown that the satisfaction set of the CTL specification can be soundly under-approximated by the union of convex polytopes. Case studies display the scalability of these procedures to large MDPs.
Place, publisher, year, edition, pages
Association for Computing Machinery (ACM) , 2024. article id 20
Keywords [en]
computation tree logic, Markov decision processes, reachability analysis, transient probability distributions
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-347118DOI: 10.1145/3641513.3651397Scopus ID: 2-s2.0-85193796030OAI: oai:DiVA.org:kth-347118DiVA, id: diva2:1864366
Conference
27th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2024, Hong Kong, China, May 13 2024 - May 16 2024
Note
QC 20240612
Part of ISBN 9798400705229
2024-06-032024-06-032024-06-12Bibliographically approved