meyerweb.com

Skip to: site navigation/presentation
Skip to: Thoughts From Eric

Pathfinding

This is a thing I’ve been trying to figure out in my spare time, mostly noodling about in my head with various ideas when I have some down time, and now I want to know if there’s a formal answer of some sort.  It goes like this: in a lot of situations, ranging from airplane autopilots to self-driving cars (I think) to videogames, there are times when you want a moving object to get itself as precisely as possible with a known path.  For example, having the autopilot line up with the approach path for a runway.

So how is that done?  What’s the general approach to programming a moving thing to find, with decent efficiency, its way onto a given path in 3D space?  Or in 2D space, if that’s easier to understand?  I can think of a few naïve approaches, but none of them seem anywhere near robust enough to be trusted.

14 Responses»

    • #1
    • Comment
    • Mon 28 Mar 2016
    • 2327
    John wrote in to say...

    In video games, the A* algorithms are what are used for pathfinding.

    • #2
    • Comment
    • Mon 28 Mar 2016
    • 2334
    Eric Meyer wrote in to say...

    A* is good for traversing a set of points, but doesn’t seem to be what I’m after here (see the example of a plane lining up for landing). Though perhaps I have misunderstood.

    • #3
    • Comment
    • Mon 28 Mar 2016
    • 2333
    Mark wrote in to say...

    I think Dijkstra’s is the most common, at least among introductory algorithms courses. There’s a great list of them here: https://en.wikipedia.org/wiki/Pathfinding#Algorithms_used_in_pathfinding

    • #4
    • Comment
    • Mon 28 Mar 2016
    • 2341
    Eric Meyer wrote in to say...

    I think what I want is broadly an any-angle path planner, except even those seem to consider a start point and an end point, not an ending vector that matches a desired vector.

    • #5
    • Comment
    • Tue 29 Mar 2016
    • 0006
    Will Kessel wrote in to say...

    It’s called a Radio Direction Finder. When a plane is aloft, the pilot flies by a map which contains the locations of hundreds of these little buggers, which you can tune your radios to during fight (typical airplane’s avionics contains anywhere from 3 to 10 RDF radios dedicated to this process), and you determine your exact location, speed, and direction, independently from your cockpit instrumentation which will tell you the same, by triangulation – and this process is at least as accurate as GPS. Flight computers will get the airplane lined up precisely with the runway (two dimensions), and will guide the plane down its glideslope (3 dimensions) by using the data from the RDF units and the glidepath beacons. When you consider that all commercial aviation flies by instrument and not VFR (Visual Flight Rules), you’d think there’d be far more collisions. But, honestly, it’s surprisingly accurate.

    • #6
    • Comment
    • Tue 29 Mar 2016
    • 0045
    Eric Meyer wrote in to say...

    Flight computers will get the airplane lined up precisely with the runway (two dimensions), and will guide the plane down its glideslope (3 dimensions) by using the data from the RDF units and the glidepath beacons.

    Right, but how do the flight computers line the aircraft up precisely? There has to be more to this than flying point-to-point, because aircraft cannot make instantaneous changes of direction once they reach a given point. There has to be a gradual alignment ahead of time, or else the plane will overshoot each point, leading to a serpentine path when viewed from above. My question is: how, exactly, is that alignment accomplished?

    • #7
    • Comment
    • Tue 29 Mar 2016
    • 0145
    Will Kessel wrote in to say...

    If you look at an airport (one which supports IFR – Instrument Flight Rules) from above, like with Google Maps, you’ll see a set of structures, usually orange, which have lights on top, starting a couple hundred yards out from the end of the runway, aligned with the centerline, about every 50 yards (or so) apart. There’s a radio beacon on top of each one, all transmitting the same frequency. That’s what the airplane’s computer homes in on (at night, there are strobe lights which are timed to flash progressively toward the runway, which is a big visual aid, especially for those in general aviation flying VFR at night). From that, the computer can create a composite of virtual glidepath windows that the plane can guide itself through. There’s little you can do to mess it up. In the airport’s pattern, you fly directly over a beacon in a particular direction, then the next, then the next, etc. At a pre-determined point, you make a 90° turn onto the base leg that takes place in a particular amount of time, and it places you above the next beacon in a particular direction. Same deal to turn onto final approach, which, with a large airliner, can be 10 miles or more long. Plenty of time to align with the glideslope. The plane’s computer knows optimum airspeed, thrust, and elevator trim to maintain proper glideslope. Does that help?

    • #8
    • Comment
    • Tue 29 Mar 2016
    • 0644
    Florian Pichler wrote in to say...

    Back in university I helped with creating a game engine and had to solve the same problem. While our solution might not be the best there is, it worked pretty well.

    It helped a lot to split the problem into smaller ones:

    1. Finding possible paths (we used Dijkstra, which gave us a list of points)
    2. Moving to the next node alongside the found path

    Now that we have a list of our points, we look not at a single point, but at a point and its next sibling, which gives us what you’re looking for: A vector.

    (Since we knew how our object should be oriented at the end of the path, we even had a vector for the very last point in the path.)

    We also looked ahead even further and used bezier curves to connect three or more points in a smooth curve. Doing that and adding a little variation to the movement gave us pretty good looking results for what we needed.

    I don’t know it that’s in any way close to what you’re looking for, but at least from my experience it helped a lot to look at navigation as a set of problems instead of a single one.

    • #9
    • Comment
    • Tue 29 Mar 2016
    • 1100
    Eric Meyer wrote in to say...

    Ah, Florian, I think that’s exactly what I needed! Bézier curves—why did I not think of that? As long as you can do a reasonable job of picking control points, the rest follows. You can either construct a series of interim waypoints along the curve, or just follow the curve precisely, depending on the needs and situation. It makes perfect sense, and I think it could easily be generalized to three dimensions. Thank you!

    • #10
    • Pingback
    • Tue 29 Mar 2016
    • 1103
    Received from Pathfinding — Q’s from Eric Meyer | Carpet Bomberz Inc.

    […] via Pathfinding — Thoughts From Eric […]

    • #11
    • Comment
    • Tue 29 Mar 2016
    • 1133
    Carlos wrote in to say...

    A* works for any topology. Most videogame oriented sample implementations and tutorials use some sort of 2D-ish square grid, but you can apply it to any optionally weighted, optionally directed graph structure. That weight calculation can be anything, it doesn’t have to be just plain Manhattan distance over a map. It could be fuel vs atmospheric drag vs panic factor on your passengers. Your node links could model things like rudder changes, throttle, etc. I’m sure there’s better methods for landing a plane, but A* can work as a sorta general solver.

    • #12
    • Comment
    • Thu 31 Mar 2016
    • 1212
    dj wrote in to say...

    Know anybody at NASA you can call? Most of those guys seem like they can do it in their sleep!

    • #13
    • Comment
    • Fri 1 Apr 2016
    • 1520
    David wrote in to say...

    I’m not sure why you started to think Bezier curves solve your problem. That is just giving you the path, not how to get onto the path.

    What you want are the algorithms used in PID controllers. This is what gets you onto the path and corrects for any errors taking you off path. It also has the correct properties for moving you onto a new path (say you need to make an emergency landing).

    https://en.wikipedia.org/wiki/PID_controller

    As mentioned in the history, one of the first uses for these was in automatic ship steering 100 years ago, so it has been around in this field for a long time. For some applications, more model control theory is needed, but not usually for smooth paths in 2D or 3D space.

    • #14
    • Comment
    • Fri 1 Apr 2016
    • 1547
    Eric Meyer wrote in to say...

    It’s quite true that PID controllers can be used to stay on the path, but my question was about how to figure out what path to stay on. So both would be used in the end, but my question was about the first part (finding a reasonable path to take), not the second part (staying on the reasonable path). Apologies if I made that unclear.

Leave a Comment

Line and paragraph breaks automatic, e-mail address required but never displayed, HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>



Remember to encode character entities if you're posting markup examples! Management reserves the right to edit or remove any comment—especially those that are abusive, irrelevant to the topic at hand, or made by anonymous posters—although honestly, most edits are a matter of fixing mangled markup. Thus the note about encoding your entities. If you're satisfied with what you've written, then go ahead...


March 2016
SMTWTFS
February April
 12345
6789101112
13141516171819
20212223242526
2728293031  

Sidestep

Feeds

Extras