You can check out Part 1 here.
Ad Hoc Navigation
The next step in navigation is to be able to travel from the current point to some other point. That is, we expect the satellite receiver to handle an ad hoc navigation command: “I’m here, but I want to go there, somehow.”
But, how does the receiver know where “there” is? And once it knows, how does it “somehow” calculate the path to that point? Let’s start by examining the first question.
Modern receivers contain a navigational database. It consists of many waypoints that represent different entities such as points on the roads, residential addresses, gas stations, shops, and restaurants. The database also contains geographical entities for countries, states, cities, and streets. When the rider performs ad hoc navigation, he is typically presented with selections starting from the larger scope (country/state) then going into finer details (city/street/street number). In each step, the receiver shows a list of available options, which are narrowed down by the previous selection. For example, suppose I want to ride to “206 North Spruce St, Winston-Salem, NC” (RoadRUNNER’s headquarters). I would first select the country as ‘U.S.’ then ‘NC’ for state, ‘Winston-Salem’ for city, ‘N Spruce St’ for street, and ‘206’ for street number. In some countries, like the USA, the convention is to write the street number before the street name; therefore, it is often entered that way even though the actual order in the database is street name first. Some receivers allow entering a postal code (zip code in the USA) as a shortcut since a postal code is quick and easy to enter, and it always uniquely matches to a single city within a given country. The receiver organizes these entities into data structures.
The receiver’s goal in this phase is to take the address input from the rider and convert it to a waypoint—latitude and longitude. Try it by entering that address in a site such as www.gps-coordinates.net and notice the waypoint value that is calculated: Latitude: 36.095977 | Longitude: -80.248786.
While this site is online and uses Google Maps functions, Garmin, TomTom, and other vendors work offline using similar principles in order to convert addresses to waypoints.
The receiver now has two inputs for finding a path—the current waypoint, or source, and the target waypoint. The challenge is how to find a path between them. Inside the receiver there is another very large database of waypoints, which describes how they are connected in a graph structure. This is similar to a big interconnected network. The graph consists of vertices (one for each waypoint) and edges that connect the vertices. The edges have attributes that describe the physical road between two vertices. Attributes can consist of distance, speed, type (toll, road, off-road, etc.), direction (one-way, two-way), and others.
At the heart of the path calculation process, there is routing algorithm software. This algorithm attempts to find the shortest path between the source and target waypoints using the information in the navigation graph. The shortest path is calculated using some metric, such as distance or time. Then, the metric can be selected by the rider in the settings screen. Typical choices are to find the shortest time or the shortest distance. For example, in diagram 3, the shortest time path is ADF (331 seconds), whereas the shortest distance path is ABDF (5 miles). As a side note, some receivers display the maximum speed of the road as you ride. This speed value comes from the edges of the navigation graph. A road is composed of many small edges and each can have a different maximum speed.
The rider can enforce restrictions to control how the path is calculated. For example, if the ‘Avoid Toll Roads’ setting is selected, edges that are marked as toll roads would be avoided. The shortest time path with a ‘No Toll’ restriction is ACDF (400 seconds).
There could also be another metric that measures ‘Fun Penalty Factor,’ which riders most often associate with scenic and twisty roads. In fact, the latest version of the TomTom Rider GPS receiver includes a feature named ‘Winding Roads’ that works similarly. A path would be selected so Fun Penalty values are minimized, where those values can be one, for causing the least penalty on fun, to nine, causing the most penalty on fun.The path ACEF has the shortest total Fun Penalty Factor (7 Fun Penalty units). It is not the shortest distance nor is it the shortest time, but it would probably be the most exciting to ride of the possible routes.
It is recommended to turn off restrictions before starting navigation. Forgetting to do so could result in unwanted paths when least expected. Sometimes when you need to get to a target waypoint quickly (e.g., find a gas station ASAP when you’re running on fumes), having a much longer path can be counterproductive to say the least.
The Good with the Bad
Hopefully, it should be clear now why map updates are so important. Maps change daily, some roads are closed while others are constructed or changed, speed limitations change, gas stations shut down, and new shops appear, etc.
Some vendors still charge for map updates, but the market is quickly moving to ‘LM’ updates (i.e., free Lifetime Maps), which are becoming the standard.
Ad hoc navigation is very useful and can save a lot of time and stress. But, this ‘lazy mode’ has its limitations as it lets the satellite receiver make decisions for the route. Planning routes manually takes more time, but it allows the rider to have explicit control over where they are going.