Multi-robot extension for safe planning under dynamic uncertainty

Abstract

Safe planning problem arises in many applications including autonomous driving and exploration scenarios. In this thesis, we focus on a particular case studied for emergency rescue missions. The main challenge of such problems is the computational complexity of handling a dynamic uncertainty, e.g., a spreading hazard. A multi-agent extension can potentially improve the safety of the mission. However, it further increases the computational complexity with the need to consider exponentially many possible task-robot combinations. To overcome these computational issues, we propose a two-stage framework splitting the multi-robot safe planning problem into a low-level single-agent safe planning problem and a high-level multi-robot task allocation problem. For single-agent safe planning, we utilize an efficient Monte-Carlo sampling-based approximation to handle the dynamic uncertainty. For the task allocation problem, we use forward and reverse greedy heuristics to obtain approximate solutions. These algorithms are equipped with provable performance bounds on the safety of the resulting approximate solutions. Finally, we present several case studies on example environments to compare the performance of these different algorithms.