Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T01:22:45.043Z Has data issue: false hasContentIssue false
  • English
  • Français

A Generalised Approach for Encoding and Reasoning with Qualitative Theories in Answer Set Programming

Published online by Cambridge University Press:  21 September 2020

GEORGE BARYANNIS Open the ORCID record for GEORGE BARYANNIS [Opens in a new window] ,
ILIAS TACHMAZIDIS Open the ORCID record for ILIAS TACHMAZIDIS [Opens in a new window] ,
SOTIRIS BATSAKIS ,
GRIGORIS ANTONIOU ,
MARIO ALVIANO Open the ORCID record for MARIO ALVIANO [Opens in a new window]  and
EMMANUEL PAPADAKIS
GEORGE BARYANNIS
Affiliation:
University of Huddersfield, UK (e-mail: [email protected], [email protected], [email protected], [email protected])
ILIAS TACHMAZIDIS
Affiliation:
University of Huddersfield, UK (e-mail: [email protected], [email protected], [email protected], [email protected])
SOTIRIS BATSAKIS
Affiliation:
University of Huddersfield, UK (e-mail: [email protected], [email protected], [email protected], [email protected])
GRIGORIS ANTONIOU
Affiliation:
University of Huddersfield, UK (e-mail: [email protected], [email protected], [email protected], [email protected])
MARIO ALVIANO
Affiliation:
University of Calabria, Italy (e-mail: [email protected])
EMMANUEL PAPADAKIS
Affiliation:
Center for Spatial Studies, University of California, Santa Barbara, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Qualitative reasoning involves expressing and deriving knowledge based on qualitative terms such as natural language expressions, rather than strict mathematical quantities. Well over 40 qualitative calculi have been proposed so far, mostly in the spatial and temporal domains, with several practical applications such as naval traffic monitoring, warehouse process optimisation and robot manipulation. Even if a number of specialised qualitative reasoning tools have been developed so far, an important barrier to the wider adoption of these tools is that only qualitative reasoning is supported natively, when real-world problems most often require a combination of qualitative and other forms of reasoning. In this work, we propose to overcome this barrier by using ASP as a unifying formalism to tackle problems that require qualitative reasoning in addition to non-qualitative reasoning. A family of ASP encodings is proposed which can handle any qualitative calculus with binary relations. These encodings are experimentally evaluated using a real-world dataset based on a case study of determining optimal coverage of telecommunication antennas, and compared with the performance of two well-known dedicated reasoners. Experimental results show that the proposed encodings outperform one of the two reasoners, but fall behind the other, an acceptable trade-off given the added benefits of handling any type of reasoning as well as the interpretability of logic programs.

Keywords

Answer Set ProgrammingQualitative CalculusQualitative ReasoningSpatial Reasoning
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 20 , Issue 5: 36th International Conference on Logic Programming Special Issue I , September 2020 , pp. 687 - 702
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Allen, J. F. 1981. An interval-based representation of temporal knowledge. In IJCAI, P. J. Hayes, Ed. William Kaufmann, 221–226.Google Scholar
Baryannis, G., Tachmazidis, I., Batsakis, S., Antoniou, G., Alviano, M., and Papadakis, E. 2020. A generalised approach for encoding and reasoning with qualitative theories in answer set programming. https://arxiv.org/abs/2008.01519.Google Scholar
Baryannis, G., Tachmazidis, I., Batsakis, S., Antoniou, G., Alviano, M., Sellis, T., and Tsai, P.-W. 2018. A Trajectory Calculus for Qualitative Spatial Reasoning Using Answer Set Programming. Theory and Practice of Logic Programming 18, 3-4, 355–371.Google Scholar
Batsakis, S., Tachmazidis, I., and Antoniou, G. 2017. Representing Time and Space for the Semantic Web. International Journal on Artificial Intelligence Tools 26, 3, 1–30.Google Scholar
Brenton, C., Faber, W., and Batsakis, S. 2016. Answer Set Programming for Qualitative Spatio-Temporal Reasoning: Methods and Experiments. In ICLP (Technical Communications), Carro, M., King, A., Saeedloei, N., and Vos, M. D., Eds. OASICS, vol. 52. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 4:1–4:15.Google Scholar
Calimeri, F., Faber, W., Gebser, M., Ianni, G., Kaminski, R., Krennwallner, T., Leone, N., Maratea, M., Ricca, F., Schaub, T., and et al. 2020. Asp-core-2 input language format. Theory and Practice of Logic Programming 20, 2, 294–309.CrossRefGoogle Scholar
Clementini, E. and Di Felice, P. 1995. A comparison of methods for representing topological relationships. Information sciences-applications 3, 3, 149–178.Google Scholar
Dylla, F., Lee, J. H., Mossakowski, T., Schneider, T., van Delden, A., van de Ven, J., and Wolter, D. 2017. A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties. ACM Comput. Surv. 50, 1, 7:1–7:39.Google Scholar
Freksa, C. and Zimmermann, K. 1992. On the utilization of spatial structures for cognitively plausible and efficient reasoning. In Proceedings of the 1992 IEEE International Conference on Systems, Man, and Cybernetics. IEEE, 261–266 vol.1.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., and Wanko, P. 2016. Theory solving made easy with clingo 5. In Technical Communications of the Thirty-second International Conference on Logic Programming (ICLP’16), Carro, M. and King, A., Eds. Open Access Series in Informatics (OASIcs), vol. 52. Schloss Dagstuhl, 2:1–2:15.Google Scholar
Horwitz, J. 2019. The definitive guide to 5G low, mid, and high band speeds. https://spectrum.ieee.org/video/telecom/wireless/everything-you-need-to-know-about-5g.Google Scholar
Huang, J., Li, J. J., and Renz, J. 2013. Decomposition and tractability in qualitative spatial and temporal reasoning. Artif. Intell. 195, 140–164.Google Scholar
Izmirlioglu, Y. and Erdem, E. 2018. Qualitative reasoning about cardinal directions using answer set programming. In AAAI, McIlraith, S. A. and Weinberger, K. Q., Eds. AAAI Press, 1880–1887.Google Scholar
Kreutzmann, A., Wolter, D., and Lee, J. 2013. Towards safe navigation by formalizing navigation rules. International Journal on Marine Navigation and Safety of Sea Transportation 7, 2, 161–168.CrossRefGoogle Scholar
Li, J. J. 2012. Qualitative Spatial and Temporal Reasoning with Answer Set Programming. In ICTAI. IEEE Computer Society, 603–609.Google Scholar
Li, J. J. and Renz, J. 2010. In Defense of Large Qualitative Calculi. In AAAI, Fox, M. and Poole, D., Eds. AAAI Press.Google Scholar
Navarrete, I., Morales, A., Sciavicco, G., and Viedma, M. A. C. 2013. Spatial reasoning with rectangular cardinal relations - The convex tractable subalgebra. Ann. Math. Artif. Intell. 67, 1, 31–70.CrossRefGoogle Scholar
Nordrum, A. 2017. Everything you need to know about 5G. IEEE Spectrum. https://spectrum.ieee.org/video/telecom/wireless/everything-you-need-to-know-about-5g.Google Scholar
Pham, D. N., Thornton, J., and Sattar, A. 2008. Modelling and Solving Temporal Reasoning as Propositional Satisfiability. Artif. Intell. 172, 15, 1752–1782.Google Scholar
Randell, D. A., Cui, Z., and Cohn, A. G. 1992. A Spatial Logic Based on Regions and Connection. In Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning. KR’92. Morgan Kaufmann Publishers Inc., 165–176.Google Scholar
Renz, J. and Nebel, B. 2007. Qualitative Spatial Reasoning Using Constraint Calculi. In Handbook of Spatial Logics, Aiello, M., Pratt-Hartmann, I., and Van Benthem, J., Eds. Springer Netherlands, Dordrecht, 161–215.Google Scholar
Skiadopoulos, S. and Koubarakis, M. 2005. On the consistency of cardinal direction constraints. Artif. Intell. 163, 1, 91–135.Google Scholar
van Beek, P. and Manchak, D. W. 1996. The Design and Experimental Analysis of Algorithms for Temporal Reasoning. Journal of Artificial Intelligence Research 4, 1–18.Google Scholar
Van de Weghe, N., Kuijpers, B., Bogaert, P., and Maeyer, P. D. 2005. A Qualitative Trajectory Calculus and the Composition of Its Relations. In GeoS, Rodríguez, M. A., Cruz, I. F., Egenhofer, M. J., and Levashkin, S., Eds. Lecture Notes in Computer Science, vol. 3799. Springer, 60–76.Google Scholar
Westphal, M., Wölfl, S., and Gantner, Z. 2009. GQR: A Fast Solver for Binary Qualitative Constraint Networks. In AAAI Spring Symposium: Benchmarking of Qualitative Spatial and Temporal Reasoning Systems. AAAI, 51–52.Google Scholar
Wolter, D. and Kirsch, A. 2015. Leveraging qualitative reasoning to learning manipulation tasks. Robotics 4, 3, 253–283.CrossRefGoogle Scholar
Wolter, D. and Wallgrün, J. O. 2012. Qualitative Spatial Reasoning for Applications: New Challenges and the SparQ Toolbox. In Qualitative Spatio-Temporal Representation and Reasoning: Trends and Future Directions, S. M. Hazarika, Ed. Global, IGI, Hershey, PA, 336–362.Google Scholar