15th International Conference on Principles of Knowledge Representation and Reasoning (KR 2016)

Doctoral Consortium Abstracts

Doctoral Consortium Chairs: Meghyn Bienvenu (CNRS), Joohyung Lee (Arizona State University)

  • Online and Hierarchical Agent Supervision in the Situation Calculus

    Bita Banihashemi

    Agent supervision is a form of control/customization where a supervisor restricts the behavior of an agent to enforce certain requirements, while leaving the agent as much autonomy as possible. This framework is based on the Situation Calculus and a variant of the ConGolog agent programming language. In this doctoral research we focus on two of the open problems with the original account of agent supervision: i) supervising an agent's online executions where she must make decisions based on what she knows and her knowledge is updated through sensing or exogenous actions as she executes the program, and ii) supervising complex agents in multi-agent settings that need to represent and reason about a large amount of knowledge about their environment and execute complex actions/behaviors. We particularly focus on investigating the extended supervision framework in the context of customizing processes based on a client's preferences or constraints.

    Mentor: Gerhard Lakemeyer

  • Querying Inconsistent Description Logic Knowledge Bases

    Camille Bourgaux

    The problem of querying description logic knowledge bases using database-style queries (in particular, conjunctive queries) has been a major focus of recent description logic research. An important issue that arises in this context is how to handle the case in which the data is inconsistent with the ontology. Indeed, since in classical logic an inconsistent logical theory implies every formula, inconsistency-tolerant semantics are needed to obtain meaningful answers. The semantics AR, IAR, and brave are three well-known semantics, that rely on the notion of a repair, that is an inclusion-maximal subset of the data consistent with the ontology.
    This thesis aims to develop methods for dealing with inconsistent knowledge bases, using these semantics.
    Beyond efficient query answering, we address the problems of explaining the query results, and of query-driven repairing of the data. We also consider variants of these semantics based on preferred repairs. We study the complexity of these problems for the lightweight description logic DL-Lite, and we find connections between intractable cases and variants of propositional satisfiability that enable us to capitalize on the performance of modern-day SAT solvers to practically solve them. We implement the proposed methods and empirically study their efficiency."

    Mentor: Sebastian Rudolph

  • German Braun

    Methodologies and Tools for Conceptual Modelling with Reasoning Support

    Ontology designers have different expertise, social background and understanding of the needs related to potential uses of their models. Moreover, ontologies that represent knowledge in the real world have to be dynamically updated to cover new requirements according to how the world evolves. In this context, complex tasks as ontology development and maintenance require automatic tools which are essential for a successful integration between the modeller's intention and the formal semantics in an ontology. In this work, we exploit the ontology graphical representation, which is closer to the modeller's intention, and the Description Logics (DL)-based reasoning in the context of a tool. The main objective is to close the gap between domain experts, its understanding about ontologies, the underlying formal logic and the modelling tools to satisfy the ontology engineering challenges. The intention is to offer methodologies integrated to a simple conceptual modelling tool that demonstrates the use of the novel and powerful knowledge representation based technologies for ontology design.

    Mentor: Giuseppe De Giacomo

  • Representing and Reasoning about the social character of place

    Alessia Calafiore

    Classical representations of space are based on absolute space which exists independently of the object that happen to be located in it. Recently, in divergent ways the notion of "space" has evolved to notions of "place" in many conceptual schemas, vocabularies and ontologies. However, a theory to differentiate space from place is still missed.
    The thesis presents a conceptual framework for representing and reasoning about the social knowledge related to places and applies it to support decision-making in urban design and planning. We realized an ontology to model place as social construction having a relative approach to space. Relative space is a construct induced by spatial relations over non-purely spatial entities. Place has been defined as role involving spatial entities and action entities, thus introducing a clear relation to time. As a consequence, ontological dependences throughout place and space-time realms had to be addressed.
    We introduced the concept of social place to represent the specific social knowledge of places related to collectives. A multi-level ontological approach has been adopted to allow reasoning on both individual and collective representations of places. Next we consider the dynamic of social places changes, and its integration with qualitative spatial representation and reasoning.

    Mentor: Roman Kontchakov

  • ABA+: Assumption-Based Argumentation with Preferences

    Knowledge Representation and Reasoning (KR) is the field of AI dedicated to representing information about the world and automating various forms of reasoning. In particular, common-sense reasoning concerns simulation of the human ability to effortlessly make alterable decisions based on incomplete and conflicting information. In essence, common-sense reasoning is mostly defeasible and has to account for ubiquitous preference information. A well established branch of AI, called argumentation, aims at modelling common-sense reasoning. It represents knowledge via arguments and captures conflicts via attacks between arguments. Reasoning is done using procedures, called semantics, for selecting acceptable arguments. Despite of argumentation's success at formalizing defeasible reasoning, there is a lack of consensus on how it should account for preferences. Existing approaches suffer from various deficiencies, and general undersupply of guidelines regarding preference treatment persists. Building on a well studied argumentation formalism, Assumption-Based Argumentation, we present its extension that deals with preferences in a novel way. The essential idea is to utilize preferences on the structure of arguments to reverse certain attacks. This captures the interplay between conflicts and preferences, and yields arguably desirable outcomes in terms of both examples and formal properties. As a by-product, we contribute to the understanding of preference information management in KR at large.

    Mentor: Leila Amgoud

    Kristijonas Cyras

  • Fabio D'Asaro

    Modeling uncertainty in the Event Calculus

    My thesis is primarily aimed at exploring how some models of uncertainty, and probability in particular, can be incorporated in a standard framework for Reasoning About Actions known as the Event Calculus. A further challenge that I will tackle is the introduction of an epistemic component in this context: that is, the somewhat unrealistic assumption that an agent has perfect knowledge of the world is dropped, and the less restrictive case where an agent can only (imperfectly) sense some characteristics of the environment is considered. These efforts will result in the development and implementation of an action language, which has been tentatively called EPEC (for Epistemic Probabilistic Event Calculus), using a Modular-E style syntax and an Epistemic Functional Event Calculus (EFEC) style possible-worlds semantics. Crucial to the achievement of such goals is a better understanding of how non-monotonic logic and probability theory interact, and how default commonsensical assumptions can be used to constrain an agent's belief to infer meaningful and consistent conclusions from states of partial knowledge expressed in form of probabilities.

    Mentor: Son Cao Tran

  • Belief Change in Fragments

    My research deals with belief change in fragments. The aim is to understand how belief change applies to a wide variety of knowledge representation formalisms: thus, we want to talk of revising (or updating, or merging) not just propositional theories, as is usually taken to be the case, but also Horn propositional theories, logic programs or Argumentation Frameworks (Afs). However, restricting belief change operators to fragments poses a series of characteristic challenges: the inexpressibility problem refers to the fact that existing model-based belief change operators (tailored for unrestricted propositional logic) do not work in the restricted cases, as the result usually cannot be expressed in the fragment we are working in. The computation problem refers to the fact that computation of the result of a belief change operation is inefficient, except for some special cases. In my thesis I plan to address both problems by: (i) finding concrete belief change operators tailored for the fragments of interest, (ii) obtaining general representation theorems which characterize all possible belief change operators for a given fragment, (iii) providing algorithms and complexity analysis for belief change in fragments.

    Mentor: Jerome Lang

    Adrian Haret

  • Concept invention for AI using image schemas in conceptual blending

    One unsolved problem in artificial general intelligence is concept generation and conceptual grounding in the environment. Approaching this problem from cognitive perspective at the intersection of formal AI, psychology and linguistics, my dissertation aims provide a cognitively plausible foundation to aid formal concept formation.
    Conceptual Blending(CB) is a theory for concept invention that proposes novel concepts to be a result of combining pre-existing knowledge. Formal CB struggle to consistently generate a 'sensible' blend as random combination rarely provide value. Therefore one important aspect is not only the merging of the input spaces, but also the search for common structure, that may lay the foundation for the blended concept.
    Image Schemas are defined as the generic, abstract patterns obtained by sensorimotor processes, modelling relationships in the environment (e.g. Link, Containment). In language they can be identified in abstract concepts and metaphors (e.g. Marriage is an abstract Link).
    Hypothesized is that using image schemas as the common structure in conceptual blending, will allow for more cognitively relevant information to be transferred during the blending. The main challenge is how to formally identify and represent image schemas in such a way that utilizing them in a formal CB-system will be possible.

    Mentor: Frank Wolter

    Maria Hedblom

  • Multi-context Systems with Preferences

    Multi-Context System (MCS) (Brewka and Eiter 2007) has been introduced as a framework for integration of knowledge from different sources. The information flow among contexts is modeled via bridge rules. The semantics of MCSs is defined in terms of its equilibria that are states in which every context contributes a local model that is consistent with local models contributed by other contexts, obeying the knowledge imported by bridge rules. Observing that a MCS might have several equilibria, and as long as decision-making is concerned, such a MCS needs to represent the preferences over its equilibria. The purpose of my dissertation is to study how to combine preferences into MCS framework. My main contributions are to (i) define a general framework, MCS with local preferences (MCS-LP), that integrates preferences at the context level of MCSs, (ii) define a general framework, MCS with global preferences (MCS-GP), that allows to express the preference aggregation for MCSs, (iii) introduce a preference language that is used to construct a concrete MCS-GP, and (iv) propose novel algorithms to solve MCSs with Preferences (i.e., either MCS-LP or MCS-GP) in a distributed manner.

    Mentor: Thomas Eiter

    Tiep Le

  • Domain-Aware Cognitive Question Answering Systems: Paradigms and Inference Techniques

    Emily LeBlanc

    One of the most exciting futurist notions is a machine that can think and interact like a human. Although we presently cannot have true discourse with a computer, we know that techniques from a number of research areas must be integrated to advance towards cognitive computer systems. A cognitive system solves a prescribed task by utilizing unified mechanisms inspired by the abilities of the human mind. A cognitive QA system with domain expertise, then, should strive to answer questions by emulating the natural thought processes, research approaches, and pattern recognizing capabilities of a human expert in that domain. Work at the intersection of Natural Language Processing (NLP), Knowledge Representation (KR), Question Answering (QA), and Cognitive Computing (CC) is required to advance towards this goal. My efforts to achieve this goal begin with my dissertation work in which I aim to research and discover new models and complementary reasoning techniques for representing question and answer paradigms. I consider the characteristic attributes of questions, answers, and series of related questions and answers. Moreover, I consider how these models and reasoning processes can be expressed in ways that are easily comprehendible by human experts. I believe that my work will result in novel, generalizable models and inference techniques that will provide a foundation for next-generation cognitive QA systems with domain awareness.

    Mentor: Chitta Baral

  • Julio Lemos

    Complexity of Query Answering in Lightweight Description Logics with Datatypes

    Description Logics (DLs) are a family of knowledge representation formalisms. The search for tractable fragments inspired the design of the so-called lightweight DLs, among which DL-Lite and EL stand out, being at the basis of OWL 2.0. We investigate query answering over lightweight DLs extended with attributes ranging over a datatype D where the query contains predicates of higher arity (k > 1) over data values from D. We present preliminary results, first by showing a tight link between query answering over DL-Lite parametrised with some datatype D, the evaluation of existential positive sentences over the datatype complementary to D and temporal Constraint Satisfaction Problems. In particular, we prove upper and lower complexity bounds for query answering over DL-Lite(D), where D is defined as the rational numbers with their natural linear order (and similar numerical datatypes), and provide a characterisation of tractability of this problem in a non-standard way, obtained by imposing a syntactical restriction on the form of the query.

    Mentor: Diego Calvanese

  • Thomas Linsbichler

    Abstract Argumentation Frameworks: Dynamics and Computation

    Recently argumentation has become a major topic of artificial intelligence. In particular, the formal approach of abstract argumentation frameworks (AFs) introduced by Dung has aroused much interest of research. The problem of solving certain reasoning tasks on AFs is the centerpiece of many advanced higher-level argumentation systems. Moreover, given that argumentation can be viewed as a process as well as a product, recent years have seen an increasing number of studies on different problems in the dynamics of argumentation frameworks, concerned with the incorporation of new information to an argumentation framework as well as with computation in a changing environment. In the thesis, we deal with topics which concern the dynamics of abstract argumentation in general, and computation in dynamic argumentation scenarios in particular. We plan to apply them to both, the well-known Dung frameworks as well as the powerful generalization of AFs, abstract dialectical frameworks. First, we want to complete and extend the study on expressiveness of argumentation semantics. Based on this we plan to define AGM style revision operators imposing minimal change. Moreover, we want to study the issue of splitting. Finally, we plan to investigate how and to which extent the theoretical insights on argumentation semantics presented above can be used in implementations thereof.

    Mentor: Francesca Toni

  • Daniel Lupp

    Nonmonotonic Mappings and Epistemic Queries in Ontology-Based Data Access

    Ontology-based data access (OBDA) is a paradigm for data access and integration that makes use of a semantic layer, consisting of an ontology and mappings, to enable conceptual querying over relational data sources. Classical OBDA mappings, being strictly first-order implications, have been well-studied in the last few years. However, the discrepancy between the data sources' closed-world assumption (CWA) and the ontology's open-world assumption (OWA) cannot be adequately expressed with mappings that are inherently open-world. To address this, I propose to extend classical OBDA mappings with nonmonotonic features. By interpreting the mappings as rules under ASP-like semantics, one is able to extend the expressive power of the mappings, while still being able to resort to efficient ASP solvers for query answering. By shifting the complexity to the mappings, we are able to express nonmonotonic features over the ontology, such as negation-as-failure and default reasoning as well as epistemic properties over the data source, while still retaining the desired computational properties of the ontology. This would allow for a more sophisticated means of query rewriting optimization and benefit system and mapping maintenance, as well as potentially support epistemic querying.

    Mentor: Carsten Lutz

  • Abductive Diagnosis with Description Logics

    The task of diagnosis is highly relevant in many application domains, such as medical information systems, multimedia content analysis, proactive manufacturing control, etc. Diagnosis is a classic example of abductive reasoning, a type of reasoning typically used to derive explanations for some observations and an existing knowledge base. Many of the above mentioned application domains rely on ontologies, that is, knowledge bases typically based on description logics. Therefore it is useful to investigate abductive reasoning over description logics. Especially ABox abduction is relevant for the task of diagnosis, where we most often look for explanations in form of ground facts. Our aim is to propose and develop an abductive algorithm for description logics. There are some existing approaches based on tableau reasoning techniques and the Reiter's minimal hitting set algorithm, but they were developed for DLs with limited expressivity (e.g. ALC) and to our best knowledge they were not implemented. In this thesis we want to improve and optimize existing approaches and develop a functional prototype implementation based on an existing tableau reasoner. We also want to compare the performance of our implementation with other existing approaches based on translation to first-order logic and logic programming.

    Mentor: Magdalena Ortiz

    Julia Pukancova

  • Vasanth Sarathy

    Cognitive Affordance Representations in Uncertain Logic

    The concept of "affordance" represents the relationship between human perceivers and their environment. Affordance perception, representation, and inference are central to commonsense reasoning, tool-use and creative problem-solving in artificial agents. Existing approaches to representing affordances have focused on its functional aspects, relying on either static ontologies or statistical formalisms to extract relationships between physical features of objects, actions and the corresponding effects of their interaction. These approaches fail to provide flexibility with which to reason about affordances in the open world, where they are influenced by changing context, social norms, historical precedence, and uncertainty. I am developing a formal rules-based logical representational format coupled with an uncertainty-processing framework to reason about cognitive affordances in a more general manner than shown in the existing literature. My framework allows agents to make deductive and abductive inferences about functional and social affordances, collectively and dynamically, thereby allowing the agent to adapt to changing conditions. The ultimate goal of my research is to endow artificial agents with the ability to find creative ways to use and manipulate objects and their environment, especially when there is minimal and uncertain information.

    Mentor: Lise Getoor

  • Logical Mechanisms for Confidentiality in Shared Knowledge Bases

    Knowledge bases can be interconnected to share knowledge. The control of interconnection mechanisms is important to ensure that sensitive information is not extracted in an inappropriate way from connected bases.
    Our goal is to propose a logical model to specify mechanisms for query control, reasoning and evolution of knowledge bases and their corresponding ontologies, ensuring the confidentiality of information whenever appropriate.
    We describe the techniques currently in development to address this problem and show their capabilities and limitations.
    Finally, we introduce the requirements for a software tool to allow a designer of knowledge bases to define sensitive data elements and implement mechanisms to ensure their confidentiality.

    Mentor: Ian Horrocks

    Erika Guetti Suca

  • Formalizing Failed Actions in the Situation Calculus

    In the Situation Calculus the term do(a, s) denotes "the successor situation to s, resulting from performing the action a". In other words, it is assumed that actions always succeed. If action a is not possible in situation s, then do(a, s) and subsequent situation are what Reiter calls "ghost" situations. In these cases the actions still succeed but the situations are not physically realizable.
    This interpretation of do(a, s) shows up in the Reiter's solution to the frame problem as well. Subsequently, the successor state axiom which is developed on top of the solution to the frame problem, is indifferent whether an action is possible or not. In other words, the truth value of a fluent defined by the successor state axiom does not depend on whether the action is possible or not. This makes no room for formalizing failed actions.
    To make up for this representational problem, I give a different interpretation of do(a, s). This new interpretation leads to a more general formulation of the frame problem which takes into account possibility of actions. The solution to this version of the frame problem leads to a successor state axiom which is sensitive whether an action is possible or not. In the new interpretation success or failure of an action corresponds with whether the action is possible or not.
    The new framework has some advantages. For example we can solve a more general case of the projection problem. It also leads to a more general account of knowledge.

    Mentor: Yves Lesperance

    Vahid Vaezian

  • Przemyslaw Walega

    Nonmonotonic Qualitative Spatial Reasoning

    My work on the PhD thesis concerns human-like nonmonotonic reasoning about relations between spatial objects and the way they change in time. The aim of my thesis is to construct new logical approaches for spatial (and nonmonotonic) reasoning.
    The research will embrace theoretical problems of human spatial representation methods, complexity of reasoning as well as computer implementations and applications of the introduced approaches. My main motivation is to obtain a better understanding of qualitative aspects of human spatial reasoning and further use of this knowledge in constructing efficient AI reasoning methods.
    The work accomplished so far amounts to constructing HLQL - Hybrid Logic for Qualitative Reasoning about Location, and ASPMT(QS) - a general framework for spatial reasoning within the paradigm of Answer Set Programming Modulo Theories.
    As one of possible directions for my future work I consider extending the already introduced systems in order to perform more complex spatio-temporal reasoning and using them in practical applications, e.g., navigation of mobile robot

    Acknowledgement   This work is partially supported by the Polish National Science Centre grant 2011/02/A/HS1/00395.

    Mentor: Jochen Renz