  This paper addresses the task allocation problem for multi-robot systems. The
main issue with the task allocation problem is inherent complexity that makes
finding an optimal solution within a reasonable time almost impossible. To hand
the issue, this paper develops a task allocation algorithm that can be
decentralised by leveraging the submodularity concepts and sampling process.
The theoretical analysis reveals that the proposed algorithm can provide
approximation guarantee of $1/2$ for the monotone submodular case and $1/4$ for
the non-monotone submodular case in average sense with polynomial time
complexity. To examine the performance of the proposed algorithm and validate
the theoretical analysis results, we design a task allocation problem and
perform numerical simulations. The simulation results confirm that the proposed
algorithm achieves solution quality, which is comparable to a state-of-the-art
algorithm in the monotone case, and much better quality in the non-monotone
case with significantly less computational complexity.
