Are there any examples of orienteering (off-trail) route-finding software?

Question

Route-finding software is common nowadays. For example, you can use Google Maps to navigate from one town to another. It's even possible to use apps like Gaia GPS to plan a route between two points along mapped trails. However, I have not been able to find software that will estimate the best foot route between two points in an area with no trails. I have tried searching online, and I looked through this list of software compiled by the Institute of Orienteeering.

Answer 1

tldr; No.

I am looking at doing this by using LIDAR information and coding it in R.(For both human and robot use.) IMHO you need a data/map resolution of 1m (9 points / m^2) at most with vegetation density ranging from open to impassable. I feel it would also be best to use a hex based GIS system (location and altitude) to aid with route planning. Each cell will need a slope derived from surrounding hexes and vegetation thickness attribute. You can then assign an 'effort' to traverse the hex, modify it by surface reflectance intensity of the cell to indicate underfoot roughness and an exit edge. Once you have this setup it is relatively easy to use existing libraries for route planning. The big challenge is firstly extracting accurate vegetation density from the LIDAR LAS files. This can be done manually using OCAD or Karttapullautin software however you then need to convert this into useful digital data rather than just an image (good for O maps) which isn't an accurate approach. So that will probably need new code using existing LIDAR/GIS libraries and a fair bit of fieldwork to check a calibrate the results. These results will also need to be local to typical vegetation types in certain climates etc. E.G Australian forest is different to UK forest, trust me , I've run through both with the same Orienteering shade (white/green) and they are not the same!

There is some research in the military however it is classified however I have not seen anything I would rate as useful for cross country foot movement. I am sure that some of the mobile robot companies would be working on it but if they are they are also keeping it very close to their chest as I've looked too, the ones I have dealt with had nothing although it is clear their are using vision/LIDAR in a dynamic sense for local path planning.(Which is slow and rubbish in the bush.) I have only seen urban route planning with the map cells basically being flagged passable/not passable. The handful of people who do the path planning for the Mars rovers might also be useful contacts however I haven't seen anything really advanced/automatic with the method they use. Still seems quite manual. The real key issue is lack of suitable maps at a 1m resolution with vegetation density and how to create them with the end use in mind.

Answer 2

This is a hard problem.

First you have to define "best".

• In open terrain, not too steep, it's easy - just a straight line, and handheld mapless GPSs have been able to do that for 20+ years.
• Add hills, and different people on different surfaces have different maximum gradients so choose different zig-zag courses. Still it might be possible to come up with something if you know whether you've got grass, moorland, scree, or solid rock (for example). Already though, eyes on the ground are going to be necessary, as a slope you could walk up on average can often have scrambly bits.
• Add impassable (but whose idea of impassable?) stuff like boulders, bogs or vegetation, and the level of detail such software would need increases dramatically. Bogs and vegetation change seasonally too; shrubs may have grown since the area was surveyed, and you may or may not have the means and rights to cut it.

Most free tools are based on OpenStreetMap data, which is usually good but you'd need micromapping of every little outcrop and thicket for it to help here. And that means people in the field, with a lot of time on their hands.

The best in practice is to get your device or mapping software to plot a straight line between points (I use Komoot for hiking and mountain biking as well as running and road cycling; it can plot off-track sections as straight lines by deselecting the default "follow ways" option). Then you do your best to follow the general direction of the line, using your own senses. In some places this is true even if trying to follow a mapped path. I had an example at New Year where none of us could find the path on the ground. Anything that looked like a path soon became the track of a creature that could fit under thorny bushes.

Answer 3

This is called a least-cost or least-cost-path analysis. The quality of the analysis is dependent on the quality of the input data. For example, a 1km x 1km pixel surface model would be unsuited for a walking cost path analysis where a 1m x 1m pixel surface model would. Similarly other data could be incorporated such as land use and land cover, slope surface, aspect surfaces (easier to hike up a south facing snow-free hill), barrier data such as rivers or private lands. Also, some assumptions bias the analysis depending on the analysts (maybe the analyst thinks it's easier to travel though wetlands than brambles and codes the algorithm that way).

As you can imagine, a cost surface is difficult to generate and requires a geo-spatial professional, GIS software, and a sporting computer. See here for an example of a cost path analysis.

Answer 4

Although I haven't used it for a while, I found that bikemap.net does a fairly good job in planning routes even if no official, marked trail is available. It will not plan a route across a forest for you, but it recognizes paths to a greater granularity than Google Maps would. It is based on OpenStreetMaps.

Mapy.cz has a functionality to plan a walk for you literally from anywhere to anywhere, but it only takes roads/paths into consideration.