Working as a Team: Using Social Criteria in the Timed Patrolling Problem

The multi-agent patrolling task constitutes a challenging issue for Artificial Intelligence and has the potential to cover a variety of domains ranging from agent-based simulations to crises management. Several techniques have been proposed in the last few years to address the multi-agent patrolling task with a closed-system setting. A few centralized strategies were also described to address the open-system setting, in which the agents can enter or leave the patrolling task at will. In this article, we propose two decentralized, cooperative, auction-based strategies in which agents trade the nodes they have to visit. These strategies are inspired from the computational social choice theory and allow the agents to reason on the performances of the group rather than on their own. We show that these strategies perform at least as well as the state-of-the-art centralized performances, and better on specific criteria.