TR2018-151

Algorithms for Task Allocation in Homogeneous Swarm of Robots



In this paper, we present algorithms for synthesizing controllers to distribute a swarm of homogeneous robots (agents) over heterogeneous tasks which are operated in parallel. Swarm is modeled as a homogeneous collection of irreducible Markov chains. States of the Markov chain represent the tasks performed by the swarm. The target state is a pre-defined distribution of agents over the states of the Markov chain (and thus the tasks). We make use of ergodicity property of irreducible Markov chains to ensure that as an individual agent converges to the desired behavior in time, the swarm converges to the target state. To circumvent the problems faced by a global controller and local/decentralized controllers alone, we design a controller by combining global supervision with local-feedback-based state level decisions. Some numerical experiments are shown to illustrate the performance of the proposed algorithms.