Why doesn’t my navigation system understand me?

Automotive

A story where big is good, but small is even better.

Yoshiki Chubachi

My wife and I are about to go shopping in a nearby town. So I get into my car, turn the key, and set the destination from POIs on the navigation system. The route calculation starts and gives me today’s route. But somehow, I feel a sense of doubt every time this route comes up on the system...

Route calculation in navigation uses Dijkstra's algorithm, invented by Edsger Dijkstra in 1956 to determine the shortest path in a graph. To save calculation time, navigation systems use two directional searches: one as the starting point and the other as the destination point. The data scheme that navigation systems use to represent maps consists of nodes, links, and attributes. Typically, a node represents a street intersection; a link represents the stretch of road, or connection, between two nodes; and attributes consist of properties such as street name, street addresses, and speed limit (see diagram).

Features of a map database. From Wikipedia.

As you may guess, it can take a long time to calculate the shortest path from all of the routes available. The problem is, automakers typically impose stringent requirements on timing. For example, I know of an automaker that expected the route from Hokkaido (in northern Japan) to Kyushu (in southern Japan) to be calculated in just a few seconds.

To address this issue, a system can use a variety of approaches. For instance, it can store map data hierarchically, where the highest class consists of major highways. To choose a route between two points, the system follows the hierarchical order, from high to low. Another approach is to use precalculated data, prepared by the navigation supplier. These examples offer only a glimpse of the complexity and magnitude of the problems faced by navigation system vendors.

An encouraging trend
Big data is the hot topic in the navigation world. One source of this data is mobile phones, which provide floating car data (current speed, current location, travel direction, etc.) that can be used by digital instrument clusters and other telematics components. A system that could benefit from such data is VICS (Vehicle Information and Communication System), a traffic-information standard used in Japan and supported by Japanese navigation systems. Currently, VICS broadcasts information updates only every 5 minutes because of the bandwidth limitations of the FM sub-band that it uses. As a result, a navigation system will sometimes indicate that no traffic jam exists, even though digital traffic signs indicate that a jam does indeed exist and that service is limited to the main road. This delay, and the inconvenience it causes, could be addressed with floating car data.


An example of a VICS-enabled system in which traffic congestion, alternate routes, and other information is overlaid on the navigation map. Source: VICS

During the great earthquake disaster in East Japan, Google and automotive OEMs (Honda, Nissan, Toyota) collaborated by using floating car data to provide road availability — a clear demonstration of how can big data can enhance car navigation. Leveraging big data to improve route calculation is an encouraging trend.

Small data: making it personal
Still, a lot can be accomplished with small data; specifically, personalization. I may prefer one route on the weekend, but another route on a rainy day, and yet another route on my wife's birthday. To some extent, a self-learning system could realize this personalization by gauging how frequently I've used a route in the past. But I don’t think that's enough. As of now, I feel that my navigation system doesn't understand me as well as Amazon, which at least seems to know which book I’d like to read! Navigation systems need to learn more about who I am, how well I can drive, and what I like.

Personalization resides on the far side of big data but offers more convenience to the driver. The more a navigation system can learn more about a driver (as in “Oh, this guy has limited driving skills and doesn’t like narrow roads”), the better. It is best to store this data on a server; that way, the driver could benefit even if he or she switches to a different car or navigation system. This can be done using the latest web technologies and machine learning. Currently, navigation systems employ a rule-based algorithm, but it would be interesting to investigate probability-based approaches, such as Bayesian networks.

I’m looking forward to the day when my navigation system can provide a route that suits my personal tastes, skills, and habits. Navigation suppliers may be experiencing threats from the mobile world, including Google and Apple, but I think that returning to the original point of navigation — customer satisfaction — can be achieved by experienced navigation developers.

Yoshiki Chubachi is the automotive business development manager for QNX Software Systems in Japan

Automotive