Reeds-Shepp Cars

Remember my post on the Dubin’s car? It’s a car that can either go forward, turn fully left, or turn fully right. In that post I explained that the shortest path from one point to another via the Dubin’s car could be described by one of six control sequences. The Reeds-Shepp car is essentially the same thing as the Dubin’s car, except it can also move backwards! This post isn’t quite the comprehensive step-by-step guide as the Dubin’s one, but I’ll give you a great overview of the paths, point you to some great online resources, and give you some tips if you plan on implementing them yourself!

Overview

The Reeds-Shepp car is named after two guys, J.A. Reeds and L.A. Shepp, who in 1990 published a really comprehensive paper that showed we could classify all the control sequences that account for the shortest paths of the Dubin’s car if we permitted it to go in reverse. However, instead of 6 paths, they showed there to be 48, which is quite a few more if you’re implementing them one by one. (Fortunately they also showed an easier way to implement things such that we’d only have to write 8 or 9 functions and reuse them cleverly).

However, a year later two other people (HJ Sussman and G Tang) showed that 48 is actually too many control sequences, and the real number is 46. The proofs for all these things are quite complicated, so I won’t try to explain them here (And I don’t fully understand all of them myself!).

Great resources

The above-mentioned paths/control sequences I’ve been mentioning are fairly well explained by Steven LaValle’s webpage. Also, Mark Moll at Lydia Kavraki’s lab wrote an implementation of the Reeds-Shepp paths for their Open Motion Planning Library. Steven LaValle also has his own implementation that became part of NASA’s CLARAty project.

Some tips for your own implementation

Clearly there’s tons of information, and even code, online about the Reeds-Shepp cars, so why write about them? Well, because I implemented them myself, and learned a few things that might help you:

1. There are typos in the original Reeds-Shepp paper
   • This is important. Besides some formatting mistakes that they make here and there, the major issue is with paths described by 8.3 and 8.4. These paths include C | C | C (for example Left forwards, Right backwards, Left forwards) and C | C C (Left forwards, Right backwards, Left backwards). If you try to implement things as they stand it WILL NOT WORK!
2. (Update 5-30-2013: I have been in contact with the OMPL developers and have determined that the following claim was made in error, so I am retracting it) The OMPL library tries to address these issues, but in my experience theese paths don’t work either!
   • The lengths of the paths being returned by their implementation seem correct, but the actual controls for those paths seem incorrect at time (or didn’t work for me at least).
3. Steven LaValle’s implementations of 8.3 and 8.4  do work, though with some minor modifications.
   • I don’t claim to be the expert on how his code was supposed to be used, as I was doing my own thing, but if you try to grab the source, you may need to change some “eta” values to “y – 1.0 + cos(phi)”.
4. You can be more efficient than all of these implementations!
   • For one, Dr. LaValle’s implementation just has too many redundant functions that you could just ignore by using the other ones as recommended in the Reeds-Shepp paper (see the section on reflecting, timeflipping, and backwards paths)
   • For another, there was yet another paper published in 1998 by P Soueres and J Boissonnat that gave us some strategies for ignoring entire swaths of potential paths, because we could know a priori they wouldn’t be optimal. Basically, this works by defining theta to be the angle from the start to goal configuration, and then performing some really simple checks on the value of theta.
5. Finally, a word of caution — the formulas provided by Reeds and Shepp assume the start configuration to be at position (0, 0) with rotation 0. If you use a global coordinate system, you need to convert the goal coordinates to relative ones, which is not just as simple as (goal.x – start.x), (goal.y – start.y), (goal.theta – start.theta). Well, it’s almost that simple. You need to rotate the (relativeX, relativeY) point by -start.theta so that it’s truly relative to (0, 0, 0).
   • Also, the formulas all assume a unit turning radius, but you can easily account for this. (sidenote: they also assume unit velocity, i.e. no accelerating or braking, but you can also fake this afterwards!)

That’s pretty much it.  The academic publishing scene is a great venue to show people what does work, but not so well for discussing what doesn’t work, or providing tips/tricks for getting things to work better. That’s what blogs are for

One word of advice: if you do use someone else’s open source code, always make sure to provide any disclaimers they require, as well as attribute the pieces you used to the original authors!