Time scaling and RRT

The path is where. The clock is when.

Same arc, two clocks. Then a wall, and a tree that grows around it. Scroll to change the clock.

Scroll the tour
Fig. 28 · Arm on the bench01 · Path and timing
ORBEFAB · 2R BENCH · L28steadycubic
t
time
cubic clockone arc
Drag time. Switch the clock.

01 · Same path

The path is not the timing

The arm traces one arc. A cubic clock and a steady clock visit the same places. They just arrive on different schedules.

Show the math
θ(s) = θ_start + s · Δθ, with s from 0 to 1τ = t / Tcubic s = 3τ² − 2τ³steady s = τModern Robotics §9.2.
02 · Cubic

A cubic clock

Rest to rest in T = 2 s, through Δθ = 1 rad. Speed peaks at 0.75 rad/s. Acceleration peaks at 1.5 rad/s². Drag T and both climb, acceleration with 1/T².

Show the math
a₂ = 3/T² = 0.75, a₃ = −2/T³ = −0.25θ̇_max = 3·Δθ / (2T) = 0.75 rad/sθ̈_max = 6·Δθ / T² = 1.5 rad/s²Limits drawn at 1 rad/s and 2 rad/s².Modern Robotics §9.2.2.1. Lesson 28 worked example.
Now you try

How hard does it accelerate?

A cubic of 2 rad in T = 1 s. What is the peak acceleration?

03 · Jerk

The cup feels the jerk

A cubic acceleration jumps at the start and the stop, so the cup kicks. A quintic leaves both ends at zero acceleration. Its peaks are 0.9375 rad/s and 1.443 rad/s², higher than the cubic, and the cup barely ripples.

Show the math
quintic s = 10τ³ − 15τ⁴ + 6τ⁵ṡ_max = 15/(8T) = 0.9375 rad/ss̈_max = 10/(√3·T²) = 1.443 rad/s²s̈(0) = s̈(T) = 0Modern Robotics §9.2, Fig. 9.4. Lesson 28 worked example.
04 · Trapezoid

Coast, or a triangle

Cap the speed at 0.8 rad/s and the acceleration at 2 rad/s². The ramp lasts 0.4 s and the move lasts 1.65 s. Drag either cap. Once v²/a is larger than the move, the coast disappears and the shape becomes a triangle.

Show the math
t_a = v/a = 0.4 sT = Δθ/v + v/a = 1.65 sv²/a = 0.32 ≤ 1, so a coast existsWhen v²/a > Δθ, v_peak = √(a·Δθ) and T = 2·v_peak/aModern Robotics §9.2.2.2. Lesson 28 worked example.
Now you try

How long is the move?

v = 1 rad/s, a = 4 rad/s², Δθ = 1 rad. How long is T?

05 · A wall

A straight line hits the wall

The same bench, in the arm's working plane. A wall blocks the middle of a unit square mapped onto the bench. The straight path from start to goal runs through it.

Show the math
wall: x ∈ (0.45, 0.55) and y < 0.7start (0.1, 0.1), goal (0.9, 0.1)A straight segment samples 21 points. One of them sits in the wall.Lesson 28 worked example. Modern Robotics §10.5.1.
06 · RRT

The tree finds a way around

Press grow. Samples pull the tree into open space. This seeded run stops at 260 iterations and 170 nodes. The path is then shortcut, and a quintic plays it on the arm.

Show the math
seed 1, step 0.05, 5% goal bias260 iterations, 170 nodesThe path climbs above y = 0.7Shortcut keeps a collision-free segment, then a quintic times itLesson 28 worked example. Modern Robotics Algorithm 10.3.

The path and the clock are separate. A cubic is simple and kicks the cup. A quintic spends a little more speed to leave the ends quiet. When a wall sits in the plane, a tree of samples finds a way around.

Next is lesson 29, Wheeled robots: differential drive and odometry. It is not open yet.

Trajectories and motion planning: time scaling and RRT

Check questions

  1. A cubic move of 2 rad in T = 1 s: what are the peak velocity and acceleration? Answer: 3·2/(2·1) = 3 rad/s, 6·2/1 = 12 rad/s².
  2. Joint limit 6 rad/s². What is the minimum T for a 1.5 rad cubic move? Answer: 6·1.5/T² ≤ 6 ⇒ T ≥ √1.5 = 1.22 s.
  3. Trapezoid with v = 1 rad/s, a = 4 rad/s², Δθ = 1 rad: what is the total time? Answer: T = 1/1 + 1/4 = 1.25 s (v²/a = 0.25 ≤ 1, so it coasts).
  4. What do the "nearly uniform samples" do in RRT? Answer: they pull the tree toward unexplored space, so it rapidly explores the free space (MR §10.5.1).

Sources

  • Modern Robotics (Lynch & Park, Dec 2019 preprint), Ch. 9 "Trajectory Generation": §9.2 point-to-point trajectories (p. 328), §9.2.2.1 polynomial time scaling (pp. 331–332: eq. 9.9–9.13, quintic discussion), Fig. 9.4 (quintic peaks), §9.2.2.2 trapezoidal profiles (p. 333: eq. 9.14–9.15, Fig. 9.5); Ch. 10 "Motion Planning": §10.5.1 "The RRT Algorithm" (pp. 381–382: Algorithm 10.3, sampler and goal bias, Fig. 10.17), §10.5.1.4 variants. https://hades.mech.northwestern.edu/images/2/25/MR-v2.pdf
  • Berkeley CS287 (Fall 2019) Lecture 10 "Motion Planning" (sampling-based planning, PRM, RRT). https://people.eecs.berkeley.edu/~pabbeel/cs287-fa19/slides/Lec10-motion-planning.pdf
  • Robotic Manipulation (Tedrake), motion planning chapter.
  • Derived and checked: all numbers above, and the RRT run (seeded, reproducible).