  We propose an approach to find low-makespan solutions to multi-robot
multi-task planning problems in environments where robots block each other from
completing tasks simultaneously. We introduce a formulation of the problem that
allows for an approach based on greedy descent with random restarts for
generation of the task assignment and task sequence. We then use a multi-agent
path planner to evaluate the makespan of a given assignment and sequence. The
planner decomposes the problem into multiple simple subproblems that only
contain a single robots and a single task, and can thus be solved quickly to
produce a solution for a fixed task sequence. The solutions to the subproblems
are then combined to form a valid solution to the original problem. We showcase
the approach on robotic stippling and robotic bin picking with up to 4 robot
arms. The makespan of the solutions found by our algorithm are up to 30% lower
compared to a greedy approach.
