Multirobot Stochastic Patrolling via Graph Partitioning

Abstract

In this article, we study a multirobot stochastic patrolling problem by employing graph partitioning techniques, where each robot adopts a Markov-chain-based strategy over its assigned subgraph, so that the overall patrolling performance is optimized. To quantify the patrolling performance of the robot team, we first introduce a novel performance measure based on the mean first hitting time. We then formulate optimization problems for unweighted complete graphs and transcribe it to the well-known maximum <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-cut problem. To reduce the computational complexity, we identify a special solution structure of the optimization problem, and we develop an efficient heuristic descent-based algorithm by taking advantage of this special property of the optimal solution. We show that our algorithm converges in a finite number of steps and finds a suboptimal solution that preserves the special solution structure and satisfies a suboptimality bound. We validate our findings through numerical experiments and show the clear advantages of our partition-based strategy.