Adaptive Time Stepping for Real-Time Motion Planning

Kris Hauser. Workshop on the Algorithmic Foundations of Robotics (WAFR) 2010

An expanded version of this paper appears in Autonomous Robots, 32(1), 35-48, 2012.

Abstract. 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 across several simulated scenarios over a range of difficulties, including applications to pursuit-evasion and aggressive collision-free teleoperation of an industrial robot arm in a cluttered environment.

Download PDF (original version)

Download PDF (expanded version)

Media

All videos are captured on a 2Ghz laptop PC in ``simulated real time'', which means that for each second the CPU spends planning, then exactly one second elapses in the simulation time.

Assisted Teleoperation Experiments on the Staubli TX90L Industrial Robot

Our real-time planner is used to command the robot to reach a user-controlled point (yellow) in a cluttered environment. A sample-based planner constructs complex dynamic collision-free trajectories to pass around and through complex obstacles.

MPEG, 17mb

Greedy planning to a dynamic user-controlled point (yellow). The motion is collision free, but the robot gets easily stuck in local minima, putting more burden on the user.

MPEG, 7.6mb

Path Following Benchmarks for the Staubli TX90L

Following a circle using real-time planning.

MPEG, 4.3mb

Following a circle, intermediate motion plans drawn.

MPEG, 7.6mb

Following the circle moving twice as fast as before.

MPEG, 5.2mb

Dynamic, Unpredictable Obstacle Avoidance

A robot (orange) with bounded acceleration and velocity seeks a goal (red) while avoiding 3 pursuers. Cyan path: optimistic goal-seeking path. Green path: pessimistic safety-seeking path.

MPEG, 3.7mb

A robot (orange) with bounded acceleration and velocity seeks a goal (red) while avoiding 3 pursuers and 7 unpredictably behaving obstacles. Cyan path: optimistic goal-seeking path. Green path: pessimistic safety-seeking path. The robot is eventually trapped.

MPEG, 1.7mb

A robot (orange) with bounded acceleration and velocity avoids 63 unpredictably behaving obstacles.

MPEG, 21.5mb

A robot (orange) with bounded acceleration and velocity avoids 266 unpredictably behaving obstacles. The robot briefly collides (magenta) at 0:06.

MPEG, 31.8mb

A robot (orange) with bounded acceleration and velocity seeks a goal (red) while avoiding 63 unpredictably behaving obstacles.

MPEG, 21.2mb

A robot (orange) with bounded acceleration and velocity seeks a goal (red) while avoiding 266 unpredictably behaving obstacles. The robot briefly collides (magenta) at 0:11 and 0:18.

MPEG, 38.3mb