<story><title>Traffic Prediction with Advanced Graph Neural Networks</title><url>https://deepmind.com/blog/article/traffic-prediction-with-advanced-graph-neural-networks</url></story><parent_chain><item><author>2bitencryption</author><text>Google Map&amp;#x27;s traffic prediction has always led me to a very curious question:&lt;p&gt;Clearly Google Maps has the ability to turn into a feedback loop. Traffic exists -&amp;gt; people use Google Maps to find better routes -&amp;gt; traffic is modified due to people taking alternate routes -&amp;gt; new traffic emerges.&lt;p&gt;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?&lt;p&gt;Should Google Maps route several cars through a suboptimal route, if it results in traffic as a whole becoming better?&lt;p&gt;If Google Maps is &amp;quot;greedy&amp;quot; for every driver, can that make a traffic problem worse?&lt;p&gt;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?&lt;p&gt;edit: there&amp;#x27;s also Braess&amp;#x27;s paradox. I&amp;#x27;m not sure if it applies here, but perhaps it does -- could &amp;quot;sending some users down a new route during heavy traffic&amp;quot; be identical to  &amp;quot;adding a road to a network&amp;quot;, which can therefore result in the paradox (worse network conditions for everyone)?&lt;p&gt;&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Braess%27s_paradox&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Braess%27s_paradox&lt;/a&gt;</text></item></parent_chain><comment><author>adanto6840</author><text>It&amp;#x27;s a good question, even if it&amp;#x27;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&amp;#x27;s now working at DeepMind last I looked).&lt;p&gt;WHCA* turned out to be a bit too suboptimal for our use-case, people generally expected &amp;quot;perfectly optimal&amp;quot; routes to be used for aircraft, and they weren&amp;#x27;t even overly happy with most-optimal &amp;quot;for-all&amp;quot; paths either.  We eventually implemented a relatively simple &amp;quot;AStar-3D&amp;quot;, essentially just A* against a space-time graph, and it&amp;#x27;s greedy&amp;#x2F;FIFO -- meaning it&amp;#x27;s optimal for each aircraft at the time the aircraft runs it&amp;#x27;s path.  That made people happy -- aircraft no longer did seemingly stupid things like &amp;quot;oscillate&amp;quot;, or get &amp;quot;temp. stuck&amp;quot; for overly long periods, etc.&lt;p&gt;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&amp;#x27;s when you even have perfect information!  Such a cool domain, tons of respect for the work that&amp;#x27;s being done here, even if there are some tricky&amp;#x2F;ethical aspects that are going to come into play eventually, inevitably.  :)&lt;p&gt;0 - &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.aaai.org&amp;#x2F;Papers&amp;#x2F;AIIDE&amp;#x2F;2005&amp;#x2F;AIIDE05-020.pdf&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.aaai.org&amp;#x2F;Papers&amp;#x2F;AIIDE&amp;#x2F;2005&amp;#x2F;AIIDE05-020.pdf&lt;/a&gt;</text></comment>
<story><title>Traffic Prediction with Advanced Graph Neural Networks</title><url>https://deepmind.com/blog/article/traffic-prediction-with-advanced-graph-neural-networks</url></story><parent_chain><item><author>2bitencryption</author><text>Google Map&amp;#x27;s traffic prediction has always led me to a very curious question:&lt;p&gt;Clearly Google Maps has the ability to turn into a feedback loop. Traffic exists -&amp;gt; people use Google Maps to find better routes -&amp;gt; traffic is modified due to people taking alternate routes -&amp;gt; new traffic emerges.&lt;p&gt;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?&lt;p&gt;Should Google Maps route several cars through a suboptimal route, if it results in traffic as a whole becoming better?&lt;p&gt;If Google Maps is &amp;quot;greedy&amp;quot; for every driver, can that make a traffic problem worse?&lt;p&gt;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?&lt;p&gt;edit: there&amp;#x27;s also Braess&amp;#x27;s paradox. I&amp;#x27;m not sure if it applies here, but perhaps it does -- could &amp;quot;sending some users down a new route during heavy traffic&amp;quot; be identical to  &amp;quot;adding a road to a network&amp;quot;, which can therefore result in the paradox (worse network conditions for everyone)?&lt;p&gt;&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Braess%27s_paradox&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Braess%27s_paradox&lt;/a&gt;</text></item></parent_chain><comment><author>paxys</author><text>When User 3982274 is on a busy road using the app, Google optimizes for that user&amp;#x27;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.&lt;p&gt;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&amp;#x2F;50 split, so good for everyone.</text></comment>