There’s a Map for That

    Looking down and across the San Francisco Bay from the Berkeley hills during the evening rush hour, one sees an umbilicus of traffic – amber headlights on the left, ruby taillights on the right – stretching across the Bay Bridge, connecting the gridded East Bay streets to the skyline of San Francisco. A traffic engineer admiring this scene might ask: “Where are all these people going?” “Is traffic this bad everyday?” or “How can we make it flow faster and more efficiently?” Increasingly, the need for real-world solutions to traffic problems requires transcribing this bird’s-eye view of traffic information into actual hard data on a computer. This task requires ubiquitous technology allowing individuals to transmit information about their environment, as well as the computational power to amass and analyze this data at break-neck speeds. Today, UC Berkeley researchers are merging the fields of civil engineering and information technology to bridge these information gaps between the traffic models on their computers and the drivers and control systems on the ground.
    Real-time traffic information is a valuable commodity. For over 40 years, the major source of traffic information for the California Department of Transportation (Caltrans) has been loop detectors. These are the thick cables embedded as a circle or hexagon in the asphalt of highway lanes and are also commonly used to detect whether cars are stopped at stoplights. Historically, Caltrans invested in loop detectors because they report the three main pieces of information – traffic speed, volume, and occupancy – necessary for generating a complete picture of highway conditions.  However, loop detectors are expensive to build, highly sensitive, and difficult to maintain, requiring Caltrans to shut down whole lanes of traffic if an array of detectors goes haywire. As California state budgets continue to shrink, Caltrans is looking for cheaper and more effectives alternatives for gathering traffic information.

    One such alternative is now available in the form of Global Positioning System (GPS) data from mobile devices. GPS data from the smartphone in your pocket and navigation devices on your dashboard may revolutionize how Caltrans and UC Berkeley researchers track travel behavior and design transportation infrastructure.

    Integration of mobile technologies into traffic monitoring and planning is a problem that sits at the intersection of academic research and the public and private sectors.  The California Center for Innovative Transportation (CCIT) was started to attack precisely this kind of problem by taking an innovative approach to the significant scientific, business and deployment challenges it presents. A non-profit affiliate of the UC Berkeley Institute of Transportation Studies, CCIT works to bring cutting edge research from UC Berkeley outside the ivory tower to make transportation systems safer, cleaner and more efficient: in a word, more sustainable.

    The mobile solution

    Fast forward to February 2008. One hundred cars driven by UC Berkeley students roll onto a 10-mile stretch of I-880 between Hayward and Fremont, California. Each car is identified by a tarp taped to its hood numbering between 00 and 99 and carries in it a GPS-equipped Nokia cell phone. For the next eight hours, these intrepid students drive in loops on the I-880 while their cell phones transmit GPS coordinates back to a server at UC Berkeley.

    Credit: Gregory Thomas

    Dubbed Mobile Century, this mass joyride was sponsored by Caltrans and involved CCIT, Nokia, and the UC Berkeley Civil and Environmental Engineering department. Mobile Century sought to demonstrate that cell phone-based GPS data could be used to accurately estimate traffic speed and trip duration in real time. While other researchers had deployed this technology in highly controlled experiments, the Mobile Century experiment tested this concept in real-world traffic conditions for the first time.

    Traffic engineers are giddy about the rise of GPS-equipped mobile devices.  As Professor Alex Bayen, who is jointly appointed in the Department of Electrical Engineering and Computer Science and the Department of Civil Engineering, explained enthusiastically in a recent interview, “the big novelty in 2009 was that every cell phone,” (waving at the iPhone I’m using to record our interview and the Android phone he pulls out of his pocket), “suddenly had a GPS, and that created an explosion of data. That opened a big opportunity for transportation because suddenly you could do monitoring in places where you don’t have dedicated infrastructure.”

    That explosion of data could potentially be harnessed as a cheap and widely available data source for use in traffic monitoring, control and planning. For Caltrans and traffic engineers everywhere, Mobile Century was a scientific leap forward. It demonstrated that it was possible to build algorithms and data infrastructure to process cell phone GPS data in real time, and that these estimates of traffic conditions were accurate and reliable. Following Mobile Century, the next crucial question became: how do we capture more of the valuable GPS data riding around in everyone’s pocket?

    As it turns out, there’s an app for that. Mobile Millennium – the next generation real-world experiment that emerged from Mobile Century – rolled out in November 2008.  Rather than providing drivers with a particular cell phone, UC Berkeley researchers – with the help of Navteq, a location-based services company – rolled out a traffic application that drivers could download from the Mobile Millennium website. (This was before the iPhone App Store, by the way.) Mobile Millennium had two goals. The first was to incorporate GPS data reported by cell phones, as well as historical data, GPS from San Francisco’s taxi cabs, and data from existing radar and loop detector infrastructure into a complex traffic model to monitor traffic conditions on both highways and arterial streets.  The second was to report this traffic information back to users. This app – the first traffic app deployed by Nokia in North America – was downloaded from the Mobile Millennium website by over 5000 users during the twelve months of the experiment.

    Developing a new market

    Mobile Millennium, in principle, served as a proof of concept for a traffic information product to help consumers plan their commutes using real-time traffic information. This idea has now been replicated, implemented and marketed by a number of companies, including among others, Navteq, Traffic.com and Google Traffic. The success of the latter, however, has driven the consumer-product based business model to extinction. “It is hard to sell a free commodity,” Professor Bayen quipped. “Because some websites give it for free, the market of travel information has dramatically shrunk in recent years.” Yet, in the face of Google’s grip on the traffic monitoring market, an innovative new business model is emerging from the Mobile Millennium research thanks to a continued collaboration between Caltrans and CCIT.

    The CCIT office sits on the third floor of the former Masonic Temple in Berkeley, at the corner of Bancroft and Shattuck. It is a beautiful building, with a stained glass window of a mason’s compass and square above the entrance. The day I met Ali Mortazavi, program manager of the deployment and innovation team at CCIT, there was a blue Corvette convertible parked out front – a gas guzzling eight-cylinder sports car with leather bucket seats. Surprised, having assumed that the CCIT staff would be a more eco-friendly bunch, I asked Mortazavi whether it belonged to someone inside. He reassured me that it didn’t – and that he himself commuted to work in a fuel efficient four-cylinder Hyundai.

    Credit: Marek Jakubowski

    Caltrans and researchers at CCIT are very interested in using mobile probe data collected from GPS-enabled phones and other dashboard GPS units. Currently, however, loop detectors are the only technology that provide all three crucial pieces of traffic data – occupancy, volume and speed – needed by CalTrans’ traffic models. “Right now Caltrans installs sensors every half a mile,” says Mortazavi. “Now imagine you install sensors every mile or two miles, and fill in the gaps with [GPS] data. That would be a huge cost reduction.” Furthermore, rather than kicking out all of the existing traffic monitoring infrastructure, he says, while gesturing with both hands to sweep the doomed loop detectors off the table, CCIT and Caltrans are taking an incremental approach to assessing the added value of GPS data purchased from third party vendors.

    The available GPS data is a heterogeneous mix, coming from mobile consumer devices, GPS in commercial fleets (such as buses, trucks and taxicabs), the San Francisco Bay area’s electronic toll collection system, FasTrak Ò, and radar. CCIT and Caltrans want to figure out whether the information they are collecting might allow them to decrease the number of loop detectors to install and maintain. In addition to the scientific work of building traffic models, Mortazavi and CCIT are also working on each step on the business side of deploying this cutting-edge technology, from designing the data specs, writing the terms and conditions of data contracts and procuring the data. Mortazavi says, “We’re trying to create a win-win situation for both Caltrans, who would like to provide something beneficial for the public, and the private sector, who are looking for more profit.”

    There are also significant scientific challenges once traffic data is acquired. There are different errors associated with various measurement devices, and orthogonal types of information available from each technology. For example, one task for the algorithms being developed in Professor Alex Bayen’s lab is to fuse count and volume data from loop detectors with speed data from cell phone GPS. The end goal is to leverage both types of information to get a better estimate of traffic density. The problem is, Mortazavi explains, “it’s really easy to blend speed from different sources, but it’s really difficult to mix different data types, for example, volume and speed.” This challenge is now being tackled in Professor Bayen’s lab, using what Mortazavi calls “fusion algorithms” for the different data types and in the traffic models that use this data to generate a real-time traffic map.

    So far, it seems like the algorithms and models work pretty well. I dropped by post-doc Anthony Patire’s cubicle at CCIT to have a closer look at these traffic models. He has been at CCIT for less than a year, after getting his PhD in Civil and Environmental Engineering at UC Berkeley. Patire clearly keeps busy: the walls of his cubicle are lined with cryptic, albeit neatly organized, labels headlining different projects, such as “MM” (that would be Mobile Millennium), “FHWA,” “T01702”, as well as other titles like “Random” and “Fun Stuff.” His workstation is composed of two computer screens aglow with computer code and a groaning bookshelf that carries hefty titles such as “Stochastic Processes” and “Non-linear Programming.”

    Patire pulls up what looks like a Google Maps based web application to show me the Mobile Millennium traffic models running in real time.  “The purpose here is to take real time data, run it through a model, and use the model to fill in gaps where we have no data,” he explains. “The model’s not perfect. Sometimes, it’ll predict something that’s just a little bit off. For those places that we have measurements, we can get it back on track.” In other words, the model is able to reflect traffic conditions in real time using a combination of real data and computer modeling. As Patire reports, “You would see a traffic jam form [in the Mobile Millenium app], and it could be 15 minutes until it is posted on other traffic monitoring websites.”

    Noon on Wednesday looks like a good time to head into San Francisco – the real-time traffic map he pulls up shows all the major highways and arterial streets highlighted in a “happy traffic” green. In fact, it looks very much like the map you would see if you clicked the current traffic conditions button on Google Maps  – the Mobile Millennium map looks equally well connected and the coverage is quite extensive.

    Moving forward

    The Mobile Millennium real-time maps are not yet available online to the public, but can be seen on display in the lobby of the Sutardja Dai Hall on UC Berkeley’s campus. This building houses CITRIS, the Center for Information Technology Research in the Interest of Society, whose mission it is to “`shorten the pipeline’ between world-class laboratory research and the creation of start-ups, larger companies, and whole industries.” Inside the lobby of the CITRIS building, there is a touch-screen TV, displaying the Mobile Millennium traffic map. Patire suggests Friday afternoons are the best time for watching the Bay Area traffic mayhem.

    The data algorithms and infrastructure developed in Mobile Millennium are now being used in Professor Bayen’s lab at CITRIS to develop next-generation traffic routers. Bayen describes how traffic routers currently fall into four generations of ascending sophistication: “zero notion of traffic, historical traffic, now traffic and future traffic.”

    Bayen explains: “Let’s say you want to go from Berkeley to Mountain View. The simplest router is going to give you a route based on shortest travel time, based on posted speed limit. Because it’s smart, it’s not going to route you through the tiny roads, even though it might be faster on the map. It’s not, because of stop signs and pedestrians. In practice it’s going to route you by the shortest time through the freeway system, when it can. That doesn’t take into account traffic. The [second generation] routers account for historical traffic data – [it tells you,] don’t count on 20 minutes between San Mateo and the Dumbarton Bridge, you should count on 30 minutes.”

    Credit: Eric Fischer

    But what if there is an accident on the Dumbarton Bridge? Third generation routers will incorporate real-time traffic information to optimize your route. Bayen says, “You look at traffic now…and actually there is no traffic today, even though it’s 6 o’clock. Since there is no traffic, you’ll still use this freeway.”

    Bayen’s master’s student Paul Borokhov is working precisely on this problem of the third-generation router. Borokhov met me at CCIT, out of breath with a bike helmet in hand. Borokhov is developing a smartphone app, tentatively titled the “Reliable Router,” that will use real-time traffic data to suggest routes that would maximize the probability of reaching a destination on time. For drivers, getting to a destination on time may be more important than getting there along a shorter, or nominally faster, route that also comes with a high probability of lengthy delays.

    The “Reliable Router” algorithm works by creating a network of alternative routes between point A and point B. It then uses real-time traffic information from the Mobile Millenium traffic monitoring server to estimate the probability of arriving at your destination on time for each alternative route. In order for the “Reliable Router” algorithm to produce the best possible route, the algorithm cannot give the full set of directions to your destination at the outset. Instead, the app gives a set of guidelines that update themselves as you drive. As you come to a node leading to alternative routes in the network, the algorithm chooses the best next segment for your route based on the time remaining to travel to your destination and the updated traffic conditions along the alternative routes.

    The instantaneously updated traffic directions in “Reliable Router” led Borokhov to develop a method for giving audio directions on the fly. Borokhov explains, “When you’re driving, looking at street names is difficult. You have to figure out where the sign is, read the sign, remember which street you’re supposed to turn on, and then you’ve already passed the street because you’re driving 45mph…The innovative thing is that we can tell people, `go right on the second street’, and it takes care of the problem of needing to know street names. You also minimize driver distractions because these are audio directions.”

    I asked Borokhov whether this app could be used to optimize for routes that minimized fuel consumption. He speculated that it could be done with a few modifications. For each link in the network, one could estimate the amount of fuel consumed along a given route based on the current traffic conditions, and then optimize the route for fuel efficiency. However, Borokhov cautioned that to generate an accurate environmental impact estimate, one would have to avoid making overly simplistic assumptions about the vehicle and its rate of fuel consumption. By integrating robust models of vehicle emissions and real-time travel data, future travel behavior models developed at CCIT and CITRIS may be able to enable unprecedented minimization of environmental impact for regional transportation networks.

    Building this integrated network of multimodal transportation information poses the next significant challenge for traffic modeling algorithms. The use of data from mobile technologies – which can give granular information down to the level of individual people and their movements – will provide both the scaffolding and the substance for these algorithms as they enable the next level of interaction with our transportation system.

    From linear highways to transportation networks

    Researchers like Anthony Patire and Alex Bayen can no longer regard highways as linear systems largely disconnected from surface streets. While the earliest models, like the one used in Mobile Century, focused on highways, the next generation of traffic models must also address improving mobility in the arterial streets that feed these highways. As Ali Mortazavi at CCIT says,

    “You cannot draw a boundary here on the highway and not care about what’s happening in the arterials. Everything is connected. If you mess up something in one corridor, you’ll affect everything in the network. If something happens along 101 and you shut down the whole stretch and people only have the 92, that’ll affect the 880 … In urban areas, the congestion is high and if you shut down one thing you’ll affect everything.”

    This network approach will be a significant scientific challenge. “The highway is easily mapped [using GPS] because it’s easy to when see someone is driving 60 miles an hour,” explains Mortazavi. “Now you have a lot more parameters. You have people walking outside and inside buildings, and people stopping at traffic signals. That’s another challenge and it’s exciting.”

    Future directions

    Today’s transportation systems are complex networks populated by multimodal users. Everyone I interviewed for this article had a different way of getting to work – biking, driving, taking the commuter rail – showing just how many parameters the traffic engineer of the near future will have to account for in models of traffic network control and planning.

    Real-time traffic information and mobile technologies could potentially nudge commuters towards more sustainable modes of transportation. Given its eco-conscious and multi-modal workforce, CCIT is cognizant that traffic congestion cannot be solved by only better monitoring and upgrading roadway infrastructure.  Travel behavior itself must change.

    Fortunately, Caltrans is also increasingly in the business of influencing driver behavior, by giving real-time information on traffic congestion to help drivers predict travel time, plan alternate routes, or even choose to take public transit instead of using their vehicles.  Caltrans and CCIT are already active in pursuing this line of thought in a project you have probably seen on highways around the bay area – the deployment of the black and orange Changeable Message Signs (CMS) that give, for example, rush hour travel times from Berkeley to Downtown San Francisco.  CCIT has recently partnered with Caltrain – the commuter rail between San Jose and San Francisco – to add public transit information to these signs. During rush hour, signs along Highway 101 now compare drive times with riding Caltrain to work, as a nudge to drivers to choose public transit for their commute. In addition, CCIT is currently developing another mobile app in collaboration with IBM, called “Smarter Traveler,” that will push commuters to take transit, walk or bike even before they get into their autos. Combined with the vertically integrated, palm-of-your-hand transportation data in applications like Mobile Millennium and Google Maps, this top-down approach to transportation communication aims to empower commuters with an incredible range of options to optimize their preferred mode of transportation.

    With these systems in development, the focus now shifts to the way commuters will actually interact with the information with which they are presented.  Will commuters optimize travel time or greenhouse gas emissions? Are drivers worried about fuel consumption or more subjective concerns like how relaxing, safe or scenic their commute can be? By intersecting sustainability, technology and transportation and information, UC Berkeley researchers are giving us, and the statewide agencies that set transportation policy, the tools and knowledge to start answering these questions and to use these answers to improve our daily lives.

    Leave a Reply