Inproceedings,
Routing by Landmarks
Proc. 6th Swiss Transport Research Conf. (STRC'06), Ascona, (2006)CD-ROM.
Abstract
A route in a network can be described as a sequence
of nodes. Given a route, travellers need directions
to follow it, which are preferably expressed as a
sequence of instructions, as for instance, "face
towards the tower" and "move along the river". This
paper presents a method to find routes in a network
with the property that they can be described by a
simple sequence of instructions. The key problems
that we need to solve are (1)~how to attribute
landmark information to the network and (2)~how to
find an optimal route. We approach the first problem
by using landmarks as parts of instructions and
mapping instructions to sets of edges in the
network. The second problem can be solved by
building an auxiliary graph such that a standard
Dijkstra shortest path algorithm can be used to find
optimal routes. Preliminary tests indicate that our
approaches produce good results.
