Selective Smooth Fictitious Play: An approach based on game theory for patrolling infrastructures with a multi-robot system

摘要

The multi-robot patrolling problem is defined as the activity of traversing a given environment. In this activity, a fleet of robots visits some places at irregular intervals of time for security purpose. To date, this problem has been solved with different approaches. However, the approaches that obtain the best results are unfeasible for security applications because they are centralized and deterministic. To overcome the disadvantages of previous work, this paper presents a new distributed and non-deterministic approach based on a model from game theory called Smooth Fictitious Play. To this end, the multi-robot patrolling problem is formulated by using concepts of graph theory to represent an environment. In this formulation, several normal-form games are defined at each node of the graph. This approach is validated by comparison with best suited literature approaches by using a patrolling simulator. The results for the proposed approach turn out to be better than previous literature approaches in as many as 88% of the cases of study. Moreover, the novel approach presented in this work has many advantages over other approaches of the literature such distribution, robustness, scalability, and dynamism. The achievements obtained in this work validate the potential of game theory to protect infrastructures. © 2013 Elsevier Ltd. All rights reserved.