Publication type: 
Article in Proceedings 
Author: 
Dominik Lücke, Till Mossakowski 
Editor: 
A. GomezPerez, T. Agotnes 
Title: 
A much better polynomial time approximation of consistency in the LR calculus 
Book / Collection title: 
Proceedings of the 5th Starting AI Researcher Symposium (STAIRS 2010) 
Volume: 
222 
Page(s): 
175 – 185 
Series: 
Frontiers in Artificial Intelligence and Applications 
Year published: 
2010 
Publisher: 
IOS Press, Amsterdam 
Abstract: 
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 OPRA1
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
flipflop 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 NPhard.
In this paper we propose a new polynomial time approximation
procedure for this NPhard 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.unibremen.de/~till/papers/stairs2010.pdf 
Keywords: 
qualitative calculus consistency 
Status: 
Reviewed 
Last updated: 
31. 01. 2011 