How does the software evaluate route choices?
Potential alternative routes on a leg are retrieved for the routing engine used by StreetO. When evaluating a course leg, the routing engine can return up to 10 different ways of getting from the start to the end of the leg.
Some of these alternatives are better, i.e. quicker, than others, and the engine will always identify the best alternative.
However, one of the things that we are looking for during course evolution is good route choice options on a leg.
So, ideally, we don’t just one way of navigating the leg, but two or three options that are nearly as good as the best alternative, leaving it up to the orienteer to decide which one to take whilst out on the course.
The issue for the software is identifying what constitutes a valid alternative route choice. It needs to be sufficiently dissimilar to the other alternatives to be considered a valid choice.
When a route choice option takes you along different paths and down different roads than the other options do, then it is probably a valid alternative route choice.
However, what constitutes different paths and different roads is not always easy to determine from OpenStreetMap data in urban environments.
In Urban areas, roads often have pavements/sidewalks/footpaths adjacent to them for pedestrians to use.
There are two separate schemes that Open Street Map contributors use to document these roads:
- Sidewalk as a refinement to a highway
- Sidewalk as a separate way
The preferred mapping option to use is largely driven by regional norms.
See this article for more information on these two schemes.
Consider these two streets:
and
These are basically the same kind of street, tertiary road with a sidewalk on both sides.
However, they are mapped differently.
and
The first, an Australian street, is mapped with the sidewalks as separate ways. The second, a UK street, is mapped with the sidewalks as a refinement to the highway. The sidewalk on the right is only mapped separately, when it veers away from the route of the highway.
From an orienteering route choice point of view the fact that there are sidewalks implies that this route would be safe to take, but there is probably no real route choice decision associated with whether you run down the sidewalk on the left or the sidewalk on the right, where these roads form part of the route to your next control.
This was causing problems for the StreetO algorithm, it used to see the first example as three separate route choice options. This has been fixed in the recent Beta4 release.
We need to consider route geographical similarity rather than considering just the path/track or highway that the route travels along.
Based on the research described in this article, StreetO now evaluates route choices based on whether they follow or deviate from the locations taken along other routes.
This is described below.
The Graphhopper routing engine used by the StreeetO software returns a list of possible routes between two locations. For StreetO, the locations are the control sites marking the beginning and end of a leg on a course.
Each individual route is described as a list of points requiring a navigational action, and the location of those points.
The algorithm breaks the area between the first control and the second control into a rectangular grid of cells, by default 10 meters across, but this is configurable, and maps the Graphopper route points into that grid.
For Example:
Next the algorithm interpolates the route points on the grid to make a path
Then the path is dilated to make a path that is a bit wider than the actual route.
This is done for all the potential route options returned from the Graphhopper routing engine.
Then the dilated routes are compared against each other and those occupying largely the same cells are considered to be equivalent routes rather than an actual alternative route.
This option, for example, can be seen to go more ‘up and around’ that the original dilated track which is more ‘straight across’. Only a minority of the dilated points are common to both traces, largely those near the start and the end of the track, and so this trace is probably a valid alternative route choice option when compared against the original trace.
Fuzzing the route in this way gets rid of the ‘sidewalks mapped as separate ways’ issue described above. Whether you take the left sidewalk or the right sidewalk, or even start on the left then cross the road and continue on the right, the dilated route traces of these option will still largely occupy the same cells of the grid, and so these can be discarded as not real options.