Michael Gelfond

KR Conference 2020 Conference Paper

An Answer Set Programming Framework for Reasoning about Agents' Beliefs and Truthfulness of Statements

• Marcello Balduccini
• Michael Gelfond
• Enrico Pontelli
• Tran Cao Son

The paper proposes a framework for capturing how an agent’s beliefs evolve over time in response to observations and for answering the question of whether statements made by a third party can be believed. The basic components of the framework are a formalism for reasoning about actions, changes, and observations and a formalism for default reasoning. The paper describes a concrete implementation that leverages answer set programming for determining the evolution of an agent's ``belief state'', based on observations, knowledge about the effects of actions, and a theory about how these influence an agent's beliefs. The beliefs are then used to assess whether statements made by a third party can be accepted as truthful. The paper investigates an application of the proposed framework in the detection of man-in-the-middle attacks targeting computers and cyber-physical systems. Finally, we briefly discuss related work and possible extensions.

JAIR Journal 2019 Journal Article

REBA: A Refinement-Based Architecture for Knowledge Representation and Reasoning in Robotics

• Mohan Sridharan
• Michael Gelfond
• Shiqi Zhang
• Jeremy Wyatt

This article describes REBA, a knowledge representation and reasoning architecture for robots that is based on tightly-coupled transition diagrams of the domain at two different levels of granularity. An action language is extended to support non-boolean fluents and non-deterministic causal laws, and used to describe the domain's transition diagrams, with the fine-resolution transition diagram being defined as a refinement of the coarse-resolution transition diagram. The coarse-resolution system description, and a history that includes prioritized defaults, are translated into an Answer Set Prolog (ASP) program. For any given goal, inference in the ASP program provides a plan of abstract actions. To implement each such abstract action, the robot automatically zooms to the part of the fine-resolution transition diagram relevant to this action. The zoomed fine-resolution system description, and a probabilistic representation of the uncertainty in sensing and actuation, are used to construct a partially observable Markov decision process (POMDP). The policy obtained by solving the POMDP is invoked repeatedly to implement the abstract action as a sequence of concrete actions. The fine-resolution outcomes of executing these concrete actions are used to infer coarse-resolution outcomes that are added to the coarse-resolution history and used for subsequent coarse-resolution reasoning. The architecture thus combines the complementary strengths of declarative programming and probabilistic graphical models to represent and reason with non-monotonic logic-based and probabilistic descriptions of uncertainty and incomplete domain knowledge. In addition, we describe a general methodology for the design of software components of a robot based on these knowledge representation and reasoning tools, and provide a path for proving the correctness of these components. The architecture is evaluated in simulation and on a mobile robot finding and moving target objects to desired locations in indoor domains, to show that the architecture supports reliable and efficient reasoning with violation of defaults, noisy observations and unreliable actions, in complex domains.

AIJ Journal 2019 Journal Article

Vicious circle principle, aggregates, and formation of sets in ASP based languages

• Michael Gelfond
• Yuanlin Zhang

The paper introduces an extension of the original Answer Set Prolog (ASP) by several set constructs including aggregates, defined as functions on sets. The new language, called A l o g allows creating sets based on the Vicious Circle Principle by Poincaré and Russell which eliminates a number of problems found in existing extensions of ASP by aggregates. We argue that, despite the fact that A l o g is not as expressive as other extensions of ASP by aggregates, clarity of its syntax and semantics, addition of several new set-based constructs, and simplicity and the ease of use make it a viable competitor to these languages. We also study a number of important properties of the language and show how ideas used in its design can be utilized to generalize and simplify the definition of another important extension of ASP by aggregates.

IJCAI Conference 2016 Conference Paper

On the Relationship between P-log and LP MLN

• Evgenii Balai
• Michael Gelfond

The paper investigates the relationship between knowledge representation languages P-log and LPMLN designed for representing and reasoning with logic and probability. We give a translation from an important subset of LPMLN to P-log which preserves probabilistic functions defined by LPMLN programs and complements recent research by the authors of LPMLN where they give a similar translation from a subset of P-log to their language. This work sheds light on the different ways to treat inconsistency in both languages.

KR Conference 2016 Short Paper

Reasoning about Truthfulness of Agents Using Answer Set Programming

• Tran Cao Son
• Enrico Pontelli
• Michael Gelfond
• Marcello Balduccini

We propose a declarative framework for representing and reasoning about truthfulness of agents using answer set programming. We show how statements by agents can be evaluated against a set of observations over time equipped with our knowledge about the actions of the agents and the normal behavior of agents. We illustrate the framework using examples and discuss possible extensions that need to be considered. 2. We observe that John has a Ferrari. A common person would normally be unable to afford a luxury car. At this point, we will likely withdraw our conclusion about John having no money and classify John as a liar. 3. We learn that John inherited the Ferrari from his parents. Inheritance is a possible way to acquire something and thus we might need to reconsider our position about John being a liar. Yet, if someone inherits a Ferrari from his parents then commonsense dictates that the person comes from an affluent household and thus should have money (enough to attend a college). All this reasoning implies that we should not trust John even after this new piece of information.

AIJ Journal 2011 Journal Article

Approximation of action theories and its application to conformant planning

• Phan Huy Tu
• Tran Cao Son
• Michael Gelfond
• A. Ricardo Morales

This paper describes our methodology for building conformant planners, which is based on recent advances in the theory of action and change and answer set programming. The development of a planner for a given dynamic domain starts with encoding the knowledge about fluents and actions of the domain as an action theory D of some action language. Our choice in this paper is AL – an action language with dynamic and static causal laws and executability conditions. An action theory D of AL defines a transition diagram T ( D ) containing all the possible trajectories of the domain. A transition 〈 s, a, s ′ 〉 belongs to T ( D ) iff the execution of the action a in the state s may move the domain to the state s ′. The second step in the planner development consists in finding a deterministic transition diagram T l p ( D ) such that nodes of T l p ( D ) are partial states of D, its arcs are labeled by actions, and a path in T l p ( D ) from an initial partial state δ 0 to a partial state satisfying the goal δ f corresponds to a conformant plan for δ 0 and δ f in T ( D ). The transition diagram T l p ( D ) is called an ‘approximation’ of T ( D ). We claim that a concise description of an approximation of T ( D ) can often be given by a logic program π ( D ) under the answer sets semantics. Moreover, complex initial situations and constraints on plans can be also expressed by logic programming rules and included in π ( D ). If this is possible then the problem of finding a parallel or sequential conformant plan can be reduced to computing answer sets of π ( D ). This can be done by general purpose answer set solvers. If plans are sequential and long then this method can be too time consuming. In this case, π ( D ) is used as a specification for a procedural graph searching conformant planning algorithm. The paper illustrates this methodology by building several conformant planners which work for domains with complex relationship between the fluents. The efficiency of the planners is experimentally evaluated on a number of new and old benchmarks. In addition we show that for a subclass of action theories of AL our planners are complete, i. e. , if in T l p ( D ) we cannot get from δ 0 to a state satisfying the goal δ f then there is no conformant plan for δ 0 and δ f in T ( D ).

AAAI Conference 2005 Conference Paper

Conformant Planning for Domains with Constraints—A New Approach

• Tran C. Son
• Michael Gelfond

The paper presents a pair of new conformant planners, CPApc and CPAph, based on recent developments in theory of action and change. As an input the planners take a domain description D in action language AL which allows state constraints (non-stratified axioms), together with a set of CNF formulae describing the initial state, and a set of literals representing the goal. We propose two approximations of the transition diagram T defined by D. Both approximations are deterministic transition functions and can be computed efficiently. Moreover they are sound (and sometimes complete) with respect to T. In its search for a plan, an approximation based planner analyses paths of an approximation instead of that of T. CPApc and CPAph are forward, best first search planners based on this idea. We compare them with two stateof-the-art conformant planners, KACMBP and Conformant- FF (CFF), over benchmarks in the literature, and over two new domains. One has large number of state constraints and another has a high degree of incompleteness. Our planners perform reasonably well in benchmark domains and outperform KACMBP and CFF in the first domain while still working well with the second one. Our experimental result shows that having an integral part of a conformant planner to deal with state constraints directly can significantly improve its performance, extending a similar claim for classical planners in (Thiebaux, Hoffmann, & Nebel 2003).

AIJ Journal 2002 Journal Article

Knowledge Representation and Logic Programming

• Michael Gelfond
• Nicola Leone

AIJ Journal 2002 Journal Article

Logic programming and knowledge representation—The A-Prolog perspective

• Michael Gelfond
• Nicola Leone

In this paper we give a short introduction to logic programming approach to knowledge representation and reasoning. The intention is to help the reader to develop a ‘feel’ for the field's history and some of its recent developments. The discussion is mainly limited to logic programs under the answer set semantics. For understanding of approaches to logic programming built on well-founded semantics, general theories of argumentation, abductive reasoning, etc. , the reader is referred to other publications.

JELIA Conference 2002 Invited Paper

The USA-Advisor: A Case Study in Answer Set Programming

• Michael Gelfond

Abstract Answer set programming [ 8 ] is a new declarative programming paradigm suitable for solving a large range of problems related to knowledge representation and search. The paradigm is rooted in recent developments in several areas of artificial intelligence. Answer set programming starts by encoding relevant domain knowledge as a (possibly disjunctive) logic program, Π. The connectives of this program are normally understood in accordance with the answer set (stable model) semantics [ 4 ], [ 5 ]. The language’s ability to express defaults, i. e. statements of the form “normally, objects of class C have property P ”, coupled with its natural treatment of recursion, and other useful features, often leads to a comparatively concise and clear representation of knowledge. Insights on the nature of causality and its relationship with the answer sets of logic programs [ 6 ], [ 7 ], [ 10 ] allows description of the effects of actions which solves the frame, ramification, and qualification problems, which for a long time have caused difficulties in modeling knowledge about dynamic domains. In the second stage of the programming process, a programming task is reduced to finding the answer sets of a logic program Π ∪ R where R is normally a simple and short program corresponding to this task. The answer sets are found with the help of programming systems [ 9 ], [ 2 ], [ 3 ] implementing various answer set finding algorithms. During the last few years the answer set programming paradigm seems to have crossed the boundaries of artificial intelligence and has started to attract people in various areas of computer science. In this talk I will briefly describe the basic idea of the approach and outline its use for the development of the USA-Advisor decision support system for the Space Shuttle. The largest part of this work was done by my former and current students Monica Nogueira, Marcello Balduccini, and Dr. Richard Watson, in close cooperation with Dr. Matt Barry from the USA Advanced Technology Development Group [ 1 ]. Our goals in creating the USA-Advisor were two-fold. From a scientific standpoint we wanted to test if the rapidly developing answer set programming methodologies, algorithms, and systems could be successfully applied to the creation of medium size, knowledge intensive applications. From the standpoint of engineering, the goal was to design a system to help flight controllers plan for correct operation of the shuttle in situations where multiple failures have occurred. Even though the engineering part of the project is not yet fully completed it is clear that the approach proved to be successful. In this talk I’ll share some lessons and observations learned from this work.

TARK Conference 1994 Conference Paper

Autoepistemic Logic and Introspective Circumscription

• Michael Gelfond
• Vladimir Lifschitz
• Halina Przymusinska
• Grigori Schwarz

We investigate the relationship between two epistemic nonmonotonic formalisms: autoepistemic logic and introspective circumscription. Finitely axiomatized autoepistemic theories are shownto be equivalent to the propositional case of introspective circumscription. This theorem is applied to the problem ofrelating the usual "minimizing" circumscription to autoepistemic logic.

IJCAI Conference 1993 Conference Paper

Representing Concurrent Actions in Extended Logic Programming

• Chitta Baral
• Michael Gelfond

Gelfond and Lifschitz introduce a declarative language A for describing effects of actions and define a translation of theories in this language into extended logic programs(ELP, s). The purpose of this paper is to extend the language and the translation to allow reasoning about the effects of concurrent actions. Logic programming formalization of situation calculus with concurrent actions presented in the paper can be of independent interest and may serve as a test bed for the investigation of various transformations and logic programming inference mechanisms.

AAAI Conference 1991 Conference Paper

Strong Introspection

• Michael Gelfond

NMR Workshop 1989 Conference Paper

Autoepistemic Logic and Formalization of Commonsense Reasoning: Preliminary Report

• Michael Gelfond

NMR Workshop 1989 Conference Paper

Compiling Circumscriptive Theories into Logic Programs

• Michael Gelfond
• Vladimir Lifschitz

Abstract We study the possibility of reducing some special cases of circumscription to logic programming. The description of a given circumscriptive theory T can be sometimes transformed into a logic program II, so that, by running II, we can determine whether a given ground literal is provable in T. The method is applicable, in particular, to some formalizations of tree-structured inheritance systems with exceptions.

AIJ Journal 1989 Journal Article

On the relationship between circumscription and negation as failure

• Michael Gelfond
• Halina Przymusinska
• Teodor Przymusinski

The aim of this paper is to investigate two powerful methods of handling negative information in logic-based knowledge representation systems: the logical minimization in the form of circumscription and the negation as failure rule, formalized by various closures (or completions) of original theories. We suggest a new, more powerful form of the negation as failure rule and describe an important class of theories for which this form of negation as failure is equivalent to particular forms of circumscription. These results establish a close relationship between the two important formalizations of nonmonotonic reasoning and provide a syntactic characterization of the corresponding circumscriptive theories. This allows us to apply existing methods of deduction using various negation as failure rules to answering queries in a broad class of circumscriptive theories.

AAAI Conference 1988 Conference Paper

Compiling Circumscriptive Theories into Logic Programs: Preliminary Report

• Michael Gelfond

AAAI Conference 1987 Conference Paper

On Stratified Autoepistemic Theories

• Michael Gelfond

In this paper we investigate some properties of "autoepistemic logic" approach to the formalization of common sense reasoning suggested by R. Moore in [Moore, 1985]. In particular we present a class of autoepistemic theories (called stratified autoepistemic theories) and prove that theories from this class have unique stable autoepistemic expansions and hence a clear notion of "theoremhood". These results are used to establish the relationship of Autoepistemic Logic with other formalizations of non-monotonic reasoning, such as negation as failure rule and circumscription. It is also shown that "classical" SLDNF resolution of Prolog can be used as a deductive mechanism for a rather broad class of autoepistemic theories. Key words and phrases: common sense reasoning, autoepistemic logic, negation as failure rule, non-monotonic reasoning.

AIJ Journal 1986 Journal Article

Negation as failure

• Michael Gelfond
• Halina Przymusinska

The aim of this paper is a modification of Minker's Generalized Closed World Assumption that would allow application of the “negation as failure rule” with respect to a set P of (not necessarily all) predicates of a database DB. A careful closure procedure is introduced which, when applied to a database DB, produces a new database DB∗, that is used to answer queries about predicates from DB. It is shown that DB∗ is consistent iff DB is consistent. If P is the set of all predicates from DB and DB does not contain functional symbols, then DB∗ coincides with Minker's GCWA. The soundness and completeness of the careful closure procedure with respect to a minimal model style semantic is shown. As an inference engine associated with DB∗ we propose a query evaluation procedure QEP∗ which is a combination of a method of splitting an indefinite database DB into a disjunction of Horn databases and Clark's query evaluation procedure QEP. Soundness of QEP∗ with respect to DB∗ is shown for a broad class of databases.