Provably Safe Robot Navigation with Obstacle Uncertainty

Authors: Brian Axelrod, Leslie Kaelbling, Tomas Lozano-Perez

As drones and autonomous cars become morewidespread it is becoming increasingly important that robots canoperate safely under realistic conditions. The noisy informationfed into real systems means that robots must use estimates ofthe environment to plan navigation. Efficiently guaranteeing thatthe resulting motion plans are safe under these circumstanceshas proved difficult. We examine how to guarantee that atrajectory or policy is safe with only imperfect observationsof the environment. We examine the implications of variousmathematical formalisms of safety and arrive at a mathematicalnotion of safety of a long-term execution, even when conditionedon observational information. We present efficient algorithmsthat can prove that trajectories or policies are safe with muchtighter bounds than in previous work. Notably, the complexity ofthe environment does not affect our method’s ability to evaluateif a trajectory or policy is safe. We then use these safety checkingmethods to design a safe variant of the RRT planning algorithm.