# User Preferences and the Shortest Path

Isabella Kreller and Bernd Ludwig
University of Regensburg,
Universitätsstraße 31
D-93053 Regensburg, Germany
<EMAIL_ADDRESS>
###### Abstract

Indoor navigation systems leverage shortest path algorithms to calculate
routes. In order to define the “shortest path”, a cost function has to be
specified based on theories and heuristics in the application domain. For the
domain of indoor routing, we survey theories and criteria identified in the
literature as essential for human path planning. We drive quantitative
definitions and integrate them into a cost function that weights each of the
criteria separately. We then apply an exhaustive grid search to find weights
that lead to an ideal cost function. “Ideal” here is defined as guiding the
algorithm to plan routes that are most similar to those chosen by humans. To
explore which criteria should be taken into account in an improved pathfinding
algorithm, eleven different factors whose favorable impact on route selection
has been established in past research were considered. Each factor was
included separately in the Dijkstra algorithm and the similarity of thus
calculated routes to the actual routes chosen by students at the University of
Regensburg was determined. This allows for a quantitative assessment of the
factors’ impact and further constitutes a way to directly compare them. A
reduction of the number of turns, streets, revolving doors, entryways,
elevators as well as the combination of the aforementioned factors was found
to have a positive effect and generate paths that were favored over the
shortest path. Turns and the combination of criteria turned out to be most
impactful.

##  1 Introduction

Finding a way through their immediate environment to reach a sought
destination is a task highly relevant to humans since they see themselves
confronted with it regularly. Due to the available options of traveling and
visiting unfamiliar cities in foreign countries, the cultural differences as
well as the possible language barrier may further complicate wayfinding tasks.
Being able to facilitate situations like these, location-based navigation
services, particularly those intended for car navigation, enjoy great
popularity and have established themselves as indispensable supporting tools
for navigation in the modern world, as indicated by the high usage of Google
Maps [17].

Although still overshadowed by the ubiquity of outdoor navigation systems,
indoor wayfinding is not anymore an obscure area of research and it might be
that in this setting navigational support might be needed most. Wayfinding,
meaning the goal-oriented process of a person finding a predefined destination
[2], often involving navigation through large areas without initial perception
of the target location [27], is deemed a cognitive challenging task requiring
a variety of mental resources [35].
In addition, indoor spaces exhibit structural attributes, such as the
additional dimensionality inherent in multi-storied buildings [18] or the lack
of reliable methods for localization [42], which give rise to further
difficulties and require current systems to be adapted to this navigational
context.
This likewise concerns the pathfinding algorithm: due to the current lack of
geospatial research regarding this setting, employed algorithms have shown
little to no deviation from optimizing only in regard to the route’s
efficiency disregarding human preference. Previous studies, as discussed in
subsections 2.2, 2.3, and 3.3, have determined a multitude of diverse criteria
as influential to people’s path choices, yet quantification of their impact
and applicability in indoor environments remain to be studied.

##  2 Related Work

###  2.1 Difficulties of Indoor Navigation

The reasons for which indoor navigation systems lack the popularity and
widespread use their outdoor counterparts are enjoying are twofold.
Firstly, there exist additional difficulties regarding the implementation of
indoor navigation systems. The additional third dimension, the height,
inherent in multi-level buildings creates challenges regarding a suitable
design for the visual projection onto the small two-dimensional screens of
smartphones [5]. This is important for providing easily comprehensible and
unambiguous instructions to the user to direct them to the correct floor.
Hence, conventional visualizations and user interfaces of map-based
applications are not predestined for wayfinding support inside buildings.
Yet the most crucial obstacle to overcome is likely the absence of a reliable
method of localization. Whereas the vast majority of outdoor navigation
systems make use of Global Positioning System (GPS) signals [42], this does
not constitute a viable option indoors. These signals manage to pass through
the walls and ceilings of buildings only sporadically, rendering it an
unsatisfactory solution for optimal navigational support [42]. Although
numerous alternatives, including WiFi, Bluetooth, and Infrared, have been
proposed, these too entail drawbacks regarding performance, cost, or
reliability. [42]
Furthermore, human orientation may also prove more challenging in this
setting. The third dimension, i.e. multiple stories inside buildings, creates
challenges not only for the system’s ability to display information but for
human wayfinding as well. Staircases have been identified as the location
where mistakes are being made most frequently during a wayfinding task [18];
other research supports the idea that people struggle with vertical, rather
than horizontal, movement, which might be explained by the mistaken assumption
that a building’s layout is identical across floors [43]. A restricted field
of vision due to walls and corners makes the usage of landmarks as points of
reference only possible if they are local or in direct line of view, whereas
in outdoor spaces global landmarks, such as towers or the city skyline, can
also support wayfinding. [52].

###  2.2 Influential Factors

There is reason to contest and doubt that humans’ behavior is purely rational
and can be explained with conscious and deliberate reasoning alone for we are
susceptible to numerous biases in our ways of thinking and decision making
[23].

The same holds for wayfinding behavior: while the most logical path to the
desired destination would generally be the shortest or least time consuming
one, this does not align with actual human conduct or preference [3, 14, 3,
54].
Afyouni, Ray, and Claramunt [1] suggest a classification of the context in
which decision making takes place that can also be applied to wayfinding
tasks. The user-centered context takes into account the navigator’s profile,
such as mental capabilities of visualization [44], or rotation of objects
[32], their age [45] and gender [28], or cultural background [20]. The context
of execution, on the other hand, describes qualities of the information
systems which aid the user; the representation of maps and real-world
references used by mobile applications [38] has been found to impact
navigational success, and so do conventional means of support, such as signs
and paper maps to varying degrees.
What is most relevant for the adjustment of the pathfinding algorithm,
however, can be described by the environmental context.
According to Lynch [29], the components most crucial for the formation of
mental maps are paths, edges, districts, and landmarks, which, belonging to
the same mental models, exist in connection and mutual interference. This
concept fits well into the research conducted, which suggests that humans
mentally visualize their environment as being structurally equivalent to a
network of streets and paths [13, 27, 33].
In this sense, the definition of a path’s complexity contrived by Golledge
[14] and since adopted into the work of many others [11, 19, 40] is to
consider the number of streets or turns connecting them.
Alternative approaches [4, 12, 16, 40, 51] of achieving simplicity take into
account the number of decision points, i.e. intersections of multiple streets,
or their branching factor. It is defined by the number of streets meeting,
thus considered a measure of difficulty or complexity of a decision point [37]
and increasing the possibility of losing one’s way [2].
Rather than the number of branches, Dalton [8] found a preference for choosing
the maximum, rather than mean or minimum, angles of paths available at
decision points, meaning that people were more likely to choose the way that
was aligned most with from where they were coming, presumably as a complexity-
minimizing strategy. Further observations support the idea of people’s
predilection towards maintaining linearity in their routes [7, 34, 41, 53].
Similarly, another study points towards a human preference of decreasing the
angular distance to the destination (Turner, 2009) at decision points,
favoring this over a reduction of the Manhattan distance.
Other than a preference for simple paths, the absence or presence of certain
path entities could serve as a decisive factor. Landmarks, defined by their
conspicuity and recognizability [6, 29] commonly function as points of
reference and may help reduce cognitive load for orientation [15]. For
staircases, both a preference [24] and avoidance [24, 26] have been
identified.

###  2.3 Alternatives to the Shortest Path

Variants for the cost function in path planning have been proposed with
different objectives in mind. Grum [16] describes a way of extending the
Dijkstra algorithm so that it incorporates a weight for the risk of making a
wrong decision at an intersection proportional to the distance of the
mistakenly chosen path, assuming that the navigator notices their mistake at
the next decision point and retraces their way. In this manner, not the
shortest path, but the one with the least danger of getting lost is computed.
Yet, the question remains open how the risk for wrong decisions may be
estimated for arbitrary environments.
Duckham and Kulik [11] proposed a way of calculating the simplest path, using
solely a measure for ease of navigation by weighting route instructions
without taking distance into account at all. Instructions needed to navigate
decision points were penalized according to adjusted slot values for turns and
branches as proposed by Mark [31], yielding the sought-after advantages.
Physically constrained people constitute a group of users which might benefit
immensely from adjustments to conventional navigation systems. A proposed way
of achieving this is by taking into account edge weights other than distances,
thus considering specific user preferences such as avoiding stairs or
minimizing turns which can be input directly by the user [30].
In contrast, introducing a measure of beauty as a way of suggesting short
routes that are perceived to be emotionally pleasant was accomplished by
crowdsourcing of people’s judgments of places along the dimensions beautiful,
quiet, and happy, making use of pictures from Google Street View or taken by
volunteers [39]. Such an aesthetic criterion has not been considered by the
persons who provided us with their preferred routes, because they tried to
reach their destination as quickly and easily as possible. However, [22]
report that minimizing the number of turns is a key criterion for route
planning in outdoor environments. Such routes seems to be more easily
perceivable and cognitively less demanding.

In our study we evaluate, whether this result can be transferred to indoor
environments and whether other criteria (e.g. level changes or use of
elevators) that result from indoor architectural constraints also influence
human decision making for route planning.

##  3 Route Calculation

To operationalize the above research question, we make use of the indoor
navigation system URWalking [36, 49] (urwalking.ur.de). It implements
Dijkstra’s algorithm [10] to determine the shortest path in terms of the
distance between starting point and destination in meters.

###  3.1 User Preferred Routes

Our empirical study is based on a data set of 221 routes, collected both
during the summer (100 paths) and winter semester (121 paths) at the
University of Regensburg, thus accommodating for differences in weather and
temperature. All participants, 129 of which were male, stated to be highly
familiar with the environment and ranged in age from 19 to 33 (mean age =
22.93, SD = 2.67). As means for data collection, participants were asked to
walk and describe their daily route on the campus. The university campus spans
over an expanse of 1 km² and includes 16 buildings with a sum of 86 individual
floors and 5228 rooms, encompassing both paths indoors and outdoors [36].

The aim of the data collection was to find out whether modifications of
URWalking’s path planning algorithm could lead to routes users enjoy taking,
so as to find a compromise between the theoretically minimal walking distance
and the distance of preferred paths (i.e. can we approximately simulate human
decision making using Dijkstra’s efficient algorithm?). For the envisioned
modifications, we identified criteria in research literature that are argued
to impact human decision making during wayfinding tasks.

###  3.2 Criteria

The criteria that will be described in the following were chosen due to the
extent of the research they are supported by and applied in, and also based on
the feasibility of their incorporation into the Dijkstra algorithm. The scope
of literature on the measurement of path complexity suggests that there is no
agreed-upon answer as to how to define it. Although a few studies have
suggested more elaborate ways of ruling how complex a path is, a few
elementary classifications resurface frequently across research papers. We
identified 11 factors:

A straightforward way to determine complexity is by considering the (1) number
of turns a route contains. Regarding the definition of what constitutes a turn
in navigation the answers once again are ambiguous. According to the Cambridge
Dictionary [47], a turn can be considered ”a change in the direction in which
you are moving or facing”. Although in some studies a sufficient change in
directions achieved only when the angle between two path segments is smaller
or equal to 90 degrees [19, 50], others interpret every branch at a decision
point to count as a turn [11, 25].

A related factor influential to wayfinding is the (2) number of streets,
meaning the path segments separated by decision points or turns of any kind
[19]. Considering only turns up to a maximum angle of 90 degrees would not
account for the number of streets whereas disregarding the angle entirely
would run the risk of accounting for turns that might not be perceived as such
due to their small deviation from a linear path. For these reasons, both of
the definitions of what constitutes a turn were examined: weighting turns
regardless of their angle will acknowledge the number of streets more
completely, and following the definition in accordance with [19] comprises a
more traditional way of regarding turns and assessing their impact
independently.

The (3) number of decision points themselves was considered for route
calculation as well. Since the number of paths at a junction demanding a
decision is two in addition to the path the navigator came from, a decision
point in this study was defined as an intersection of three or more paths;
their exact number was disregarded and every path located at a point which
fits this definition was penalized in the same way.

The (4) branching factor, meaning the number of intersecting paths, was
regarded separately. To weigh the paths proportionally to their quantity,
every path at a decision point received the additional weight times the number
of intersecting paths. These weights were taken into account only at places
that qualify as decision points corresponding to the aforementioned
definition.

The findings on which paths at intersections constitute the most likely choice
are ambiguous, which is why two divergent findings were considered. One is the
preference for selecting the path which most closely aligns with the global
direction of the destination [48], being equal to the avoidance of all paths
other than the one with the (5) minimum deviation angle.

Alternatively, a preference for (6) linearity [7] might influence the person
navigating to continue their route along the most linear path, i.e. the path
with the largest angle (between 0 and 180 degrees) in regard to the direction
from which the navigator arrived. For this, all except the most linear branch
at a decision point were penalized, allowing for the option of exempting two
branches in case of identical largest angles. To keep with the definition of
linearity as well as Dalton’s study [8], the condition was added that the
largest angle had to span 150 degrees or more. If there was no such angle,
e.g. in a T-crossing, no weighting was carried out.

Due to the contradictory nature of the literature regarding the preference for
(7) staircases in routes, both a preference for and avoidance of stairs were
considered. (8) Elevators constituted the only alternative for changing floors
at the university; hence the avoidance of stairs, being equal to a preference
for elevators, was implemented by adding weights for every staircase and vice
versa.

Another element to be taken into consideration for indoor environments
exclusively is doors. The path network used for calculating routes includes
different types of nodes that differentiate between (9) doorways, (10)
entrances to closed premises such as offices or lecture halls, termed
entryways, and (11) revolving doors. Since it has been found that doors take
on the function of important landmarks in indoor spaces, and serve as
transitions between separate spaces [46], the effect of doors, with the above-
mentioned differentiation, will be included in the analysis.

We modified the original URWalking path finding algorithm such as to
separately take the 11 above factors into account and to identify their
optimal weights for calculating optimal routes. This constitutes a method of
path calculation that, while still maintaining the objective of minimizing
distance, can easily integrate different factors and assign them distinct
levels of importance.

Result: Shortest paths to all nodes starting from source

create vertex set Q;

for  _each vertex v in Graph_ do

dist[v] ← INFINITY;

prev[v] ← UNDEFINED;

add v to Q;

dist[source] ← 0;

end for

while  _Q is not empty_ do

u ← vertex in Q with min dist[u];

remove u from Q;

for  _each neighbor v of u_ do

alt ← dist[u] + wlength(u, v);

if  _alt ¡ dist[v]_ then

dist[v] ← alt;

prev[v] ← u;

end if

end for

end while

return dist[], prev[];

Algorithm 1 Dijkstra’s algorithm (source: Wikipedia)

The standard shortest path definition of $\mbox{wlength}(x,y)$ is the metric
distance $\mbox{length}(x,y)$ between two nodes $x$ and $y$ connected by an
edge. The operationalization of the identified factors is quite
straightforward: we simply modified the cost function used by Dijkstra’s
algorithm (see Algorithm 1). The key to taking the factors into account is a
modification of the function $\mbox{length}(x,y)$ for the cost of edges in the
graph. In the standard version, the function computes the distance between $x$
and $y$ in meters. In our modifications, we add artificial, heuristic costs to
$\mbox{length}(x,y)$. We apply the idea that a factor can be accounted for by
extending the distance between $x$ and $y$, i.e. by making artificially the
edge $(x,y$) more expensive. For each factor, a particular criterion
determines whether it actually applies for an edge currently considered by
Dijkstra’s algorithm:

  1. 1.

number of turns:

$\mbox{wlength}(x,y,w)=\left\\{\begin{array}[]{ll}\mbox{length}(x,y)+w&\mbox{angle}(x,y)\leq
90\\\ \mbox{length}(x,y)&\mbox{otherwise}\\\ \end{array}\right.$

  2. 2.

number of streets:

$\mbox{wlength}(x,y,w)=\left\\{\begin{array}[]{ll}\mbox{length}(x,y)+w&\mbox{angle}(x,y)\leq
180\\\ &(\mbox{route does not continue straight on after $y$})\\\
\mbox{length}(x,y)&\mbox{otherwise}\\\ \end{array}\right.$

  3. 3.

number of decision points:

$\mbox{wlength}(x,y,w)=\left\\{\begin{array}[]{ll}\mbox{length}(x,y)+w&\mbox{$x$
has at least three neighbours}\\\ \mbox{length}(x,y)&\mbox{otherwise}\\\
\end{array}\right.$

  4. 4.

branching factor:

$\mbox{wlength}(x,y,w)=\left\\{\begin{array}[]{ll}\mbox{length}(x,y)+n\cdot
weight&\mbox{$x$ has exactly $n$ neighbours and $n\geq 3$}\\\
\mbox{length}(x,y)&\mbox{otherwise}\\\ \end{array}\right.$

  5. 5.

minimum deviation angle:

$\mbox{wlength}(x,y,w)=\left\\{\begin{array}[]{ll}\mbox{length}(x,y)+w&\mbox{$x$
has at least three neighbours}\\\ &\mbox{and
$y\not=\operatorname*{arg\,min}_{z}\mbox{angle}(x,z)$}\\\
\mbox{length}(x,y)&\mbox{otherwise}\\\ \end{array}\right.$

  6. 6.

linearity:

$\mbox{wlength}(x,y,w)=\left\\{\begin{array}[]{ll}\mbox{length}(x,y)+w&\mbox{$x$
has at least three neighbours}\\\ &\mbox{and
$y\not=\operatorname*{arg\,max}_{z}\mbox{angle}(x,z)$}\\\ &\mbox{and
$\max_{z}\mbox{angle}(x,z)\geq 150$}\\\ \mbox{length}(x,y)&\mbox{otherwise}\\\
\end{array}\right.$

  7. 7.

staircases:

$\mbox{wlength}(x,y,w)=\left\\{\begin{array}[]{ll}\mbox{length}(x,y)+w&\mbox{$y$
is an edge of type {\tt staircase}}\\\ \mbox{length}(x,y)&\mbox{otherwise}\\\
\end{array}\right.$

  8. 8.

elevators:

$\mbox{wlength}(x,y,w)=\left\\{\begin{array}[]{ll}\mbox{length}(x,y)+w&\mbox{$y$
is an edge of type {\tt elevator}}\\\ \mbox{length}(x,y)&\mbox{otherwise}\\\
\end{array}\right.$

  9. 9.

doorways:

$\mbox{wlength}(x,y,w)=\left\\{\begin{array}[]{ll}\mbox{length}(x,y)+w&\mbox{$y$
is of type {\tt doorway}}\\\ \mbox{length}(x,y)&\mbox{otherwise}\\\
\end{array}\right.$

  10. 10.

entrances:

$\mbox{wlength}(x,y,w)=\left\\{\begin{array}[]{ll}\mbox{length}(x,y)+w&\mbox{$y$
is of type {\tt entrance}}\\\ \mbox{length}(x,y)&\mbox{otherwise}\\\
\end{array}\right.$

  11. 11.

revolving doors:

$\mbox{wlength}(x,y,w)=\left\\{\begin{array}[]{ll}\mbox{length}(x,y)+w&\mbox{$y$
is of type {\tt revolving-door}}\\\ \mbox{length}(x,y)&\mbox{otherwise}\\\
\end{array}\right.$

In these definition $w$ is a constant whose value determines by how many
meters the length of an edge between $x$ and $y$ is extended. Consequentially,
the shortest path gets ”longer” the more instances of the respective
considered factor it includes.

With this model, our main task is now to determine values of $w$ for each
factor that maximizes the similarity between routes calculated by URWalking
and those chosen by the participants of our study.

###  3.3 Systematic Search for Optimal Weights

Our intuition is that a meaningful assessment of similarity between two routes
$r_{1}$ and $r_{2}$ reflects the length of shared path segments, i.e. edges in
$r_{1}$ and $r_{2}$:

$\mbox{similarity}(r_{1},r_{2})=\frac{\displaystyle\sum_{e\in r_{1}\wedge e\in
r_{2}}\mbox{length}(e)}{\min(\mbox{length}(r_{1}),\mbox{length}(r_{2}))}$

with $\mbox{length}(r)=\sum_{e\in r}\mbox{length}(e)$ for any route $r$ and
$\mbox{length}(e)=\mbox{length}(x,y)$ with $x$ being the source node and $y$
the sink node of any edge $e$.

In other words, the calculated Similarity Score
$\mbox{similarity}(r_{1},r_{2})$ was defined as the sum of the distances
belonging to shared edges divided by the length of the shorter path (analogous
to [21]). Following Delling et al.’s [9] approach, the mean of the similarity
scores across all path comparisons was then considered for assessment of the
algorithm, i.e. each factor’s individual impact on wayfinding.

To identify an optimal weight $w$ for each factor, we performed a systematic
grid search for this one-dimensional parameter. Overall, we performed 11
independent searches considering a different factor in each search.

In such a search, we first set $w=0$ to identify the shortest path in terms of
the metric distance between a fixed start and destination. Then we iterated
over $w$ and incremented it by 1 in each iteration. As the cost function
$\mbox{wlength}(x,y,w)$ computes costs in meters, incrementing $w$ by $1$ adds
one meter to the physical distance between $x$ and $y$ allowing a detour of
$1$ meter for a path still to be identified as the shortest path, this time
however taking one of the identified factors into account. After having
calculated this shortest path for a fixed $w$ we computed the similarity score
to preferred routes in our data set with identical start and destination
resulting in a list of similarity scores for which we could easily calculate a
mean similarity. We repeated this process for all pairs
$(\mbox{start},\mbox{destination})$ in our data set and calculated a mean
similarity score for the fixed $w$.

We proceeded in the same way for each value of $w$ in the interval of $[0,25]$
(see Figure 1). For $25<w\leq 100$ we changed the step size to $10$. Should a
higher similarity be observed here than was calculated for weights in range 0
to 25, the scope of weights that are sampled in intervals of 1 was extended.
This served to ascertain that the best possible results did not lie beyond the
boundary that was established.

The maximum detour from the shortest path in order to satisfy user preferences
that would still be considered acceptable amounted to $w=100$ meters. However,
as can be seen in Figures 1 and 2 the similarity between calculated paths and
user preferred routes was maximal for $w<25$ for each of the factors
considered.

##  4 Results

The work was conducted to find answers to the following questions, the answers
to which are laid out in corresponding subchapters:

  1. 1.

Does the consideration of the individual criteria, which were found to be
influential to human wayfinding in previous work, lead to a higher similarity
to paths that align with human preferences compared to the shortest path? And
if so, to what extent?

  2. 2.

Assuming independence, how does a combination of all criteria with their
respective optimal weights impact path similarity?

  3. 3.

How do the criteria found to be influential compare to one another regarding
their impact on human path selection?

###  4.1 Individual Evaluation

(a) Similarity Scores of Angles

(b) Similarity Scores of Branching Factor

(c) Similarity Scores of Decision Points

(d) Similarity Scores of Doorways

(e) Similarity Scores of Linearity

(f) Similarity Scores of Staircases

Figure 1: Similarity Scores of Noninfluential Criteria

As described in the preceding chapter, for each factor, the average Similarity
score was calculated in dependence on its weighting in order to determine
which weight would lead to the best possible average approximation of the
entire set of 221 user paths. Starting off the weighting with an increase of 1
in the range of 0 to 25, or if needed higher, provided the weight which leads
to the optimum result. The unaltered shortest path displayed a similarity of
50% to the user paths.

As shown in the following figure, not all factors led to an increase in
similarity regardless of the added weight. This proved to be the case for the
following factors: decision points, branching factors, doorways, staircases,
minimum angle to the destination, and linearity at decision points. For the 5
Results 28 sake of a uniform presentation, all plots encompass a sampling of
weights in the range of 0 to 25.

An improvement of the similarity means was therefore reached for all the other
inspected criteria, which were turns, streets, entryways, revolving doors, and
elevators. The plots depicted in the plots figure 2 visualize the relation
between the weights and their improvement, a perpendicular red line marking
the weight belonging to the corresponding maximum similarity score.

(a) Similarity Scores of Elevators

(b) Similarity Scores of Entryways

(c) Similarity Scores of Streets

(d) Similarity Scores of Revolving Doors

(e) Similarity Scores of Turns

Figure 2: Similarity Scores of Influential Criteria

###  4.2 Combination

Assuming independence, all criteria that have been found to bring about a
positive change in similarity score in the preceding section were then
combined into one algorithm, each with their established best weight.
Due to the complementary nature of the factors turns and streets, which both
penalize slightly altered variations of a deviation from a straight path and
are thus evidently not independent from each other, taking into account both
of them would lead to duplicate weights being added for some edges; only turns
were therefore considered in this step since a bigger increase in similarity
was observed. With an absolute similarity score of 52.30%, this combination of
criteria also resulted in a better approximation of user paths.

###  4.3 Comparison

Figure 3 lists the results for each factor and their combination in descending
order of resemblance to the user paths measure by similarity score.
Additionally, the percentage of affected paths is displayed.

Factors | Weight | Similarity Score | Difference to SP | Impacted Paths
---|---|---|---|---
Turns | 1 | 52.47% | 2.43% | 19.91%
Combination | varied | 52.30% | 2.26% | 32.58%
Streets | 1 | 51.48% | 1.38% | 19.46%
Elevator | 17 | 50.85% | 0.81% | 8.60%
Entryway | 16+ | 50.55% | 0.51% | 11.76%
Revolving Door | 25 | 50.32% | 0.28% | 2.26%
Figure 3: Sorted Table of Criteria with Scores and Percentage of Impacted
Paths

The greatest increase in similarity measured 2.43% and was achieved by turns,
i.e. a reduction in the number of turns spanning 90 degrees or less, followed
by the combination of criteria with 2.26%. The avoidance of revolving doors
produced the smallest improvement of 0.28%.

##  5 Discussion

In consideration of the individual factors, one must retain that not in each
case it was a higher number of occurrences that increased or decreased the
assessed similarity to user paths. Following the elaboration of the criteria’s
specific implementation in 4.3, it was their avoidance instead that was
implied.
Many of the considered influential factors, previously found to be impactful,
did not lead to the computation of paths that were more similar to those
people prefer. This was the case for paths that integrated the avoidance of
decision points, their reduced branching factors, the avoidance of entrances
to rooms, as well as staircases, and a preference for choosing paths that
either minimized the global angular distance to the destination’s location or
aligned with the most linear path selection option. Consequently, all other
factors – the avoidance of elevators, entryways, revolving doors, turns, and
streets – produced an increase in similarity.

A comparison shows that not only did the criteria’s impact on the similarity
to user paths vary, but so did the number of affected paths: the differences
between the “best” factor (turns) and “worst” one (revolving doors) are almost
ten-fold regarding both similarity (2.43% vs. 0.28%) as well as impacted paths
(19.91% vs. 2.26%). This certainly may be explained by the frequency with
which each factor or entity occurs, for to produce significant changes it has
to be present in the paths initially suggested by the shortest path algorithm.
A preference for the most impactful factor can be reinforced by the finding
that with an increasing number of turns included in a route, the likelihood of
making a mistake while navigating, and thus the time needed for task
completion, increases [37]. The erroneous perception that routes containing
more turns are longer than routes with fewer turns despite being equal in
length (Dalton, 2003), might further explain our results.
In the cases of revolving doors, elevators, and entryways a boundless increase
of their weights lead to an improvement (Figures X), signifying that the
banishing of all occurring entities would be in the interest of users.
Unsurprisingly, since a study conducted on part of the same data set already
discovered a significant decline in the number of entryways in preferred
routes [36], it was found that adding weights for all occurring entryways
would improve the similarity.
The absence of entryways in the favored paths can be understood by considering
the inconvenience this would imply, for taking a shortcut through lecture
halls would generally only serve as an option during breaks, or passing
through shops or offices would be equally unreasonable. A case against
revolving doors can be made by considering that these types of doors are
generally not barrier-free and users of wheelchairs would naturally avoid
them.
The avoidance of choosing elevators as a means of transitioning to other
floors implies that people favored the alternative option of taking stairs,
which also concurs with previous findings [24, 36].
The results found are much the same for turns and streets, which can be
explained with the apparent similarities of the factors. Since turns only
penalized right-angled deviations, and reducing the number of streets happened
by penalizing all deviations from a straight path, reducing the number of
streets can be viewed as an extension of turns since above 90 degrees
(excluding 180 degrees) were also included.
Despite apparent similarities, a preference for linearity was not found and
neither was a preference for minimizing the angular distance. These results
could be attributed to decision points, which by themselves, and consequently
their branching factor as well, were found ineffective. In addition, although
such preferences have formerly been identified [8, 48], the environments in
which the studies took place differed greatly from navigating a university
campus.
To find the optimal integration of multiple criteria into one algorithm, their
specific weights would need to be identified anew. As was expected given the
incorrectly assumed independence of the variables, the results fell short of
reducing the number of turns alone. For taking dependencies between the
factors into account, as a next step, we will train a predictor for
$\mbox{wlength}(x,y)$ – i.e. a neural network that allows non-linear function
approximation.

Given all these limitations and observations from our analyses, we can still
claim that our algorithm finds a good compromise between shortest paths and
user preferred routes: The objective of minimizing path distance, which was
evident in every route calculation performed, achieved conformity with the
user paths of 50% on average without further augmentation, and can therefore
attest to align with human preferences. The overall results are encouraging
for the incorporation of the criteria, which were found to lead to an increase
of the similarity score, to create an algorithm able to suggest paths that
humans like to follow.

##  6 Conclusion

This work aimed to acknowledge users as the focal point of navigational
support systems and therefore suggest paths that match with their preferences.
To quantify the extent to which this is accomplished, a set of paths, which
people take in their daily lives, was considered representative of human
preferences, and similarity to these paths was treated as a measure of
accomplishment. The assumption that people enjoy being suggested the same
routes that they take in well-known environments might be flawed, since
aspects regarding the navigation app, such as the ease with which instructions
can be displayed and comprehended, are disregarded. Some of the factors were
not found to be influential in an indoor environment specifically, but rather
in settings whose similarity to the one considered here seems dubious.
Narrowing down the findings of previous studies to research applicable to an
indoor setting might help identify influential factors more successfully. On
the upside, putting these findings into a different context sheds light on
their transferability and may offer insights into why they have been found to
impact wayfinding decisions. Future research might proceed by taking criteria
into consideration that have not been discussed and considered here, including
not only environmental factors but more subjective criteria which might be
more difficult to assess. Lastly, shedding more light on the interrelations of
influential factors might be necessary for the conception of an ideal
algorithm that can consider more than one element at a time.

As far as the comparison between indoor and outdoor environments is concerned,
our study reproduces the results reported in [22] for indoor environments:
user prefer routes with a small number of turns. However, as indoor
environments are more complex that streets outside, also other criteria are
influential. It is an interesting challenge for future work whether a
transformation of a graph in which nodes actually represent actual distances
physical properties of the environment to another model in which nodes
represent inevitable choices (such as taking a turn) is feasible if multiple
criteria have to be considered simultaneously.

## References

  * [1] Imad Afyouni, Cyril Ray, and Claramunt Christophe.  Spatial models for context-aware indoor navigation systems: A survey.  Journal of Spatial Information Science, 1(4):85–123, 2012.
  * [2] Gary L Allen.  Cognitive abilities in the service of wayfinding: A functional approach.  The Professional Geographer, 51(4):555–561, 1999.
  * [3] Iro Armeni and Konstantinos Chorianopoulos.  Pedestrian navigation and shortest path: Preference versus distance.  In Intelligent environments (workshops), pages 647–652, 2013.
  * [4] Michael Brown and James Pinchin.  Exploring human factors in indoor navigation.  In The European Navigation Conference, 2013.
  * [5] Beatrix Brunner-Friedrich and Verena Radoczky.  Active landmarks in indoor environments.  In International Conference on Advances in Visual Information Systems, pages 203–215. Springer, 2005.
  * [6] David Caduff and Sabine Timpf.  On the assessment of landmark salience for human navigation.  Cognitive processing, 9(4):249–267, 2008.
  * [7] Ruth Alison Conroy.  Spatial navigation in immersive virtual environments.  PhD thesis, Citeseer, 2001.
  * [8] Ruth Conroy Dalton.  The secret is to follow your nose: Route path selection and angularity.  Environment and Behavior, 35(1):107–131, 2003.
  * [9] Daniel Delling, Andrew V Goldberg, Moises Goldszmidt, John Krumm, Kunal Talwar, and Renato F Werneck.  Navigation made personal: Inferring driving preferences from gps traces.  In Proceedings of the 23rd SIGSPATIAL international conference on advances in geographic information systems, pages 1–9, 2015.
  * [10] Edsger W Dijkstra et al.  A note on two problems in connexion with graphs.  Numerische mathematik, 1(1):269–271, 1959.
  * [11] Matt Duckham and Lars Kulik.  “simplest” paths: automated route selection for navigation.  In International Conference on Spatial Information Theory, pages 169–185. Springer, 2003.
  * [12] Ioannis Giannopoulos, Peter Kiefer, Martin Raubal, Kai-Florian Richter, and Tyler Thrash.  Wayfinding decision situations: A conceptual model and evaluation.  In International Conference on Geographic Information Science, pages 221–234. Springer, 2014.
  * [13] Sabine Gillner and Hanspeter A Mallot.  Navigation and acquisition of spatial knowledge in a virtual maze.  Journal of cognitive neuroscience, 10(4):445–463, 1998.
  * [14] Reginald G Golledge.  Path selection and route preference in human navigation: A progress report.  In International conference on spatial information theory, pages 207–222. Springer, 1995.
  * [15] Joy Goodman, Phil Gray, Kartik Khammampad, and Stephen Brewster.  Using landmarks to support older people in navigation.  In International Conference on Mobile Human-Computer Interaction, pages 38–48. Springer, 2004.
  * [16] E Grum and AU Frank.  Risk of getting lost: Optimize a path to minimize risk. corp, vienna.  Competence Center for Urban and Regional Planning, 2005.
  * [17] Viddit Haria, Yashvi Shah, Vanya Gangwar, Vansh Chandwaney, Tarang Jain, and Yash Dedhia.  The working of google maps, and the commercial usage of navigation systems.  International Journal of Innovative Research in Technology, 6(5), 2019.
  * [18] Christoph Hölscher, Tobias Meilinger, Georg Vrachliotis, Martin Brösamle, and Markus Knauff.  Up the down staircase: Wayfinding strategies in multi-level buildings.  Journal of Environmental Psychology, 26(4):284–299, 2006.
  * [19] Christoph Hölscher, Thora Tenbrink, and Jan M Wiener.  Would you follow your own route description? cognitive strategies in urban route planning.  Cognition, 121(2):228–247, 2011.
  * [20] Alycia M Hund, Martin Schmettow, and Matthijs L Noordzij.  The impact of culture and recipient perspective on direction giving in the service of wayfinding.  Journal of Environmental Psychology, 32(4):327–336, 2012.
  * [21] Oliver Jan, Alan J Horowitz, and Zhong-Ren Peng.  Using global positioning system data to understand variations in path choice.  Transportation Research Record, 1725(1):37–44, 2000.
  * [22] Bin Jiang and Xintao Liu.  Computing the fewest-turn map directions based on the connectivity of natural roads.  International Journal of Geographical Information Science, 25(7):1069–1082, 2011.  doi:10.1080/13658816.2010.510799.
  * [23] Daniel Kahneman.  Maps of bounded rationality: Psychology for behavioral economics.  American economic review, 93(5):1449–1475, 2003.
  * [24] Panayotis Kikiras, Vassileios Tsetsos, and Stathes Hadjiefthymiades.  Ontology-based user modeling for pedestrian navigation systems.  In ECAI 2006 Workshop on Ubiquitous User Modeling (UbiqUM), Riva del Garda, Italy, pages 1–6, 2006.
  * [25] Alexander Klippel, Heike Tappe, Lars Kulik, and Paul U Lee.  Wayfinding choremes—a language for modeling conceptual route knowledge.  Journal of Visual Languages & Computing, 16(4):311–329, 2005.
  * [26] Shohei Koide and Masami Kato.  3-d human navigation system considering various transition preferences.  In 2005 IEEE International Conference on Systems, Man and Cybernetics, volume 1, pages 859–864. IEEE, 2005.
  * [27] Benjamin Kuipers.  Modeling spatial knowledge.  Cognitive science, 2(2):129–153, 1978.
  * [28] Carol A Lawton.  Gender and regional differences in spatial referents used in direction giving.  Sex Roles, 44(5):321–337, 2001.
  * [29] Kevin Lynch.  The image of the city (vol. 11), 1960.
  * [30] Bharadwaj RK Mantha, Carol C Menassa, Vineet R Kamat, and Clive R D’Souza.  Evaluation of preference-and constraint-sensitive path planning for assisted navigation in indoor building environments.  Journal of Computing in Civil Engineering, 34(1):04019050, 2020\.
  * [31] David M Mark.  Automated route selection for navigation.  IEEE Aerospace and Electronic Systems Magazine, 1(9):2–5, 1986\.
  * [32] Richar E Mayer.  Visual aids to knowledge construction: Building mental representations from pictures and words.  In Advances in psychology, volume 108, pages 125–138. Elsevier, 1994.
  * [33] Tobias Meilinger, Markus Knauff, and Heinrich H Bülthoff.  Working memory in wayfinding—a dual task experiment in a virtual city.  Cognitive Science, 32(4):755–770, 2008.
  * [34] Daniel R Montello.  Spatial orientation and the angularity of urban routes: A field study.  Environment and Behavior, 23(1):47–69, 1991.
  * [35] Daniel R Montello and Martin Raubal.  Functions and applications of spatial cognition.  In Handbook of Spatial Cognition, page 249–264. American Psychological Association, 2013.
  * [36] Manuel Müller, Christina Ohm, Florin Schwappach, and Bernd Ludwig.  The path of least resistance.  KI-Künstliche Intelligenz, 31(2):125–134, 2017.
  * [37] Michael J O’Neill.  Effects of familiarity and plan complexity on wayfinding in simulated buildings.  Journal of Environmental Psychology, 12(4):319–327, 1992.
  * [38] Arto Puikkonen, Ari-Heikki Sarjanoja, Merja Haveri, Jussi Huhtala, and Jonna Häkkilä.  Towards designing better maps for indoor navigation: experiences from a case study.  In Proceedings of the 8th international conference on mobile and ubiquitous multimedia, pages 1–4, 2009.
  * [39] Daniele Quercia, Rossano Schifanella, and Luca Maria Aiello.  The shortest path to happiness: Recommending beautiful, quiet, and happy routes in the city.  In Proceedings of the 25th ACM conference on Hypertext and social media, pages 116–125, 2014.
  * [40] Kai-Florian Richter and Alexander Klippel.  You-are-here maps: Wayfinding support as location based service.  GI-Technologien für Verkehr und Logistik. Beiträge zu den Münsteraner GI-Tagen, 20:21, 2002.
  * [41] Edward K Sadalla and Daniel R Montello.  Remembering changes in direction.  Environment and Behavior, 21(3):346–363, 1989.
  * [42] Wilson Sakpere, Michael Adeyeye-Oshin, and Nhlanhla BW Mlitwa.  A state-of-the-art survey of indoor positioning and navigation systems and technologies.  South African Computer Journal, 29(3):145–197, 2017.
  * [43] Masashi Soeda, Noriko Kushiyama, and Ryuzo Ohno.  Wayfinding in cases with vertical motion.  Proceedings of MERA, 97:559–564, 1997.
  * [44] Robert J Sternberg.  Metaphors of mind: Conceptions of the nature of intelligence.  Cambridge University Press, 1990.
  * [45] Mathieu Taillade, Bernard N’Kaoua, and Hélène Sauzéon.  Age-related differences and cognitive correlates of self-reported and direct navigation performance: the effect of real and virtual test conditions manipulation.  Frontiers in Psychology, 6:2034, 2016.
  * [46] YingLi Tian, Xiaodong Yang, Chucai Yi, and Aries Arditi.  Toward a computer vision-based wayfinding aid for blind persons to access unfamiliar indoor environments.  Machine vision and applications, 24(3):521–535, 2013.
  * [47] turn.  Cambridge Dictionary.  Cambridge University Press, 2021.  URL: https://dictionary.cambridge.org/dictionary/english/turn.
  * [48] Alasdair Turner.  The role of angularity in route choice.  In International Conference on Spatial Information Theory, pages 489–504. Springer, 2009.
  * [49] Manuel Ullmann.  Datengetriebene optimierung präferenzadaptiver fußwegrouten durch gebäudekomplexe, September 2020.  URL: https://epub.uni-regensburg.de/43697/.
  * [50] Ann Vanclooster, Nina Vanhaeren, Pepijn Viaene, Kristien Ooms, Laure De Cock, Veerle Fack, Nico Van de Weghe, and Philippe De Maeyer.  Turn calculations for the indoor application of the fewest turns path algorithm.  International Journal of Geographical Information Science, 33(11):2284–2304, 2019.
  * [51] Ann Vanclooster, Pepijn Viaene, Nico Van de Weghe, Veerle Fack, and Philippe De Maeyer.  Analyzing the applicability of the least risk path algorithm in indoor space.  In ISPRS Acquisition and Modelling of Indoor and Enclosed Environments 2013 (Indoor 3D), volume 2, pages 19–26. International Society for Photogrammetry and Remote Sensing (ISPRS), 2013.
  * [52] Liping Yang and Michael Worboys.  Similarities and differences between outdoor and indoor space from the perspective of navigation.  Poster presented at COSIT, 2011.
  * [53] John Zacharias.  Pedestrian behavior pedestrian behavior and perception in urban walking environments.  Journal of planning literature, 16(1):3–18, 2001.
  * [54] Shanjiang Zhu and David Levinson.  Do people use the shortest path? an empirical test of wardrop’s first principle.  PloS one, 10(8):e0134322, 2015.