Computer Science – Computer Science and Game Theory
Scientific paper
2009-12-16
Computer Science
Computer Science and Game Theory
Scientific paper
Using mobile robots for autonomous patrolling of environments to prevent intrusions is a topic of increasing practical relevance. One of the most challenging scientific issues is the problem of finding effective patrolling strategies that, at each time point, determine the next moves of the patrollers in order to maximize some objective function. In the very last years this problem has been addressed in a game theoretical fashion, explicitly considering the presence of an adversarial intruder. The general idea is that of modeling a patrolling situation as a game, played by the patrollers and the intruder, and of studying the equilibria of this game to derive effective patrolling strategies. In this paper we present a game theoretical formal framework for the determination of effective patrolling strategies that extends the previous proposals appeared in the literature, by considering environments with arbitrary topology and arbitrary preferences for the agents. The main original contributions of this paper are the formulation of the patrolling game for generic graph environments, an algorithm for finding a deterministic equilibrium strategy, which is a fixed path through the vertices of the graph, and an algorithm for finding a non-deterministic equilibrium strategy, which is a set of probabilities for moving between adjacent vertices of the graph. Both the algorithms are analytically studied and experimentally validated, to assess their properties and efficiency.
Amigoni Francesco
Basilico Nicola
Gatti Nicola
No associations
LandOfFree
A Formal Framework for Mobile Robot Patrolling in Arbitrary Environments with Adversaries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Formal Framework for Mobile Robot Patrolling in Arbitrary Environments with Adversaries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Formal Framework for Mobile Robot Patrolling in Arbitrary Environments with Adversaries will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-684685