Adaptive time stepping in real-time motion planning

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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. We present a real-time replanning technique that uses adaptive time stepping to learn the amount of time needed for a sample-based motion planner to make monotonic progress toward the goal. The technique is robust to the typically high variance exhibited by planning queries, and we prove that it is asymptotically complete for a deterministic environment and a static objective. For unpredictable environments, we present an adaptive time stepping contingency planning algorithm that achieves simultaneous safety-seeking and goal-seeking motion. These techniques generate responsive and safe motion in simulated scenarios across a range of difficulties, including applications to pursuit-evasion and aggressive collision-free teleoperation of an industrial robot arm in a cluttered environment.

Original languageEnglish (US)
Title of host publicationAlgorithmic Foundations of Robotics IX - Selected Contributions of the Ninth International Workshop on the Algorithmic Foundations of Robotics
Number of pages17
StatePublished - 2010
Externally publishedYes
Event9th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2010 - Singapore, Singapore
Duration: Dec 13 2010Dec 15 2010

Publication series

NameSpringer Tracts in Advanced Robotics
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X


Other9th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2010

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence


Dive into the research topics of 'Adaptive time stepping in real-time motion planning'. Together they form a unique fingerprint.

Cite this