Pathfinding
Published 8 years, 8 months pastThis 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.
Comments (14)
In video games, the A* algorithms are what are used for pathfinding.
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.
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
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.
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.
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?
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?
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.
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!
Pingback ::
Pathfinding — Q’s from Eric Meyer | Carpet Bomberz Inc.
[…] via Pathfinding — Thoughts From Eric […]
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.
Know anybody at NASA you can call? Most of those guys seem like they can do it in their sleep!
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.
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.