Mapping for navigation
The most basic use of a map is to find out where one is located. After that, one usually wants to use the map to find the best route to another location. On a digital map, this is usually provided with turn by turn navigation using a navigation device.
Let the computer find the best route for you!
A navigations system has user facing components that interact with the user and back end components that computes the best route based on the user input and available data. In this guide we will focus on the back end components that rely on map data.
User facing components
- User interface controls for setting the the origin and destination
- Map display that visually represents the route to take
- Turn by turn instructions that accurately describe the navigation maneuvers at the appropriate time
- Route status that includes current progress and the estimated time of arrival (ETA) at the destination
Back end components
- A navigation profile that describes the mode of transport to use for the routing algorithm (eg. truck, cycle or foot)
- A route finder that finds the best possible route between the origin and destination for the selected navigation profile
- A guidance system that converts the route into instructions for turn by turn navigation
The navigation profile accurately describes the preferred types of roads to take based on the mode of transport used. A walking profile will have a fairly constant walking speed on any type of road, while a car profile will have avery high traveling speed on a motorway and will be much slower on a residential road. This has a large influence on the route finder.
Different routing profiles: cars, walking, bicycle.
Routing is the process of selecting the best path in a network interconnected of roads on the map. Every road segment on the map has a traveling speed calculated based on various road factors, and the fastest and safest route is selected from all possible combinations.
Finding the route between two points involves complex calculations on a routing graph
The calculation of an accurate route depends on a variety of factors which are taken into account by the routing algorithm:
- Personal factors: fastest route, most scenic route, quietest route, shortest route, facilities needed, toll rates
- Vehicle factors: mode of transport, physical category of vehicle, optimum traveling speed, riding surface requirements, fueling requirements
- Route factors (static): classification of road, access restrictions, speed limits, turn restrictions, oneway rules, number of lanes
- Traffic factors (dynamic): traffic conditions, traffic signal cycle duration, weather conditions
- Riding surface factors: surface material, smoothness, barriers, speed breakers, road width, lane width, age
A route is converted into a series of easy to follow instructions for the user
Route guidance is used to lead a person through the determined path. Once the routing algorithm determines the best path, that route is converted into a set of human-readable instructions known as guidance. The guidance represents the street names, the turn lanes marked on the roads, exit numbers, and destinations shown on sign boards. Accurate and relevant guidance can greatly enhance the user experience of using the map for navigation.
Providing accurate navigation using maps is dependent on having detailed and updated data about the world. The world is transforming every second and the next generation of navigation will need to have the latest information about the world that will come from various sources.
_Telemetry traces of Strava users from [Strava Globalheatmap](http://labs.strava.com/heatmap/#14/-74.02871/40.70159/blue/both)_
Telemetry is the remote collection of data which can be physical, environmental or biological. Most internet and GPS enabled phones collect location and other environmental data and reports it to a central service that can aggregate the data to determine traffic conditions on a road.
Crowdsourced streetview photographs from narrow alleys in India using Mapillary
Street view images from dashcams, mounted cameras in vehicles using apps gives highly detailed 360° view of streets. This can help detect traffic signage, access restrictions, traffic signals, road markings to help add and confirm ground features into a map. Opensource street view photos include Mapillary and OpenStreetView.
High resolution imagery captured from UAVs in Srilanka
Aerial imagery using drones can capture the changing surface of the earth at a much higher resolution and lower cost compared to traditional satellite imagery that is expensive to acquire and are updated less frequently.
Automatic image segmentation by Mapillary
Advances in machine learning opens up opportunities to automate manual tasks like digitization of roads from satellite imagery and can accelerate the creation and maintenance of map data.
A navigation map is influenced by several road characteristics, such as the turn restrictions, improper way of road tracing and road classification. The most important ones among those are:
Roads are the main features that are used for rendering a route in all navigational applications. Correct road mapping leads not only to the well-looking map but also to better navigation experience. With the change in the shape of the traced road, the distance covered will be altered which affects the route. The common approach for road mapping is to trace roads following the center-line from satellite imagery.
Roads on satellite imagery
If you want to travel from point A to point E as shown in the below image, you can either travel from A to B, B to C and then C to E or A to B, B to D and then D to E.
But, if you have a restriction to enter D from A, the only possible route will be A to B, B to C and then C to E. This is where connectivity plays a major role in deciding the final route.
If A to C is a primary road which is crossing through a service road B to D and you want to travel from A to E, the navigation map comes up with the route traveling from A to B, B to C and then C to E and completely avoids A to B, B to D and then D to E because the travel on Primary road is much efficient than a narrow service road. This is how the attributes / properties with which the road is assigned with plays a crucial role in deciding the final route.
The OpenStreetMap data model consists of nodes, ways, relations, and tags. A detailed description of the data model can be found in the The OpenStreetMap Data Model guide.
Navigation data is similarly a combination of nodes, ways, relations, and tags. Some of the examples are illustrated below:
- Nodes:
- Exit numbers:
- Ways:
- Highway=*
An way tagged with highway=secondary tag
- Relations:
- Turn restrictions are a combination of nodes, ways, tags, and relations. It consists of
from wayvia nodeandto way, tied together by arestriction=*relation.
- Tags: All the navigation features are differentiated and defined based on how they are tagged. Tags can be on any element: on nodes, ways, and relations.
Examples are: destination=*, ref=*, turn:lanes=*, restriction=*, etc.
Before tracing, we need to inspect the start and endpoints of the road segment. We need to identify the road direction, general numbers of lanes and the places where there are extra lanes. Based on this we choose our strategy for tracing.
We are not able to draw a road on its center line, especially if roads join/fork or the number of lanes change. Imagine two roads which join: how would you draw the OSM-way around the point where the roads join?
Center line tracing
Tracing based on road direction
There are two cases:
-
Dual carriageway roads
These are bidirectional roads which have a physical separation between the lanes in both the directions. Both the ways will be counted for lanes and will be tagged with lanes=*. Dual carriageways are always oneway roads.
Placement of nodes of the lines in each direction, opposite to each other
-
Roads which carry traffic in both directions (Bidirectional roads)
Road carrying traffic in both directions