Document Open Access Logo

Learning Qualitative Constraint Networks

Authors Malek Mouhoub , Hamad Al Marri, Eisa Alanazi

PDF
Thumbnail PDF

File

LIPIcs.TIME.2018.19.pdf
  • Filesize: 438 kB
  • 13 pages

Document Identifiers

Author Details

Malek Mouhoub
  • University of Regina 3737 Wascana Parkway, Regina SK S4V 0A2, Canada
Hamad Al Marri
  • University of Regina 3737 Wascana Parkway, Regina SK S4V 0A2, Canada
Eisa Alanazi
  • Um Al Qura University Aif Road, 21955, Mecca, Makkah Province, Saudi Arabia

Funding

  • Mouhoub, Malek: Natural Sciences and Engineering Research Council of Canada (NSERC), RGPIN-2016-05673

Cite As Get BibTex

Malek Mouhoub, Hamad Al Marri, and Eisa Alanazi. Learning Qualitative Constraint Networks. In 25th International Symposium on Temporal Representation and Reasoning (TIME 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 120, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.TIME.2018.19

Abstract

Temporal and spatial reasoning is a fundamental task in artificial intelligence and its related areas including scheduling, planning and Geographic Information Systems (GIS). In these applications, we often deal with incomplete and qualitative information. In this regard, the symbolic representation of time and space using Qualitative Constraint Networks (QCNs) is therefore substantial.
We propose a new algorithm for learning a QCN from a non expert. The learning process includes different cases where querying the user is an essential task. Here, membership queries are asked in order to elicit temporal or spatial relationships between pairs of temporal or spatial entities. During this acquisition process, constraint propagation through Path Consistency (PC) is performed in order to reduce the number of membership queries needed to reach the target QCN. We use the learning theory machinery to prove some limits on learning path consistent QCNs from queries. The time performances of our algorithm have been experimentally evaluated using different scenarios.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Temporal reasoning
Keywords
  • Temporal Reasoning
  • Qualitative Constraint Network (QCN)
  • Constraint Learning
  • Path Consistency
  • Constraint Propagation

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. Communications of the ACM, 26(11):832-843, 1983. Google Scholar
  2. Dana Angluin. Queries and concept learning. Machine Learning, 2(4):319-342, 1988. Google Scholar
  3. R. Arcangioli and N. Lazaar. Multiple Constraint Acquisition. In Workshop on Constraints and Preferences for Configuration and Recommendation, the Twenty-Forth International Joint Conference on Artificial Intelligence, 2015. Google Scholar
  4. Philippe Balbiani, Jean-François Condotta, and Luis Farinas del Cerro. A new tractable subclass of the rectangle algebra. In Proceedings of the 16th international joint conference on Artifical intelligence - Volume 1, pages 442-447, 1999. Google Scholar
  5. C. Bessiere, R. Coletta, B. O'Sullivan, and M. Paulin. Query-Driven Constraint Acquisition. In Proceedings of the Twentiest International Joint Conference on Artificial Intelligence, pages 50-55, 2007. Google Scholar
  6. Christian Bessiere, Remi Coletta, Emmanuel Hebrard, George Katsirelos, Nadjib Lazaar, Nina Narodytska, Claude-Guy Quimper, and Toby Walsh. Constraint acquisition via partial queries. In IJCAI'2013: 23rd International Joint Conference on Artificial Intelligence, page 7, 2013. Google Scholar
  7. Christian Bessiere, Frédéric Koriche, Nadjib Lazaar, and Barry O'Sullivan. Constraint acquisition. Artificial Intelligence, 244:315-342, 2017. URL: http://dx.doi.org/10.1016/j.artint.2015.08.001.
  8. Christian Bliek and Djamila Sam-Haroud. Path consistency on triangulated constraint graphs. In IJCAI, volume 99, pages 456-461. Citeseer, 1999. Google Scholar
  9. Rina Dechter. Constraint Processing. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003. Google Scholar
  10. Max J. Egenhofer and Robert D. Franzosa. Point-set topological spatial relations. International Journal of Geographical Information Systems, 5(2):161-174, 1991. Google Scholar
  11. Sally A. Goldman and Michael J. Kearns. On the complexity of teaching. Journal of Computer and System Sciences, 50:20-31, 1995. Google Scholar
  12. Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, USA, 1994. Google Scholar
  13. Sanjiang Li and Mingsheng Ying. Region connection calculus: Its models and composition table. Artificial Intelligence, 145(1):121-146, 2003. Google Scholar
  14. Zhiguo Long, Michael Sioutis, and Sanjiang Li. Efficient path consistency algorithm for large qualitative constraint networks. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, pages 1202-1208. AAAI Press, 2016. Google Scholar
  15. Roger Mohr and Thomas C Henderson. Arc and path consistency revisited. Artificial intelligence, 28(2):225-233, 1986. Google Scholar
  16. Malek Mouhoub and Amrudee Sukpan. Managing temporal constraints with preferences. Spatial Cognition & Computation, 8(1-2):131-149, 2008. Google Scholar
  17. Malek Mouhoub and Amrudee Sukpan. Conditional and composite temporal csps. Applied Intelligence, 36(1):90-107, 2012. Google Scholar
  18. Peter Revesz. Tightened transitive closure of integer addition constraints. In Eighth Symposium on Abstraction, Reformulation, and Approximation, pages 136-142. AAAI, 2009. Google Scholar
  19. Samira Sadaoui and Shubhashis Kumar Shil. A multi-attribute auction mechanism based on conditional constraints and conditional qualitative preferences. JTAER, 11(1):1-25, 2016. Google Scholar
  20. Peter Van Beek and Dennis W Manchak. The design and experimental analysis of algorithms for temporal reasoning. Journal of Artificial Intelligence Research, 4(1):1-18, 1996. 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 About DROPS Imprint Privacy Contact