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

11–20 of 45 posts

Re: Traffic Prediction with Advanced Graph Neural Networks

#11

Post by abra529 »

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…

Surprisingly, it isn't always the case that each driver optimizing their own route will lead to a global optimum - see Braess's paradox. "If every driver takes the path that looks most favourable to them, the resultant running times need not be minimal." [0]

[0] https://en.wikipedia.org/wiki/Braess's_paradox

Re: Traffic Prediction with Advanced Graph Neural Networks

#12

Post by wardrop »

ocdtrekkie wrote: post #6
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…

There's been a lot of anger in some neighborhoods when mapping apps start directing people through their small streets. This isn't really hypothetical. In theory, if Google Maps starts directing some portion of traffic through an alternate route, it's because it's less congested. As it does so, the main route also becomes less congested. In theory, it should reach a point where roughly, cars are being assigned to bot…

Indeed, the central hypothesis of most of the traffic simulation tools is what’s known as a Wardrop Equilibrium, in which users choose selfishly optimal routes until the traffic is evenly spread and no user has an incentive to deviate to an alternative route. Of course this is an instance of the more general and well known notion of Nash equilibrium.

https://en.m.wikipedia.org/wiki/Route_assignment#Equilibrium...

Re: Traffic Prediction with Advanced Graph Neural Networks

#15

Post by filleokus »

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…

I think that modelling is to simplistic. Travel time is often times dependent on traffic load, with a stark discontinuity reaching 100% (stop and go traffic).

Consider a contrived example of two similar bridges gapping some body of water. Bridge A is fed by a major highway, Bridge B is downstream a couple of miles and connected to the highway on both sides. For most drivers, if there are no other cars on the road, the preferred route is Bridge A.

The global optimum would be to divert some percentage of highway traffic to Bridge B, _before_ we saturate Bridge A. But for each individual on the highway this would mean a detour and would prefer someone else to take Bridge B.

Re: Traffic Prediction with Advanced Graph Neural Networks

#16

Post by layoutIfNeeded »

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…

That's definitely not how it works. Traffic is a nonlinear dynamical system with all sorts of non-intuitive coupling between various components.

Re: Traffic Prediction with Advanced Graph Neural Networks

#17

Post by symplee »

Is it just me, or is it a little disingenuous to write the claim "...improve the accuracy of real time ETAs by up to 50% in places like Berlin, Jakarta, São Paulo, Sydney, Tokyo, and Washington D.C."

When the actual numbers listed for those cities are:

  Berlin - 21%
  Jakarta - 22%
  São Paulo - 23%
  Sydney - 43%
  Tokyo - not listed
  Washington D.C. - 29%

Re: Traffic Prediction with Advanced Graph Neural Networks

#18

Post by cik2e »

layoutIfNeeded wrote: post #16
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…

That's definitely not how it works. Traffic is a nonlinear dynamical system with all sorts of non-intuitive coupling between various components.

In some cases that’s exactly how it works. There’s a four way stop on a major commuter route where I live. Most of the traffic passes through it in a straight line and there is a major build up, like 20-30 min long during rush hour. In one direction there is a side road that loops around off the main road for about 2 miles in a big U and joins back up again at that 4-way stop. Before Waze became popular you could shoot around this bypass and be the only car on that side of the stop sign. Now there is a pretty significant amount of traffic there every rush hour thanks to the GPS apps. Lowell road and Barnes Hill road in Concord, MA for anyone curious.

Re: Traffic Prediction with Advanced Graph Neural Networks

#19

Post by CyberDildonics »

layoutIfNeeded wrote: post #16
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…

That's definitely not how it works. Traffic is a nonlinear dynamical system with all sorts of non-intuitive coupling between various components.

What's the difference between a dynamic system and a dynamical system?

Re: Traffic Prediction with Advanced Graph Neural Networks

#20

Post by cmehdy »

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…

There's a likely future for someone boarding self-driving equipment: higher-quality (of car, traffic conditions, wait, etc) depending on price. And public transit with dedicated/prioritized lanes (by law).
Post reply on HN