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.
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.
One interesting approach could be to correlate existing trails to geographic features - after all, they are paths that people have found useful. Maybe machine learning could find some rules.– jpaFeb 12 at 18:26
I'm accepting this answer as it actually responds to the question in the title, but some others provide nice additional information on why this task is difficult (Chris H) and existing algorithms (GBG). Feb 19 at 22:48
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.
2Agreed. The 5m grid would be needed. Even that could not detect small local impassibilities, so it would need to consider nearby terrain contours too, and find routes with an acceptable width margin to hedge the bets. Feb 9 at 21:15
9"Why did the statistician drown while crossing a river? It was only 3 feet deep...on average."– erfinkFeb 10 at 3:45
2This is an excellent answer, but I feel there is also an ethical issue if you are the developer of such software: if it does a reasonable but not perfect job, you know that it is going to be used by people who do not have the good judgement to know that it is not working out and they need to implement plan B, or even if they do, be unable to figure out what plan B is for their situation. So, should you make it available or not? I don't think there is one right answer.– sdenhamFeb 10 at 4:35
2@sdenham the OpenStreetMap community is going through something similar at the moment. A difficult and indistinct path was mapped, and mapped as a challenging scramble. The app that displayed that data didn't show the difficulty. Some people had to be rescued.– Chris HFeb 10 at 6:42
1(@sdenham) following on from my previous comment: a little about the mapping/rescue debate and a description plus photos of the route involved– Chris HFeb 10 at 8:39
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.
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.
Thank you for making me aware of these tools. But as you say, they don't handle off-trail navigation. Feb 19 at 22:50