On Qualitative Route Descriptions: Representation and Computational Complexity

Westphal, Matthias; Wölfl, Stefan; Nebel, Bernhard; Renz, Jochen

doi:10.5591/978-1-57735-516-8/IJCAI11-191

On Qualitative Route Descriptions: Representation and Computational Complexity

Matthias Westphal, Stefan Wölfl, Bernhard Nebel, Jochen Renz

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1120-1124.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-191

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.

Matthias Westphal, Stefan Wölfl, Bernhard Nebel, and Jochen Renz. 2011. On Qualitative Route Descriptions: Representation and Computational Complexity. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1120–1124. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-191

@inproceedings{ijcai2011p191,
  title     = {On Qualitative Route Descriptions: Representation and Computational Complexity},
  author    = {Westphal, Matthias and Wölfl, Stefan and Nebel, Bernhard and Renz, Jochen},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {1120--1124},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-191},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-191},
}

TY  - CPAPER
TI  - On Qualitative Route Descriptions: Representation and Computational Complexity
AU  - Westphal, Matthias
AU  - Wölfl, Stefan
AU  - Nebel, Bernhard
AU  - Renz, Jochen
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 1120
EP  - 1124
DO  - 10.5591/978-1-57735-516-8/IJCAI11-191
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-191
ER  -