Optimal Strategy Model Checking in Possibilistic Decision Processes

Abstract

Probabilistic model checking has received increasing attention in formal verification. Meanwhile, in the fuzzy setting, the possibilistic model checking has been well studied by Li et al. in recent years. However, nondeterminism of choices was not considered in previous work. The nondeterminism is crucial for modeling open systems interacting with the environment. To fill the gap, we propose the possibilistic decision processes (PDPs) to model fuzzy systems with nondeterminism and introduce possibilistic strategy computation tree logic (PoSCTL) to specify properties with nondeterministic choices. More importantly, optimal strategy model checking over PDPs has been investigated, which is an important formal verification method for quantitatively checking the degree of satisfiability of properties in a model. We give mathematical methods to calculate the maximum and minimum possibilities for a system modeled by PDPs satisfies a property specified by PoSCTL when ranging over all strategies. We prove memoryless strategies are sufficient for PoSCTL model checking without the step-bounded until operator, and give the algorithms to output the corresponding optimal strategy. Finally, an illustrative example of robots moving is given to explain the methods presented in this article.