Provably safe robot navigation with obstacle uncertainty
Authors:
- 7 June 2018
- journal article
- research article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 37 (13-14) , 1760-1774
Abstract
As drones and autonomous cars become more widespread, it is becoming increasingly important that robots can operate safely under realistic conditions. The noisy information fed into real systems means that robots must use estimates of the environment to plan navigation. Efficiently guaranteeing that the resulting motion plans are safe under these circumstances has proved difficult. We examine how to guarantee that a trajectory or policy has at most collision probability ( -safe) with only imperfect observations of the environment. We examine the implications of various mathematical formalisms of safety and arrive at a mathematical notion of safety of a long-term execution, even when conditioned on observational information. We explore the idea of shadows that generalize the notion of a confidence set to estimated shapes and present a theorem that allows us to understand the relationship between shadows and their classical statistical equivalents such as confidence and credible sets. We present efficient algorithms that use shadows to prove that trajectories or policies are safe with much tighter bounds than in previous work. Notably, the complexity of the environment does not affect our method’s ability to evaluate whether a trajectory or policy is safe. We then use these safety-checking methods to design a safe variant of the rapidly exploring random tree (RRT) planning algorithm.
Keywords
Funding Information
- Office of Naval Research (N00014-14-1-0486)
- Army Research Office (W911NF1410433)
- National Science Foundation (1420316)
- National Science Foundation (1523767)
- National Science Foundation (1723381)
- National Science Foundation (DGE-1656518)
- Air Force Office of Scientific Research (FA9550- 17-1-0165)
- Thomas and Stacey Siebel Foundation
This publication has 18 references indexed in Scilit:
- Multi-objective planning with multiple high level task specifications2016
- Modular task and motion planning in belief space2015
- Integrated task and motion planning in belief spaceThe International Journal of Robotics Research, 2013
- Strategic planning under uncertainties via constrained Markov Decision Processes2013
- Rapidly-exploring Random Belief Trees for motion planning under uncertainty2011
- Robotic motion planning in dynamic, cluttered, uncertain environments2010
- Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions2009
- Approximating Submodular Functions Everywhere2009
- Convex Optimization2004
- Planning and acting in partially observable stochastic domainsArtificial Intelligence, 1998