Definition
How does a map app know about a traffic jam that started five minutes ago?
Navigation apps combine two things: route-finding methods that search a map of roads for the best path, and machine learning models that predict traffic and arrival time from live and past travel data.
In simple words
Imagine asking a friend who has driven every road in the city at every hour of every day. They would say, "At 6 p.m. avoid the market road, it is always jammed." A map app is that friend, built from the journeys of millions of phones.
Why it matters
Maps show clearly how prediction works: the app is guessing the future from patterns in the past. That also explains its mistakes. A sudden accident or a newly closed road is something the past data never showed.
Key terms
- Route planning
- Finding the best path between two places on a network of roads.
- Graph
- A way of describing a network as points joined by lines. For roads, junctions are points and roads are lines.
- Shortest-path method
- A step-by-step procedure that finds the quickest route through a graph.
- Live traffic
- Information about how fast vehicles are moving on each road right now.
- Estimated time of arrival (ETA)
- The predicted time at which you will reach your destination.
- Location data
- Records of where a phone has been, which can reveal a great deal about a person.
Explained in detail
A map is a network
To a computer, a city is not a picture. It is a network: every junction is a point, and every stretch of road is a line joining two points, with a number saying how long it takes to travel. Finding a route means finding the chain of lines from your starting point to your destination with the smallest total time. In a large city there are more possible chains than anyone could check one by one.
Two different kinds of cleverness
Finding the best route is done by a search method, not by learning. In the 1950s the Dutch computer scientist Edsger Dijkstra worked out a procedure that is guaranteed to find the shortest path through a network. In 1968 researchers building Shakey the robot improved on it with a method called A-star, which searches towards the destination and wastes less effort. Versions of these methods run inside every navigation app.
Machine learning does a different job. It supplies the numbers the search needs: how long will each road take, not on an empty map, but at 6 p.m. on a rainy Friday? A model learns this from years of past journeys and from the live speeds of phones on the road now. In 2020 Google and the research company DeepMind reported that a new kind of model, one that looks at neighbouring roads together, had improved the accuracy of arrival times by a large margin in several cities.
Where the traffic colours come from
- Phones with location switched on report their position and speed, without a name attached.
- The app groups the reports by road and works out the typical speed on each stretch.
- It compares that speed with what is normal for the road.
- Much slower than normal is shown in red, a little slower in orange, normal in green.
This explains two weaknesses. On a quiet road with few phones, the app has little information and may be wrong. And when the app sends thousands of drivers down the same "faster" side street, it can create a new jam there.
Beyond road maps
| Service | What AI predicts |
|---|---|
| Cab and auto booking apps | Where riders will be, which driver to match, the fare |
| Food and parcel delivery | The best order of stops and the delivery time |
| Railways and airlines | Delays, demand for seats, maintenance needs |
| City traffic signals | How long each direction should have a green light |
Your location is sensitive
A record of where a phone goes each day reveals where its owner lives, works, prays and visits a doctor. Map apps let you switch off the saving of location history and delete what has been stored. It is worth knowing where those settings are.
How it works
- The map is stored as points (junctions) joined by lines (roads). Each road has a length and a usual speed.
- Phones that have location switched on report how fast they are moving, without names attached. Slow phones on a fast road mean a jam.
- A model adds what usually happens at this hour on this day, such as office rush or a weekly market.
- The app works out the travel time of many possible routes and shows the quickest ones.
- While you travel it keeps checking. If a faster route appears, it offers to change.
| What you see | What is behind it |
|---|---|
| Red, orange and green roads | Live speeds of phones on that road |
| "You will arrive at 5:42" | A prediction from live and past traffic |
| "A faster route is available" | The prediction changed, so the best route changed |
| Cab fare that changes with demand | A model predicting how many riders and drivers are nearby |
Try it yourself
How an arrival time is predicted
You ask for the way to the railway station at 6 p.m.
Why did the prediction go wrong?
Each trip took longer than the app said. Could the app have known?
A tree fell across the road one minute ago
The same road jams at 9 a.m. every weekday
A new bridge opened this morning and is not on the map
A festival procession is held on this street every year
Common mistakes
- Treating the arrival time as exact. It is a prediction that updates as conditions change.
- Following the app into a road that is clearly closed or unsafe.
- Forgetting that traffic colours come from people's location data, so quiet roads with few phones are less reliable.
Check yourself
Summary
- Map apps find routes on a network of roads and predict travel time with machine learning.
- Live phone speeds and past patterns are the data behind traffic colours and arrival times.
- Sudden events and out-of-date maps cause mistakes, so keep watching the real road.
Finished reading?
Sources: Elements of AI (University of Helsinki) · AI4K12: Five Big Ideas in AI