Algorithm for RC car

Question

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, initialPosition, 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

Answer 1

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.