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

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)35-48
Number of pages14
JournalAutonomous Robots
Issue number1
StatePublished - Jan 2012
Externally publishedYes


  • Assisted teleoperation
  • Model predictive control
  • Motion planning
  • Obstacle avoidance
  • Pursuit-evasion
  • Receding horizon control

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'On responsiveness, safety, and completeness in real-time motion planning'. Together they form a unique fingerprint.

Cite this