IMSD: Interactive Methods for Finding Similar or Diverse Answer Sets

Abstract

Answer set programming (ASP) is a modeling language in knowledge representation, rooted in Logic Programming and Nonmonotonic Reasoning, which has been gaining increasing attention during the last years. In recent years, many of the researchers developed integrated development environments (IDE) for ASP programs including editors and debuggers. Other researchers focused on analyzing the answer sets, they introduced offline and online methods to find specific solutions of a given problem in answer set programming in different approaches such as phylogeny reconstruction. However, with an enormous number of answer sets could be available, the user is not interested in all of them. Thus, a navigation of the search space could be a solution to help the user to access the specific answer sets. To this end, we aim at finding similar/diverse solutions of the answer sets with a new method. The intuition behind this navigation is to make the search faster than other methods and explore information that is related to the user’s query. Afterward, we implement a tool performing the above approach in order to simplify the search task and show the applicability and effectiveness of our method. We conclude by testing the performance of the proposed tool into a real-world example of ASP programs.

Keywords

• Answer set programming
• Navigation approach
• Diversity
• Similarity.

References

1. Afeefi, A. (2019, April). NavAS: Navigation Approaches for Answer Sets. In 2019 IEEE Jordan International Joint Conference on Electrical Engineering and Information Technology (JEEIT) (pp. 79-84). IEEE. https://doi.org/10.1109/JEEIT.2019.8717370
2. Ambroz, T., Charwat, G., Jusits, A., Wallner, J. P., & Woltran, S. (2013, September). ARVis: Visualizing relations between answer sets. In International Conference on Logic Programming and Nonmonotonic Reasoning (pp. 73-78). Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40564-8_8
3. Baum, D. (2004). Finding All Maximal Cliques of a Family of Induced Subgraphs., 1–15. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.358
4. Bron, C., & Kerbosch, J. (1973). Algorithm 457: Finding all cliques in an undirected graph, Community. ACM, 16(9), 575-577. https://doi.org/10.1145/362342.362367
5. Busoniu, P. A., Oetsch, J., Pührer, J., Skočovský, P., & Tompits, H. (2013). SeaLion: An eclipse-based IDE for answer-set programming with advanced debugging support. Theory and Practice of Logic Programming, 13(4–5). https://doi.org/10.1017/S1471068413000410
6. Computing the Stable Model Semantics. (n.d.). Retrieved June 30, 2021, from http://www.tcs.hut.fi/Software/smodels/
7. Das, A., Sanei-Mehri, S.-V., & Tirthapura, S. (2020). Shared-memory parallel maximal Clique Enumeration from static and dynamic graphs. ACM Transactions on Parallel Computing, 7(1), 1–28.
8. Deng, F., Siersdorfer, S., & Zerr, S. (2012). Efficient Jaccard-based diversity analysis of large document collections. ACM International Conference Proceeding Series. https://doi.org/10.1145/2396761.2398445

9. Eiter, T., Erdem, E., Erdoǧan, H., & Fink, M. (2009). Finding similar or diverse solutions in answer set programming. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5649 LNCS. https://doi.org/10.1007/978-3-642-02846-5_29
10. Erdem, E., Gelfond, M., & Leone, N. (2016). Applications of answer set programming. AI Magazine, 37(3), 53–68.
11. Everardo, F., & Osorio, M. (2020). Towards an answer set programming methodology for constructing programs following a semi-automatic approach – extended and revised version. Electronic Notes in Theoretical Computer Science, 354, 29–44.
12. Fakecineaste : How to Calculate the Hamming Code. (n.d.). Retrieved June 30, 2021, from http://fakecineaste.blogspot.com/2012/11/how-to-calculate-hamming-code.html
13. Fandinno, J., & Schulz, C. (2019). Answering the “why” in answer set programming - A survey of explanation approaches. Theory and Practice of Logic Programming, 19(2). https://doi.org/10.1017/S1471068418000534
14. Febbraro, O., Reale, K., & Ricca, F. (2011). ASPIDE: Integrated development environment for answer set programming. In Logic Programming and Nonmonotonic Reasoning (pp. 317–330). Berlin, Heidelberg: Springer Berlin Heidelberg.
15. Gebser, M., Kaminski, R., Kaufmann, B., & Schaub, T. (2014). Clingo = ASP + Control: Preliminary Report. 1. http://arxiv.org/abs/1405.3694
16. Güven, Ç., & Atzmueller, M. (2019). Applying answer set programming for knowledge-based link prediction on social interaction networks. Frontiers in Big Data, 2, 15.
17. iGROM download | SourceForge.net. (n.d.). Retrieved June 30, 2021, from https://sourceforge.net/projects/igrom/
18. Li, Y., Shao, Z., Yu, D., Liao, X., & Jin, H. (2019). Fast maximal clique enumeration for real-world graphs. In Database Systems for Advanced Applications (pp. 641–658). Cham: Springer International Publishing.
19. Makino, K., & Uno, T. (2004). New algorithms for enumerating all maximal cliques. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3111. https://doi.org/10.1007/978-3-540-27810-8_23
20. Marcopoulos, E., Reotutar, C., & Zhang, Y. (2017). An Online Development Environment for Answer Set Programming. 1. http://www.math.ttu.edu/texprep/
21. Niemelä, I., & Simons, P. (n.d.). Smodels: An implementation of the stable model and well-founded semantics for normal lp”.
22. Son, T. C., & Balduccini, M. (2018). Answer set planning in single- and multi-agent environments. KI - Künstliche Intelligenz, 32(2–3), 133–141.
23. Sureshkumar, A., De Vos, M., Brain, M., & Fitch, J. (2007). APE: An AnsProlog* environment. CEUR Workshop Proceedings, 281.
24. Zhu, Y., & Truszczynski, M. (2013). On optimal solutions of answer set optimization problems. In Logic Programming and Nonmonotonic Reasoning (pp. 556–568). Berlin, Heidelberg: Springer Berlin Heidelberg.