Posts Tagged ‘motion planning’

Reeds-Shepp Cars

November 15, 2012

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!


A Comprehensive, Step-by-Step Tutorial to Computing Dubin’s Paths

October 21, 2012

Imagine you have a point, a single little dot on a piece of paper. What’s the quickest way to go from that point to another point on the piece of paper? You (the reader) sigh and answer ”A straight line” because it’s completely obvious; even first graders know that. Now let’s imagine you have an open parking lot, with a human standing in it. What’s the quickest way for the human to get from one side of the parking lot to the other? The answer is again obvious to you, so you get a little annoyed and half-shout ”A straight-line again, duh!”. Okay, okay, enough toss-up questions. Now what if I gave you a car in the parking lot and asked you what was the quickest way for that car to get into a parking spot? Hmm, a little harder now.

You can’t say a straight line because what if the car isn’t facing directly towards the parking space? Cars don’t just slide horizontally and then turn in place, so planning for them seems to be a lot more difficult than for a human. But! We can make planning for a car just about as easy as for a human if we consider the car to be a special type of car we’ll call a Dubin’s Car. Interested in knowing how? Then read on!