5

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

antonakos
  • 8,261
  • 2
  • 31
  • 34
loneboat
  • 2,845
  • 5
  • 28
  • 40

4 Answers4

5

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.

AnT stands with Russia
  • 312,472
  • 42
  • 525
  • 765
  • but that does not account for terrain or roads – Parris Oct 27 '10 at 18:48
  • 4
    @Parris: What terrain? What roads? There's no mention of any "terrain" or "roads" in the statement of the problem. The problem, as stated, is getting from point A to point B specified by their cartesian coordinates on continuous and infinite flat plane. – AnT stands with Russia Oct 27 '10 at 18:50
  • Ahh true, I assumed the problem was more difficult. When I read RC car, I assumed game or real RC car. The problem statement does not say infinite or flat plane by the way. This method would work fine if that were truly the case, or is a simple animation. However, how often is a system completely flat, with no obstacles, and infinite. – Parris Oct 27 '10 at 19:00
  • Excellent description - thanks so much! The case where the destination was what had me stuck until now (or rather, "going in circles" - har-har). Thanks! – loneboat Oct 27 '10 at 19:14
  • What if B is perpendicular and relatively close to A (Similar to a parking maneuver)? I think that hen your algorithm will fail. – Alejandro Oct 27 '10 at 19:51
  • @Alejandro Weinstein: I don't see any problem in this case. If it is too close on the left, my algorithm says that the car has to turn right. Easy. Where do you see the problem? – AnT stands with Russia Oct 27 '10 at 20:25
1

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.

Alejandro
  • 1,002
  • 8
  • 14
  • 2
    Importantly, LaValle's book explains that such paths are optimal solutions for this class of problem. However, because the OP stated that the car can also drive backward this should actually be Reeds-Shepp curves (sec. 15.3.2), rather than Dubins curves (sec. 15.3.1). – Andrew Walker Feb 05 '11 at 00:39
0

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.

Parris
  • 17,833
  • 17
  • 90
  • 133
  • Sorry, I said grid, which implies I'm talking about a graph with discreet nodes. This is in a continuous coordinate system. Thanks! – loneboat Oct 27 '10 at 18:37
  • Well they aren't different. There is no way to not have a grid. Your grid might contain extremely small "points" and as a result not seem grid like. Think about pixels on a screen. Consider that in 3d games positions are defined using floating point values; however, a grid is overlayed to calculate path, oct-trees, etccc – Parris Oct 27 '10 at 18:41
  • Parris: I understand that I _could_ quantize the grid into one giant graph with nodes (hence enabling me to use A*), but I think doing it to the degree of precision which I need would make it computationally prohibitive on my platform. Thanks, though! – loneboat Oct 27 '10 at 19:27
0

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!]

Kaelin Colclasure
  • 3,925
  • 1
  • 26
  • 36
  • Yes, I'm really attaching an embedded system to an RC car. It'll be fun! Thanks for the book recommendation. – loneboat Oct 27 '10 at 19:25