Evaluating and minimizing ambiguities in qualitative route instructions

Route 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.