Decentralized task allocation for surveillance systems with critical tasks

•A task allocation problem with peculiar constraints, such as critical tasks, is modeled.•Heterogeneous robotic agents with limited capacity are considered.•The proposed decentralized algorithm relies on auction and consensus algorithms.•The proposed decentralized algorithm is a polynomial time algorithm.

This paper considers the problem of assigning a set of tasks to a set of heterogeneous agents under the additional assumptions that some tasks must be necessarily allocated and therefore are critical for the assignment problem, and that each agent can execute a limited number of tasks. In order to solve this problem in a decentralized way (i.e., without any form of central supervision), we develop an extension of an algorithm proposed in the recent literature. After analyzing convergence and communication requirement of the algorithm, a set of numerical simulations is provided to confirm the effectiveness of the proposed approach.