M4-T5 — Dubins and Reeds-Shepp Curves

Learning objectives

After this lesson, you should be able to:

• Compute the minimum turning radius of a car-like robot from its wheelbase and maximum steering angle.
• Build a circle-line-circle (CSC) Dubins path from two turning circles and compute its length.
• List the six Dubins words and say when the CCC words matter.
• Describe what Reeds-Shepp curves add, and how a gear change appears as a cusp.

The intuition

Drive a shopping trolley with a fixed front wheel and you cannot make it spin on the spot. A car is the same: with its steering at full lock it follows a circle of radius R, and with the wheels straight it follows a line. Any path it can drive forward is made of these two kinds of motion, and an optimal one never needs anything in between. That is the whole idea.

To go from one pose to another, imagine two circles of radius R: one tangent to the start pose, on its left or right, and one tangent to the goal pose. Leave the start along its circle, step off onto a straight line that touches both circles, and roll onto the goal circle to arrive in the right direction. Choose left or right at each end and you have four paths with a line in the middle. Two more, three arcs in a row, appear when the poses are close together.

Because a car may also reverse, Reeds and Shepp allowed backward motion. The shortest path then sometimes drives forward, stops, and backs up: a gear change, or cusp.

The mathematics

The turning radius

For the bicycle model of lesson M1-T3 with wheelbase L and a maximum steering angle δ_max, the rear axle follows a circle of radius

A tug with a 1.0 m wheelbase and a maximum steering angle of 40° has R = 1 / tan 40° = 1.19 m. The lab uses 1.2 m.

Dubins paths

A pose is (x, y, θ). The shortest forward path between two poses is, in the words of Dubins’s theorem, one of six, written as the sequence of motions: L (arc turning left at radius R), R (arc turning right), S (straight line):

A path is a list of three numbers: two arc angles and a line length. Its length is R·(t₁ + t₃) + p, with t₁, t₃ ≥ 0 in radians, and the vehicle drives all of it forward.

Constructing a CSC path

1. Place a circle of radius R tangent to the start pose, on its left for L or its right for R: its centre is (x − R sin θ, y + R cos θ) for L and (x + R sin θ, y − R cos θ) for R. Do the same at the goal pose with the last letter.
2. Let c₁, c₂ be the centres and D = |c₂ − c₁|. For the same letters (LSL, RSR) the line has length D and heading φ = atan2(c₂ − c₁). For opposite letters it has length sqrt(D² − 4R²) and heading φ = atan2(c₂ − c₁) + asin(2R / D) for LSR and − asin(2R / D) for RSL. Opposite circles closer than 2R have no inner tangent.
3. The first arc turns the heading from θ_start to φ in the direction of the first letter, and the last arc turns it from φ to θ_goal. Each angle is taken modulo 2π in [0, 2π): a negative angle would be an arc driven in reverse.
4. Compute the length of each word and keep the shortest.

If the start and goal are more than 4R apart, one of the four CSC words is always the shortest, which is the case in lab M4-L4. Closer than that, the CCC words may win (Shkel and Lumelsky, 2001).

Reeds-Shepp

Reeds and Shepp (1990) allowed the vehicle to drive each segment forward or backward. The shortest path is then one of a family of a few dozen word types, with at most five segments and at most a few cusps, and it is never longer than the Dubins path. Two properties matter to planners:

• Asymmetry. Dubins distance is not symmetric: going from a to b can be much longer than from b to a. Reeds-Shepp distance is symmetric, because any path can be driven in reverse.
• Cusps. At a gear change the vehicle stops, which costs time and is uncomfortable on a car. Real systems add a penalty to each change of direction.

A worked example

Four words, one answer. Start at (0, 0) facing +x, goal at (8, 3) facing +y, R = 1.2 m. The straight-line distance is 8.544 m, far more than 4R = 4.8 m, so a CSC word is shortest.

LSL wins, with a length of 1.2 × (0.259 + 1.312) + 7.034 = 8.919 m, only 0.375 m longer than the straight line. The centres are (0, 1.2) and (6.8, 3.0), so D = sqrt(6.8² + 1.8²) = 7.034 m, φ = atan2(1.8, 6.8) = 0.259 rad = 14.8°. The first arc turns the heading from 0 to 0.259 rad, the last from 0.259 to π/2 = 1.571 rad: t₃ = 1.312 rad. The right-hand words have arcs of more than 5 rad because they turn the long way round.

A negative arc is a reversal. If t₁ is taken as φ − θ_s without the modulo and happens to be negative, the end pose of the path is still correct: driving a negative arc is driving the same circle backwards. The vehicle reaches the goal, but not by a forward path. This is the starter bug of lab M4-L4, stage 1.

Asymmetry. The same two poses with start and goal swapped, (8, 3, π/2) to (0, 0, 0), give an LSL path of 12.689 m instead of 8.919 m: 42% longer. A planner that treats the cost of an edge as symmetric will be wrong by that much.

Backing into a bay. The charger is at the back of the bay, so the tug must end at (6, 0.8) facing +y (out of the bay) after reversing. With a lead of 1.5 m the staging pose is 1.5 m ahead of the bay along its heading: (6, 0.8 + 1.5) = (6, 2.3, π/2). Starting from (0, 8) facing −y the forward Dubins path to the staging pose is 10.512 m (word LSL) and the reverse straight line adds 1.5 m, 12.012 m in total. Driving the whole route in reverse, as a forward path from the bay to the start run backwards, is 11.820 m: slightly shorter, but the tug drives 11.8 m with no sensor looking where it goes. One cusp near the bay is usually the better trade.

Engineering implications and limitations

Radius with margin

The limit R_min = L / tan δ_max assumes full steering lock and no tyre slip. Plan with a larger radius, for example 10–20% more, so the controller has room to correct errors (module 5). A path planned at exactly R_min leaves none.

Use them as steering and as heuristics

Dubins and Reeds-Shepp curves are the standard steering functions for RRT and RRT* with a car: the extension from a node towards a sample follows the curve, and the length of the curve serves as the distance (lesson M4-T3). Hybrid A* uses them as the final connection to the goal and as an obstacle-free heuristic (lesson M4-T6).

Curvature is discontinuous

The curvature of these paths jumps from 1/R to 0 at every junction. A real vehicle needs time to steer, so it will cut the corner. Where it matters, replace the arcs by clothoids (curvature that changes linearly) or smooth the path afterwards (module 5).

Obstacles are not included

The curves ignore obstacles. In a planner they are tested with the same collision check as any other edge (lesson M4-T2) and discarded if blocked; the shortest feasible path may be none of the six.

Cusps and safety

Reversing is slower, sensors usually look forward, and every direction change is a stop. Reeds-Shepp is the right tool for a parking manoeuvre in a bay and the wrong one for a corridor where turning around would be safer than backing out.

Common misconceptions

Engineering takeaways

1. A car-like robot has a minimum turning radius R = L / tan(δ_max); every path it drives is arcs of radius at least R and lines.
2. Dubins: the shortest forward path is one of six words, LSL, RSR, LSR, RSL, RLR, LRL.
3. A CSC path is built from two tangent circles; arc angles are taken modulo 2π so every arc is driven forward.
4. Dubins distance is asymmetric; Reeds-Shepp distance, which allows reversing, is symmetric and never longer.
5. These curves ignore obstacles and have discontinuous curvature; planners check them and may smooth them.

References and further reading

The two original papers and a classification of the Dubins set.

• L. E. Dubins, “On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents”, American Journal of Mathematics, 79(3), 1957.
• J. A. Reeds and L. A. Shepp, “Optimal Paths for a Car That Goes Both Forwards and Backwards”, Pacific Journal of Mathematics, 145(2), 1990.
• A. M. Shkel and V. Lumelsky, “Classification of the Dubins Set”, Robotics and Autonomous Systems, 34(4), 2001.
• S. M. LaValle, “Planning Algorithms”, Cambridge University Press, 2006, chapter 15.3.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: searching over poses with motion primitives so that every edge of the plan is drivable: Hybrid A* and state lattices.

Related content

Nothing below is required to finish this lesson.

• Before
  M4-T4: RRT*, Informed RRT* and BIT*

  Explain rewiring and asymptotic optimality, and how informed sampling focuses the search once a path exists.

• Lab
  M4-L4: Park the Car-Like Robot

  Reverse a tug into a charging bay with a Dubins and Reeds-Shepp path.