Papers

Note: Many of the papers here are also being presented at IJCAI-01 (Seventeenth International Joint Conference on Artificial Intelligence). Due to copyright restrictions, the full text of these papers cannot be included on this website. Links to the texts of these papers will be added here after the conference takes place (Aug. 4-10).

Copyright to the papers here is held by the individual authors, or, where noted, by IJCAI.

Authors: Varol Akman, Selim Erdogan, Joohyung Lee, and Vladimir Lifschitz
Title: A Representation of the Traffic World in the Language of the Causal Calculator
Full paper (Postscript)
Abstract: The Traffic World is an action domain proposed by Erik Sandewall as part of his Logic Modelling Workshop. We show how to represent this domain in the input language of the Causal Calculator.

Authors: Eyal Amir and Pedrito Maynard-Reid II
Title: LiSA: A Robot Driven by Logical Subsumption
Full paper Postscript / PDF
Abstract: This paper describes an implemented robot-control system that is based on Brooks-style subsumption [Brooks86] of logical theories. It implements Brooks-style subsumption between layers using nonmonotonic reasoning. We describe the control and reasoning algorithms and some of the experiments that we did with the system, running on a Nomad200 robot and a set of computers. Our experimental study shows that commonsense theories and general-purpose first-order logic theorem provers can be used to control real-time agents and robots in particular. Our system improves over traditional subsumption systems in several ways. It allows the user to send new axioms to each of the layers as the robot is running, allowing the user to give advice to the robot and to correct behaviors in runtime. Our system has no voting scheme for deciding on the behavior that should be followed. Instead, the layers work in synergy to provide the compound behavior. Our system improves over other robot-control systems that are based on logic in that it allows full first-order expressivity and that it is fully declarative.

Authors: Chitta Baral and Le-Hi Tuan
Title: Reasoning about actions in a probabilistic setting
Full paper (Postscript)
Abstract: In this paper we present a language to reason about actions in a probabilistic setting and compare our work with earlier work by Pearl and (also briefly with) representations used in probabilistic planning. The main feature of out language is its use of static and dynamic causal laws and use of unknown (or background) variables -- whose values are determined by factors beyond our model -- in incorporating probabilities. We also incorporate probabilities in reasoning with narratives.

Author: John Bell
Title: Causal Counterfactuals
Full paper Postscript / PDF
Abstract: The formal possible-worlds analysis of counterfactuals has tended to concentrate on their semantics and logic, with their pragmatics being given informally. However, if counterfactuals are to be of use in Artificial Intelligence, it is necessary to provide formal pragmatics for them. This is done in this paper by combining work on the representation of common sense reasoning about events with an appropriate semantics for counterfactuals. The resulting combination provides a unified framework for formal reasoning about actual and counterfactual events.

Author: Salem Benferhat, Souhila Kaci, Daniel Le Berre and Mary-Anne Williams
Title: : Weakening Conflicting Information for Iterated Revision and Knowledge
Abstract: The ability to handle exceptions, to perform iterated belief revision and to integrate information from multiple sources are essential skills for an intelligent agent. These important skills are related in the sense that they all rely on resolving inconsistent information. We develop a novel and useful strategy for conflict resolution, and compare and contrast it with existing strategies. Ideally the process of conflict resolution should conform with the principle of Minimal Change and should result in the minimal loss of information. Our approach to minimizing the loss of information is to weaken information involved in conflicts rather than completely removing it. We implemented and tested the relative performance of our new strategy in three different ways. We show that it retains more information than the existing Maxi-Adjustment strategy at no extra computational cost. Surprisingly, we are able to demonstrate that it provides a computationally effective compilation of the lexicographical strategy, a strategy which is known to have desirable theoretical properties.
To appear at IJCAI-01.

Authors: Brandon Bennett and Antony P. Galton
Title: A Versatile Representation for Time and Events
Full paper (Postscript)
Abstract: The paper gives an overview of a highly expressive language for representing temporal relationships and events. This language, which we call Versatile Event Logic (VEL), provides a general temporal ontology encompassing many other representations.

Author: Richard Booth
Title: A negotiation-style framework for non-prioritised revision
Full paper (Postscript)
Abstract: We present a framework for non-prioritised belief revision --- i.e., belief revision in which newly acquired information is not always fully accepted --- in which the result of revision is arrived at via a kind of negotiation between old information and new. We show how both ordinary partial meet revision and Ferme and Hansson's selective revision can be captured in this framework, and also how it supports the definition of contraction operators which do not necessarily satisfy the basic AGM contraction postulate of (Success).
To appear at TARK-01 (Theoretical Aspects of Reasoning about Knowledge); however, Prof. Booth holds the copyright.

Authors: Craig Boutilier, Ray Reiter, and Bob Price
Title: Symbolic Dynamic Programming for First-Order MDP's
Full paper (Postscript)
Abstract: We present a dynamic programming approach for the solution of first-order Markov decision processes. This technique uses an MDP whose dynamics are represented in a variant of the situation calculus allowing for stochastic actions. It produces a logical description of the optimal value function and policy by constructing a set of first-order formulae that minimally partition state space according to distinctions made by the value function and policy. This is achieved through the use of an operation known as decision-theoretic regression. In effect, our algorithm performs value iteration without explicit enumeration of either the state or action spaces of the MDP. This allows problems involving relational fluents and quantification to be solved without requiring explicit state space enumeration or conversion to propositional form.

Author: Anthony G Cohn and Shyamanta M Hazarika
Title: Continuous Transitions in Mereotopology
Full paper PDF
Abstract: Continuity from a qualitative perspective is different from both the philosophical and mathematical view of continuity. We explore different intuitive notions of spatio-temporal continuity. We present a general formal framework for continuity and continuous transitions in mereotopology for spatio-temporal histories and thus sketch the correctness of the conceptual neighbourhood for the qualitative spatial representation language RCC-8.

Authors: P. Doherty, W. Lukaszewicz, and A. Szalas
Title: Computing Strongest Necessary and Weakest Sufficient Conditions of First-Order Formulas.
Abstract: A technique is proposed for computing the weakest sufficient (wsc) and strongest necessary (snc) conditions for formulas in an expressive fragment of first-order logic using quantifier elimination techniques. The efficacy of the approach is demonstrated by using the techniques to compute snc's and wsc's for use in agent communication applications, theory approximation and generation of abductive hypotheses. Additionally, we generalize recent results involving the generation of successor state axioms in the propositional situation calculus via snc's to the first-order case. Subsumption results for existing approaches to this problem and a re-interpretation of the concept of "forgetting" as a process of quantifier elimination are also provided.
To appear at IJCAI-01.

Author: Barbara Dunin-Keplicz and Rineke Verbrugge
Title: The Role of Dialogue in Cooperative Problem Solving
Full paper (Postscript)
Abstract: Though communication is a vital ingredient of Computer Supported Cooperative Work (CSCW) as well as Cooperative Problem Solving (CPS) in multiagent system (MAS), the in-depth analysis of different types of communication has been missing in MAS literature. This paper presents an investigation into the role the specific types of dialogue play during consecutive stages of CPS in BDI systems, i.e. potential recognition, team formation, plan formation, and team action. The relevant dialogue types are: persuasion, negotiation, inquiry, deliberation, and information seeking . In the present paper informal characterizations of these types are presented.

Author: Alberto Finzi and Fiora Pirri
Title: Diagnosing failures and predicting safe runs in robot control
Abstract: We present a formal framework for diagnosing failures and predicting safe runs of actions, given incomplete information on the initial state of affair, i.e. on the initial database providing a description of the domain before any action has taken place. Two aspects of uncertainty are formalized by two different notions of probability: uncertainty in the initial database and uncertainty during the execution of a course of actions. We introduce also a third concept of probability, which is obtained by combining the two previous notions. We call this new concept expected probability: it accounts for the probability of a sentence on the hypothesis that the sequence of actions needed to make it true might have failed. This new probability can be used to predict what would happen after a given course of actions; it leads to the possibility of comparing courses of actions and verifying which one is more safe. On the other hand, after a course of actions has been executed, and failures might have occurred, we give a methodology to diagnose what had really happened during the execution.
To appear at IJCAI-01

Authors: Peter Gardenfors and Mary-Anne Williams
Title: Reasoning about Categories in Conceptual Spaces
Abstract: Understanding the process of categorization is a primary research goal in artificial intelligence. The conceptual space framework provides a flexible approach to modeling context-sensitive categorization via a geometrical representation designed for modeling and managing concepts.

In this paper we show how algorithms developed in computational geometry, and the Region Connection Calculus can be used to model important aspects of categorization in conceptual spaces. In particular, we demonstrate the feasibility of using existing geometric algorithms to build and manage categories in conceptual spaces, and we show how the Region Connection Calculus can be used to reason about categories and other conceptual regions.
To appear at IJCAI-01

Author: Andrew Gordon
Title: The Representational Requirements of Strategic Planning
Full paper (PDF)
Abstract: An analysis of strategies, recognizable abstract patterns of planned behavior, reveals an enormous divide between the kind of planning that artificial intelligence planning systems do and the kind of strategic planning that people do. This paper describes a project to collect and represent strategies on a large scale to identify the representational requirements of strategic planning in order to inform the design of futhre artificial intelligence planning systems. Three hundred and seventy-two strategies were collected from ten different planning domains. Each was represented at an abstract level and in a preformal manner designed to reveal the planning concepts that each strategy contains. The contents of these representations, consisting of nearly one thousand unique planning concepts, were then collected and organized into forty-eight groups that outline the representational and functional components of strategic planning systems.

Author: Henrik Grosskreutz and Gerhard Lakemeyer
Title: Belief Update in the pGolog Framework
Full paper (PDF)
Abstract: High-level controllers that operate robots in dynamic, uncertain domains are concerned with at least two reasoning tasks dealing with the effects of noisy sensors and effectors: They have a) to project the effects of a candidate plan and b) to update their beliefs during on-line execution of a plan. In this paper, we show how the pGolog framework, which in its original form only accounted for the projection of high-level plans, can be extended to reason about the way the robot's beliefs evolve during the on-line execution of a plan. pGolog, an extension of the high-level programming language GOLOG, allows the specification of probabilistic beliefs about the state of the world and the representation of sensors and effectors which have uncertain, probabilistic outcomes. As an application of belief update, we introduce belief-based programs, GOLOG-style programs whose tests appeal to the agent's beliefs at execution time.

Author: Joakim Gustafsson and Jonas Kvarnström
Title: Elaboration Tolerance through Object-Orientation
Full paper (Postscript)
Abstract: Although many formalisms for reasoning about action and change have been proposed in the literature, their semantic adequacy has primarily been tested using tiny domains that highlight some particular aspect or problem. However, since some of the classical problems are completely or partially solved and since powerful tools are available, it is now necessary to start modeling more complex domains. This paper presents a methodology for handling such domains in a systematic manner using an object-oriented framework and provides several examples of the elaboration tolerance exhibited by the resulting models.

Author: Jerry R. Hobbs
Title: Causality
Full paper (Postscript)
Abstract: We do things in the world by exploiting our knowledge of what causes what. But in trying to reason formally about causality, there is a difficulty: to reason with certainty, we need complete knowledge of all the relevant events and circumstances, whereas in everyday reasoning tasks we need a more serviceable but looser notion that does not make such demands on our knowledge. In this work I introduce the notion of "causal complex" for a complete set of events and conditions necessary for the causal consequent to occur, and use the term "cause" for the makeshift, nonmonotonic notion we require for everyday tasks such as planning and natural langauge understanding. I discuss the issue of how to distinguish between what is in a causal complex from what is outside it, and within a causal complex, how to distinguishy the eventualities that deserve to be called "causes" from those that do not, in particular circumstances. In addition, I discuss some general properties of causality, such as transitivity, and how related notions such as "prevent", "enable", and "maintain" can be defined in terms of "cause".

Author: John F. Horty
Title: Skepticism and Floating Conclusions
Full paper (Postscript)
Abstract: The purpose of this paper is to question some commonly accepted patterns of reasoning involving nonmonotonic logics that generate multiple extensions. In particular, I argue that the phenomenon of floating conclusions indicates a problem with the view that the skeptical consequences of such theories should be identified with the statements that are supported by each of their various extensions.

Author: G. Neelakantan Kartha
Title: A Circumscriptive Formalization of the Qualification Problem
Abstract: The qualification problem refers to the difficulty that arises in formalizing actions, because it is difficult or impossible to specify in advance all the preconditions that should hold before an action can be executed. We study the qualification problem in the setting of the situation calculus and give a simple formalization using nested abnormality theories, a formalism based on circumscription. The formalization that we present allows us to combine a solution to the frame problem with a solution to the qualification problem.
To appear at IJCAI-01.

Authors: Joohyung Lee, Vladimir Lifschitz, and Hudson Turner
Title: A Representation of the Zoo World in the Language of the Causal Calculator
Full paper (Postscript)
Abstract: The Zoo World is an action domain proposed by Erik Sandewall as part of his Logic Modelling Workshop. We show how to represent this domain in the input language of the Causal Calculator.

Authors: Sheila A. McIlraith and Eyal Amir
Title: Theorem Proving with Structured Theories
Abstract: Motivated by the problem of query answering over multiple structured commonsense theories, we exploit graph-based techniques to improve the efficiency of theorem proving for structured theories. Theories are organized into subtheories that are minimally connected by the literals they share. We present message-passing algorithms that reason over these theories using consequence finding, specializing our algorithms for the case of first-order resolution, and for batch and concurrent theorem proving. We provide an algorithm that restricts the interaction between subtheories by exploiting the polarity of literals. We attempt to minimize the reasoning within each individual partition by exploiting existing algorithms for focused incremental and general consequence finding. Finally, we propose an algorithm that compiles each subtheory into one in a reduced sublanguage. We have proven the soundness and completeness of all of these algorithms.
To appear at IJCAI-01.

Authors: Sheila McIlraith and Tran Cao Son
Title: Adapting Golog for Programming the Semantic Web
Full paper (Postscript)
Abstract: Motivated by the problem of automatically composing network accessible services, such as those on the World Wide Web, this paper proposes an approach to building agent technology based on the notion of generic procedures and customizing user constraint. We argue that an augmented version of the logic programming language Golog provides a natural formalism for programming Web services. To this end, we adapt and extend the Golog language to enable programs that are generic, customizable, and usable in the context of the Web. We realize these extensions in an augmented ConGolog interpreter that combines online execution of information-providing Web services with offline simulation of world-altering Web services, to determine a sequence of Web Services for subsequent execution. Our implemented system is currently interacting with services on the Web.

Authors: Thomas Meyer, Aditya Ghose, and Samir Chopra
Title: Context-sensitive merging
Full paper (Postscript)
Abstract: Intelligent agents have to be able to merge (possibly conflicting) pieces of information obtained from different sources to produce a coherent picture of the world. In this paper we propose a model for context-sensitive merging. We show that the success of the model depends, to a large extent, on the availability of suitable merging operations on epistemic states; structures in the spirit of Spohn (1988). As a result, we investigate the link between such merging operations and the aggregation operations studied in social choice theory (Arrow, 1963). We show that Arrow's impossibility result disappears when recast into the framework that we employ.

Authors: David Randell, Mark Witkowski and Murray Shanahan
Title: From Images to Bodies: Modelling and Exploiting Spatial Occlusion and Motion Parallax
Abstract: This paper describes the Region Occlusion Calculus (ROC-20), that can be used to model spatial occlusion and the effects of motion parallax of arbitrary shaped objects. ROC-20 assumes the region based ontology of RCC-8 and extends Galton's Lines of Sight Calculus by allowing concave shaped objects into the modelled domain. This extension is used to describe the effects of mutually occluding bodies. The inclusion of van Benthem's axiomatization of comparative nearness facilitates reasoning about relative distances between occluding bodies. Further, an envisionment table is developed to model sequences of occlusion events enabling reasoning about objects and their images formed in a changing visual field.
To appear at IJCAI-01.

Authors: N. Sabouret and J.-P. Sansonnet
Title: Automated Answers to Questions about a Running Process
Full paper (Postscript)
Abstract: We propose here a formal model and a classification of the questions that a human user can ask about the actions, behaviour and activity of an active component. The components are described using a specific language and have access at runtime to a formal specification of their actions and current states. We present a formal model for requests about actions based on the combination of speech acts and procedural types that determines the answering mechanism. We also study some procedural problems raised by the formalisation of such common sense questions. Eventually, we show some examples of questions represented in our request model.

Authors: Stuart C. Shapiro, Eyal Amir, Henrik Grosskreutz, David Randell, and Mikhail Soutchanski
Title: Commonsense and Embodied Agents: A Panel Discussion
Full paper Postscript / PDF

Author: Josefina Sierra-Santibanez
Title: Heuristic Planning: a Declarative Forward Chaining Approach
Full paper (Postscript)
Abstract: This paper introduces the notion of heuristic planning, and describes a particular approach to heuristic planning based on a declarative formalization of strategies for action selection. This approach is compared with some heuristic planning systems proposed in the literature. The heuristic information and declarative formalisms for the representation of heuristic knowledge used by these systems are compared in terms of their capacity of controlling the search process and their effectiveness for solving some planning problems.

Author: Mikhail Soutchanski
Title: A correspondence between two different solutions to the projection task with sensing.
Full paper (Postscript)
Abstract: The paper compares an approach to reasoning about effects of actions, knowledge, and sensing that relies on epistemic fluent (and reduces reasoning about knowledge to provability) to another approach that does not rely on epistemic fluents and suggests to account for effects of sense actions directly in successor state axioms. It is shown that under certain assumptions these two approaches are essentially equivalent. The second approach is used in a high level program that controls a mobile robot.

Back to conference home page