The security of sensitive areas against adversarial threats is a critical concern, necessitating the development of effective patrol strategies. This thesis addresses the problem of optimal patrolling in adver- sarial scenarios through the formulation of an analytical method to calculate the interception probability of a possible attacker in a graph-based patrolling game. By leveraging Markovian strategies, the research provides a robust framework for efficiently calculating interception probabilities and proposes a methodology to optimize patrol routes.

Firstly, the structure and modeling framework that is used in this thesis is set out. Subsequently, a probabilistic, a recursive, and a matrix-product method are derived to calculate the interception probability. This constitutes the core of this thesis. Lastly, the discussion is extended by applying the matrix-product method to practical examples. Monte Carlo simulations are used to compare the performance of different patrol strategies under varying conditions. The results illustrate how the developed methods enable detailed performance analyses, showing that the effectiveness of patrol strategies can vary based on the distribution of attack strategies.

Key findings highlight the impact of graph structure and attack strategy distributions on interception probabilities, the scalability and practicality of the matrix product method to calculate the interception probability, and the significant computational efficiency gained by using this approach. The research also outlines several avenues for future work, including the exploration of heterogeneous environments, optimization improvements, and multi-agent scenarios. Overall, this thesis contributes to the field of patrolling games by offering enhanced methods to evaluate and optimize Markovian patrol strategies, providing both theoretical methodologies and practical implementations that can be used to improve security in adversarial settings.