By

  1. David Wilkie
  2. Jur van den Berg
  3. Ming C. Lin
  4. Dinesh Manocha

In the proceedings of AAAI 2011 and SPARK 2013.

One of the most ubiquitous AI applications is vehicle route planning. While state-of-the-art systems take into account current traffic conditions or historic traffic data, current planning approaches ignore the impact of their own plans on the future traffic conditions. We present a novel algorithm for self-aware route planning that uses the routes it plans for current vehicle traffic to more accurately predict future traffic conditions for subsequent cars. Our planner uses a roadmap with stochastic, time-varying traffic densities that are defined by a combination of historical data and the densities predicted by the planned routes for the cars ahead of the current traffic. We have applied our algorithm to large-scale traffic route planning, and demonstrated that our self-aware route planner can more accurately predict future traffic conditions, which results in a reduction of the travel time for those vehicles that use our algorithm.

Discussion


We address the problem that arises when a large percentage of cars all use a traffic routing system, especially a traffic routing system that takes into account the traffic conditions.

Currently, a small percentage of cars use routing systems. If a routing system is aware of congestion on part of the road network, it can route around that congestion.


However, if a large percentage of the cars are using a routing system, then the routing system may route all the cars around the current congested region of the road network, and in doing so create congestion elsewhere.


To address this issue, we work with a representation of traffic that is time-varying and stochastic. Here, we have distributions that represent the density of traffic on individual road linkages.


When our system routes a car, we predict the trajectory of that car and estimate its impact on the underlying traffic state.

To understand just how this update is made, please see the paper below.


Using our method and a traffic simulation validation, we see a significant speed up over other routing techniques.

Full Paper Download

Paper (PDF)

Acknowledgement