Capturing intruders based on Voronoi diagrams assisted by information networks

Abstract

We consider a scenario of deploying multiple robots to capture all intruders in a cluttered workspace with many obstacles. Here, we say that a robot captures an intruder in the case where the intruder is within the maximum range of a weapon on the robot. All robots use the Voronoi diagram as the topological map of the workspace. Due to obstacles, intruders are confined to move along a passage between obstacles. Suppose the weapons on every robot are powerful enough to cover a passage in the workspace. Then, we can consider a simplified scenario such that robots and intruders are restricted to stay on the Voronoi diagram. We assume that a robot can detect the position of any intruder using the information network. This article presents an intruder capturing strategy that is robust to time delay in data transfer using the network. Our strategy does not require the localization of a node or a robot. Based on this strategy, we provide an upper bound for the minimum number of robots required to capture all intruders on a general graph, which leads to a result of the Voronoi diagram. Lastly, we provide MATLAB (version 7.10.0 R2010a) simulations to verify the effectiveness of our capturing strategy.