Using a landscape raster-based model for optimal route navigation in orienteering sports, velocity related attributes are mapped onto single squares. Both, accelerators and dampeners as well as barriers are taken into consideration. The optimization calculation between points is based on A* while the entire route is calculated by asymmetric traveller salesman problem solutions. Orienteering is an example, where routing is not limited to predefines paths. Foot orienteering is considered the mother of all derivatives in orienteering sports. Primarily, the competitor aims to find the shortest path between two control points (CP) in terms of time consumption. This leads into the question: Where is the right place to leave a given foot path network into vegetation covered countryside? A detailed map (Fig. 1) and compass assist the competitor. Except for restricted areas, any way through rural terrain is valid. Amateur Radio Direction Finding (ARDF), where CPs are hidden transmitters called foxes, extends the competition goal by two dimensions, using a portable direction selective radio receiver: 1. Fox location: The location of CPs within the countryside is not known from the very beginning. However, after five minute running, a competitor has a rough idea about their locations by means of his radio. 2. Fox order: The order in which competitors search for and discover the foxes is entirely at their discretion except for the finish beacon, which shall be registered as the last one of the transmitters.
This contribution focuses on (
Natively, vectored paths are perfect for route optimization problems. However, orienteering offers the entire landscape as competition area. Therefore, a “navigation on areas” approach [2] will be targeted. As ARDF competitions mostly not exceed a race length of 12 km bee line, the relevant part of the map is typically not larger than 3 km by 3 km. At a scale of 1:10.000 this will fit an A3 sheet of paper. 2.1
The types of convex polygons with equal edge length which are sufficient to raster the projection of a surface into regular shapes is limited to triangle, square and hexagon (Fig. 2). For reasons of given data sources, the rectangle will be evaluated as an additional candidate right here.
(a) (b) (c) (d) Having path mapping in mind, the neighbourhood relations of raster fields are important. Starting from a single shape, two types of direct neighbours can be identified: 1. Line neighbour (L): Two adjacent shapes have exactly two corners in common. 2. Corner neighbour (C): Two adjacent shapes have exactly one corner in common. By design, each raster field has the same number of neighbours. Neighbours with the distance one, sharing either one or two corners, should be called first (1st) order neighbours. In other words, L neighbours share one edge. of triangles, i.e. each hexagon can be split into six triangles. In small map scale, a rectangle would perfectly fit to geo-coordinates, as 1 arc sec in Central Europe equals about a size of 20 m by 30 m. However, a square better represents the symmetric resolution for the given problem in latitude and longitude. Therefore, squares are taken for this raster approach model. 2.2
More general the order of neighbourhood is defined as the number of circle-free and outwards first order steps between two selected raster fields. Outwards indicates an increasing distance by each step. Distances are always measured between the centres of squares; see white arrows in Fig. 3.
As distance reference the edge length of a single square is to be considered as a. 1. Line (L) and corner (C) direction extension towards higher order (O) is always commutative regarding distance and direction. 2. Only 8*(O-1) new directions in higher order are potential of interest, as others can be modelled iteratively by lower order without any routing gain. To simplify the methodology for the upcoming sections, only the first order relationship will be applied within this contribution. 3
Orienteering typically takes place in difficult rural areas. There are two factors that heavily influence the speed of the competitor: height differences and the surface coverage e.g., plants or swamp. This information is given to the competitor by a detailed “orienteering map”. For the envisaged approach the information needs to be transferred into the raster model (Section 4). 3.1
Although height information is given by contour lines within the orienteering map, there is a better source to meet the raster approach. The Shuttle Radar Topography Mission (SRTM) has collected earth surface height data by Spacebone Imaging Radar measurements (SIR-C). The data is public available all over the world between 60 degree latitude south and 60 degree latitude north. There are data sets of two resolutions: 1 arc sec and 3 arc sec. The latter is generated by calculating the average of nine SRTMGL1 values1. The access to the SRTMGL1 resolution requires a personal registration. The other sets of Table 4 are subject to instant download.
The sources claim an accuracy of about 6 (DLR) to 12 meters (NASA) [3]. However, height differences of neighbour fields are more important, which imply better results. The data is provided as file of 16-bit-integer numbers in big endian (BE) notation without a header as a bulk for one degree latitude by one degree longitude. Positive values represent heights in meter above mean sea level. Values are arranged from West to East and then North to South. The value “-32768” is reserved for not known height. SRTM Void Filled altitude data are the result of additional processing to address areas of missing data or voids in the SRTM Non-Void Filled set.
There is a unique file naming convention. The tiles are distributed as zip files, containing HGT files labelled with the coordinate of the southwest cell. As an example, looking for the data covering Magdeburg, the file N52E011.hgt is required. 1 Official data source URL: https://lta.cr.usgs.gov/SRTM1Arc
A field of one arc sec by one arc sec equals roughly to a rectangle of 20 m by 30 m in Northern and Central Europe. To symmetrize the map raster, it is proposed to make three squares out of two vertical rectangles. An absolute metric accuracy of the altitude is not required to solve the given problem sufficiently.
There are three types of rectangle R to square S height h transformation as shown in
Fig. 4. For T1 the average of the west (W) and east (E) is calculated (
hS = 1/2*(hR(W)+hR(E))
hS = 1/3*(hR(NW)+hR(NE)) + 1/6*(hR(SW)+hR(SE))
hS = 1/6*(hR(NW)+hR(NE)) + 1/3*(hR(SW)+hR(SE))
(
An orienteering map is a collection of vectored and carefully adjusted objects, either of punctual (0D) type (big single tree, landmark, single rock, …), linear (1D) type (foot path, street, creek, …) or areal (3D) type (meadow, forest, lake, …). A natural area is given a colour and optional pattern attribute which is an indication for the percentage of maximum speed, a competitor typical reaches on ideal paths. All symbols, colours and patterns are standardized by the International Orienteering Federation (IOF) [5].
As punctual objects are mainly required for orientation, they can simply be ignored for later raster attribution, as they do never influence the speed of a competitor. 1D and 2D objects can indicate both, passable and impassable character. While passable objects modify the average speed of a competitor, impassable objects are a rather strong restriction. Linear objects which raise neither one nor other e.g., a high voltage power line are out of interest for raster attribution.
All symbols are standardized in shape, size, colour and pattern. The International Specification for Orienteering Map (ISOM) applies a basic colour scheme, where spot colour printing should be processed in the following order: {White}: Yellow: Green: Grey: Brown: Blue: Black: Purple:
Open forest without ground vegetation Open areas and culture land Natural ground vegetation Canopy Landform relief and contour lines Water and marsh Path network, rocks and manmade features
Race specific add-on information For raster attribution a subset of the ISOM standard is selected that influence clearly the speed of the competitor. Both, passable objects (Table 5) and impassable objects (Table 6) are required to be taken into consideration. Section 4 will introduce the overall modelling and provide application examples.
Since classical path search algorithms rely on graphs, the given map has to be transformed to such. Using regular shapes (Section 2), the map gets rastered into a network of nodes. Each of them represents a single part area that the map has been decomposed into. A suitable shape is a square of 20 x 20 m that easily allows the later import of altitude data (Section 3). Using these squares, information will be extracted from the map in four steps: 1. Each square obtains a numerical value that is associated with the underlying areal objects’ properties. 2. Linear objects modify these values. 3. Correct insertion order of objects has to be guaranteed so that dominant objects win over non-dominant ones. 4. Altitude data will be used for the final transformation into a bi-directional graph. 4.1
In an orienteering map, properties of areal objects are represented by their colour and colour pattern, respectively (Fig. 6a). Their appearance and meaning are standardised [5]. They often already represent a normalised speed value. An open forest (ISOM-ID 405) is the reference that will be set to a normalized, unitless speed value of 100. Most symbols describe the vegetation and soil condition that have the biggest impact on the runner’s speed. A direct connection between areal object’s properties and real speed is a very complex and hard to describe, because they depend on physical and cognitive performance as well [6]. Thus, the normalised speed value is an approximation that is admissible to build the model. Using a lookup table (Table 5), each colour pattern has a fixed mapping to a normalised speed value v(n) where n identifies the square (Fig. 6c).
In the basic case, the speed value is the real speed projected on the horizontal plane. Otherwise the altitude change between two squares must be considered as well, when calculating the distance. With this simplification, the two-dimensional one is admissible.
Special areal objects are out-of-bound areas (Table 6). Some of them are explicitly designated like private estates and may result in a penalty. Others implicitly restrict the accessibility of an area like buildings or deep lakes. They have a fixed value of v(n) = 0. After the map has been sectioned into regular shapes, many of them will cover a borderline of two or more different areal objects. In this case, the dominant colour of the shape will determine the normalised speed value (Fig. 6b). A colour is considered dominant when it has the highest part in the square compared to other colours.
Finer raster resolutions than 20 m by 20 m would provide a more detailed and more exact model, if a precise map was available. But on the other side, they would increase the computing time as well. Since orienteering maps only give a generalised representation of the landscape, they lack in details in smaller scales. Thus, finer resolutions are not expected to improve the model. Following the areal object extraction, linear objects must be transferred into the model. Linear objects can be classified into: 1. Objects with distinct normalised speed value (Table 5). 2. Decelerators that scale the areal object’s normalised speed value down (Table 7). 3. Barriers that are impassable (Table 6).
Roads and wide paths take course through the landscape as individual objects. They
have greater normalised speed values vlin than neighbouring areal objects. Thus, linear
objects reassign new values v’(n) to the squares they pass (
v’ (n) = max (v (n), vlin)
(
Object
Trench Crossable watercourse Minor water channel Narrow marsh
ID 105 109 111 112 215 304 306 309 Speed scaling factor 0,7 0,5 0,5 0,3 0,6 0,6 0,8 0,9
Brown Brown Brown Black Solid line Blue Blue Fig. 8. Extraction of linear objects’ properties from the map. (a) Part of the map rastered into squares, (b) Linear objects found on the map, (c) Re-assignment of speed values. Thus, the insertion algorithm has to ensure that a single linear object has no more than two direct neighbour squares. There is an approach to regularly insert it into all squares it touches (Fig. 7b). If the map data is a bit-mapped graphic the linear objects must be transformed to a set of vectors prior to this in order to avoid ambiguity. Then all squares that cause a split of the path have to be removed in a manner that the square with the shortest part of the linear object will lose it (Fig. 7c).
This procedure is repeated for the other linear object classes as well (Fig. 8b). They
differ in the assignment of speed values (Fig. 8c). Decelerators like ramparts or ditches
are special features of the landscape. They have no fixed speed value, but a scaling
factor k that reduces the speed value v’ (
Like restricted areas, linear barriers (fences, railways etc.) assign the square that they pass a value of zero. At this point, the order of including the different linear objects becomes important. Barriers should always be dominant over other objects. Else a possibly dominant path could remove a neighbouring barrier in the same square and enable a passage that is not present in the original environment. On the other hand a bridge under a railway or a street through a restricted area explicitly provides a valid passage. Thus following order in insertion is suggested: 1. Areal objects’ dominant colour patterns are mapped to the squares. 2. Decelerating linear object scale the speed values. 3. Objects with distinct speed values replace the previously assigned ones if they are greater. 4. Linear barriers are inserted.
Every square that has both barriers and paths with a distinct value that do not cross each other needs a special treatment. The barrier is moved to the neighbour square so that neither the barrier nor the path gets deleted.
The result is a matrix of normalised speed values that will be transformed into a
unidirectional graph in the next step (Fig. 9b). Each node of that graph represents a
square. Nodes are linked with their direct neighbours. The weight w (n, m) of the edges
is the mean speed of the two square n and m that they are connected to (
w (n, m) = ½ * (v’ (n) + v’ (m))
(
An increase would usually lower the normalised speed value in contrast to a decrease
that speeds the runner up to a certain degree. Too steep decreases however have a
negative effect on the speed as well. Based on experiments, a lookup table (LUT) is utilised
to resemble this fact (Table 8). It delivers a value that scales the edge’s weight. The
lookup table relies on empirical data and is might possibly not be defined by an
analytical function (Fig. 10).
The steepness is correlated to the difference of altitude of two squares n and m and their
altitude difference Δe (n, m) = e (m) – e (n) in meters (
e n, m e' n, m d n, m
e m e (n)
d (n, m)
(
Classical graph search algorithms can be employed to find an optimal route on the given map after it has been transferred into a graph. The problem is visiting all control points and then returning to the start position which is known as the travelling salesman problem (TSP). Since a bidirectional graph is given it is an asymmetric TSP (ATSP) [8].
The graph obtained by extracting the map’s objects (Fig. 12a) is not eligible for directly solving the TSP. Using the original graph, the solution would yield a route visiting all squares, which is not feasible. 5.1
Prior to applying the TSP, it is necessary to reduce the graph until its nodes solely are the control points including start and finish (Fig. 12b). This can be reached by pairwise searching for the shortest path between each control point. The A* algorithm [9] is proposed therefore.
The A* algorithm finds the path in the graph that has the smallest cost. Smallest cost
refers to minimum time in this case. It is an iterative algorithm. In each step, it expands
its solution towards the goal, using an estimate of the cost f (n) required going to that
final node. The estimate is calculated from the real cost g (n) needed to go from the
start node to n and a heuristic h (n) that estimates the cost from n to the goal without
knowing the real costs (
Given a start and end point, it finds always the path with the smallest cost. The original
path represents the speed on its edges. But the criterion of optimisation is the time
needed to complete the competition. Thus the speed needs to be converted into a time
representing value. The time t (n, m) required to go from a square n to m and speed
w’(n, m) between the squares are reciprocally connected by the distance between the
centres of them d (n, m) (
t n, m d n, m
w' n, m
(
f (ngoal) = g (ngoal)
(
g (ngoal) g (n) + h (n)
(
Now, the ATSP can be applied to the new graph. Several algorithms exist to solve it [10]. The solution gives a path that connects every control point and is the global optimum (Fig. 13). All edges of the optimal path get re-expanded, using the previously found local routes on the original graph. The so obtained route can easily be mapped onto the orienteering map where each square that it has been decomposed to is a node.
The final result can be exported to a common file format like the GPS exchange format (GPX)2. A mapping to WGS 843 conform geo-coordinates is required in this case. That allows the visualisation to be done in any software capable of reading this file format (Fig. 14). 6
Publicly available DEM e.g., SRTM data, are native raster data. The available resolution of 1 arc sec equals to a rectangle of approx. 20 by 30 meters in Central Europe. For the model building, see Fig. 15, rectangles will be substituted by squares. Each square will be assigned a set of independent attributes, where, besides altitude, the type of vegetation is the most important one. Both, linear and areal objects are taken into consideration. They can be extracted from an orienteering map as majority decision for the texture pattern of each given square.
Afterwards, areal and linear vector objects are mapped onto the neighbourhood relations by a speed adaptation factor or by cutting the neighbourhood in case of barriers. As sometimes closed areas offer pathways, food paths and roads are calculated last as overlay.
Altitude differences influence the speed of the competitor. As experimental investigations show, the adaptation is individually. Therefore, a LUT is recommended to represent the correction factor to be applied to the entire model. Depending on the direction different corrections must be applied, which results in a bi-graph. This methodology is also applicable for other personal characteristics.
In the following steps, known algorithms of asymmetric path optimization are applied e.g., A* to calculate an optimal route as a sequence of first order raster fields by solving the ATSP.
Fig. 15 illustrates the entire chain of model building and route calculation in eight sequential steps. The selected square resolution of about 20 m by 20 m fits to cover a typical orienteering map of up to 16 square kilometres. Orienteering maps are often created with the OpenOrienteering Mapper. The open source project [11] offers a rich function set, already exceeding comparable commercial tools. An exporter could be defined to transfer all relevant linear and areal objects into the raster approach.
With FjwMap a well-established route planning and visualization tool is freely available [12]. Applying GPX, a common import format is already supported. An import plug-in for the raster approach results is proposed.
For each step of the processing queue shown in the upper boxes of Fig. 15, a key improvement has been already identified. By extending the variety and number of barrier objects, the verification of the right order of map feature extraction required, not to miss potential passages.
The proposed solution does not yet consider classical objective ARDF specifics, namely the uncertain CP locations as well as transmission to silence ratio of 1 to 4. Those should be called dynamic problems.
In a next step, an individual parametrisation will be needed. LUT for speed adjusting should be personalized and verified by further experiments and analysing publicly available competition results4.
Depending on the estimated distance to the upcoming CP, the competitor adjusts the speed and movement direction often in a special manner to succeed logging the CP even out of the transmission time. Furthermore, the influence of increasing tiredness during a competition should become part of the personal model.