  This paper considers the problem of multi-robot safe mission planning in
uncertain dynamic environments. This problem arises in several applications
including safety-critical exploration, surveillance, and emergency rescue
missions. Computation of a multi-robot optimal control policy is challenging
not only because of the complexity of incorporating dynamic uncertainties while
planning, but also because of the exponential growth in problem size as a
function of the number of robots. Leveraging recent works obtaining a tractable
safety maximizing plan for a single robot, we propose a scalable two-stage
framework to solve the problem at hand. Specifically, the problem is split into
a low-level single-agent planning problem and a high-level task allocation
problem. The low-level problem uses an efficient approximation of stochastic
reachability for a Markov decision process to handle the dynamic uncertainty.
The task allocation, on the other hand, is solved using polynomial-time forward
and reverse greedy heuristics. The safety objective of our multi-robot safe
planning problem allows an implementation of the greedy heuristics through a
distributed auction-based approach. Moreover, by leveraging the properties of
the safety objective function, we ensure provable performance bounds on the
safety of the approximate solutions proposed by these two heuristics. Our
result is illustrated through case studies.
