×

A generalised approach for encoding and reasoning with qualitative theories in answer set programming. (English) Zbl 1468.68218

Summary: 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.

MSC:

68T30 Knowledge representation
68N17 Logic programming
68T27 Logic in artificial intelligence

Software:

Clingo
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Allen, J. F.1981. An interval-based representation of temporal knowledge. In IJCAI, P. J. Hayes, Ed. William Kaufmann, 221-226.
[2] 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. · Zbl 1451.68252
[3] 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. · Zbl 1451.68252
[4] 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.
[5] 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. · Zbl 1428.68282
[6] 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. · Zbl 1472.68180
[7] Clementini, E. and Di Felice, P.1995. A comparison of methods for representing topological relationships. Information sciences-applications 3, 3, 149-178.
[8] 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.
[9] 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.
[10] 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.
[11] 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.
[12] Huang, J., Li, J. J., and Renz, J.2013. Decomposition and tractability in qualitative spatial and temporal reasoning. Artif. Intell. 195, 140-164. · Zbl 1270.68270
[13] 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.
[14] 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.
[15] Li, J. J.2012. Qualitative Spatial and Temporal Reasoning with Answer Set Programming. In ICTAI. IEEE Computer Society, 603-609.
[16] Li, J. J. and Renz, J.2010. In Defense of Large Qualitative Calculi. In AAAI, Fox, M. and Poole, D., Eds. AAAI Press.
[17] 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. · Zbl 1286.68432
[18] 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.
[19] Pham, D. N., Thornton, J., and Sattar, A.2008. Modelling and Solving Temporal Reasoning as Propositional Satisfiability. Artif. Intell. 172, 15, 1752-1782. · Zbl 1184.68485
[20] 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.
[21] 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.
[22] Skiadopoulos, S. and Koubarakis, M.2005. On the consistency of cardinal direction constraints. Artif. Intell. 163, 1, 91-135. · Zbl 1132.68713
[23] 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. · Zbl 0900.68389
[24] 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 inComputer Science, vol. 3799. Springer, 60-76.
[25] Westphal, M., Wölfl, S., and Gantner, Z.2009. GQR: A Fast Solver for Binary Qualitative Constraint Networks. InAAAI Spring Symposium: Benchmarking of Qualitative Spatial and Temporal Reasoning Systems. AAAI, 51-52.
[26] Wolter, D. and Kirsch, A.2015. Leveraging qualitative reasoning to learning manipulation tasks. Robotics 4, 3, 253-283.
[27] 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.