  Multi-robot systems are uniquely well-suited to performing complex tasks such
as patrolling and tracking, information gathering, and pick-up and delivery
problems, offering significantly higher performance than single-robot systems.
A fundamental building block in most multi-robot systems is task allocation:
assigning robots to tasks (e.g., patrolling an area, or servicing a
transportation request) as they appear based on the robots' states to maximize
reward. In many practical situations, the allocation must account for
heterogeneous capabilities (e.g., availability of appropriate sensors or
actuators) to ensure the feasibility of execution, and to promote a higher
reward, over a long time horizon. To this end, we present the FlowDec algorithm
for efficient heterogeneous task-allocation achieving an approximation factor
of at least 1/2 of the optimal reward. Our approach decomposes the
heterogeneous problem into several homogeneous subproblems that can be solved
efficiently using min-cost flow. Through simulation experiments, we show that
our algorithm is faster by several orders of magnitude than a MILP approach.
