Document Open Access Logo

On the Utility of Neighbourhood Singleton-Style Consistencies for Qualitative Constraint-Based Spatial and Temporal Reasoning

Authors Michael Sioutis , Anastasia Paparrizou , Tomi Janhunen

PDF
Thumbnail PDF

File

LIPIcs.TIME.2019.14.pdf
  • Filesize: 0.56 MB
  • 17 pages

Document Identifiers

Author Details

Michael Sioutis
  • Department of Computer Science, Aalto University, Espoo, Finland
Anastasia Paparrizou
  • CRIL CNRS UMR 8188, Artois University, Lens, France
Tomi Janhunen
  • Department of Computer Science, Aalto University, Espoo, Finland
  • Tampere University, Tampere, Finland

Cite AsGet BibTex

Michael Sioutis, Anastasia Paparrizou, and Tomi Janhunen. On the Utility of Neighbourhood Singleton-Style Consistencies for Qualitative Constraint-Based Spatial and Temporal Reasoning. In 26th International Symposium on Temporal Representation and Reasoning (TIME 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 147, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.TIME.2019.14

Abstract

A singleton-style consistency is a local consistency that verifies if each base relation (atom) of each constraint of a qualitative constraint network (QCN) can serve as a support with respect to the closure of that network under a (naturally) weaker local consistency. This local consistency is essential for tackling fundamental reasoning problems associated with QCNs, such as the satisfiability checking or the minimal labeling problem, but can suffer from redundant constraint checks, especially when those checks occur far from where the pruning usually takes place. In this paper, we propose singleton-style consistencies that are applied just on the neighbourhood of a singleton-checked constraint instead of the whole network. We make a theoretical comparison with existing consistencies and consequently prove some properties of the new ones. In addition, we propose algorithms to enforce our consistencies, as well as parsimonious variants thereof, that are more efficient in practice than the state of the art. We make an experimental evaluation with random and structured QCNs of Interval Algebra in the phase transition region to demonstrate the potential of our approach.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
  • Computing methodologies → Temporal reasoning
  • Computing methodologies → Spatial and physical reasoning
Keywords
  • Qualitative constraints
  • spatial and temporal reasoning
  • singleton-style consistencies
  • neighbourhood
  • minimal labeling problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. James F. Allen. Maintaining Knowledge about Temporal Intervals. Commun. ACM, 26:832-843, 1983. Google Scholar
  2. Nouhad Amaneddine, Jean-François Condotta, and Michael Sioutis. Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints. In IJCAI, 2013. Google Scholar
  3. Amine Balafrej, Christian Bessiere, El-Houssine Bouyakhf, and Gilles Trombettoni. Adaptive Singleton-Based Consistencies. In AAAI, 2014. Google Scholar
  4. Albert-László Barabási and Réka Albert. Emergence of Scaling in Random Networks. Science, 286:509-512, 1999. Google Scholar
  5. Hachemi Bennaceur and Mohamed-Salah Affane. Partition-k-AC: An Efficient Filtering Technique Combining Domain Partition and Arc Consistency. In CP, 2001. Google Scholar
  6. Mehul Bhatt, Hans Guesgen, Stefan Wölfl, and Shyamanta Hazarika. Qualitative Spatial and Temporal Reasoning: Emerging Applications, Trends, and Directions. Spatial Cognition & Computation, 11:1-14, 2011. Google Scholar
  7. Mehul Bhatt and Jan Oliver Wallgrün. Geospatial Narratives and Their Spatio-Temporal Dynamics: Commonsense Reasoning for High-Level Analyses in Geographic Information Systems. ISPRS Int. J. Geo-Information, 3:166-205, 2014. Google Scholar
  8. Manuel Bodirsky, Peter Jonsson, Barnaby Martin, and Antoine Mottet. Classification Transfer for Qualitative Reasoning Problems. In IJCAI, 2018. Google Scholar
  9. Manuel Bodirsky and Stefan Wölfl. RCC8 is polynomial on networks of bounded treewidth. In IJCAI, 2011. Google Scholar
  10. Assef Chmeiss and Jean-François Condotta. Consistency of Triangulated Temporal Qualitative Constraint Networks. In ICTAI, 2011. Google Scholar
  11. Jean-François Condotta and Christophe Lecoutre. A Class of ^⋄_f-Consistencies for Qualitative Constraint Networks. In KR, 2010. Google Scholar
  12. Romuald Debruyne and Christian Bessière. Some Practicable Filtering Techniques for the Constraint Satisfaction Problem. In IJCAI, 1997. Google Scholar
  13. Rina Dechter, Itay Meiri, and Judea Pearl. Temporal Constraint Networks. Artif. Intell., 49:61-95, 1991. Google Scholar
  14. Rina Dechter and Judea Pearl. Network-Based Heuristics for Constraint-Satisfaction Problems. Artif. Intell., 34:1-38, 1987. Google Scholar
  15. Krishna Sandeep Reddy Dubba, Anthony G. Cohn, David C. Hogg, Mehul Bhatt, and Frank Dylla. Learning Relational Event Models from Video. J. Artif. Intell. Res., 53:41-90, 2015. Google Scholar
  16. Frank Dylla, Jae Hee Lee, Till Mossakowski, Thomas Schneider, André van Delden, Jasper van de Ven, and Diedrich Wolter. A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties. ACM Comput. Surv., 50:7:1-7:39, 2017. Google Scholar
  17. Frank Dylla, Till Mossakowski, Thomas Schneider, and Diedrich Wolter. Algebraic Properties of Qualitative Spatio-Temporal Calculi. In COSIT, 2013. Google Scholar
  18. Frank Dylla and Jan Oliver Wallgrün. Qualitative Spatial Reasoning with Conceptual Neighborhoods for Agent Control. J. Intell. Robotic Syst., 48:55-78, 2007. Google Scholar
  19. Alfonso Gerevini and Alessandro Saetti. Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure. Artif. Intell., 175:556-585, 2011. Google Scholar
  20. Martin Charles Golumbic and Ron Shamir. Complexity and Algorithms for Reasoning about Time: A Graph-Theoretic Approach. J. ACM, 40:1108-1133, 1993. Google Scholar
  21. Georg Gottlob. On minimal constraint networks. Artif. Intell., 191-192:42-60, 2012. Google Scholar
  22. Jinbo Huang. Compactness and Its Implications for Qualitative Spatial and Temporal Reasoning. In KR, 2012. Google Scholar
  23. Jinbo Huang, Jason Jingshi Li, and Jochen Renz. Decomposition and tractability in qualitative spatial and temporal reasoning. Artif. Intell., 195:140-164, 2013. Google Scholar
  24. Peter Jonsson and Victor Lagerkvist. Why are CSPs Based on Partition Schemes Computationally Hard? In MFCS, 2018. Google Scholar
  25. Nikhil Krishnaswamy, Scott Friedman, and James Pustejovsky. Combining Deep Learning and Qualitative Spatial Reasoning to Learn Complex Structures from Sparse Examples with Noise. In AAAI, 2019. Google Scholar
  26. Olivier Lhomme. Quick Shaving. In AAAI, 2005. Google Scholar
  27. Jason Jingshi Li, Jinbo Huang, and Jochen Renz. A divide-and-conquer approach for solving interval algebra networks. In IJCAI, 2009. Google Scholar
  28. Gérard Ligozat. Qualitative Spatial and Temporal Reasoning. Wiley, 2013. Google Scholar
  29. Gérard Ligozat and Jochen Renz. What Is a Qualitative Calculus? A General Framework. In PRICAI, 2004. Google Scholar
  30. Weiming Liu and Sanjiang Li. Solving Minimal Constraint Networks in Qualitative Spatial and Temporal Reasoning. In CP, 2012. Google Scholar
  31. Ugo Montanari. Networks of constraints: Fundamental properties and applications to picture processing. Inf. Sci., 7:95-132, 1974. Google Scholar
  32. Bernhard Nebel. Solving Hard Qualitative Temporal Reasoning Problems: Evaluating the Efficiency of Using the ORD-Horn Class. Constraints, 1:175-190, 1997. Google Scholar
  33. Anastasia Paparrizou and Kostas Stergiou. On Neighborhood Singleton Consistencies. In IJCAI, 2017. Google Scholar
  34. David A. Randell, Zhan Cui, and Anthony Cohn. A Spatial Logic Based on Regions & Connection. In KR, 1992. Google Scholar
  35. Jochen Renz and Gérard Ligozat. Weak Composition for Qualitative Spatial and Temporal Reasoning. In CP, 2005. Google Scholar
  36. Jochen Renz and Bernhard Nebel. On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus. Artif. Intell., 108:69-123, 1999. Google Scholar
  37. Jochen Renz and Bernhard Nebel. Qualitative Spatial Reasoning Using Constraint Calculi. In Handbook of Spatial Logics, pages 161-215. Springer, 2007. Google Scholar
  38. Michael Sioutis, Jean-François Condotta, and Manolis Koubarakis. An Efficient Approach for Tackling Large Real World Qualitative Spatial Networks. Int. J. Artif. Intell. Tools, 25:1-33, 2016. Google Scholar
  39. Michael Sioutis, Zhiguo Long, and Sanjiang Li. Efficiently Reasoning about Qualitative Constraints through Variable Elimination. In SETN, 2016. Google Scholar
  40. Michael Sioutis, Zhiguo Long, and Sanjiang Li. Leveraging Variable Elimination for Efficiently Reasoning about Qualitative Constraints. Int. J. Artif. Intell. Tools, 27:1860001, 2018. Google Scholar
  41. Michael Sioutis, Anastasia Paparrizou, and Jean-François Condotta. A Lazy Algorithm to Efficiently Approximate Singleton Path Consistency for Qualitative Constraint Networks. In ICTAI, 2017. Google Scholar
  42. Michael Sioutis, Anastasia Paparrizou, and Jean-François Condotta. Collective Singleton-Based Consistency for Qualitative Constraint Networks. In TIME, 2017. Google Scholar
  43. Michael Sioutis, Anastasia Paparrizou, and Jean-François Condotta. Collective Singleton-Based Consistency for Qualitative Constraint Networks: Theory and Practice. Theor. Comput. Sci, 2019. In press. Google Scholar
  44. Michael Sioutis, Yakoub Salhi, and Jean-François Condotta. Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning. Knowl. Eng. Rev., 32:e4, 2016. Google Scholar
  45. Robert E. Tarjan and Mihalis Yannakakis. Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM J. Comput., 13:566-579, 1984. Google Scholar
  46. Peter van Beek and Rina Dechter. On the Minimality and Decomposability of Row-Convex Constraint Networks. J. ACM, 42:543-561, 1995. Google Scholar
  47. Richard J. Wallace. Neighbourhood SAC: Extensions and new algorithms. AI Commun., 29:249-268, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact