6 ms·

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

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.
- abra529 6y ago
  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 https://en.wikipedia.org/wiki/Braess's_paradox
- filleokus 6y ago
  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.
- 6y ago
rkagerer 6y ago
If drivers discovered Google Maps was intentionally sending them down sub-optimal routes, they'd quickly switch to a different navigator. (Even if the Google way was better for the network overall).
- goodside 6y ago
  Not if the sub-optimal routes happen only intermittently and the extent to which they’re sub-optimal (or whether they’re sub-optimal at all) is difficult to determine. If you take the same route every day you’ll notice when it changes, but who are you to say a one-time detour wasn’t the right decision given what you don’t know about traffic conditions?
adanto6840 6y ago
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 https://www.aaai.org/Papers/AIIDE/2005/AIIDE05-020.pdf
- hackingthenews 6y ago
  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.
cmehdy 6y ago
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).
dqpb 6y ago
I assume at some point Google will just start offering me a list of Pareto efficient activities that maximize the global action-value function, economic nirvana will be achieved for all of humanity, Sergey Brin will ascend beyond the physical plane, and then maybe, hopefully, they can stop serving me ads.
namelosw 6y ago
> in 30 years, if all cars are self-driving and self-navigating via systems like Google Maps, what is the system optimizing for? If most users are connected to the same system, an obvious direction would be optimizing globally - if there are two routes to go, just load balance them. I live in Beijing and the traffic is horrible sometimes. The Uber counterpart Didi mandates the routes, and sometimes counterintuitively nice - it seems to be a detour in a narrow valley but it's faster because there is no traffic jam there. I'm not sure Uber or Didi is doing this already. At the end of the day, if most vehicles' GPS is connected to a single system, while the system is recommending routes to most users. Then it would be possible for the system to optimize for the whole population, rather than being greedy for individuals and create traffic problems.
nur0n 6y ago
People seem to focus on the volume of cars. But traffic is not just a matter of volume but of friction between cars. Reducing the friction (naively) appears to be a simpler problem. You wouldn't even need full self driving, only enough tech for cars to merge/switch lanes without slowing down. Not requiring a central point of control is an additional benefit. The reduction of traffic would be an "emergent" behavior.
scythe 6y ago
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/abstract 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.
nurettin 6y ago
> 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.
SergeAx 6y ago
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.
Recursing 6y ago
Fun short fiction story on how predictive systems whose predictions influence what they might predict might evolve: https://www.lesswrong.com/posts/SwcyMEgLyd4C3Dern/the-parable-of-predict-o-matic 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
mwc 6y ago
This is how Uber matches trips[0]. Optimising not for the fastest pick up for any one rider, but to reduce the total time of arrival in the whole network. [0] http://blogs.cornell.edu/info2040/2019/10/23/uber-ride-sharing-a-matching-market/ http://blogs.cornell.edu/info2040/2019/10/23/uber-ride-shari...
lr4444lr 6y ago
Doesn't that already happen as a corollary of a greedy per user optimization? Each marginal car on the best course slows down the traffic, ergo weighting it slightly lower vs. alternatives. Isn't GMaps just filling out the best routes first?

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.
abra529 6y ago
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 https://en.wikipedia.org/wiki/Braess's_paradox
filleokus 6y ago
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.
6y ago

rkagerer 6y ago

If drivers discovered Google Maps was intentionally sending them down sub-optimal routes, they'd quickly switch to a different navigator. (Even if the Google way was better for the network overall).

goodside 6y ago
Not if the sub-optimal routes happen only intermittently and the extent to which they’re sub-optimal (or whether they’re sub-optimal at all) is difficult to determine. If you take the same route every day you’ll notice when it changes, but who are you to say a one-time detour wasn’t the right decision given what you don’t know about traffic conditions?

adanto6840 6y ago

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 https://www.aaai.org/Papers/AIIDE/2005/AIIDE05-020.pdf

hackingthenews 6y ago
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.

cmehdy 6y ago

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).

dqpb 6y ago

I assume at some point Google will just start offering me a list of Pareto efficient activities that maximize the global action-value function, economic nirvana will be achieved for all of humanity, Sergey Brin will ascend beyond the physical plane, and then maybe, hopefully, they can stop serving me ads.

namelosw 6y ago

> in 30 years, if all cars are self-driving and self-navigating via systems like Google Maps, what is the system optimizing for? If most users are connected to the same system, an obvious direction would be optimizing globally - if there are two routes to go, just load balance them. I live in Beijing and the traffic is horrible sometimes. The Uber counterpart Didi mandates the routes, and sometimes counterintuitively nice - it seems to be a detour in a narrow valley but it's faster because there is no traffic jam there. I'm not sure Uber or Didi is doing this already. At the end of the day, if most vehicles' GPS is connected to a single system, while the system is recommending routes to most users. Then it would be possible for the system to optimize for the whole population, rather than being greedy for individuals and create traffic problems.

nur0n 6y ago

People seem to focus on the volume of cars. But traffic is not just a matter of volume but of friction between cars. Reducing the friction (naively) appears to be a simpler problem. You wouldn't even need full self driving, only enough tech for cars to merge/switch lanes without slowing down. Not requiring a central point of control is an additional benefit. The reduction of traffic would be an "emergent" behavior.

scythe 6y ago

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/abstract 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.

nurettin 6y ago

> 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.

SergeAx 6y ago

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.

Recursing 6y ago

Fun short fiction story on how predictive systems whose predictions influence what they might predict might evolve: https://www.lesswrong.com/posts/SwcyMEgLyd4C3Dern/the-parable-of-predict-o-matic 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

mwc 6y ago

This is how Uber matches trips[0]. Optimising not for the fastest pick up for any one rider, but to reduce the total time of arrival in the whole network. [0] http://blogs.cornell.edu/info2040/2019/10/23/uber-ride-sharing-a-matching-market/ http://blogs.cornell.edu/info2040/2019/10/23/uber-ride-shari...

lr4444lr 6y ago

Doesn't that already happen as a corollary of a greedy per user optimization? Each marginal car on the best course slows down the traffic, ergo weighting it slightly lower vs. alternatives. Isn't GMaps just filling out the best routes first?