Traffic Prediction with Advanced Graph Neural Networks

Re:Traffic Prediction with Advanced Graph Neural Networks by adanto6840 on Saturday September 05, 2020 @06:08PM (#24387239)

It's a good question, even if it's likely not applicable practically yet. In a game my company created, we implemented cooperative realtime pathfinding using WHCA* -- an algorithm that David Silver published [0] (he's now working at DeepMind last I looked).

WHCA* turned out to be a bit too suboptimal for our use-case, people generally expected "perfectly optimal" routes to be used for aircraft, and they weren't even overly happy with most-optimal "for-all" paths either. We eventually implemented a relatively simple "AStar-3D", essentially just A* against a space-time graph, and it's greedy/FIFO -- meaning it's optimal for each aircraft at the time the aircraft runs it's path. That made people happy -- aircraft no longer did seemingly stupid things like "oscillate", or get "temp. stuck" for overly long periods, etc.

I had no idea cooperative path-planning was so damn difficult -- I remember estimating it as a 1-week mini-project initially. Wow, such naivety, and that's when you even have perfect information! Such a cool domain, tons of respect for the work that's being done here, even if there are some tricky/ethical aspects that are going to come into play eventually, inevitably. :)

0 - https://www.aaai.org/Papers/AIIDE/2005/AIIDE05-020.pdf

[ Parent | on HN ]

Re:Traffic Prediction with Advanced Graph Neural Networks by hackingthenews on Sunday September 06, 2020 @05:40AM (#24390171)

I can see how solving for perfect cooperation can leave people irritated. That's why most algorithms used in OSs takes latency, fairness etc. into account.

Algorithms in between might work better in real life, e.g. people routes can be adjusted slightly to make paths better overall, but no adjustment (away from greedy) is made that the average pilot would find overly unfair or unpractical.

[ Parent | on HN ]