Westphal, MatthiasRenz, Jochen2015-12-10November 19781450310314http://hdl.handle.net/1885/38982Route navigation is a widely studied subject from both cognitive and practical points of view. A particular aspect is the generation of (verbal) route instructions that are robust with respect to ambiguous verbal terms. Work in this area usually builds on counting the number of ambiguous turn options along a route. Simple graph search can then be used to derive a route whose description is the most fault-tolerant according to this measure. In this paper we contrast this approach with a probabilistic planning one that estimates the probability of reaching the destination given a probabilistic model of an agent interpreting the route instruction. To this end, we discuss different models of agents, the evaluation of route instructions and derive optimal and approximate approaches for the planning problem.Keywords: Fault-tolerant; Graph search; Planning problem; Probabilistic models; Probabilistic planning; Qualitative reasoning; route instructions; Route navigation; Artificial intelligence; Cognitive systems; Information systems; Geographic information systems qualitative reasoning; route instructions201110.1145/2093973.20939972016-02-24