Tracking 4D data
The problem is finding the optimal route for the plane through 4D winds (winds with different heights and which change as they move (predictive wind model)).
I used the traditional A * search algorithm and hacked it to get it to work in 3 dimensions and with wind vectors.
It works in many cases, but is very slow (im working with a huge number of data nodes) and doesn't work for some edge cases.
I feel like it works "well" for me, but it feels very hacked.
Is there a more efficient way to find paths through data like this (maybe a genetic algorithm or a neural network) or something that I haven't even considered? Maybe fluid dynamics? I dont know?
Edit: further details.
Data are wind vectors (direction, magnitude). The data is spaced 15x15 km at 25 different heights.
By "doesnt always work" I mean it will take a stupid path for the aircraft because the weight of the path is the same as the other path. It's great for pathfinding, but not optimal for plane.
For every node change I take into account a lot of things:
- Descending elevation cost.
- Wind resistant.
- Ignoring nodes with too high resistance.
- The cost of a diagonal tavel against a straight line, etc.
I use euclidean distance as a heuristic or H value. I use various factors for my weight or G value (list above).
Thank!
source to share
You can always have a compromise in terms of timing using a weighted A * .
A weighted A * [or A * epsilon] is expected to find the path faster than A *, but the path will not be optimal [However, it gives you an estimate of its optimality as a parameter of your epsilon / weight].
source to share
A * is not advertised as the fastest search algorithm; it makes sure that the first solution it finds is the best one (if you allow a valid heuristic). If you don't work in some cases, then there is something wrong with some aspect of your implementation (maybe with A * mechanics, maybe with domain specific items, given that you have not provided any details, you cannot say more ).
If it is too slow, you may need to rethink the heuristic you are using.
If you do not need the optimal solution, then another method may be more appropriate. Again, given how little you've reported on the issue, it's hard to say more.
source to share
Are you planning offline or online?
Usually for these problems, you don't know what the winds are until you actually fly through them. If this is indeed a problem on the Internet, you might want to try to build a near-optimal policy. There is already quite a lot of research in this area, one of the best is "Autonomous control of a takeoff and landing aircraft by teaching harps" by John Wyharton.
source to share