Computational Aspects: How Landmarks Can Be Observed, Stored, and Analysed - Landmarks: GIScience for Intelligent Services - page 156

a b c

{r}

{l}

{s}

Fig. 5.15 The complete line graph and how it applies to the labeling and decision function in
the simplest instruction algorithm. ( a ) An example street network; the solid nodes represent the
intersections (vertices), the hollow nodes are the vertices of the line graph (the edges in the original
graph). ( b ) The actual complete linegraph; the original graph is shown in light grey for reference.
( c ) Instruction labeling for some of the edges as seen from the solid vertex. Applying the decision
function d. solid node ;s/when at this solid vertex would result in the vertex just above it

there is no ambiguity in instructions, i.e., 'turn right' may not describe two or more
decisions from the same edge.
Formally, instructions are covered by the labeling function l W " ! I 2 and the
decision function d W E I ! E [f;g . For a given edge e and an instruction i ,
d.e; i/ D e 0 gives the edge e 0 that results from executing the decision i at e,which
may be the empty set indicating that instruction i is not possible to execute at e.
Each instruction has a cost associated with it, represented by the weighting function
w W I ! R C . Costs reflect the cognitive effort to execute an instruction, i.e., how
difficult it is to understand and to identify what to do in the actual environment.
Figure 5.15 shows an example that illustrates these concepts.
As a further feature of this algorithm, which makes it complex in the end,
instructions may be 'spread forward through the graph'. This reflects the fact that
often a single instruction may cover several intersections, such as in 'turn left
at the third intersection' where implicitly the instruction tells a wayfinder to go
straight at intersection one and two [ 25 ] . The cognitive and communication benefits
of combining instructions this way will be further discussed in Chap. 6 . Here,
it is only important to note that there are limits to combining instructions (e.g.,
nobody would instruct someone to 'turn left at the 47th intersection'). Therefore, in
spreading instructions through the graph, a distinction is needed between an edge
being reachable and being chunkable . An edge e t is reachable from an edge e s with
an instruction i if there exists a path from e s to e t that can be encoded as a sequence
of executions of instruction i . The same edge is chunkable from e s if the sequence
of instruction i required to reach e t from e s is valid according to the combination
rules. This is checked by the validity function v W E E !f tr u e; false g .
An instruction gets spread forward as long as there are edges reachable with it.
A cost update is then only performed for those edges that are chunkable. This way