Algorithm for RC car

I'm looking for an algorithm, and I have no idea where to start!

I'm trying to get from point A to point B in a cartesian graph. Movement is restricted to that of a RC car: backward, forward, forward-left, and forward-right (constant turning radius; car is either turning completely, or it is not turning at all).

How would I construct an algorithm which takes the following:

turningRadius, initialPositi开发者_如何学Goon, initialOrientation, finalPosition

And yields an ordered set of steps to get to finalPosition?

Note that I don't care what the final orientation is.

Thanks!

EDIT: Note that this is not in a graph with discreet nodes, but a continuous coordinate system

The way you problem is described, the algorithm is straightforward and requires only two simple steps: 1) move forward while turning (left or right) until the car is pointed directly at B, 2) move straight forward until you hit B. Done.

The only relatively tricky part is the first step. If B lies to the left from the longitudinal axis of the car in its initial position, the natural approach would be to start by turning left. This will work, unless point B lies inside the circular trajectory produced by such a left turn (of radius turningRadius). In the latter case the car will run in circles, but will never be able to aim directly at B. In such cases the proper strategy is actually to start with a right turn and keep turning until you aim the car at B.

So, if you don't have any optimality requirements for your trajectory, the simplest algorithm for the first step would be to unconditionally turn "away" from the point: turn right if B lies to the left of the longitudinal axis of the car, and turn left if B lies to the right. Keep turning until the car is aimed directly at B. This sounds a bit unnatural, but it always works, i.e. you will always be able to eventually aim the car.

If you care for a more optimal (shorter) trajectory, then you need to analyze the location of B with respect to the initial position/orientation of the car ("Is B inside the turning circle or outside?") and choose the direction of the first turn accordingly.

In general this is not an easy problem. It falls under the category of "Planning under differential constrains". The last three chapters of LaValle's book (available online here) deal with this. In particular, look at section 14.4.2., that deals with a "Dubins car", which is like your RC car, except that it doesn't move backwards.

Also search for "Dubins car path planning". You will find a lot of papers.

Have your tried a* (a-star)? it is also nice when you provide it a terrain map. You can assign weights to different portions of terrain which will result in a different path. I believe the algorithm by default does not provide diagonal directions, but you can add that in pretty easily.

Also it does not by default deal with "turning" but a-star will give the full path. What you could do is calculate the turn radius based on 2 points. The current position and the next calculated position, OR the last position and the current position. You can then add or subtract the facing direction with the change in angle. You may need to tweak this some.

Sounds like an interesting and fun project! To get a specific algorithm recommendation, you should probably provide more detail… Like are you expecting to literally run this on some sort of embedded controller attached to an RC car? Or is the algorithm to run on a workstation and control the car remotely? (Or is this purely an abstract exercise and there is no car… awwww.)

My generic recommendation for getting a handle on where to start would be Building Problem Solvers, which is a great intro to the world of "AI" problem solving techniques. It might be a bit dated these days… but wait, what am I saying! Probably not. :-)

[Okay I should explain that last comment: Most "modern" AI techniques that I've seen in practice actually date back to ideas many years old… They've just become practical now thanks to the relentless advance of Moore's Law. So a book written in 1993 is still discussing fairly state-of-the-art techniques, from what I have personally seen. I'd love to be pointed at a counter-example!]