Driving Direction Instructions

The question of natural language driving directions gets raised on a regular basis regarding pgRouting. I have done some work in this area and explained it on the list few times so I thought is would be useful to put my thoughts here in the wiki. -Stephen Woodbridge

Why don't we have driving directions?

In general this is a hard problem to solve in a generic way that will support random user data sets and the need for multiple languages on output. Many of the ideas here have evolved to deal with some of those problems.

How can we approach this problem?

Lets start with a big picture view of the problem.

1. we get a list of edges as output from the routing code
2. we need to analyze this list and transform it into a list of maneuvers
3. we need to turn the maneuvers into natural language instructions

What is a maneuver?

If you go to OSRM maps or google maps and generate a bunch of maps and abstract the instructions you will see that they can be grouped into N number of common phrases. Any single instruction is informing the reader that something is changing on their route path, like: a turn, a street name, departing or arriving, etc. The following are a list of maneuvers used by OSRM, you have have more or less for your needs:

No Turn
Go Straight
Turn Slight Right
Turn Right
Turn Sharp Right
UTurn
Turn Sharp Left
Turn Left
Turn Slight Left
Reach Via Point
Head On (Compass heading)
Enter Round About
Leave Round About
Stay On Round About
Start At End Of Street
Reached Your Destination
Enter Against Allowed Direction
Leave Against Allowed Direction
Access Restriction Flag
Inverse Access Restriction Flag

One could define a maneuver as a Postgresql Type. The following is an extension of the OSRM maneuver:

create type maneuver (
        rid integer,        -- route id inscase there are multiple routes
        seq integer,        -- seq number for maneuver to force order by
        direction integer,  -- maneuver identifier
        name text,          -- name of street
        meters integer,     -- distance to next maneuver
        "position" integer, -- index into array of points indicating the lat/long position of the maneuver
        "time" integer,     -- time in seconds to next maneuver
        length text,        -- distance with "m" or "km" appended
        dir text,           -- direction abbreviation (N|S|E|W|NW|...)
        azimuth float       -- compass heading in degrees (north as zero)
);

How do we convert segments into maneuvers?

There are a bunch of things that need to be done to convert segments into maneuvers. Here is a list that I came up with:

1. reorder the direction of edge geometry so it flows from start to end
2. compare segment names so we can aggregate multiple adjacent segments with the same name into a single maneuver.
3. compute the turn angles between segments when we are making a turn
4. counting roundabout exits from our entrance point
5. identify a via point
6. check for some degenerate cases like the whole route is on a single segment

Here is some pseudo-code that might help for items 1-3:

open cursor to results

first = true
last = fetch cursor

while (this = fetch cursor) {
   if (first) {
     check which end of last is connected to this
     flip last if needed
     trim the segment to the start point if needed
     first = false
   }
   if ( this needs to be flipped ) {
     flip this
   }
   compute azimuth of end of last and beginning of this
   turn = the change in direction
   ...
   if (last.name = this.name) {
     join this to last to compress out an extraneous maneuver
   }
}

this is the final segment in the route
trim it to the end point if needed.

close the cursor

How do we explicate the maneuvers into a natural language?

There are probably a lot of ways to do this step but they depend on the generation of maneuvers. I've identified a bunch of maneuvers above used by OSRM, but they can get far more complex when using some of the commercial dataset like Navteq ot TeleAtlas data.

OSRM returns a set of maneuvers, that the client is responsible for explicating. This works well given that there is javascript code to do the explication in the language needed. This can be done by providing a javascript library that can be extended for various languages. This also off loads the server from having to deal with this and means that new languages can be added by extending the javasscript library.

I have implemented an in database explicator, that selects a schema for a language, and uses a template to convert maneuvers into instructions. One can easily add a new language be creating a new schema and and have the instruction templates converted to that language.

If someone wants to work on this or fund this, please let us know.

Thanks, -Stephen Woodbridge