Driverless cars may know how to negotiate intersections and park themselves better than humans, but so far I haven’t read about a smart car that can get me through Silicon Valley faster during rush hour. The problem isn’t with drivers, the problem is with pavement. There just doesn’t seem to be enough roadway to accommodate everyone at the same time. Perhaps the solution lies in data, not just driverless technology.

A truly smart car has to outwit the other smart cars on the road, just as an honor student has to score higher on the SAT than his or her peers. So, in addition to driving itself, the car of the future—what I once called the “Batmobile.car” [1]—will use big data analytics to outsmart traffic. One way to do so, is to aggregate GPS tracking data in the cloud and use predictive analytics to forecast where traffic jams might appear minutes ahead of time. The car of the immediate future is likely to run from the cloud, just like your cell phone.

Data R Us

In 1997 I wrote the car of the future would be an information appliance—what some people today call an “Internet of Things” thing. The scientific community scoffed, because back then most scientists had only heard of the Internet. Few people imagined the convergence of cars and computers that is shaping transportation today. Braden R. Allenby quoted my Scientific American article in a National Academy of Engineering report, saying, “Lewis claimed, perhaps optimistically, that ‘The society of Web cars will be able to get themselves out of traffic jams, avoid bad weather and keep their inhabitants well informed and entertained. With such a huge potential market waiting for manufacturers, Web cars are inevitable. Exactly what form they will take remains to be seen [2].’” In hindsight, my prediction seems naïve and weak. By 2020 automobiles will be much more intelligent than simple self-driving vehicles. For example, they may know where I want to go before I do.

Back in 1997, an early prototype of an Internet-enabled car was able to chart its own course through Los Angeles traffic using primitive GPS navigation [1]—an everyday common feat today. Trials in Los Angeles confirmed shortest-path navigation coupled with traffic congestion data (from sensors embedded in the pavement) reduced congestion as long as a small percentage of automobiles used GPS. But, once the density of GPS-guided cars increased beyond a certain threshold, traffic jams simply moved to the alternate route proposed by identical algorithms running in the GPS-equipped cars.

This made me realize the difference between a smart car and one that simply drives itself is immense. Smart cars process big data, that makes all the difference. It is what makes my car smarter than your honor student. Fortunately, there is a mass of big data already available to cars with smart algorithms onboard. They simply need to access it from the cloud and use smarter algorithms than simple shortest-path.

Specifically, very little is done with the GPS traces produced by GPS-enabled navigation systems embedded in the modern car. Aggregation of these traces from millions of cars every day can reveal useful information at both global and personal levels. Obviously, GPS can track your vehicle and email speeding tickets directly to your gmail.com account, but they can also predict traffic jams, expose hidden traffic dangers, tell the county where the potholes are, and alert motorists of approaching emergency vehicles such as fire engines and ambulances. When projected on the windshield as augmented reality, occupants of the smart car will have full situational awareness. Moreover, your car will know what to do about the shifting situation before you can react.

Shortest distance, nyet. Minimal time, dah.

Consider my commute to the San Francisco Bay Area through the road network shown in Figure 1. Without information about the number of cars ahead of me, I opt for the shortest route between my current point A and my destination point B. I assume everyone else does the same thing. As a consequence, the most traveled road segments become more congested as the number of automobiles entering the network at random intersections increases. The intensity over a 12-hour simulation period is shown in Figure 1a (red links are more traveled than green or gray links, etc.). Interestingly, regardless of your points A and B, nearly everyone finds the same road segments along their shortest paths. Simulation of shortest-distance navigation confirms the result of the 1997 Los Angeles trials.

Now consider what happens when GPS traces are aggregated and a simple predictive algorithm is used to estimate the present and immediate future load on each road segment. With this information, my car can chart a minimum time route instead of a shortest path route. Traffic density changes dynamically over time, so my car must decide which roadway to take at every intersection, using updated data. To do so, my car uses a modified Dijkstra’s shortest time algorithm to decide which roadway to take next. Using posted speed limits and an algorithm that models traffic speed versus number of scheduled cars per mile of road segment, my car can predict how long it takes to travel the next leg of the trip. (Obviously, speed drops as number of cars per mile rises).

Aggregation in the cloud makes it possible to anticipate future traffic jams by recording every car’s intent. That is, all others know my intended route before committing to the next road segment ahead. A first-come-first-served algorithm (with timestamps) is used to schedule every car’s path. When one route schedules too many cars, the next minimum-time route is selected, etc.

The shortest time paths shown in Figure 1b spread vehicular load over more links as indicated by “cooler” colors (green and blue indicates less congestion than yellow and red). Simulation of 5,000, … 100,000 vehicles added at randomly selected intersections, heading toward randomly selected destinations, over a 2-4 hour commuter period of day suggests the following: 1) Shortest time navigation performs four times better than shortest distance, and 2) The shortest-time algorithm gets better as traffic gets worse.

The traffic simulation used to produce the load patterns shown in Figure 1 makes a few assumptions. First, traffic builds up over time, following an S-shaped growth curve. Second, travel times were computed by averaging the minimum and maximum average elapsed times over the S-shaped growth curve (lower loads take less average time). Finally, travel times were assumed to be proportional to number of cars per mile with 60 mph as a cut-off value (no speeding is assumed).

So What?

The solution to traffic congestion may lie partly with big data analytics versus building more roads. But, my point is the driverless car idea is only one of many ideas that may spring from mashing up cars with computers. What other innovations might be discovered when aggregating transportation data in the cloud? Does heavy GPS traces left behind by vacationing tourists tell me the best place to vacation?

References

[1] Lewis, T. www.batmobile.car. Cyberview. Scientific American 277, 1 (July 1997), 38.

[2] Allenby, B. R. The Information Revolution and Sustainability: mutually reinforcing dimensions of the human future. National Academy of Engineering. Information Systems and the Environment. Washington, DC: The National Academies Press, 2001. doi:10.17226/6322