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.