Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Traffic Prediction with Advanced Graph Neural Networks

deepmind.com

Post reply on HN
Print view View original

31–40 of 45 posts

Re: Traffic Prediction with Advanced Graph Neural Networks

#31

Post by scythe »

2bitencryption wrote: post #5

Google Map's traffic prediction has always led me to a very curious question: Clearly Google Maps has the ability to turn into a feedback loop. Traffic exists -> people use Google Maps to find better routes -> traffic is modified due to people taking alternate routes -> new traffic emerges. So my question is: what is Google Maps traffic optimizing for? The best traffic experience for User 3982274, or the best traffic…

It might as well be noted that Braess's paradox is a phenomenon observed in a world of (mostly) predictionless navigating, i.e. before Google Maps. When fluids flow, phonons communicate "traffic information" at the speed of sound and the resulting flow is usually efficient. You can get Braess's paradox in physics, but you need quantum mechanics:

https://ui.adsabs.harvard.edu/abs/2012PhRvL.108g6802P/abstra...

However, Google Maps updates its traffic predictions much more slowly than the "speed of sound" by any useful definition of the way disturbances propagate in traffic. As 'frogblast noted, far more cars may be suddenly directed down a side road than it can carry, and the recommendation stops being broadcast too late.

Re: Traffic Prediction with Advanced Graph Neural Networks

#32

Post by HALtheWise »

frogblast wrote: post #23
paxys wrote: post #7

Earlier quoted context omitted.

When User 3982274 is on a busy road using the app, Google optimizes for that user's experience. If every user on that road is using the app at the same time, these algorithms should theoretically result in the optimal condition you described above. For example, if there are two roads leading up to the destination, one at 100% capacity and the other at 0%. The app will start routing people from road 1 to road 2. When…

I live in an area strongly impacted by Google making ‘individually optimal’ decisions for each driver, and actually leaving those drivers in a dramatically worse situation. I live in a rural area, between a major population center and a major resort area, with one major highway and a few small back roads that provide alternate paths for part of the highways route. Every summer weekend the highway becomes highly conge…

In theory, the learning based approach in this blog post could solve this without any architectural changes. They mention predictions spilling to nearby roads, learning the pattern that "if the highway is backed up now, the little road will be too in a few minutes". Once that is baked into the model, Google Maps won't direct (as many) people onto the site road because they would get stuck in the predicted traffic there. The nice thing about this is it also handles the case where other mapping applications direct drivers there, and the "smartest" mapping application will still get you there fastest.

Re: Traffic Prediction with Advanced Graph Neural Networks

#33

Post by Areading314 »

paxys wrote: post #7
2bitencryption wrote: post #5

Google Map's traffic prediction has always led me to a very curious question: Clearly Google Maps has the ability to turn into a feedback loop. Traffic exists -> people use Google Maps to find better routes -> traffic is modified due to people taking alternate routes -> new traffic emerges. So my question is: what is Google Maps traffic optimizing for? The best traffic experience for User 3982274, or the best traffic…

When User 3982274 is on a busy road using the app, Google optimizes for that user's experience. If every user on that road is using the app at the same time, these algorithms should theoretically result in the optimal condition you described above. For example, if there are two roads leading up to the destination, one at 100% capacity and the other at 0%. The app will start routing people from road 1 to road 2. When…

This is correct. The optimal routing that improves transit time for individual travelers would also minimize global transit time. However, it is true that there could be externalities to this behavior, like cars being routed through neighborhoods with higher likelihood of accidents.

Re: Traffic Prediction with Advanced Graph Neural Networks

#34

Post by nurettin »

2bitencryption wrote: post #5

Google Map's traffic prediction has always led me to a very curious question: Clearly Google Maps has the ability to turn into a feedback loop. Traffic exists -> people use Google Maps to find better routes -> traffic is modified due to people taking alternate routes -> new traffic emerges. So my question is: what is Google Maps traffic optimizing for? The best traffic experience for User 3982274, or the best traffic…

> Clearly Google Maps has the ability to turn into a feedback loop.

Google and yandex average traffic by hour, they don't factor in their own users. That would be double counting and assuming that they are the only service.

Re: Traffic Prediction with Advanced Graph Neural Networks

#35

Post by SergeAx »

2bitencryption wrote: post #5

Google Map's traffic prediction has always led me to a very curious question: Clearly Google Maps has the ability to turn into a feedback loop. Traffic exists -> people use Google Maps to find better routes -> traffic is modified due to people taking alternate routes -> new traffic emerges. So my question is: what is Google Maps traffic optimizing for? The best traffic experience for User 3982274, or the best traffic…

Yandex, Google's Russian rival, is doing just this from time to time. I am taking a taxi from home to office every day and it sends a driver via longer routes when traffic is heavier.

I beleive that greater mileage contributes only to car's service frequency, and it's pennies when amortized to years of duty. Driver's and passenger's time is much more valuable.

Re: Traffic Prediction with Advanced Graph Neural Networks

#36

Post by GistNoesis »

I'm not sure this is advancing in the right direction for the users.

Optimizing traffic is probably doing more harm than good. It's one kind of premature optimization. I see it as a way of masking potential underlying problems like not enough investment in infrastructure, or too many cars for the capacity.

Squeezing out the performance from existing infrastructure, is probably harming the longer game of having a good transporting system for the users. And that's a game that should be played by the owner of the infrastructure, not some third party which just exploit the externalities by sending heavy road traffic through calm neighborhoods every-time there is a traffic jam, often increasing the risks of further accidents and grid-locking everything, because those roads were not designed for those spikes.

The worse is that more often than not, those routing apps are not even making the user win some time. But it makes the user happy because he believes he took the right direction by following the app direction.

Often it's net negative for everybody.

Re: Traffic Prediction with Advanced Graph Neural Networks

#37

Post by hackingthenews »

adanto6840 wrote: post #10
2bitencryption wrote: post #5

Google Map's traffic prediction has always led me to a very curious question: Clearly Google Maps has the ability to turn into a feedback loop. Traffic exists -> people use Google Maps to find better routes -> traffic is modified due to people taking alternate routes -> new traffic emerges. So my question is: what is Google Maps traffic optimizing for? The best traffic experience for User 3982274, or the best traffic…

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…

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.

Re: Traffic Prediction with Advanced Graph Neural Networks

#38

Post by Recursing »

2bitencryption wrote: post #5

Google Map's traffic prediction has always led me to a very curious question: Clearly Google Maps has the ability to turn into a feedback loop. Traffic exists -> people use Google Maps to find better routes -> traffic is modified due to people taking alternate routes -> new traffic emerges. So my question is: what is Google Maps traffic optimizing for? The best traffic experience for User 3982274, or the best traffic…

Fun short fiction story on how predictive systems whose predictions influence what they might predict might evolve: https://www.lesswrong.com/posts/SwcyMEgLyd4C3Dern/the-parabl...

In this very theoretical scenario, left to its own (with its objective function "minimizing prediction error") Google Maps could end up making predictions that make traffic more predictable, without anybody being able to notice anything is going wrong.

A similar concept could be applied to the infamous "Youtube algorithm" for predicting user interests, might end up just showing videos that make users more predictable

Re: Traffic Prediction with Advanced Graph Neural Networks

#40

Post by jastingo »

What I've always wondered is to what extent A/B testing is conducted after any such algorithm is implemented.

For example, does Google Maps send some users deliberately down a route that it thinks is suboptimal so that it can better learn traffic patterns over a wider range of roads? My instincts as a data scientist tell me this would be a great way to gather more data and to create a better system as a whole, but at the expense of some users having longer drive times for some routes.

Putting my tin foil hat on, I've long suspected that Waze is used as the experimentation platform for Google Maps in this way. Where I live, Waze presents some highly unusual routes that I know are not optimal having lived here forever, whereas Google Maps is more on point.

Post reply on HN