Creating and sharing knowledge for telecommunications

Statistical Model Checking for Markov Decision Processes

on 07-09-2012

... David Henriques, SQIG-Instituto de Telecomunicações

September 7, 2012, Friday, 16h15m.

Statistical Model Checking (SMC) is a computationally very efficient verification technique based on selective system sampling. One well identified shortcoming of SMC is that, unlike probabilistic model checking, it cannot be applied to systems featuring nondeterminism, such as Markov Decision Processes (MDP). We address this limitation by developing an algorithm that uses multiple rounds of sampling and Reinforcement Learning to provably improve resolutions of nondeterminism with respect to satisfying a Bounded Linear Temporal Logic (BLTL) property. Extensive validation with both new and established benchmarks demonstrates that the approach scales very well in scenarios where symbolic algorithms fail to do so.A Mobile Ad-hoc Network has limited and scarce resources and thus routing protocols in such environment must be kept as simple as possible. More Information..