Using machine learning to build maps that give smarter driving advice

If you drive in the United States, chances are you can't remember the last time you bought a paper map, printed out a digital map, or even stopped to ask for directions. Thanks to Global Positioning System (GPS) and the mobile mapping apps on our smartphones and their real-time routing advice, navigation is a solved problem.

But in developing or fast-growing parts of the world, not so much. If you live in a place like Doha, Qatar, where the length of the road network has tripled over the last five years, commercial mapping services from Google, Apple, Bing, or other providers simply can't keep up with the pace of infrastructure change.

Each one of us who grew up in Europe or the US probably cannot understand the scale at which these cities grow," says Rade Stanojevic, a senior scientist at the Qatar Computing Research Institute (QCRI), part of Hamad Bin Khalifa University, a Qatar Foundation university, in Doha. Pretty much every neighborhood sees a new underpass, new overpass, new large highway being added every couple of months."

As Qatar copes with this rapid growth-and especially as it prepares to host the FIFA World Cup in 2022-the bad routing advice and accumulating travel delays from outdated digital maps is increasingly costly. That's why Stanojevic and colleagues at QCRI decided to try applying machine learning to the problem.

A road network can be interpreted as a giant graph in which every intersection is a node and every road is an edge, says Stanojevic, whose specialty is network economics. Road segments can have both static characteristics, such as the designated speed limit, and dynamic characteristics, such as rush-hour congestion. To see where traffic really is going-rather than where an old map says it should go-and then predict the best routes through an ever-changing maze, all a machine-learning model would need is lots of up-to-data data on both the static and dynamic factors. Fortunately enough, modern vehicle fleets have these monitoring systems that produce quite a lot of data," says Stanojevic.

Stanojevic is talking about taxis. His team at QCRI partnered with a Doha-based taxi company called Karwa to collect full GPS data on their vehicles' comings and goings. They used that data to build a new mapping service called QARTA that offers routing advice to drivers at Karwa and other operators such as delivery fleets.

Stanojevic says QARTA's deeper understanding of the actual road and traffic situation in Doha helps drivers shave tens of seconds off every trip, which translates into a fleet-wide efficiency gain of 5% to 10%. If you're running a fleet of 3,000 cars, 5% of that is 150 cars," Stanojevic says. You can basically remove 150 cars from the road and not lose any business."

Although QCRI's system probably can't compete with the big map-services providers in the developed world, it could help cities in the Middle East and other developing regions manage growth more wisely, Stanojevic says. And a few years from now, as more autonomous vehicles take to the streets, machine-learning-based routing advice could look at the big picture in a busy city and help fleets cut carbon emissions by keeping drivers out of traffic jams. By having some sort of a global view of what's going on in the whole city, autonomous vehicles can actually reroute us to have some sort of global load balancing, to help everyone be better off."

This podcast was produced in partnership with the Qatar Foundation.

Show notes and links

Qatar Computing Research Institute

Traffic Routing in the Ever-Changing City of Doha," Sofiane Abbar, Rade Stanojevic, Shadab Mustafa, and Mohamed Mokbel, Communications of the ACM, April 2021

Full Transcript

Laurel Ruma: From MIT Technology Review, I'm Laurel, and this is Business Lab, the show that helps business leaders make sense of new technologies coming out of the lab and into the marketplace.

Our topic today, better mapping for fast-growing cities. Traffic. Traffic is difficult for all of us, but with an increasing number of vehicles on the roads and congestion, apps that try to calculate the best routes cannot miraculously create shortcuts. But what happens when your country doubles in size in 10 years? New roads, new neighborhoods, new buildings: it's time for a new map.

Two words for you: Automatic mapping.

My guest is Dr. Rade Stanojevic, who is a senior scientist at Qatar Computing Research Institute, part of Hamad Bin Khalifa University, a Qatar Foundation university. Dr. Stanojevic studies computer networks and network economics. Currently he's using graph theory, machine learning, and other techniques to try to build more accurate models of real-world traffic in Doha, Qatar, and other cities.

Before joining QCRI, he spent time as a staff researcher at the Madrid Institute for Advanced Studies Network Institute and Telefonica I&D in Spain.

This episode of Business Lab is produced in association with the Qatar Foundation.

Welcome, Dr. Stanojevic.

Rade Stanojevic: It's great to be with you today, Laurel. Thank you.

Laurel: So lately you've been focusing on a very specific question, which is how to write mapping software that can generate more accurate estimates of the travel time if someone is driving from point A to point B. And anyone who's ever gotten stuck in traffic because they chose the wrong routes can understand why that might be useful. But can you explain why understanding traffic is a network science problem and what insights a network analysis approach can bring?

Rade: So to get an accurate understanding of the problem you just mentioned, how to route from point A to point B, you basically need two things. You need an accurate map and an accurate traffic model on top of that map. And those two problems are both network science and machine learning problems. So if you think about the road network as a network or a graph, this network is basically a list of edges, a list of nodes and a list of edges, where the edge is the road segment. This road segment, what makes this road network and interesting object to study, is the complexity that comes from the characteristics of these edges in the network.

So the characteristics of this road segments, we can split them in two types. One are static characteristics. Those are the things such as speed limit, the number of lanes, the kind of payment, et cetera. And these are the kinds of things that once you get it right, you got it right forever.

On the other hand, there are characteristics of the road network that are more dynamic. So these are the kinds of things that are related to the traffic, the level of congestion, the average speed, that depend on the time of the day, day of the week. Some events that we cannot really anticipate in advance, et cetera. Understanding both the underlying static nature of the road network as well as the dynamic parts that come from the traffic is what makes this whole problem interesting and useful to everyday life, and in particular, the business cases that we'll probably talk a bit later that, that we deal with.

Laurel: Well, speaking of dynamic, Qatar almost doubled in population in just 10 years, and so this creates a huge problem, as new roads and new buildings are constructed and drivers are stuck in traffic, but they had these quickly outdated maps that just became outdated. How did you see this as an opportunity to help those drivers and the cities themselves?

Rade: Oh boy. So each one of us who grew up in Europe or the US probably couldn't or cannot understand the scale at which these cities grow. So in my hometown, which is a city of 200 or 250,000 people, the only real change in the road network infrastructure that happened in the last 20 years since I was a kid was just the one single bridge that was built. However, in the city of Doha, pretty much every neighborhood sees a new underpass, new overpass, new large highway being added every couple of months. So with that kind of speed at which the city grows, the traditional mapping services cannot really keep up with the pace. And that caused a huge surprise for most of us who came from Europe or North America. We were amazed when we arrived in the city and realized that all the services that we take for granted like Google Maps or Bing Maps or Apple Maps, whatever your favorite digital map is, they simply don't work. They don't work in the city of Doha.

And the reason why they don't work is because they were not built on the assumption that the infrastructure changes as rapidly as it does in Doha. So in the Institute, at QCRI, we realized that a lot of these questions can be answered with network science and machine learning. And several of us started looking at the problem of automatic map inference. We started with this sometime in 2017, and we realized that this problem is both incredibly important for a lot of developing cities, but also highly challenging. And we made a lot of progress in that part, in understanding the underlying network. And then later on, we realized how we can add on top of that, these dynamic properties of the map, which are related to the traffic.

Laurel: I think that's a really great way of trying to explain to folks who may not understand a new highway being added or a new access ramp or a new overpass to every neighborhood like that's astounding, right?

Rade: It's astounding. So basically in the last seven years, since 2013, the length of the road infrastructure in the city of Doha tripled. So it's really difficult to actually wrap your head around that number. It's an unbelievable amount of infrastructure that is being built. This is all a part of the project that is targeted to build the appropriate infrastructure for the World Cup that is happening in about 18 months here in Doha, the world cup in football, or as you in North America would say soccer.

Laurel: So then why did the mapmakers like Google, Bing and Apple Maps have such problems keeping up? Like how do they traditionally estimate travel times and mapping? Sending the Google car around to map neighborhoods?

Rade: Actually that's an interesting question. So basically most of the traditional map makers such as Google Maps or Here Maps or Bing Maps, they normally have a static map that they purchase once every couple of years, from either the government or the local map providers. And then they run under the assumption that these maps change every now and then, and that they can catch these changes, observing some sort of data that is available to them, either through tracking the phones where they have some sort of location enabled services, or through some other means. The underlying assumptions that the road networks don't change that frequently. So whenever the road network changes, they would require a human annotator to label the change and update the map. However, in a city like Doha, where changes happen constantly and daily, this underlying assumption is broken.

A major intersection that was changed sometime in 2016, when we moved, when I moved to Doha, just a few hundred meters from our office, it took about 18 months for that intersection to be reflected in Google Maps. So basically that intersection was invisible to Google Maps for about 18 months. And all those routes that should be routed through that intersection, were basically, would force the drivers to go and take a big detour that was totally unnecessary. And Google got better over the years, Google and other map services, they got better over time. They recognize the problem and now it doesn't take them 18 months to reflect the change. Now that process is shortened to couple of months. But still even the couple of months can be a lot if a driver or a taxi or a delivery driver requires an accurate and optimal route. And we saw that as an opportunity to solve the problem with as much data as we could acquire and as quickly as possible.

Laurel: Yeah, a two-month response time seems impossible in everyone's real-time living, right? So how did you actually, you and your team find a better way to estimate travel times? Tell me the story about the taxi company Karwa.

Rade: That's an interesting story, but just let me say a few words on what is the key ingredient in addressing the problem of accurate routes and accurate travel times in the rapidly evolving city as Doha. The key ingredient is constantly updating the maps. So observing the map, observing the changes that happen and addressing them as quickly as possible, ideally in a fully automatic way, is the key. So we wouldn't be able to do so without the partnership with Karwa.

So Karwa is a local taxi company that operates around 3,000 vehicles in the city. It produces a vast amount of information that we utilize to build the underlying map and also to build the traffic model on top of that map. And there is an interesting story on how we kicked off this project. So this project started purely as a research project, as I mentioned, maybe sometime 2017 or early 2018, we had our first meeting with the taxi company. And at that point we made some progress regarding the map services, the automatic map inference project that I mentioned a few minutes ago. But after we shared those initial results with them, what they told us was that they were using Google Maps. They were not a hundred percent happy with that, but the fact that that whole service was relatively cheap, somewhere in the order of magnitude between $10,000 and $20,000 per year, that wasn't a huge item in their annual bill. And they basically told us, we don't really worry about these sorts of problems because we purchase that information is not ideally accurate, but it's cheap enough for us not to worry about it.

And then we agreed with that. It was just, that's how it is. If Google or commercial maps services can sell that for such a low price, it doesn't really make sense for the taxi company to worry much about it. However, Google Maps, and as well, many other map providers, pretty much raised this map API services prices by a factor of 10 to 20 sometime in the late 2018. And at that point with the growth of their volume, their bills grew from tens of thousands of dollars to hundreds of thousands of dollars, pretty much overnight. At that point they were way more receptive to the idea of building the service that can help them shave off a few hundred thousand dollars per year of that map services bill. And at that point, we started looking into the problem. At that point, we couldn't really tell whether we can build a product that has a quality comparable to the commercial maps. And that's where our journey started.

Sometime in late 2018, we already had quite a bit of understanding and experience on how to do these sorts of things. But we actually started working on the product sometime in late 2018, and by middle 2019, we had a product ready for testing. And it took a couple of months of testing to actually figure out how good we are compared to Google Maps. And the findings were really impressive in terms of the quality of our results, in the speed of our responses, in the availability of our resources. And then sometime late in 2019, the local taxi company with 3,000 vehicles switched from the commercial maps, from Google Maps, to using our services.

So it was a rocky road, it took us couple of years of going back and forth. And I would say probably the major step was introduction of this new pricing, the time where Google realized that they can actually monetize on this and where they raised the prices by a factor of 10 to 20, that was a deal breaker for us. Without that we would probably not make this happen.

Laurel: That is an incredibly enormous increase when you are probably a taxi company that may or may not be doing well, depending on how competitive that kind of ride sharing is.

Rade: Exactly, that made a huge deal. So basically taxi businesses in general are very low profit margin businesses. So they care about every little penny they can save.

Laurel: So how do you provide those similar services at lower costs? Is because you don't have the overhead of a Google Map or a Waze?

Rade: So we like to think of our system as a very lightweight Google Maps for businesses. So Google Maps probably takes around $1 billion, the public, I mean, it's difficult to come up with an accurate estimate of how much Google invests in maps every year, but some rough estimates are in the order of magnitude of $1 billion per year. And that's a huge investment. However, for the particular type of applications that delivery and taxi companies need, you don't really need all the machinery that Google Maps deploy. So we like to think about our system that we coined QARTA-QARTA is a word that is in many languages, a word that is used for maps-so our system called QARTA is a very lightweight, so we basically remove all the unnecessary blocks and we keep all the things that are necessary for answering the type of queries that the delivery companies, last-mile delivery companies, logistic companies, or ride sharing companies or taxi companies, require to run their businesses. And by doing so, we can keep the running cost as small as possible.

Laurel: QARTA, but with a Q, which is a nod to Qatar, which is fantastic.

Rade: QARTA with a Q. If you permute the letters you get the name of the country that we are at, Qatar.

Laurel: That's right. So tell us more about the technology. You were using machine learning with the data from Karwa to try to figure out the best way to adjust the travel time estimates depending on the time of day, et cetera. So can you talk a little bit more about that approach? Like how did you actually keep your data in real time?

Rade: So machine learning is great when you want to capture complex relationship on one hand, and you also have enough data to capture those relationships and train your machine learning models. So, fortunately enough, modern vehicle fleets have these monitoring systems that produce quite a lot of data. Production of that data makes this machine learning possible. I would say 10 or 15 years ago, most of taxis wouldn't have that GPS tracking enabled. And then without such GPS tracking, all this machine learning wouldn't have been possible. However, we are fortunate enough to collaborate with Karwa, which have that rich monitoring system that basically helps us capture that data, process it, and figure out those two important ingredients that I just mentioned, but I'm going to repeat them again, understanding the underlying road network on one hand and understanding the traffic that goes on top of that.

So all of that information allows us to be not only comparable with commercial maps, but also to shave off a few tens of seconds of errors for every trip. And these few tens of seconds translate to increase in efficiency of somewhere between 5 and 10 percent. It's really difficult to come up with the exact number of how efficiency is improved by improvement in the errors of the underlying digital map. This may not sound [like] a lot, but as I mentioned, in a business that is running under very tight profit margin, improving efficiency for five percent is a huge deal.

Or in other words, if you're running a fleet of 3,000 cars, five percent of that is 150 cars. You can basically remove 150 cars from the road and not lose any business. And removing 150 cars translates to X million dollars per year of cost reduction. So what I'm trying to say is that all of these little things, a few seconds here, a few percent there, actually matter because of the increased efficiency, and increased efficiency results in better cost revenue equation.

Laurel: And that's also important for public transportation, for government agencies who are trying to save that small percentage here or there as they try to become more efficient.

Rade: Absolutely. Actually public services here, public transportation here is very, very immature. So a lot of the public transportation relies on taxi and ride sharing services. There is some sort of estimate that the taxi and ride sharing services take over 80 percent of public transportation. So the bus network is very sparse. So most of the time, if you don't own a car and you want to move from A to B, you're going to call a taxi or Uber or similar transportation service. Currently, the Metro is being built, and that's part of the infrastructure projects that we were talking about earlier on. The first line was opened last year. And the following two lines are being opened this year. Hopefully with the public transportation being a bit more regular and the public transportation network being a bit denser, the need for taxis will hopefully go down.

Laurel: So speaking of trying to build a better society, the QCRI is one of the Qatar Foundation's research institutes. And the Qatar Foundation's goals are to, one, advance pioneering research in areas of national priority for Qatar, and two, to also support sustainable development and economic diversification. But these kinds of goals have the benefit to help the entire world. So clearly the work that you're doing fits both of these criteria. What is the broader importance of building smarter and less expensive mapping systems, as well as transportation systems? How could this technology help other growing urban centers in the Middle East and the rest of the world?

Rade: So, one interesting thing about commercial maps and a lot of the high-tech products that are built in Europe and North America: They are built in the developed world and for the developed world. So commercial maps are not an exception over there. They are developed with a particular user in mind, and that user normally comes with a deep pocket, and normally comes in the world where the roads don't change that frequently. Those two assumptions are broken in the developing world. Paying a couple of dollars per month may not be a big deal for a taxi operating in Boston or Madrid. But few dollars per month per taxi is perhaps 10 percent of salary of a driver in New Delhi or Kuala Lumpur. So we see QARTA as a solution that I mentioned, a lightweight solution, that can address the needs without going deep in the pockets of these transportation providers.

That somewhat goes along the mission of Qatar Foundation of helping the developing world. We see our target market for the system that we are building in the developing world. I don't think we can compete with the Googles of the world in the developed world for the reasons that I just described. We don't have the resources and the expectations of the users in the West are sort of different from the expectations in the developing world. This is one of the reasons why, what ourselves and our leadership is excited to push for Qatar.

Laurel: That's excellent. How, though, do you respond to the possible new wave of autonomous vehicles? Is that something that actually helps you meet this challenge?

Rade: Oh wow, yeah, I'm very, very excited about the era of autonomous vehicles. It's difficult to say when that era will come, but the closer we get to that date, the more important will be the role of accurate digital maps. So one rate of reporting opportunity for autonomous vehicles is their ability to optimize the routes and the driving in general, to reduce inefficiencies of human decision making. So for example, humans tend to use suboptimal routes. So each time I go from home to work, each time I take this route, I don't really like to explore. I have friends who actually, every time they get into the car, they type in the destination and they look for the optimal route at that particular time. I'm not one of those people. I take the same route every day. The cognitive load for me to worry about the optimal route is something I don't really want to worry myself with.

However, with autonomous vehicles, people wouldn't need to worry about it. You could just press the button and the autonomous vehicle would take that optimal route for you whenever you enter the car. So that's one way for the autonomous vehicles to help you save couple of minutes here, a couple of minutes there, probably a couple of hours every month.

Additionally, autonomous vehicles with an accurate understanding of the road network infrastructure and all the dynamics things that are going on, autonomous vehicles can optimize for some sort of global optimum. Very often humans tend to be greedy. And by being greedy, we may all end up using the highway. And by hoping to save couple of minutes, we may put so much congestion on the highway that we all suffer. By having some sort of a global view of what's going on in the whole city, autonomous vehicles can actually reroute us to have some sort of global load balancing to help everyone be better off.

And how far are we from there? I wouldn't say we are that far, but we are probably a few years, if not a decade away from that globally optimum routing, which I'm really, really looking forward to. Because if you think about it, there are so much road infrastructure out there. If you think about how many streets are out there in the city of Boston and the city of Doha. However, utilization of these resources is kind of skewed towards very few major roads that end up being congested in the peak hours. And I'm a true believer that globally optimal scheduling of the routing decisions can substantially reduce the congestion in the city and help our lives in general. Basically we can spend a few hours every week less in traffic compared to what we do nowadays. On the flip side, if it will be so easy to travel, then we may end up traveling more. But that's a separate thing to worry about.

Laurel: [Audio garbled] challenges like reducing energy and designing new internet services?

Rade: One thing that I keep myself busy lately with, is the utilization of the world that we already have. So everything related to digital maps and accurate traffic understanding to help reduce CO2 emissions. So CO2 emissions, I mean, there are people that believe and there are those people who don't believe in a greenhouse effect and global warming, but CO2 emissions, and in general, petrol consumption is a huge deal. And transportation contributes to that in a non-trivial way. I'm a strong believer that understanding of the traffic can shave off a couple of percent of the CO2 emissions and also petrol consumption, and that can have an immediate effect in reduced bills that we pay for petrol, but also long-term the reduction of CO2 emission is sort of mandatory. One way or another we will need to find a way to deal with that issue, and I believe that the combination of autonomous driving, electric cars and some sort of reduction of inefficiencies will be necessary. And to do so, underlying traffic map will be of great help.

So let me just give you an example. If your car and you as a driver had a good enough understanding of how long will that green light be still green, you can have an informed decision of whether you want to keep your driving at 50 kilometers per hour, or you perhaps want to slow down and not waste that petrol because the light will turn red in a couple of seconds, and you'll be just wasting all the energy of speeding just in front of the traffic light. These are the kinds of things that I'm working on at the moment, and hopefully we will be able to report something interesting, but this is still work in progress.

Laurel: Dr. Stanojevic, thank you so much for joining us today. It has been a great conversation on Business Lab.

Rade: Thank you very much, Laurel. It was great talking to you.

Laurel: That was Dr. Rade Stanojevic, a principal scientist at Qatar Computing Research Institute, part of Hamad Bin Khalifa University, a Qatar Foundation university, who I spoke with from Cambridge, Massachusetts, home of MIT and MIT Technology Review, overlooking the Charles River.

That's it for this episode of Business Lab. I'm your host, Laurel Ruma. I'm the director of Insights, the custom publishing division of MIT Technology Review. We were founded in 1899 at the Massachusetts Institute of technology, and you can find us in print, on the web, and at events around the world. For information about us and the show, please check out our website at technologyreview.com.

This show is available wherever you get your podcasts. If you enjoyed this episode, we hope you'll take a moment to rate and review us. Business Lab is a production of MIT Technology Review. This episode was produced by Collective Next. Thanks for listening.

This podcast episode was produced by Insights, the custom content arm of MIT Technology Review. It was not produced by MIT Technology Review's editorial staff.