Mapping for navigation

Introduction

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!

Components of map navigation

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

Navigation profile

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

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

Guidance

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.

Navigating the future

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

_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.

Forward facing cameras & Street-view

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.

Live Aerial & Drone Imagery

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.

Machine learning and image recognition

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.

---

Modeling Roads for Map Navigation

---

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:

Road geometry

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

Road connectivity / topology:

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.

Road attributes / properties:

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.

OpenStreetMap data model:

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:

Examples

• 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 way via node and to way, tied together by a restriction=* 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.

Tracing roads

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

Tracing roads with more than two lanes

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

Road Features Mapping Guide

Routing features

These are features that help the routing engine find the safest and fastest route between two points.

1. Functional Road Class

• highway=*
• OSM Wiki

Roads are categorized according to its order of importance. They are tagged with the highway=*. The general order of importance for way types are:

highway= motorway > trunk > primary > secondary > ... > living streets > ... > footway

highway=primary in San Francisco

The value of the key helps show the importance of the highway within the road network as a whole. The importance ranges from the most important motorway to the least important service. The routing engine takes into account this importance of classification when determining optimum routes.

Road classification may varies from country to country. The country specific use cases can be found in detail on separate wiki pages. For example, when mapping roads in India, the local community refer to the India road tagging wiki.

Examples:

• US roads classification
• UK roads classification/numbering

For an example of an area with a good concentration of different classes of roads on OpenStreetMap, look at San Francisco area. This osm query can be used to extract and gather numbers of all the highways present in a given bounding box on OpenStreetMap.

Department of Transportation websites and wikipedia are some of the primary sources for highway information.

2. Oneways

• oneway=yes
• OSM Wiki

Oneways generally refer to road segments which allow traffic in only one direction. There are also streets which have oneway characteristics for only on certain times of the day to regulate traffic.

oneway=yes shown in Mapillary

The best source of mapping oneways are again street level photos.

San Francisco is one area which has been well mapped for oneways in OpenStreetMap. This overpass query can be used to extract oneways from OpenStreetMap data.

3. Turn-Restrictions

• type=restriction
• OSM Wiki
• Mapping guide

type=restriction is added to a relation in OpenStreetMap which is used to describe turn restrictions at junctions. The relation has a set of tags that describes the type of restriction, for example. no_left_turn, no_right_turn, no_u_turn, etc. These are traffic signs at junctions and this information must be present on the map to find the best route by the routing engine while planning a route.

Turn restriction denoting no left turn along with conditions: opening and closing times

The main resource for turn restriction data is street view level images, local mapping drives, DOT websites

turn restriction which denotes no right turn at the junction

San Francisco in OpenStreetMap has an excellent coverage of turn by turn restrictions at junctions. This overpass query can be used to extract current turn restriction in a bounding box.

4. Speed limits

• maxspeed=60 or maxpseed=40 mph
• OSM Wiki

The maxspeed=* tag defines the maximum legal speed limit for general traffic on a particular road, railway or waterway. The max speed values will be interpreted as kilometers per hour by default. The maxspeed=* is an important part of routing as it is used in determining the shortest time taken by a specific route to reach a destination. In the case of two routes, the one with the shortest time (higher maxspeed) and shortest distance will be considered as the optimum route.

Maxspeed sign shown in Mapillary

The main data sources for detecting maxspeed signs are: street view photos, wikipedia, DOT documents.

The maxspeed=* data on OpenStreetMap (for example, in London) in an area can be extracted by this overpass query.

5. Access-Restrictions

• access=*
• OSM Wiki

Apart from turn restrictions, there are access restrictions for different parts of highways. Some of these tags are access=no, access=private etc which will end up altering the route to be taken during the journey. For more information on the various kinds of access=* tags take a look at Key:access and Conditional restrictions and access restrictions

An access=no for non-motorized traffic, ends up altering the route for bicycle profiles, source: US MUTDC

All the access=private tags on OpenStreetMap ways, which will not allow that segment of the way to be used in a route can be extracted from this overpass query. An example of well-mapped access restrictions in OpenStreetMap can be found in London.

The sources for mapping access restrictions in OpenStreetMap are: street view photos, local mapping drives.

6. Traffic signals

Traffic signals such as: highway=traffic_signals, highway=stop or barrier=toll_booth as well as traffic_calming=* are considered during routing. The type=restriction more commonly referred to as turn restrictions are traffic signage which prohibits certain turns in intersections are also a crucial part of a great routing engine.

More details on mapping traffic signals for cars and pedestrians can be found in the OpenStreetMap wiki.

Street view photos from Mapillary, local mapping drives using OpenStreetMap tracker can be used as sources to map traffic signals in OpenStreetMap.

Traffic signal in a junction

Guidance features

1. Exit & destination signs

What are exit numbers?

• An exit number is a number assigned to a road junction, usually an exit from a freeway. It is usually marked on the same sign as the destinations of the exit, as well as a sign in the gore.

Different tags for exit numbers:

• ref=* is used when the exit has a specific number assigned to it.
• noref=yes is used when the exit doesn't have any official number assigned to it.

What are destination tags?

• Destination tags describe the content of signposts or ground writing indicating the names of the locations that a certain exit from the freeway or a highway is heading to.
• The key destination=* describes where a certain exit leads to. Thus navigation systems can refer to road signs that the driver actually sees.

Different tags for destinations:

• destination tag refers to the place that the way exiting from the freeway leads to.
• destination:ref is the reference of the roads directly ahead.
• destination:ref:to is to specify the reference of a major highway ahead.
• destination:street refers to the main street the way exiting from the freeway leads to.

An example of a place with good exit/destination coverage in OpenStreetMap is Ottawa, Canada. These overpass queries for destination and exit numbers can be used to extract exit/destination data from OpenStreetMap.

The detailed guide on adding exit and destination numbers can be followed for adding exit/destinations. This guide is specifically focused on North America (US/Canada) for now.

2. Turn Lanes

As discussed in Modeling Roads for navigation page, there are two types of roads: unidirectional and bidirectional. lanes=* tag is used to count the number of lanes in both these type of roads.

To set number of lanes for roads which carry traffic in both directions use :backward and :forward suffixes

Forward means the direction in which the way is drawn in OpenStreetMap, while backward means the opposite direction.

Example:
  highway=tertiary
  lanes=5
  lanes:forward=3   
  lanes:backward=2

In the image below, the number of lanes is two - lanes=2. Orange line is the center line of bidirectional way which is the main way direction. When the extra lane starts in a bidirectional way, that segment is tagged as lanes=3+lanes:forward=2+lanes:backward=1. Optionally, we specify placement of the lanes relative to the way.

The below image have two tagging variants:

1. lanes=2 - 1 lane for each direction, or
2. lanes=3 - denote middle lane for left turn as (:point_left: this is discussed)

highway=residential
lanes=3
lanes:forward=1
lanes:backward=1
lanes:both_ways=1
turn:lanes:both_ways=left

IN case the number of lanes is even but numbers of lanes for each direction not equal. 👇

Turn lanes have an influence on the path finding and are one of the most vital components for proper guidance. Choosing the correct turn lane can have a big influence in navigation. Oftentimes, they only help to illustrate a turn better but other times, they are vitally important. In guidance, the aim is to provide a set of instructions, like keep right or keep left by describing the optimum route found by the routing algorithm to a driver.

How a driver views turn lanes from the car. For a single direction way, it will be tagged turn:lanes=left|left;through while for a bidirectional way it will be tagged turn:lanes:forward/turn:lanes:backward=left|left|through depending upon OpenStreetMap way direction

There are three turn lanes tags in OpenStreetMap:

turn:lanes=*
turn:lanes:forward=*
turn:lanes:backward=*

Turn lanes can be mapped from high-resolution satellite imagery sources and street level photos. An example of the high density turn lane area in OpenStreetMap is Los Angeles. This overpass query can be used to extract turn lanes data from OpenStreetMap

Mapping guide for mapping turn lanes: This is a detailed mapping guide for adding turn lanes in general with specific focus on the US. It will be updated as more and more countries are mapped for lane information in OpenStreetMap.

--

The other important attributes in besides turn:lanes and exit/destination data required to provide the better guidance using OpenStreetMap data are:

lanes=*
name=*
ref=*
relation:route

Information for lanes, highway names, highway ref and relation:route can be found in their respective OpenStreetMap wikis.