  We propose novel techniques for task allocation and planning in multi-robot
systems operating in uncertain environments. Task allocation is performed
simultaneously with planning, which provides more detailed information about
individual robot behaviour, but also exploits independence between tasks to do
so efficiently. We use Markov decision processes to model robot behaviour and
linear temporal logic to specify tasks and safety constraints. Building upon
techniques and tools from formal verification, we show how to generate a
sequence of multi-robot policies, iteratively refining them to reallocate tasks
if individual robots fail, and providing probabilistic guarantees on the
performance (and safe operation) of the team of robots under the resulting
policy. We implement our approach and evaluate it on a benchmark multi-robot
example.
