TY - GEN
T1 - Abstraction-Refinement for Hierarchical Probabilistic Models
AU - Junges, Sebastian
AU - Spaan, Matthijs T.J.
PY - 2022
Y1 - 2022
N2 - Markov decision processes are a ubiquitous formalism for modelling systems with non-deterministic and probabilistic behavior. Verification of these models is subject to the famous state space explosion problem. We alleviate this problem by exploiting a hierarchical structure with repetitive parts. This structure not only occurs naturally in robotics, but also in probabilistic programs describing, e.g., network protocols. Such programs often repeatedly call a subroutine with similar behavior. In this paper, we focus on a local case, in which the subroutines have a limited effect on the overall system state. The key ideas to accelerate analysis of such programs are (1) to treat the behavior of the subroutine as uncertain and only remove this uncertainty by a detailed analysis if needed, and (2) to abstract similar subroutines into a parametric template, and then analyse this template. These two ideas are embedded into an abstraction-refinement loop that analyses hierarchical MDPs. A prototypical implementation shows the efficacy of the approach.
AB - Markov decision processes are a ubiquitous formalism for modelling systems with non-deterministic and probabilistic behavior. Verification of these models is subject to the famous state space explosion problem. We alleviate this problem by exploiting a hierarchical structure with repetitive parts. This structure not only occurs naturally in robotics, but also in probabilistic programs describing, e.g., network protocols. Such programs often repeatedly call a subroutine with similar behavior. In this paper, we focus on a local case, in which the subroutines have a limited effect on the overall system state. The key ideas to accelerate analysis of such programs are (1) to treat the behavior of the subroutine as uncertain and only remove this uncertainty by a detailed analysis if needed, and (2) to abstract similar subroutines into a parametric template, and then analyse this template. These two ideas are embedded into an abstraction-refinement loop that analyses hierarchical MDPs. A prototypical implementation shows the efficacy of the approach.
UR - http://www.scopus.com/inward/record.url?scp=85135833377&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-13185-1_6
DO - 10.1007/978-3-031-13185-1_6
M3 - Conference contribution
AN - SCOPUS:85135833377
SN - 978-3-031-13184-4
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 102
EP - 123
BT - Computer Aided Verification - 34th International Conference, CAV 2022, Proceedings
A2 - Shoham, Sharon
A2 - Vizel, Yakir
PB - Springer
CY - Cham
T2 - 34th International Conference on Computer Aided Verification, CAV 2022
Y2 - 7 August 2022 through 10 August 2022
ER -