Encoding Relative Orientation and Mereotopology Relations with Geometric Constraints in CLP(QS)

• Autorzy: Carl Schultz , Mehul Bhatt
• Języki publikacji: EN

Abstrakty

EN

One approach for encoding the semantics of spatial relations within a declarative programming framework is by systems of polynomial constraints. However, solving such constraints is computationally intractable in general (i.e. the theory of realclosed fields), and thus far the proposed symbolic algebraic methods do not scale to real world problems. In this paper we address this intractability by investigating the use of constructive geometric constraint solving (in combination with numerical optimisation) within the context of constraint logic programming over qualitative spaces, CLP(QS). We present novel geometric encodings for relative orientation and mereotopology relations and show that our encodings are significantly more robust than other proposed approaches for directly encoding inequalities, due to our encodings being based on a standard, well known set of relations encoded as quadratic equations. Our encodings are general (i.e. not implementation specific) and can thus be directly employed in all standard geometric constraint solvers, particularly solvers that are prominent within the Computer Aided Design and Manufacturing communities. We empirically evaluate our approach on a range of benchmark problems from the Qualitative Spatial Reasoning community, and show that our method outperforms other symbolic algebraic approaches to spatial reasoning by orders of magnitude on those benchmark problems (such as Cylindrical Algebraic Decomposition).(original abstract)

Słowa kluczowe

EN

Mathematics

PL

Matematyka

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2015
• Tom: 7
• Strony: 55--63

Twórcy

autor

Carl Schultz

• University of Münster, Germany

autor

Mehul Bhatt

• University of Bremen, Germany

Bibliografia

• M. Aiello, I. E. Pratt-Hartmann, and J. F. v. Benthem. Handbook of Spatial Logics. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2007. ISBN 978-1-4020- 5586-7.
• D. S. Arnon, G. E. Collins, and S. McCallum. Cylindrical Algebraic Decomposition I: The basic algorithm. SIAM Journal on Computing, 13(4):865-877, 1984.
• M. Bhatt, J. H. Lee, and C. Schultz. CLP(QS): A Declarative Spatial Reasoning Framework. In Proceedings of the 10th international conference on Spatial information theory, COSIT'11, pages 210-230, Berlin, Heidelberg, 2011. Springer- Verlag. ISBN 978-3-642-23195-7.
• M. Bhatt, C. Schultz, and C. Freksa. The 'Space' in Spatial Assistance Systems: Conception, Formalisation and Computation. In T. Tenbrink, J. Wiener, and C. Claramunt, editors, Representing space in cognition: Interrelations of behavior, language, and formal models. Series: Explorations in Language and Space. 978- 0-19-967991-1, Oxford University Press, 2013.
• S. Borgo. Euclidean and mereological qualitative spaces: A study of SCC and DCC. In C. Boutilier, editor, IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, pages 708-713, 2009. URL http://ijcai.org/papers09/Papers/IJCAI09-123.pdf.
• D. Bouhineau. Solving geometrical constraint systems using CLP based on linear constraint solver. In Artificial Intelligence and Symbolic Mathematical Computation, pages 274-288. Springer, 1996.
• D. Bouhineau, L. Trilling, and J. Cohen. An application of CLP: Checking the correctness of theorems in geometry. Constraints, 4(4):383-405, 1999.
• W. Bouma, I. Fudos, C. Hoffmann, J. Cai, and R. Paige. Geometric constraint solver. Computer-Aided Design, 27(6):487-501, 1995.
• R. H. Byrd, P. Lu, J. Nocedal, and C. Zhu. A limited memory algorithm for bound constrained optimization. SIAM Journal on Scientific Computing, 16(5):1190-1208, 1995.
• S.-C. Chou. Mechanical geometry theorem proving, volume 41. Springer Science & Business Media, 1988.
• A. G. Cohn and N. M. Gotts. The Ôegg-yolkÕrepresentation of regions with indeterminate boundaries. Geographic objects with indeterminate boundaries, 2: 171-187, 1996.
• G. E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decompostion. In Automata Theory and Formal Languages 2nd GI Conference Kaiserslautern, May 20-23, 1975, pages 134-183. Springer, 1975.
• G. E. Collins and H. Hong. Partial cylindrical algebraic decomposition for quantifier elimination. Journal of Symbolic Computation, 12(3):299 - 328, 1991. ISSN 0747- 7171. doi: http://dx.doi.org/10.1016/S0747-7171(08)80152-6. URL http://www. sciencedirect.com/science/article/pii/S0747717108801526.
• X.-S. Gao and S.-C. Chou. Solving geometric constraint systems. ii. a symbolic approach and decision of rc-constructibility. Computer-Aided Design, 30(2):115-122, 1998.
• X.-S. Gao and S.-C. Chou. Solving geometric constraint systems. i. a global propagation approach. Computer-Aided Design, 30(1):47-54, 1998.
• J.-X. Ge, S.-C. Chou, and X.-S. Gao. Geometric constraint satisfaction using optimization methods. Computer-Aided Design, 31(14):867-879, 1999.
• P. J. Hayes. The second naive physics manifesto. In J. R. Hubbs and R. C. Moore, editors, Formal Theories of the Commonsense World. Ablex Publishing Corporation, Norwood, NJ, 1985.
• S. M. Hazarika. Qualitative Spatial Change : Space-Time Histories and Continuity. PhD thesis, The University of Leeds, School of Computing, 2005. Supervisor - Anthony Cohn.
• T. L. Heath (ed). The thirteen books of Euclid's Elements, volume 1. Courier Dover Publications, 1956.
• D. Kapur and J. L. Mundy, editors. Geometric Reasoning. MIT Press, Cambridge, MA, USA, 1988. ISBN 0-262-61058-2.
• P. B. Ladkin and R. D. Maddux. On binary constraint problems. Journal of the ACM (JACM), 41(3):435-469, 1994.
• J. H. Lee. The complexity of reasoning with relative directions. In 21st European Conference on Artificial Intelligence (ECAI 2014), 2014.
• J. H. Lee and D. Wolter. A new perspective on reasoning with qualitative spatial knowledge. In IJCAI-2011 Workshop 27, page 3, 2011.
• Y.-T. Li, S.-M. Hu, and J.-G. Sun. A constructive approach to solving 3-d geometric constraint systems using dependence analysis. Computer-Aided Design, 34(2):97- 108, 2002.
• G. Ligozat. Qualitative Spatial and Temporal Reasoning. Wiley-ISTE, 2011.
• G. F. Ligozat. Qualitative triangulation for spatial reasoning. In Spatial Information Theory A Theoretical Basis for GIS, pages 54-68. Springer, 1993.
• J. C. Owen. Algebraic solution for geometry from dimensional constraints. In Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, pages 397-407. ACM, 1991.
• G. Pesant and M. Boyer. QUAD-CLP (R): Adding the power of quadratic constraints. In Principles and Practice of Constraint Programming, pages 95-108. Springer, 1994.
• G. Pesant and M. Boyer. Reasoning about solids using constraint logic programming. Journal of Automated Reasoning, 22(3):241-262, 1999.
• D. A. Randell, Z. Cui, and A. Cohn. A spatial logic based on regions and connection. In KR'92. Principles of Knowledge Representation and Reasoning, pages 165-176. Morgan Kaufmann, San Mateo, California, 1992.
• C. Schultz and M. Bhatt. Towards a Declarative Spatial Reasoning System. In 20th European Conference on Artificial Intelligence (ECAI 2012), 2012.
• C. Schultz and M. Bhatt. Declarative spatial reasoning with boolean combinations of axis-aligned rectangular polytopes. In ECAI 2014 - 21st European Conference on Artificial Intelligence, pages 795-800, 2014.
• H. Winroth. Dynamic projective geometry. Tekniska högsk., 1999.