  In order to fully exploit the advantages inherent to cooperating
heterogeneous multi-robot teams, sophisticated coordination algorithms are
essential. Time-extended multi-robot task allocation approaches assign and
schedule a set of tasks to a group of robots such that certain objectives are
optimized and operational constraints are met. This is particularly challenging
if cooperative tasks, i.e. tasks that require two or more robots to work
directly together, are considered. In this paper, we present an
easy-to-implement criterion to validate the feasibility, i.e. executability, of
solutions to time-extended multi-robot task allocation problems with cross
schedule dependencies arising from the consideration of cooperative tasks and
precedence constraints. Using the introduced feasibility criterion, we propose
a local improvement heuristic based on a neighborhood operator for the problem
class under consideration. The initial solution is obtained by a greedy
constructive heuristic. Both methods use a generalized cost structure and are
therefore able to handle various objective function instances. We evaluate the
proposed approach using test scenarios of different problem sizes, all
comprising the complexity aspects of the regarded problem. The simulation
results illustrate the improvement potential arising from the application of
the local improvement heuristic.
