3

My application finds or constructs routes that are shortest for trekkers in a hilly/mountain terrain using the A* search algorithm. Input files are .dem (Digital Elevation Model) and a roadmap file that contains existing routes. Code is in Python, libraries used are pygdal, NumPy and PyQGIS.

The routes provided by the algorithm are very steep. I want my route to follow the gradient guidelines, for every 30m only 1m of elevation. A* finds the shortest route from peak to valley in a straight line, which is not practical. Output should descend from one contour line to another at less than 1.91 degrees.

user4157124
  • 2,809
  • 13
  • 27
  • 42
Navneet Srivastava
  • 933
  • 2
  • 9
  • 14
  • 1
    Don't include edges that are that steep in the graph.... – BlueRaja - Danny Pflughoeft Jul 06 '23 at 00:40
  • 5
    It would probably be better to weight the steep routes to make them very expensive that way it may still be possible to utilize a steep gradient in order to complete an otherwise impossible route. – DavidT Jul 06 '23 at 00:51
  • 1
    (Up-voted not for the presentation, but for a problem I can relate to.) – greybeard Aug 16 '23 at 05:14
  • Please edit your question and add a concrete and simple input example where your algorithm fails to find the path you want to find, and what you expected to find. – trincot Aug 17 '23 at 12:20

2 Answers2

2

I want the output should descent from one contour line to another at less that a particular angle so that the descent is not so steep. In this case the recommended gradient descent is 1.91 degrees.

  • Create graph from map
  • Remove all links that are steeper than 1.91 degrees
  • Find path through graph in usual way
desertnaut
  • 57,590
  • 26
  • 140
  • 166
ravenspoint
  • 19,093
  • 6
  • 57
  • 103
1

All-Paths ( practical alternative to A* )

Your question has so few details, it is impossible to give a detailed or complete answer.

I will assume that you are trying to minimize the distance walked AND the "steepness".

The distance is straightforward.

The "steepness" measure needs to be clarified. Do you want to minimize the total change of elevation during a walk? Minimize the maximum rate of elevation change? Minimize the average rate of elevation change? Or some other statistic?

Finally, you have to decide what is the trade off between distance walked and "steepness"

Let:

D be the total distance
S be the "steepness" statistic you have chosen
t be the amount of "steepness" you will accept to reduce D by one unit

then you want

minimum C = D + t * S       Eq 1

The algorithm goes:

- Construct a graph of the possible routes from the roadmap
- Use standard graph algorithm to find all paths between start and destination
- Apply Eq 1 to paths as they are found.
- Select path with smallest C value so far

FYI you can have look at the C++ code implementing a simple version of this at https://github.com/JamesBremner/LazyHillWalker

Performance

Run time for running the All Paths algorithm to find all the paths between two randomly selected vertices on large graphs downloaded from https://dyngraphlab.github.io/. Longest result from 3 runs using the graphex application.

Vertex Count Edge Count Run time ( secs )
4,700 27,000 20

Complete application details at https://github.com/JamesBremner/PathFinder/wiki/All-Paths#performance

A* Snags

The OP has proposed using the A* algorithm. I consider A* suitable only for small, simple problems for two reasons.

  1. A* is very expensive in memory. So not very practical for large, real world problems ( > 10,000 nodes ) "One major practical drawback is the A*'s O(b^d) space complexity, as it stores all generated nodes in memory" https://en.wikipedia.org/wiki/A*_search_algorithm

  2. A* is concerned only with individual links from the start to the current node and from the current node to the goal. If the steepness statistic is chosen as a measure based on the entire path ( e.g. maximum or average elevation change per unit distance ) then formulating the A* helper functions ( a heuristic to estimate the cost of the remaining path from current vertex, and a true measure of the cost of the cheapest path to the current vertex. ) will be a challenge.

Missing details from question:

  • Do you want to select the optimum possible path, or do you want to get all the paths that meet a strict limit? Please answer 'yes' or 'no'

  • Do you want to minimize a combination of distance and steepness. Please answer 'yes' or 'no'

  • Please clarify how you calculate steepness. Please answer by giving an example of a short path and show hoy you calculate its distance

  • How large is your input graph. Please answer with vertex and edge counts.

ravenspoint
  • 19,093
  • 6
  • 57
  • 103
  • 1
    Don't "construct a graph of the possible routes," use A* but include the steepness in the cost heuristic. You're suggesting throwing out A* in favor of considering all paths which, for a map of any decent size, would be infeasible. The whole point of A* is to NOT have to look at all possible paths. – David Conrad Jul 06 '23 at 15:55
  • @DavidConrad A* is extremely expensive, especially of memory. However the real killer here is that A* can only look at the costs of individual edges. This question needs to look at the total "steepness statistic" of the path as a whole. I have found that the method I have described works well in practice on this sort of problem and can handle graphs with tens of thousands of nodes in a few seconds. It is a pity the OP has provided so few details, so we could discuss this in more concrete terms. – ravenspoint Jul 06 '23 at 16:12
  • 2
    A* is not limited to looking at costs of individual edges. For each node there is a heuristic estimate of the cost from that node to the destination. Also, I don't see how A* could be more memory expensive than having a list of all possible routes in memory. – David Conrad Jul 06 '23 at 16:40
  • I think you misunderstand my algorithm. There is no need to store the paths in memory, just the path found so far with the lowest C. – ravenspoint Jul 06 '23 at 16:51
  • A* needs two functions: a heuristic to estimate the cost of the remaining path from current vertex, and a true measure of the cost of the cheapest path to the current vertex. Assuming, as I have, that the OP want to minimize a steepness statistic calculated on the entire path ( e.g. average or maximum change in elevation per unit distance ) how would either the heuristic or the exact measurement of path so far be formulated? – ravenspoint Jul 06 '23 at 17:03
  • There are [different approaches](https://stackoverflow.com/questions/1012691/a-heuristic-overestimation-underestimation) but one way to estimate the heuristic would be to consider a straight path from the current point to the destination and take into account the change in elevation there. As long as the heuristic is [not an overestimate](https://cs.stackexchange.com/questions/30778/why-is-the-a-search-heuristic-optimal-even-if-it-underestimates-costs) A* will find the optimal path. – David Conrad Jul 06 '23 at 17:29
  • The straight line path may go over the top of Mt Everest and give a wild overestimate. – ravenspoint Jul 06 '23 at 17:34
  • I do not understand why this seems so controversial Right in the very first paragraph of the Wikipedia article on A* it tells us: " in practical travel-routing systems, A* is generally outperformed by algorithms that can pre-process the graph to attain better performance" – ravenspoint Jul 06 '23 at 17:39
  • @ravenspoint I would like to minimize the average rate of change of steepness. Also, I want to implement gradient guidelines, which is if I walk 30m horizontally, I can only achieve elevation of 1 m and not more than that. It's like rather going straight, the route should follow the contours to reach end point. Each pixel represents a Elevation value above mean sea level. – Navneet Srivastava Jul 06 '23 at 18:29
  • @ravenspoint Can you explain this minimum C = D + t * S Eq 1 Also, what are other alternatives that can be followed other than A* – Navneet Srivastava Jul 06 '23 at 18:53
  • If you read my answer, I have described an alternative to A* – ravenspoint Jul 06 '23 at 18:54
  • " not more than that" This suggests that if there is no path that meets this limit, you want to reject all paths, return the answer "NO PATH". Is that what you want? Please edit your question to clarify these points. Do not bury important details in comments – ravenspoint Jul 06 '23 at 19:04
  • If I could put my objective in a more simpler way, then it is that using A* I can find the shortest route, but the problem with that it finds path from one peak of the mountain to the valley in a straight line, which is not practical. I want the output should descent from one contour line to another at a particular angle so that the descent is not so steep. – Navneet Srivastava Jul 06 '23 at 19:07
  • @ravenspoint For your questions 1. I want to get all the paths that meet a strict limit 2. Yes 3. I calculate steepness as following: Suppose there are two points A and B. The Elevation at point A is 1000m and at B is 1005m w.r.t. mean sea level The horizontal distance between the two points is 30m. So the gradient in degrees would be arctan(1005 - 1000)/ 30 = 9.46. 3. The matrix is of quite a large size, as it represents a 5km * 5km area. Currently I have used matrix, where its coordinates represents the location, its value represents elevation, which is used as weight – Navneet Srivastava Aug 15 '23 at 19:01
  • OK, that matches with what I assumed. What prevents you from accepting my answer? – ravenspoint Aug 15 '23 at 20:15
  • When applying your solution I was not able to find path between the two hills, as the elevation difference between two pixel is generally higher. I even tried this solution https://github.com/navneetercse/smooth-shortest-path , It also did not work out. Another approach I could think of is first finding the route without applying gradient threshold and then changing the output vector to follow the contours. Now the problem is I am not able to think of solution how should I approach its implementation. – Navneet Srivastava Aug 16 '23 at 18:04
  • " elevation difference between two pixel is generally higher. " Higher than what? – ravenspoint Aug 16 '23 at 22:43