Research Interests

Last updated Oct. 22, 1997.

I'm interested in basic questions in artificial intelligence, specially in the general area of knowledge representation and reasoning. My research to date has focused on three main topics: knowledge compilation and automated reasoning, non-monotonic temporal reasoning (reasoning about actions and knowledge base update), and belief revision, including qualitative models of the relation between perception and belief.

Automated reasoning and knowledge compilation.

Just as programs are compiled to speed up execution, knowledge can also be compiled off-line so as to speed up on-line performance in query answering and inference. (See Marco Cadoli Panel on Knowledge Compilation and Approximation: Terminology, Questions, References , in AI/MATH-96, for a review of the area.)

The expectation/assumption is that the cost of compilation can be amortized over many queries during the lifecycle of the knowledge base. Ideally, the goal of compilation is to ensure that query answering is tractable (polynomial time) with respect to the compiled knowledge base. In KR'94 (abstract) , I present the first significant proposal for equivalence preserving compilation: the compiled knowledge base allows for tractable answers for all queries with unit resolution, trading off neither expressivity nor completeness. In IJCAI'95 (abstract) , I analyze and prove the correctness of algorithms for approximate knowledge compilation, whose more modest goal is only to ensure that all queries in some restricted query language can be tractably processed. In AAAI'96 (abstract) I introduce a new algorithm for approximate knowledge compilation which can be exponentially more efficient than previous algorithms, and lift the results on approximate knowledge compilation to the first order case.

Non-monotonic temporal reasoning and reasoning about action

The goal here is to provide concise and empirically adequate descriptions of a dynamic world which changes in response to actions and events. In a series of papers AAAI'92 (abstract) , IJCAI'93a (abstract) , JLLI'94 (abstract) , Yoav Shoham and I develop a general framework for reasoning about action which can capture in its enterity one of most important proposals for knowledgebase update (Katsuno & Mendelzon), and allows us to answer questions about its scope and applicability in terms of a solution to the frame and ramification problems. As a result we unify in an important sense two previously disjoint areas of research, non-monotonic temporal reasoning and database update. In parallel, and as part of my thesis work (thesis abstract, table of contents) I developed the first algorithms for the temporal projection problem (under a minimal change semantics) which do not require direct or indirect appeal to the models of the domain theory, resulting in an easily exponential efficiency improvement. See KR'92 (abstract) , IJCAI'93b (abstract) .

Belief revision and non monotonic reasoning.

Belief revision and non-monotonic reasoning are two sides of the same coin, dealing with the defeasibility of information. Knowledge bases and beliefs are not static; they are subject to change as new information arrives, even if the world they describe does not change. The revision of an agent's beliefs can be captured in an unified framework which includes update and reasoning about action (see previous point). For this purpose, Yoav Shoham and I, in JLC'94 (abstract) extend the situation calculus (a well-known logic for reasoning about actions and events) with epistemic operators. The resulting "mental situation calculus" allows us to capture the revision of the agent's beliefs in an strictly more general way than in the AGM (Alchourron, Gardenfors & Makinson) approach to revision. As a result of the generality of this logical framework, I was able to derive in AAAI'94 (abstract) the expressive equivalence of Poole's style proof-theoretic non-monotonic reasoning and Shoham's preferential semantics, and, closely connected, between the foundational and coherentist approaches to belief revision. (All of which can be captured in the mental situation calculus.) Further connections between revision and non-monotonic reasoning are explored in the long version of the AAAI'94 paper, in JANCL'97 (abstract) .

As in the case of update and temporal reasoning, I have also developed new algorithms for implementing a number of revision operators proposed in the literature, see IJCAI93b (abstract) .

Finally, in IJCAI'97 (abstract) I develop with Pedrito Maynard-Reid and Yoav Shoham a qualitative model of reasoning about perception and belief, building upon a previous technical report (abstract) with Yoav Shoham.