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

<p>I think that the question is not research level, however perhaps this can help you: 
<a href="http://msl.cs.uiuc.edu/~lavalle/cs326a/rs.c" rel="nofollow">http://msl.cs.uiuc.edu/~lavalle/cs326a/rs.c</a> (README: <a href="http://msl.cs.uiuc.edu/~lavalle/cs326a/README_RS" rel="nofollow">http://msl.cs.uiuc.edu/~lavalle/cs326a/README_RS</a>).</p>

<p>You can also take a look at <a href="http://planning.cs.uiuc.edu/ch13.pdf" rel="nofollow">Chapter 13 of the book "Planning algorithms"</a>.</p>

CC BY-SA 3.0
2012-01-03T17:55:19.047Z
By the way, how did you find that code?
Matt Bradley
CC BY-SA 3.0
2012-01-03T17:11:22.243Z
2012-01-03T17:11:22.243Z
Marzio De Biasi
<p>Does anyone know of any open source implementations for finding the optimal path of a Reeds-Shepp car?</p>

<p>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.</p>

<p>The specific formula is found in Section 8.3 in Reeds and Shepp's 1990 paper, found <a href="http://statistics.wharton.upenn.edu/documents/research/Car%20that%20goes%20forwards%20and%20backwards.pdf" rel="nofollow">here</a>. 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.</p>

CC BY-SA 3.0
2012-01-03T09:53:18.907Z
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": http://planning.cs.uiuc.edu/ch13.pdf
Marzio De Biasi
CC BY-SA 3.0
2012-01-03T16:56:56.240Z
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.
Matt Bradley
CC BY-SA 3.0
2015-06-12T23:23:44.943Z
As far as the following code goes (http://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.
Otto Nahmee
CC BY-SA 3.0
2015-06-12T23:46:12.593Z
I eventually implemented Reeds-Shepp for my master's thesis using that original link as a guide. Here is [my C# implementation](https://github.com/mattbradley/AutonomousCar/blob/master/AutonomousCar/AutonomousCar/PathFinding/ReedsShepp/ReedsSheppSolver.cs). The solver worked perfectly for all possible Reeds-Shepp paths. Hopefully it'll point you in the right direction.
Matt Bradley
CC BY-SA 3.0
2015-06-15T07:22:33.893Z
If you have a new question, please ask it by clicking the [Ask Question](http://cstheory.stackexchange.com/questions/ask) button. Include a link to this question if it helps provide context.
Jan Johannsen
<graph-algorithms><implementation>
Any existing Reeds-Shepp implementations?
Matt Bradley
# Any existing Reeds-Shepp implementations?

(Asked by: username_0 on 2012-01-03)

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](http://statistics.wharton.upenn.edu/documents/research/Car%20that%20goes%20forwards%20and%20backwards.pdf). 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.

**Tags:** graph-algorithms, implementation
> **Comments:**
> **username_1**: 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": http://planning.cs.uiuc.edu/ch13.pdf  
> **username_0**: 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.  
> **username_2**: As far as the following code goes (http://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.  
> **username_0**: I eventually implemented Reeds-Shepp for my master's thesis using that original link as a guide. Here is [my C# implementation](https://github.com/mattbradley/AutonomousCar/blob/master/AutonomousCar/AutonomousCar/PathFinding/ReedsShepp/ReedsSheppSolver.cs). The solver worked perfectly for all possible Reeds-Shepp paths. Hopefully it'll point you in the right direction.  
> **username_3**: If you have a new question, please ask it by clicking the [Ask Question](http://cstheory.stackexchange.com/questions/ask) button. Include a link to this question if it helps provide context.  

---

## 1 answers

### Answer by username_1 on 2012-01-03. Score: 3 | Accepted answer

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"](http://planning.cs.uiuc.edu/ch13.pdf).

> **Comments:**
> **username_0**: By the way, how did you find that code?  

---

