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!

Advertisements

Tags: , , , ,

6 Responses to “Reeds-Shepp Cars”

  1. Mark Moll Says:

    I just found your post and noticed that you found some problems with OMPL’s implementation of Reeds-Shepp curves. Would you mind emailing me an example of a case where OMPL gets it wrong? You could also file a bug at https://bitbucket.org/ompl/ompl/issues?status=new&status=open.

  2. Miles J Johnson (@milesj6) Says:

    Just ran in to this, and like it. Are you going to put your Reeds-Shepp code on github? 🙂

    • gieseanw Says:

      Hi Miles,
      No plans at the moment. I would suggest you look into OMPL, which I link in the article. It’s open source and you can modify it as you like 😉

      -Andy

  3. Tim Says:

    Thanks for the tutorials. Really well done.
    You state that the Sussman paper drops the number of possible paths to 46. In the paper, the only thing I found was a statement claiming that you can replace BuBuB paths with R+R-R+ or L+L-L+.
    This makes no sense to me, as you would just be backing up on the same arc you had just traversed. You should never follow a R+R-R+ or L+L-L+ trajectory.
    Any chance you could explain what they mean?
    Thanks!

    • gieseanw Says:

      Hi Tim,
      Thanks for stopping by! One resource that was very helpful to me was this page: http://planning.cs.uiuc.edu/node822.html

      If you check out Figure 15.10 and its description, they mention how L-R+L- and R-L+R- are redundant. Now, they don’t quite explain why, as they leave that to the Sussman and Tang paper (which is more than 70 pages long!)

      Skip to the part after the Side discussion and background for an actual answer to your question. Some of the following stuff is solely for future visitors.

      I’m not even remotely an expert in Lie algebra or Pontryagin’s Maximum Principle, but I’ll try my best to understand and explain. (Fortunately, total understanding of the theory is not necessarily to implement the solution 🙂 )

      I think the R+R-R+ and L+L-L+ paths you are referring to come from Lemmas 19 and 20, as referenced by Remark 17.

      —————-Side discussion/background:——————————
      Note that B (or “bang”) stands for either an L or R control (top of page 32). The character ‘u’ stands for linear velocity (forwards/backwards) and ‘v’ stands for angular velocity (left/right). See the bottom of page 30 (start of Section 12) for more discussion on what L, R, and + or – mean.

      In much of the paper, the authors are solving the Convex Reeds Shepp problem, which allows for u and v to be less than 1 (i.e. non-unit motion and variable-degree turns). For a more thorough explanation of the difference between the CRS and RS problems, see the top of page 7. The analyses in Lemmas 19 and 20 are for CRS, but hold because the authors place restrictions on u and v such that the problem again becomes RS.

      When a u or v follows a control, that means a switch in direction, or a gear change if you will. So BuB could mean L-L+, L+L-, R-R+, R+R-, L-R-, L-R+, R-L-, or R+L-. BuBuB follows similarly.
      ————————————————————————————-

      You can see on page 31 (Figure 4) precisely what the authors mean when they say L+, L-, etc. and, well, they look exactly like what you’d expect. Just be careful to note the direction the car is facing as it goes around the turns.

      Now, you can start to see how the authors begin mixing up their lefts and rights in Figure 5 (page 33). Of the 9 paths shown, 1 of them is mislabeled. They show a R+S+R+ path, but label it as R+S+L+. Further evidence that this is an accident is the fact that the L+S+L+ path adjacent to it looks as expected.

      Labeling really just gets worse from there; a common mistake seems to be mislabeling R- as L-. Figure 8 shows this pretty clearly.

      However, despite the fact that some of the figures are (perhaps egregiously) mislabeled, the math seemed to work out (not like I’d be able to verify it) so long as the authors stayed with the more general labeling of B for a turn instead of a specific L or R.

      My conclusion: You’re right, the paper just mislabels things. What the paper should really be saying is that L-R+L- and R-L+R- paths are redundant; R+L-R+ and L+R-L+ are sufficient for the C|C|C class of paths (Alternatively stated BuBuB class).

      I hope this helps!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: