oru.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Spatial Symmetry Driven Pruning Strategies for Efficient Declarative Spatial Reasoning
Institute for Geoinformatics, University of Münster, Münster, Germany; The DesignSpace Group, Bremen, Germany.
Department of Computer Science, University of Bremen, Bremen, Germany; The DesignSpace Group, Bremen, Germany. (AASS)ORCID-id: 0000-0002-6290-5492
2015 (Engelska)Ingår i: Spatial Information Theory: 12th International Conference, COSIT 2015, Santa Fe, NM, USA, October 12-16, 2015, Proceedings / [ed] Sara Irina Fabrikant, Martin Raubal, Michela Bertolotto, Clare Davies, Scott Freundschuh, Scott Bell, Springer , 2015, Vol. 9368, s. 331-353Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Declarative spatial reasoning denotes the ability to (declaratively) specify and solve real-world problems related to geometric and qualitative spatial representation and reasoning within standard knowledge representation and reasoning (KR) based methods (e. g., logic programming and derivatives). 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 real-closed fields).

We present a new algorithm, implemented within the declarative spatial reasoning system CLP(QS), that drastically improves the performance of deciding the consistency of spatial constraint graphs over conventional polynomial encodings. We develop pruning strategies founded on spatial symmetries that form equivalence classes (based on affine transformations) at the qualitative spatial level. Moreover, pruning strategies are themselves formalised as knowledge about the properties of space and spatial symmetries. We evaluate our algorithm using a range of benchmarks in the class of contact problems, and proofs in mereology and geometry. The empirical results show that CLP(QS) with knowledge-based spatial pruning outperforms conventional polynomial encodings by orders of magnitude, and can thus be applied to problems that are otherwise unsolvable in practice.

Ort, förlag, år, upplaga, sidor
Springer , 2015. Vol. 9368, s. 331-353
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 9368
Nyckelord [en]
Declarative spatial reasoning; Geometric reasoning; Logic programming; Knowledge representation and reasoning
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:oru:diva-64161DOI: 10.1007/978-3-319-23374-1_16ISI: 000374470900016Scopus ID: 2-s2.0-84951291990ISBN: 978-3-319-23373-4 (tryckt)ISBN: 978-3-319-23374-1 (digital)OAI: oai:DiVA.org:oru-64161DiVA, id: diva2:1174423
Konferens
12th International Conference on Spatial Information Theory (COSIT 2015), Santa Fe, United States, October 12-16, 2015
Tillgänglig från: 2018-01-15 Skapad: 2018-01-15 Senast uppdaterad: 2018-01-19Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Personposter BETA

Bhatt, Mehul

Sök vidare i DiVA

Av författaren/redaktören
Bhatt, Mehul
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 149 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf