On Qualitative Route Descriptions
Matthias Westphal, Stefan Woelfl, Bernhard Nebel and Jochen Renz
The generation of route descriptions is a fundamental part of navigation systems. For several decades there has been an interest in identifying routes whose descriptions have desirable properties, e.g. a short description length. Several other criteria can be formalized that have applications in navigation assistance systems for drivers, pedestrians, travelers, or shoppers. For many criteria an optimized route can be found by shortest path algorithms with an appropriate cost function. However, we argue that these do not properly take into account ambiguities in descriptions and their effect on agents following a description. In this work, we present a unifying framework for representing route networks with the qualitative information necessary to evaluate, derive and optimize route descriptions. The qualitative primitives used are relations between line segments taken from established qualitative calculi studied in the qualitative spatio-temporal reasoning field. We show how descriptions in a fixed qualitative vocabulary can be evaluated with regard to their inherent ambiguities, enabling us to properly assess reliability of route descriptions. Further, we present complexity results on problems of matching descriptions to routes in dependency of underlying assumptions about agents.