Why doesn’t my navigation system understand me?

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

Making the smartphone connection: The state of automotive navigation in Japan

A guest post from Yoshiki Chubachi, the automotive business development manager for QNX Software Systems in Japan

The market for navigation systems in Japan grew rapidly until 2006, but since 2007 the yearly volume has reached the saturation point, at about 2.9M units. For instance, in 2008, consumers purchased 900k after-market systems, 1.1M dealer-installed systems, and 909k factory-installed systems. In 2010, those numbers had changed slightly: 1.01M after-market systems, 1.03M dealer-installed systems, and 858k factory-installed systems (source: Yano Research Institute).

That said, the market is starting to experience a shift from after-market to factory-installed devices. Automakers and their tier one suppliers are struggling to differentiate their products by implementing value-added features.

To get a feel for current navigation trends in Japan, let’s look at some notable after-market products that shipped in 2011. As you'll see, smartphones are exerting a major influence on this market, both in terms of system design and user features:

Pioneer AVIC-VH09CS — This high-end system combines augmented reality technology with a front-view camera, overlaying your route on a live video of the road. It also implements a collision warning system by measuring the distance of the car ahead. Other features include terrestrial digital TV (full HD and 1seg), DVD video, AM-FM, CD and SD music, iPod connectivity, and music ripping and encoding.

Clarion NX501 — The smartphone world seems to drive navigation trends, and the Clarion NX501 is no exception. It offers a touchscreen UI that supports swipes, flicks, and other finger gestures similar to those found in smartphones and tablets. Suzuki factory-installed systems also use the type of user interface.

Fujitsu-Ten AVN-F01i — This system comes with three bundled iPhone applications: Twitter Drive (combines tweets with location data), Where is My Car (uses augmented reality to show your parking location on the phone screen; great for finding your car in large parking lots); and News Reader (allows the system’s text-to-speech engine to read out news articles). The system connects to the phone through Bluetooth.

Panasonic CN-H500WD — The system also lets you use finger swipes to operate navigation and audio functions, including a scrolling map. It comes with a smartphone application that provides POI search, which is downloaded to the navigation system through Bluetooth.

Mitsubishi NR-MZ50 — This system provides an “OpenInfo” service based on Pioneer’s Smartloop system, which provides traffic data from a Pioneer server. VICS (Vehicle Information and Communication System) is a popular traffic data service in Japan that is similar to the RDS-TMC standard, but its coverage is limited to main highways. The smartphone receives traffic data, derived from anonymous traffic probe information, wherever the VICS service isn't supported. Information from the phone is transmitted to the navigation system through Bluetooth.

Connectivity between navigation systems and smartphones remains an issue in Japan. Conventional cell phones are equipped with the Bluetooth DUN profile, which enables data communication between the nav system and the phone, but unfortunately, some carriers still don’t support this profile. Until they do, lack of connectivity will remain a roadblock.

Nonetheless, using smartphones to deliver applications and the user experience has become a major trend in Japan’s navigation systems. Some automotive tier one suppliers, such as Pioneer, already provide navigation applications on the phone. The QNX CAR 2 application platform, with its mobile connectivity features and auto-centric HTML5 framework, offers an ideal foundation for enabling this approach.