7 ms·

Traffic Prediction with Advanced Graph Neural Networks

222 points by beefman 6y ago

ericls 6y ago
I think in addition to predict traffic jam for individuals, this can be used to adaptively control traffic lights and open/close lanes to reduce traffic jam for the whole system.
Barrin92 6y ago
related question, is there actual open source data available for traffic or other kinds of urban movement for people to toy around with?
- MR4D 6y ago
  Houston has some. I’m on my iPhone so I can’t browse the data, but XML and JSON can be found here. https://traffic.houstontranstar.org/datafeed/datafeed_info.aspx https://traffic.houstontranstar.org/datafeed/datafeed_info.a...
- patagurbon 6y ago
  Uber has some data, I don't recall if it's traffic or some proxy of it like travel time.
2bitencryption 6y ago
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 experience for the conglomerate of all cars on the road? Should Google Maps route several cars through a suboptimal route, if it results in traffic as a whole becoming better? If Google Maps is "greedy" for every driver, can that make a traffic problem worse? In reality, I guess this problem is more hypothetical than real, at least today. But imagine this: in 30 years, if all cars are self-driving and self-navigating via systems like Google Maps, what is the system optimizing for? edit: there's also Braess's paradox. I'm not sure if it applies here, but perhaps it does -- could "sending some users down a new route during heavy traffic" be identical to "adding a road to a network", which can therefore result in the paradox (worse network conditions for everyone)? https://en.wikipedia.org/wiki/Braess%27s_paradox https://en.wikipedia.org/wiki/Braess%27s_paradox
- ocdtrekkie 6y ago
  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 both routes, as both routes have roughly equalized in performance. In theory.
  - wardrop 6y ago
    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_assignment https://en.m.wikipedia.org/wiki/Route_assignment#Equilibrium...
- paxys 6y ago
  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 the two balance out and the app will stop the suggestion. Even though it helped only some individual users, the end result is a 50/50 split, so good for everyone.
  - cgriswald 6y ago
    That's how it theoretically works as a free service where all users are equal. It's not difficult to image a tiered subscription model which finds a sub-optimal 70/30 split more profitable. It's also important to note it's optimizing for time, not fuel usage (a shorter path may require expensive elevation changes, for instance), traffic noise for neighborhoods, safety, services access, etc.
usernamebacano 6y ago
bueda fixe pa!
deleted 6y ago
[deleted]
symplee 6y ago
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%
- datameta 6y ago
  It gets even more muddled when you consider they mention the following: "While Google Maps’ predictive ETAs have been consistently accurate for over 97% of trips, we worked with the team to minimise the remaining inaccuracies even further - sometimes by more than 50% in cities like Taichung." Are they essentially saying that they lowered 3% inaccuracy to ~1.5% in Taichung? (And nevermind the fact that 51% is described as "more than 50%"...) Of course this type of work is fascinating. Getting from 97 to 98.5% accuracy is far far more difficult than getting from 95.5 to 97%. But I don't enjoy the fudging of the perception of results.
  - boloust 6y ago
    It could mean that 97% of the trips had an predictive error of, say, 2 minutes, while the remaining 3% had an error of, say, 10 minutes, and they reduced that error to 5 minutes.
GistNoesis 6y ago
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.
WalterBright 6y ago
They can't even time the traffic lights correctly around here.
jastingo 6y ago
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.
thx4dafish 6y ago
Just have to point out that there is absolutely a difference between user and system optimal, even outside of Braess Paradox situations. If you’ve never noticed it, it’s because traffic engineers worked hard to mitigate it.

222 points by beefman 6y ago

I think in addition to predict traffic jam for individuals, this can be used to adaptively control traffic lights and open/close lanes to reduce traffic jam for the whole system.

Barrin92 6y ago

related question, is there actual open source data available for traffic or other kinds of urban movement for people to toy around with?

MR4D 6y ago
Houston has some. I’m on my iPhone so I can’t browse the data, but XML and JSON can be found here. https://traffic.houstontranstar.org/datafeed/datafeed_info.aspx https://traffic.houstontranstar.org/datafeed/datafeed_info.a...
patagurbon 6y ago
Uber has some data, I don't recall if it's traffic or some proxy of it like travel time.

2bitencryption 6y ago

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 experience for the conglomerate of all cars on the road? Should Google Maps route several cars through a suboptimal route, if it results in traffic as a whole becoming better? If Google Maps is "greedy" for every driver, can that make a traffic problem worse? In reality, I guess this problem is more hypothetical than real, at least today. But imagine this: in 30 years, if all cars are self-driving and self-navigating via systems like Google Maps, what is the system optimizing for? edit: there's also Braess's paradox. I'm not sure if it applies here, but perhaps it does -- could "sending some users down a new route during heavy traffic" be identical to "adding a road to a network", which can therefore result in the paradox (worse network conditions for everyone)? https://en.wikipedia.org/wiki/Braess%27s_paradox https://en.wikipedia.org/wiki/Braess%27s_paradox

ocdtrekkie 6y ago
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 both routes, as both routes have roughly equalized in performance. In theory.
- wardrop 6y ago
  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_assignment https://en.m.wikipedia.org/wiki/Route_assignment#Equilibrium...
paxys 6y ago
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 the two balance out and the app will stop the suggestion. Even though it helped only some individual users, the end result is a 50/50 split, so good for everyone.
- cgriswald 6y ago
  That's how it theoretically works as a free service where all users are equal. It's not difficult to image a tiered subscription model which finds a sub-optimal 70/30 split more profitable. It's also important to note it's optimizing for time, not fuel usage (a shorter path may require expensive elevation changes, for instance), traffic noise for neighborhoods, safety, services access, etc.

usernamebacano 6y ago

bueda fixe pa!

deleted 6y ago

[deleted]

symplee 6y ago

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%

datameta 6y ago
It gets even more muddled when you consider they mention the following: "While Google Maps’ predictive ETAs have been consistently accurate for over 97% of trips, we worked with the team to minimise the remaining inaccuracies even further - sometimes by more than 50% in cities like Taichung." Are they essentially saying that they lowered 3% inaccuracy to ~1.5% in Taichung? (And nevermind the fact that 51% is described as "more than 50%"...) Of course this type of work is fascinating. Getting from 97 to 98.5% accuracy is far far more difficult than getting from 95.5 to 97%. But I don't enjoy the fudging of the perception of results.
- boloust 6y ago
  It could mean that 97% of the trips had an predictive error of, say, 2 minutes, while the remaining 3% had an error of, say, 10 minutes, and they reduced that error to 5 minutes.

GistNoesis 6y ago

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.

WalterBright 6y ago

They can't even time the traffic lights correctly around here.

jastingo 6y ago

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.

thx4dafish 6y ago

Just have to point out that there is absolutely a difference between user and system optimal, even outside of Braess Paradox situations. If you’ve never noticed it, it’s because traffic engineers worked hard to mitigate it.