Geoscience Reference
In-Depth Information
Fig. 1
Risk value calculation
at intersection
i
. The
green
path depicts the chosen path,
the
red
edges present wrong
path choices at intersection
i
wrongly. As such, the algorithm favours paths with combined long edges and easy
intersections. The risk value is in this case a measure of the average length of a
single edge that could be taken wrongly at that intersection. The formula for the
total risk of a path (Eq.
1
) balances the sum of all intersection-based risk values
with the length of the actually taken edges. Both elements contribute in this case
equally as much to the total risk of a certain path. Applied to indoor environments,
it could be assumed that the least risk path might be quite similar to the shortest
path and simplest path. Indoor spaces often consist of many decision points and
short edges, along long corridors making derivations of the shortest path more dif-
ficult than outdoors. This will be examined in
Sect. 4
.
The algorithmic structure of the least risk path algorithm is similar to Dijkstra
with a continuous loop over all nodes including three consecutive steps:
1. Detect the next smallest node
2. Change the selected node to the next smallest node
3. Adjust the cost values for adjacent nodes
It is only in the third step that the least risk path differs from the Dijkstra algorithm
since the cost value is not only dependent on the length of the edge but also on the
risk value of each intersection that is passed. This risk value is dependent on the
previous route taken to reach the selected node and the length of its adjacent edges.
The following steps in the 'adjust cost section' are consecutively executed:
Algorithm
:
Adjust cost calculation in selected node
//Algorithm which calculates and adjusts the costs for each edge leaving the
selected node.
Input
:
Costs in selected nodes and all endnodes of edges converging in the
selected node
