Does anyone know of any open source implementations for finding the optimal path of a Reeds-Shepp car?

I'm trying to implement the formulas myself, but I'm having trouble with one of them. I think it's a typo in their paper; their formula just doesn't spit out the expected result.

The specific formula is found in Section 8.3 in Reeds and Shepp's 1990 paper, found here. I'm trying to find the optimal path from (x = 0, y = 0, theta = 0) to (x = 0, y = 0, theta = -pi), or put differently: the car goes back to the starting position, but pointed in the opposite direction. The correct solution is shown in Figure D of Section 1. The formula in Section 8.3 should give the same turn lengths, but it doesn't. The three turn lengths should all be pi / 3, but working it out by hand gives me completely different values.

  • 2
    $\begingroup$ I think that the question is not research level, however perhaps this can help you: msl.cs.uiuc.edu/~lavalle/cs326a/rs.c (README: msl.cs.uiuc.edu/~lavalle/cs326a/README_RS). You can also take a look at Chapter 13 of the book "Planning algorithms": planning.cs.uiuc.edu/ch13.pdf $\endgroup$ – Marzio De Biasi Jan 3 '12 at 9:53
  • $\begingroup$ Thanks! That C code link was exactly what I was looking for. The formula used there is definitely different from the one in the paper, but it gives the correct results. $\endgroup$ – Matt Bradley Jan 3 '12 at 16:56
  • $\begingroup$ As far as the following code goes (msl.cs.uiuc.edu/~lavalle/cs326a/rs.c) has anyone checked the validity of this code? My initial tests are showing really poor estimates, sometimes overestimating and sometimes underestimating the length. His email does mention it's "for a certain increment of configuration (x,y,phi)" which I'm not certain how to interpret. $\endgroup$ – Otto Nahmee Jun 12 '15 at 23:23
  • $\begingroup$ I eventually implemented Reeds-Shepp for my master's thesis using that original link as a guide. Here is my C# implementation. The solver worked perfectly for all possible Reeds-Shepp paths. Hopefully it'll point you in the right direction. $\endgroup$ – Matt Bradley Jun 12 '15 at 23:46
  • $\begingroup$ If you have a new question, please ask it by clicking the Ask Question button. Include a link to this question if it helps provide context. $\endgroup$ – Jan Johannsen Jun 15 '15 at 7:22

Copy of my comment above (I suppose that the question can be accepted/closed):

I think that the question is not research level, however perhaps this can help you: http://msl.cs.uiuc.edu/~lavalle/cs326a/rs.c (README: http://msl.cs.uiuc.edu/~lavalle/cs326a/README_RS).

You can also take a look at Chapter 13 of the book "Planning algorithms".

  • $\begingroup$ By the way, how did you find that code? $\endgroup$ – Matt Bradley Jan 3 '12 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.