Statistical Model Checking for Cops and Robbers Game on Random Graph Models

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.

[img]
Preview
Text
Thesis_Mtech_CS_4064.pdf - Published Version

Download (910kB) | Preview

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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
M V, Panduranga RaoUNSPECIFIED
Item Type: Thesis (Masters)
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 22 Jun 2018 09:12
Last Modified: 22 Jun 2018 09:12
URI: http://raiithold.iith.ac.in/id/eprint/4064
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 4064 Statistics for this ePrint Item