On responsiveness, safety, and completeness in real-time motion planning

Replanning is a powerful mechanism for controlling robot motion under hard constraints and unpredictable disturbances, but it involves an inherent tradeoff between the planner's power (e.g., a planning horizon or time cutoff) and its responsiveness to disturbances. This paper presents an adaptive time-stepping architecture for real-time planning with several advantageous properties. By dynamically adapting to the amount of time needed for a sample-based motion planner to make progress toward the goal, the technique is robust to the typically high variance exhibited by replanning queries. The technique is proven to be safe and asymptotically complete in a deterministic environment and a static objective. For unpredictably moving obstacles, the technique can be applied to keep the robot safe more reliably than reactive obstacle avoidance or fixed time-step replanning. It can also be applied in a contingency planning algorithm that achieves simultaneous safety-seeking and goal-seeking motion. These techniques generate responsive and safe motion in both simulated and real robots across a range of difficulties, including applications to bounded-acceleration pursuit-evasion, indoor navigation among moving obstacles, and aggressive collision-free teleoperation of an industrial robot arm.