@inproceedings{1ed39c5f154f4a229613191359e05078,
title = "On qualitative route descriptions: Representation and computational complexity",
abstract = "The generation of route descriptions is a fundamental task of navigation systems. A particular problem in this context is to identify routes that can easily be described and processed by users. In this work, we present a framework for representing route networks with the qualitative information necessary to evaluate and optimize route descriptions with regard to ambiguities in them. We identify different agent models that differ in how agents are assumed to process route descriptions while navigating through route networks. Further, we analyze the computational complexity of matching route descriptions and paths in route networks in dependency of the agent model. Finally we empirically evaluate the influence of the agent model on the optimization and the processing of route instructions.",
author = "Matthias Westphal and Stefan Wo{\"l}fl and Bernhard Nebel and Jochen Renz",
year = "2011",
doi = "10.5591/978-1-57735-516-8/IJCAI11-191",
language = "English",
isbn = "9781577355120",
series = "IJCAI International Joint Conference on Artificial Intelligence",
pages = "1120--1125",
booktitle = "IJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence",
note = "22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 ; Conference date: 16-07-2011 Through 22-07-2011",
}