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

QNX, AutoNavi collaborate to provide in-car navigation for automakers in China

Map database offers 20 million points of interest

Paul Leroux

This just in: QNX has announced that it is partnering with AutoNavi, a leading provider of digital map content and navigation solutions in China, to integrate AutoNavi’s technology into the QNX CAR platform.

AutoNavi offers a digital map database that covers approximately 3.6 million kilometers of roadway and over 20 million points of interest across China. By supporting this database, the QNX CAR platform will enable automotive companies to create navigation systems optimized for the Chinese market and users.

Said Yongqi Yang, executive vice president of automotive business, AutoNavi, “as a leading global provider of vehicle infotainment software platforms, QNX is not only a technology leader, but also a design concept innovator in enhancing vehicle flexibility — infotainment designs based on the QNX CAR Platform can be quickly customized.”

For more information on this partnership, read the press release. And to learn more about AutoNavi, visit their website.

From Hollerith to HTML5: the inevitable rise of the programmable car

Paul Leroux

Some people are crazy good at predicting the future. Case in point: Nicola Tesla. In 1909 he proclaimed that "everyone in the world" would one day communicate with wireless handheld devices. At the time, people must have thought he was, well, crazy. But look around you: when's the last time you weren't surrounded by people using wireless handhelds?

Over the years, the auto industry has produced many technology visionaries who share this talent for prognostication. Mind you, visionary is probably the wrong word. Many of these people didn’t simply envision the future; they tried to build it. All too often, however, the technology needed to make their ideas work was still in its infancy — or simply didn't exist yet.

For evidence, consider the ITER AVTO. Introduced in 1930, this dash-mounted navigation system used maps printed on rolls of paper. These maps were connected by a cable to the speedometer and would scroll forward in proportion to the car’s speed. It was all pretty cool, provided you didn’t make a turn — otherwise, quick, change rolls! Basically, a great idea hampered by the tech of its time:


Source: Dieselpunks

For another example, consider these “alarming” glasses, which made their debut at the Frankfurt Motor Show in 1951. The concept was simple: monitor eye movements to determine whether the driver is falling asleep; if so, sound an alarm. Just one problem: to detect eye movement, the glasses used a thin steel wire pressed against the driver’s eyelids. It was another great idea that needed yet-to-be invented technology — in this case, inexpensive (and non-invasive) eye-tracking cameras — to work.


Source: Modern Mechanix blog

And then there’s the 1969 Buick Century Cruiser, an autonomous concept car that used punch cards to program the car’s destination. The driver would insert a card encoded with a destination, and an electronic highway center (whatever that was) would then take over and guide the car to where it was programmed to go.


Source: Car Styling 2.0 

The car was never intended to be sold, of course. To be commercially viable, it would have required technologies that simply weren't available in 1969.

But you know what? I think the Century Cruiser represents a watershed concept: that you can use software to control or enhance a car's behavior. The Century Cruiser may have used Hollerith cards, but it presaged vehicles that, in a few short years, would use programming languages like C to control ECUs and anti-lock brakes. From there, it was only a matter of time before cars would use software technologies like HTML5 to deliver everything from weather reports to smartphone integration. The software path was set, even if no one realized it yet.