Ausgewählte Titel für das Seminar KI Sommersemester 2022 ------------------------------- Aus den Konferenzen KR20 und KR 21 PDFs sind zu finden unter https://proceedings.kr.org/2021/ und https://proceedings.kr.org/2020/ ========================================= (Thema 1) Lightweight Parallel Multi-Agent Epistemic Planning Martin Cooper(IRIT - Université Paul Sabatier - Toulouse III) Andreas Herzig(CNRS, IRIT, Univ. Toulouse) Frédéric Maris(IRIT - Université Paul Sabatier - Toulouse III) Elise Perrotin(IRIT - Université Paul Sabatier - Toulouse III) Julien Vianey(IRIT - Université Paul Sabatier - Toulouse III) In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning — Main Track. Pages 274–283. PDF BibTeX https://doi.org/10.24963/kr.2020/28 Abstract We study a simple version of multi-agent epistemic planning where the number of parallel steps has to be minimized. We prove that this extension of classical planning is in PSPACE. We propose an encoding in PDDL and present some experiments providing evidence that this encoding allows us to solve practical problems. The types of problems we can encode include problems in which one agent can teach another agent how to perform a task and communication problems where some information must not be revealed to some agents. =============================================================================================================== (Thema 2) Jokes and Belief Revision Florence Dupin De Saint-Cyr(IRIT-CNRS, Toulouse University) Henri Prade(IRIT-CNRS) In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning — Main Track. Pages 336–340. PDF BibTeXhttps://doi.org/10.24963/kr.2020/34 Abstract The paper deals with a topic little studied in artificial intelligence: the understanding of humor. In this preliminary study, we try to identify the basic mechanism at work in quips and narrative jokes. It seems that in many cases a belief revision process is operating, leading to an unexpected conclusion, through the punchline of the jest. We propose a formal modeling of jokes based on belief revision. Namely the punchline, which triggers a revision, is both surprising and explains perfectly what was reported in the beginning of the joke. This also suggests a way of ranking jokes in terms of surprise and strength of explanation, using possibilistic logic. ========================================================================================== (Thema 3) Reasoning with Inconsistent Knowledge using the Epistemic Approach to Probabilistic Argumentation Anthony Hunter(University College London) In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning — Main Track. Pages 496–505. PDF BibTeXhttps://doi.org/10.24963/kr.2020/50 Abstract Structured argumentation involves drawing inferences from knowledge in order to construct arguments and counterarguments. Since knowledge can be uncertain, we can use a probabilistic approach to representing and reasoning with the knowledge. Individual arguments can be constructed from the knowledge, with the belief in each argument determined just from the belief in the formulae appearing in the argument. However, if the original knowledgebase is inconsistent, this does not take into account the counterarguments that can be constructed. We therefore need a wider perspective that revises the belief in individual arguments in order to take into account the counterarguments. To address this need, we present a framework for probabilistic argumentation that uses relaxation methods to give a coherent view on the knowledge, and thereby revises the belief in the arguments that are generated from the knowledge. ====================================================== (Thema 4) Reasoning About Plan Robustness Versus Plan Cost for Partially Informed Agents Sarah Keren(School of Engineering and Applied Sciences, Harvard University, Center for Research on Computation and Society at Harvard University) Sara Bernardini(Department of Computer Science, Royal Holloway University of London) Kofi Kwapong(School of Engineering and Applied Sciences, Harvard University) David C. Parkes(School of Engineering and Applied Sciences, Harvard University) In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning — Main Track. Pages 550–559. PDF BibTeXhttps://doi.org/10.24963/kr.2020/55 Abstract A common approach to planning with partial information is replanning: compute a plan based on assumptions about unknown information and replan if these assumptions are refuted during execution. To date, most planners with incomplete information have been designed to provide guarantees on completeness and soundness for the generated plans. Switching focus to performance, we measure the robustness of a plan, which quantifies the plan’s ability to avoid failure. Given a plan and an agent’s belief, which describes the set of states it deems as possible, robustness counts the number of world states in the belief from which the plan will achieve the goal without the need to replan. We formally describe the trade-off between robustness and plan cost and offer a solver that is guaranteed to produce plans that satisfy a required level of robustness. By evaluating our approach on a set of standard benchmarks, we demonstrate how it can improve the performance of a partially informed agent. Seminarthemen aus KR21: Ausgewaehlte Themen ======================================================== (Thema 5) On Free Description Logics with Definite Descriptions Alessandro Artale(Free University of Bozen-Bolzano) Andrea Mazzullo(Free University of Bozen-Bolzano) Ana Ozaki(University of Bergen) Frank Wolter(University of Liverpool) In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning — Full Papers — Main Track. Pages 63–73. PDF BibTeX https://doi.org/10.24963/kr.2021/7 Abstract Definite descriptions are phrases of the form ‘the x such that φ’, used to refer to single entities in a context. They are often more meaningful to users than individual names alone, in particular when modelling or querying data over ontologies. We investigate free description logics with both individual names and definite descriptions as terms of the language, while also accounting for their possible lack of denotation. We focus on the extensions of ALC and, respectively, EL with nominals, the universal role, and definite descriptions. We show that standard reasoning in these extensions is not harder than in the original languages, and we characterise the expressive power of concepts relative to first-order formulas using a suitable notion of bisimulation. Moreover, we lay the foundations for automated support for definite descriptions generation by studying the complexity of deciding the existence of definite descriptions for an individual under an ontology. Finally, we provide a polynomial-time reduction of reasoning in other free description logic languages based on dual-domain semantics to the case of partial interpretations. ======================================================== (Thema 6) On the Computational Intelligibility of Boolean Classifiers Gilles Audemard(CRIL, Université d'Artois & CNRS) Steve Bellart(CRIL, Université d'Artois & CNRS) Louenas Bounia(CRIL, Université d'Artois & CNRS) Frédéric Koriche(CRIL, Université d'Artois & CNRS) Jean-Marie Lagniez(CRIL, Université d'Artois & CNRS) Pierre Marquis(CRIL, Université d'Artois & CNRS, Institut Universitaire de France) In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning — Full Papers — Special Session on KR and Machine Learning. Pages 74–86. PDF BibTeXhttps://doi.org/10.24963/kr.2021/8 Keywords Explainable AI Abstract In this paper, we investigate the computational intelligibility of Boolean classifiers, characterized by their ability to answer XAI queries in polynomial time. The classifiers under consideration are decision trees, DNF formulae, decision lists, decision rules, tree ensembles, and Boolean neural nets. Using 9 XAI queries, including both explanation queries and verification queries, we show the existence of large intelligibility gap between the families of classifiers. On the one hand, all the 9 XAI queries are tractable for decision trees. On the other hand, none of them is tractable for DNF formulae, decision lists, random forests, boosted decision trees, Boolean multilayer perceptrons, and binarized neural networks. ======================================================== (Thema 7) Closed- and Open-world Reasoning in DL-Lite for Cloud Infrastructure Security Claudia Cauli(University of Gothenburg) Magdalena Ortiz(TU Wien) Nir Piterman(University of Gothenburg) In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning — Full Papers — Main Track. Pages 174–183. PDF BibTeXhttps://doi.org/10.24963/kr.2021/17 Keywords Applications of KR Description logics KR and cyber security Abstract Infrastructure in the cloud is deployed through configuration files, which specify the resources to be created, their settings, and their connectivity. We aim to model infrastructure before deployment and reason about it so that potential vulnerabilities can be discovered and security best practices enforced. Description logics are a good match for such modeling efforts and allow for a succinct and natural description of cloud infrastructure. Their open-world assumption allows capturing the distributed nature of the cloud, where a newly deployed infrastructure could connect to pre-existing resources not necessarily owned by the same user. However, parts of the infrastructure that are fully known need closed-world reasoning, calling for the usage of expressive formalisms, which increase the computational complexity of reasoning. Here, we suggest an extension of DL-LiteF that is tailored for capturing such cloud infrastructure. Our logic allows combining a core part that is completely defined (closed-world) and interacts with a partially known environment (open-world). We show that this extension preserves the first-order rewritability of DL-LiteF for knowledge-base satisfiability and conjunctive query answering. Security properties combine universal and existential reasoning about infrastructure. Thus, we also consider the problem of conjunctive query satisfiability and show that it can be solved in logarithmic space in data complexity. ======================================================== (Thema 8) Borda, Cancellation and Belief Merging Patricia Everaere(Univ. Lille, CNRS, Centrale Lille, UMR 9189, CRIStAL, F-59000 Lille, France) Chouaib Fellah(CRIL - CNRS - Université d’Artois - France) Sébastien Konieczny(CRIL - CNRS - Université d’Artois - France) Ramón Pino Pérez(CRIL - CNRS - Université d’Artois - France) In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning — Full Papers — Main Track. Pages 291–300. PDF BibTeXhttps://doi.org/10.24963/kr.2021/28 Keywords Belief revision and update, belief merging, information fusion Decision making Abstract In this work, we explore the links between the Borda voting rule and belief merging operators. More precisely, we define two families of merging operators inspired by the definition of the Borda voting rule. We also introduce a notion of cancellation in belief merging, inspired by the axiomatization of the Borda voting rule proposed by Young. This allows us to provide a characterization of the drastic merging operator. ======================================================== (Thema 9) Rational Verification for Probabilistic Systems Julian Gutierrez(Monash University) Lewis Hammond(University of Oxford) Anthony W. Lin(University of Kaiserslautern) Muhammad Najib(University of Kaiserslautern) Michael Wooldridge(University of Oxford) In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning — Full Papers — Main Track. Pages 312–322. PDF BibTeXhttps://doi.org/10.24963/kr.2021/30 Keywords KR and autonomous agents and multi-agent systems KR and game theory Applications that combine KR with game theory Modeling and reasoning about preferences Abstract Rational verification is the problem of determining which temporal logic properties will hold in a multi-agent system, under the assumption that agents in the system act rationally, by choosing strategies that collectively form a game-theoretic equilibrium. Previous work in this area has largely focussed on deterministic systems. In this paper, we develop the theory and algorithms for rational verification in probabilistic systems. We focus on concurrent stochastic games (CSGs), which can be used to model uncertainty and randomness in complex multi-agent environments. We study the rational verification problem for both non-cooperative games and cooperative games in the qualitative probabilistic setting. In the former case, we consider LTL properties satisfied by the Nash equilibria of the game and in the latter case LTL properties satisfied by the core. In both cases, we show that the problem is 2EXPTIME-complete, thus not harder than the much simpler verification problem of model checking LTL properties of systems modelled as Markov decision processes (MDPs). ================================== (Thema 10) Strategic Reasoning in Automated Mechanism Design Bastien Maubert(University of Naples Federico II) Munyque Mittelmann(IRIT, Université de Toulouse 1 Capitole) Aniello Murano(University of Naples Federico II) Laurent Perrussel(IRIT, Université de Toulouse 1 Capitole) In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning — Full Papers — Main Track. Pages 487–496. PDF BibTeXhttps://doi.org/10.24963/kr.2021/46 Keywords Modeling and reasoning about preferences KR and autonomous agents and multi-agent systems Abstract Mechanism Design aims at defining mechanisms that satisfy a predefined set of properties, and Auction Mechanisms are of foremost importance. Core properties of mechanisms, such as strategy-proofness or budget-balance, involve: (i) complex strategic concepts such as Nash equilibria, (ii) quantitative aspects such as utilities, and often (iii) imperfect information,with agents’ private valuations. We demonstrate that Strategy Logic provides a formal framework fit to model mechanisms, express such properties, and verify them. To do so, we consider a quantitative and epistemic variant of Strategy Logic. We first show how to express the implementation of social choice functions. Second, we show how fundamental mechanism properties can be expressed as logical formulas,and thus evaluated by model checking. Finally, we prove that model checking for this particular variant of Strategy Logic can be done in polynomial space. ===================================================================== (Thema 11) Learning First-Order Representations for Planning from Black Box States: New Results Ivan D. Rodriguez(Universitat Pompeu Fabra) Blai Bonet(Universitat Pompeu Fabra) Javier Romero(Universitat Potsdam) Hector Geffner(ICREA, Universitat Pompeu Fabra) In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning — Full Papers — Special Session on KR and Machine Learning. Pages 539–548. PDF BibTeXhttps://doi.org/10.24963/kr.2021/51 Keywords Learning action theories Learning symbolic abstractions from unstructured data Abstract Recently Bonet and Geffner have shown that first-order representations for planning domains can be learned from the structure of the state space without any prior knowledge about the action schemas or domain predicates. For this, the learning problem is formulated as the search for a simplest first-order domain description D that along with information about instances I_i (number of objects and initial state) determine state space graphs G(P_i) that match the observed state graphs G_i where P_i = (D, I_i). The search is cast and solved approximately by means of a SAT solver that is called over a large family of propositional theories that differ just in the parameters encoding the possible number of action schemas and domain predicates, their arities, and the number of objects. In this work, we push the limits of these learners by moving to an answer set programming (ASP) encoding using the CLINGO system. The new encodings are more transparent and concise, extending the range of possible models while facilitating their exploration. We show that the domains introduced by Bonet and Geffner can be solved more efficiently in the new approach, often optimally, and furthermore, that the approach can be easily extended to handle partial information about the state graphs as well as noise that prevents some states from being distinguished.