TWGS:A Tree Decomposition Based Indoor Pursuit-Evasion Game For Robotic Networks

In this paper, we deal with the problem of pursuing a mobile target by multiple robots in indoor environments embedded with robotic networks. The target is vigilant and its speed can be arbitrarily fast while the speeds of pursuers are limited. Our object in this paper is to design effective pursuit strategies for the robots to track and finally capture the target. By using concepts of tree decomposition from graph theory, we establish an upper bound of the pursuer number that can guarantee successful capture of the mobile target. We then propose a pursuit algorithm, namely, tree-width based graph searching (TWGS), based on the theoretical analysis. Furthermore, we demonstrate the performance of the algorithm for two indoor environments by numerical simulations, which show that TWGS is efficient and the pursuer number given by the theoretical analysis is rather tight.