Distributed multi-agent coordination for energy-constrained patrolling

Abstract In this paper, the multi-agent patrolling problem subject to energy constraints is studied. Several existing online, distributed, heuristic-based patrolling algorithms are adapted to accommodate energy-constrained multi-agent patrolling. These adapted algorithms are evaluated on graphs using simulations in order to identify algorithm characteristics that are beneficial for energy-constrained multi-agent patrolling and to analyse the performance of the algorithms when subject to energy constraints. The experimental results also reveal several important considerations when planning multi-agent patrolling missions subject to energy constraints. Patrolling performance is measured using metrics based on idleness, which represents the time since a location within a patrolling area was previously visited. It was evident from the experimental results that coordination between agents, such as information sharing and/or conflict resolution, improves performance in general, especially as the number of agents increases. However, in the problem setting considered, sharing visit information alone appears to be detrimental to patrolling performance. Furthermore, careful consideration may be required regarding the patrolling area in order to ensure that agents subject to energy constraints can reach all locations when using certain distributed, heuristic-based patrolling algorithms. In addition, increasing the amount of energy available can negatively impact the performance of distributed, heuristic-based patrolling algorithms on some graphs. Overall, no single algorithm consistently outperformed all others across all graph topologies and different numbers of agents with respect to the evaluated patrolling metrics. This highlights the importance of considering each factor when planning distributed, heuristic-based multi-agent patrolling strategies under energy constraints.