Jain, Abhishek and M V, Panduranga Rao
(2018)
Statistical Model Checking for Cops and
Robbers Game on Random Graph Models.
Masters thesis, Indian Institute of Technology Hyderabad.
Abstract
Cops and robbers problem has been studied over the decades with many variants and
applications in graph searching problem. In this work, we study a variant of cops and
robbers problem on graphs. In this variant, there are di�erent types of cops and a
minimum number of each type of cops are required to catch a robber. We studied this
model over various random graph models and analyzed the properties using statistical
model checking.
To the best of our knowledge this variant of the cops and robber problem has
not been studied yet. We have used statistical techniques to estimate the probability
of robber getting caught in di�erent random graph models. We seek to compare
the ease of catching robbers performing random walk on graphs, especially complex
networks. In this work, we report the experiments that yields interesting empirical
results. Through the experiments we have observed that it is easier to catch a robber
in Barab�asi Albert model than in Erd�os-R�enyi graph model. We have also experimented
with k-Regular graphs and real street networks.
In our work, the model is framed as the multi-agent based system and we have implemented
a statistical model checker, SMCA tool which veri�es agents based systems
using statistical techniques. SMCA tool can take the model in JAVA programming
language and support Probabilistic - Bounded LTL logic for property specification.
Actions (login required)
 |
View Item |
Altmetric
Altmetric