Self-organized graph partitioning approach for multi-agent patrolling in generic graphs

Recently multi-agent patrolling became more and more crucial in security, monitoring, etc. applications. It can be used, for example, to monitor points of interest in space, such as measurement points or entrances to a guarded area. A good patrolling strategy would ensure frequent visits to all points of interest defined by a user. A variety of centralized and distributed approaches exist already to the multi-agent patrolling problem, ranging from simple reactive solutions to sophisticated planning approaches. However there has been no self-organizing partition based solution proposed that can match and improve on the performance of already existing algorithms. In this article we introduce a self-organizing autonomous algorithm to partition a graph into non-overlapping subgraphs and assign the resulting subgraphs to agents to perform patrolling. We compare our solution to other patrolling algorithms in a thorough performance evaluation and show that our autonomous solution can outperform state of the art patrolling schemes.