Hybrid ACO/EA Algorithms applied to the Multi-Agent Patrolling Problem

Patrolling an environment consists in visiting as frequently as possible its most relevant areas in order to supervise, control or protect it. This task is commonly performed by a team of agents that need to coordinate their actions for achieving optimal performance. We address here the problem of multi-agent patrolling in known environments where agents may move at different speeds and visit priorities on some areas may be specified. Two classes of patrolling strategies are studied: the single-cycle strategies and the partition-based strategies. Several single-core and multi-core variants of a template state-of-the-art hybrid algorithm are proposed for generating partition-based strategies. These are experimentally compared with a state-of-the-art heuristic-based algorithm generating single-cycle strategies. Experimental results show that: the heuristic-based algorithm only generates efficient strategies when agents move at the same speeds and no visit priorities have been defined; all single-core variants are equivalent; multi-core hybrid algorithms may improve overall quality or reduce variance of the solutions obtained by single-core algorithms.