Universität Bremen  
  FB 3  
  AG BKB > Publikationen > Suche > Deutsch

Suche nach Veröffentlichungen - Detailansicht

Art der Veröffentlichung: Artikel in Konferenzband
Autor: Dominik Lücke, Till Mossakowski
Herausgeber: A. Gomez-Perez, T. Agotnes
Titel: A much better polynomial time approximation of consistency in the LR calculus
Buch / Sammlungs-Titel: Proceedings of the 5th Starting AI Researcher Symposium (STAIRS 2010)
Band: 222
Seite(n): 175 – 185
Serie / Reihe: Frontiers in Artificial Intelligence and Applications
Erscheinungsjahr: 2010
Verleger: IOS Press, Amsterdam
Abstract / Kurzbeschreibung: In the area of qualitative spatial reasoning, the LR calculus is a quite simple constraint calculus that forms the core of several orientation calculi like the dipole calculi and the OPRA-1 calculus.

For many qualitative spatial calculi, algebraic closure is applied as standard polynomial time decision procedure. For a long time it was believed that this can decide the consistency of scenarios of the quite simple and basic LR calculus (a refinement of Ligozat's flip-flop calculus). However, Lücke et al. showed that algebraic closure is a quite bad approximation of consistency of LR scenarios: scenarios in the base relations "Left" and "Right" are always algebraically closed. So algebraic closure is completely useless here. Furthermore, Wolter and Lee have proved that the consistency problem for any calculus with relative orientation containing the relations "Left" and "Right" is NP-hard.

In this paper we propose a new polynomial time approximation procedure for this NP-hard problem. It is based on the angles of triangles in the Euclidean plane. LR scenarios are translated to sets of linear inequations over the real numbers. We evaluate the quality of this procedure by comparing it both to the old approximation using algebraic closure and to the (exact but exponential time) Buchberger algorithm for Gröbner bases.
Internet: http://www.booksonline.iospress.nl/Content/View.aspx?piid=18909
PDF Version: http://www.informatik.uni-bremen.de/~till/papers/stairs2010.pdf
Schlagworte: qualitative calculus consistency
Status: Reviewed
Letzte Aktualisierung: 31. 01. 2011

 Zurück zum Suchergebnis
Autor: Automatisch generierte Seite
Zuletzt geändert am: 23. Februar 2006   impressum