Register | Login
Attackpoint - performance and training tools for orienteering athletes

Discussion: Heuristics in Route Choice Making

in: Orienteering; General

Apr 23, 2020 7:59 AM # 
aviadfuchs:
I've been spending quite a lot of time on Webroute recently and after seeing so many different variations for possible routes I started wondering -

How do orienteers estimate and compare the length of a route in comparison to all other possible routes? What kind of heuristics help in the process?

Assuming that we are looking at only two curved lines (possible routes), just for simplifying things, what is the best and fastest way to estimate the length of each route? Please note, I'm excluding all other factors from the equation and talking only about distance/length.

A few insights -

Integrals - summing the area in between the possible route and the line between the controls - probably won't work. Even if the confined area is smaller, it still depends on the curvature of the route.

Using a thread - a slow method, not efficient during in race conditions.

Arc Length calculations - not fast enough + this is not a math exam, right?

Any ideas? Any rules of thumb that I could use?

One quick heuristic - going around, in a perfect half circle route, rather than going straight, is 50% longer (you can do the math). Of course, there are very rare instances that we actually move this way.

a more advanced question - how do you factor in elevation changes, which add distance?

One good example is here - comparing routes that go north of the line or south of it.

Thanks and stay healthy!
Advertisement  
Apr 23, 2020 8:34 AM # 
gruver:
I'd go back a step and first see if there are THREE feasible routes (L, R and straight-ish). In urban areas and MTBO some of us need to take the blinkers off to going backwards out of the start. However successive comparison rapidly leads to aviadfuchs' problem, as stated.

I'll let others come up with their technique for choosing the shorter out of two. I'm not too good at it, although getting going on any feasible route is a reasonable rule for fastest as opposed to shortest.
Apr 23, 2020 8:59 AM # 
Terje Mathisen:
I'll second gruver here: Most of the time you want to make a fast decision instead of spending a lot of time to potentially finding a faster route. It is definitely the case that route selection is a hard problem! I like to consider this the same way I think about program optimization, i.e.I am pretending to be like a ray of light passing through various materials (air/glass/plastics/water) and always finding the shortest optical path. At the micro level this means that you need to apply something like Snell's law when deciding which angle you should cross a green patch to get to the path on the other side.

At the macro level I know that elevation costs are typically in the 5-10X, with 7X a good estimate: I.e. each meter of ascent takes the same time as 7m of flat running. This is however very dependent on how long each climb is, i.e. a bunch of 3-5 m climbs up and down in an undulating landscape cost less than the same total climb up a single hill.

During the current month+ run of Jan Kocbach's WorldOfO's Route-To-O-Season I've been very happy to maintain an 80-90% hit rate on finding the fastest route. :-)

BTW, much of the formal knowledge on route finding started with Eystein Weltzien's thesis work on the subject. One particular finding which is still very relevant is the fact that when you have two routes, one ending with a sharp climb into the control and another which ends going flat/downhill, you really have to consider the time to the next control as well! Even for Norwegian national team runners (which at the time were the strongest in the world, at least on the mens' side), they all get a bit slower after a big climb.
Apr 23, 2020 10:09 AM # 
gruver:
Ahh Snells Law! I once tackled the problem of the optimum angle via geometry and calculus, and was amazed when I came up with something like cos(theta)=v2/v1.It put a theoretical basis on what was previously a "gut reaction".

I think that what helps is lots of these exercises, and I love during live coverage of events to try and sort out my route choice before the first of the dots gets there. They train the gut reaction, but I'm sure it is helped by thinking about geometry too.
Apr 23, 2020 1:48 PM # 
mikeminium:
The individual decision also has to factor in the runner's navigational abilities, strengths and weaknesses, and any prior knowledge of the terrain. One might consider the trade off, for example between taking a chance on an intensely difficult bit of navigation that might be faster if perfectly executed, versus a slightly longer route that is safer and more certain. And you might make a different choice about that trade-off in a qualifier race (safer) versus a world championship final (your only chance is to take the greater risk / higher reward).

Or perhaps the slightly longer route has a far superior attack point. You've also got to make judgements about density of vegetation, likely quality of footing and the speed over which it can be traveled.
Apr 23, 2020 4:10 PM # 
Terje Mathisen:
TG once stated that "It is not on a great day you win the WOC, it is on an average day."

I.e. you cannot depend on having that once-in-a-lifetime performance in a WOC final race, you have to be good enough that your normal performance is enough. This includes taking your normal mostly non-risky route choices (or orienteer so well technically that you can reduce the risk factors to an acceptable level) since there are so many opportunities to mess up on a championship race: You cannot take more than usual risks here and still have any hope to hit them all.
Apr 23, 2020 11:46 PM # 
aviadfuchs:
Thanks for your replies everyone - there are indeed plenty of considerations in choosing a route and I also liked the Snell's law approach for crossing green patches but I'd like to come back to my initial question, and focus only on one factor of choosing a route:

Is there any fast way to visually compare between the lengths of two route options other than just your experience and using a "mental" thread to straighten these lines up and compare their lengths in your mind?

I go back to my example - going around, in a perfect half circle route, rather than going straight, is 50% longer. That's a good rule of thumb. Any other tricks?
Apr 24, 2020 12:20 AM # 
jjcote:
Zigzagging back and forth over the purple line can be as long as a big detour that doesn't zigzag (taxicab geometry).
Apr 24, 2020 2:01 AM # 
gruver:
I'm guilty of mentioning "fastest" as opposed to first finding "shortest" - sorry. Is there a website with lots of alternative routes shown with distances (to shortcut us having to contribute examples)? Some will be obvious but we might be able to learn from those surprising ones where the "quick guess" does not give the shortest. Study of which might produce the "rules" we are seeking. JJ's zig-zag warning is one such rule.

@aviadfuchs, do you think we should consider forest orienteering separately from sprint/MTBO where the choices are often discrete rather than continuously variable? Since you started the discussion, where's your main interest?
Apr 24, 2020 8:13 PM # 
Terje Mathisen:
@gruver: I agree that focusing on shortest is almost always street-O related, it is very rare to get forest legs where relative distances aren't either obvious, or so close that other issues like having a good attack point or amount of path running should decide the issue.

On sprints the hardest to judge for me are routes where you either have to run past the control, around a corner/fence/wall and back again, vs one where you go quite a long distance off to the side: The only thing that helps here is to study as many as possible of the sprint course analyses shown on WorldOfO. When the relative differences are small I'm quite often wrong, i.e. I'll pick the second-shortest believing it to be the shortest.

PS. On today's Route-To-O-season I matched Gustav Bergman's route exactly. :-)
Apr 25, 2020 9:34 AM # 
tRicky:
One quick heuristic - going around, in a perfect half circle route, rather than going straight, is 50% longer (you can do the math).

You know, I did do the math(s) on this and my recollection of calculating the circumference of a circle from way back in primary school was (2πR) so a half circle would be (πR). If you had a straight line that was 1km, the calculation for half the circumference of the rounded route would be 3.1416 x 0.5 = 1.57km so it's actually 57% longer. Not sure if you were rounding down but I'm being technical.
Apr 25, 2020 10:25 AM # 
blairtrewin:
Except possibly in Indiana.
Apr 25, 2020 4:19 PM # 
Aragorn:
Not only does that bill imply pi=3.2, it also implies that sqrt(2) is both 10/7 and 7/5.
I’m so proud of my state.
Apr 25, 2020 5:58 PM # 
yurets:
@ blairtrewin, in mid-Kentucky they may become very aggressive if you mention this bill. Once I made a mistake of saying that the first human in space was not an American.
Apr 25, 2020 7:52 PM # 
Terje Mathisen:
@Aragorn: You should be proud, taking the average of those two values (1.42857142857 + 1.4)/2 = 1.4142857 is in fact pretty good, good enough for nearly all engineering purposes. (The error is just 72 parts per million)

If you adjust the weighting slightly away from 50/50 it can be exactly right, you just have to chose your weights very carefully. :-)
Apr 25, 2020 8:38 PM # 
Ansgar:
If you use geometric instead of arithmetic mean of the two fractions, you get the exact value...
Apr 25, 2020 9:53 PM # 
Terje Mathisen:
@Ansgar: As in sqrt(10/7 * 7/5) == sqrt(2)? :-)
Apr 26, 2020 5:48 AM # 
aviadfuchs:
@gruver: I was aiming for Foot-O, not in urban areas, since we're usually dealing with routes that are more curvy, and for me at least, are harder to compare than a few connected straight sections. Sprint-O and MTBO are definitely relevant for the discussion though.

@tRicky: I was rounding down of course however thinking of it as "a little bit more than 50%" would probably be a more accurate heuristic to use. Also - loved the discussion that followed..:-)

The more I look into that, and I've searched around, I feel that the best way is probably to plot a few examples, "store" mental images of them and use when needed. If anyone has other suggestions or insights, I'd love to hear. Thanks guys!
Apr 26, 2020 11:19 AM # 
gruver:
Do you think it would help to know a few reciprocals? Eg the short section looks like it could take 25% off my speed so I could go 1/.75 equals 33% further.

And learn some cosine values. We instinctively know that as v2/v1 tends to zero (the green gets very thick) the angle tends to 90 degrees. What actually is the angle for the above 75% case? (I think its 41 degrees). Maybe drawing the triangle for a few different speeds would help.
Apr 26, 2020 2:02 PM # 
simmo:
If you use Thierry Guergiou's full speed, no mistakes method, then there are probably fewer route choices - maybe only one - and their relative distance is largely irrelevant.
Apr 26, 2020 4:02 PM # 
ccsteve:
Very non-scientific method here -but you asked for heuristics...

It's an eyeballed estimate with 3 seconds to come up with a hypothesis and then a few more to confirm it. (while moving)

The difference is the left/right movement on the way to the control. Less total distance "off" the line is shorter. When it goes back and forth, estimate the sum of those. The shorter tent pole is the shorter route.

[and then you factor in other things like climb, terrain/vegetation, and ease of navigation as mentioned...]

Let me go one further - how about coming up with a best path for score-O event?-) I consider my skills in finding a path that maximizes points on a fixed duration to be better than average;)
Apr 26, 2020 8:16 PM # 
Terje Mathisen:
@ccsteve: Score-O/Points-O where you want to visit the maximum number of controls/points in a given time is a very interesting programming problem.

As you almost certainly know, the simple form, just visit all the controls, is the travelling salesman problem, but with an arbitrary number of intermediate points/cities, i.e. you must be able to calculate the cost/time of the best route choice for all relevant pairs of controls. This is an NP-complete problem and therefore impossible to solve exactly for larger numbers of controls, but in reality it is far easier:

You mentioned that you seem to better than most doing this, I find that the number of real alternatives are very often quite limited: You start by guesstimating approximately how large an area you can cover, then you design a route which is adjustable, both so that you can extend it with a few extra controls far away or shorten it by skipping one or more low-value controls closer to the finish area.

Besides this you just let the terrain designate clusters of controls reasonably close to each other and then you need to stitch these clusters together.

BTW, I do this all the time when I'm the course setter (6-10 times/year), in that I always design a special "put out the controls" course which should minimize the time needed, and which starts with the densest group of controls so that I can get rid of as many flags and control units as early as possible. :-)
Apr 26, 2020 10:55 PM # 
gruver:
Haha, the travelling salesman problem with a speed increasing as you "make sales". Or at the other end of the day, a reducing speed.

Rule of thumb: If the short route is (say) 25% slower running than "normal", then a 25% longer route will be BETTER.

Apr 27, 2020 12:43 AM # 
jjcote:
I remember solving essentially that same problem back in the summer of 1978, although it was presented as finding the best angle to run at in order to get out of the way of a herd of stampeding animals moving faster than you.
Apr 27, 2020 1:02 AM # 
blairtrewin:
Coming from Australia where on a lot of areas, near straight is a good option, steep central European terrain was a culture shock: it was an eye-opener on the WOC 1995 training camp in Germany to do a test (on an area with a flat top and deep green valleys off the sides) where Warren Key went straight and I did a road route around, and he did almost the same time for 1.5km straight as I did for 4km around (and the balance would have shifted even more towards the road for someone whose strength was in running speed, which mine definitely isn't).
Apr 27, 2020 1:56 AM # 
slow-twitch:
How do orienteers estimate and compare the length of a route in comparison to all other possible routes? What kind of heuristics help in the process?

Assuming that we are looking at only two curved lines (possible routes), just for simplifying things, what is the best and fastest way to estimate the length of each route?


In the context of during a race, even in a long distance race where there's more time to invest in route choice decisions compared to sprints, I think the answer has to be 'gut feel'. But many of the ideas discussed here would be worthwhile exercises outside of the race context - to help train your gut (or instincts if you prefer) to the point that you're confident that the first options you see when you look at a leg are the better ones, and also confident that the one you select 'under pressure', not being conscious of the calculations that are going on to make that choice, is mostly going to be the same as the one you'd select 'from the armchair'.
Apr 27, 2020 3:10 AM # 
ccsteve:
@Terje - Essential agreement. I did get advice early on that the very first calculation needs to be - can all these controls be cleared? If the answer is yes, it breaks down to finding an optimal route. If the answer is no, then there's a guestimation of "how many", and how to leave a good reserve at the end to either get more, or get less to match the time left.

I also set controls with the same sort of methodology. Sometimes in successive "reload at the start/finish" where supplies are. One early morning I strategically left caches of controls and then completed a circuit re-supplying at the pre-dropped off points.

And @aviadfuchs: do not think that distance alone is the gating factor. I don't think you can ignore the other aspects that go into the calculation. I was not far into the sport when one afternoon I found myself with kids and a first control that was up and over a rather large hill. Took the kids around on a trail and had one of the better splits for the day even though we were walking. It has to be a weighted distance.
Apr 27, 2020 8:21 AM # 
Terje Mathisen:
Here's a little challenge: Pick your routes over this Long training event that's open here in Oslo this week:
https://eventor.orientering.no/Events/Show/12926?f...
The map itself is here:
https://eventor.orientering.no/Documents/Event/217...

Some more info: The white forest, particularly the NE part, is very nice but the heather is normally quite high, marshes can be quite wet but are probably OK now, green stony hill and cliff sides are basically no-go zones.
Apr 30, 2020 11:47 AM # 
ccsteve:
I'll play;-)

I think you mean 2-3, it's the longest, but there are other long legs - btw - I am a bit jealous...

I evaluated straight, left, and right in that order. Straight ruled out for me as crossing no less than three steep gorges and other intricacies. Left deemed passable in the sense that there's a distinct climb to the control, but hesitation as there is a lengthy descent to the road. Right the winner - there's a darned trail covering 2/3rds of the distance that is quite attainable, it doesn't include much climb, and the final portion is specifically defined by the water to reach the control. ~30 sec effort.

I also like that the right path goes through terrain that will be used later and right by some controls to add scouting for those efforts.

I don't know the interpretation of the map nuances, and as a course setter like that this leg is close to the beginning to challenge before people have worked out things.

[Post-note - I consider myself visually impaired in that I have to wear reading glasses (safety glasses with a reading portion). Doing this in the comfort of my home is not the same as actually noticing things in-course... But I like that I seem to know what I'm looking for;-]
Apr 30, 2020 12:28 PM # 
Terje Mathisen:
Anders Nordberg, our coach and of course former WOC runner have done it, along with a more human runner. He found a sneaky almost direct route from 2 to 3 with very little climb, personally I would have done as you suggested, i.e. gone right to the paths at some point. There's a bunch of more route issues though, pretty much all the longer legs!
BTW, Anders gained international recognition along with Thierry G and Michal Smola when they stopped to help their Swedish competitor Martin Johansson on the final leg of the 2009 relay. All three of them received several awards for good sportmanship, including the International Fair Play Award in 2010.
Apr 30, 2020 8:58 PM # 
Terje Mathisen:
Re. maximum arc lengths possible when running on roads instead of tough terrain, see the article and comments in today's route to o-season:
http://news.worldofo.com/2020/04/30/route-to-o-sea...
:-)

Please login to add a message.