Integrating Discrete and Continuous Change in a Logical Framework

The goal of our work is to develop theoretical foundations for the representation of knowledge in domains in which properties may vary continuously. One achievement of our research is that it extends the applicability of current research on theories of action. Furthermore, we are able to apply known approaches to the frame and ramification problems, developed for discretely changing worlds, to domains in which the world changes continuously.
Our approach is based on the discrete situation calculus and on a monotonic solution to the frame problem. In order to address the combined frame and ramification problems, we extend Lin and Reiter's work. We use Pinto and Reiter's extension to the situation calculus to represent occurrences . We extend this work further to allow for reasoning by default. For example, if we know that a ball is falling and we do not have any reason to believe that an action would interfere with the ball's motion, then we assume that the ball will hit the ground. Finally, we extend the language of the situation calculus to allow for properties that change within situations. We also show that our proposed situation calculus inherits the solutions to the frame and ramification problems.     

Goal Change in the Situation Calculus

Although there has been much discussion of belief change (e.g.[4, 21]), goal change has not received much attention. In thispaper, we propose a method for goal change in the frameworkof Reiter's; [12] theory of action in the situation calculus[8, 10], and investigate its properties. We extend the frameworkdeveloped by Shapiro et al. [17] and Shapiro and Lespérance[16], where goals and goal expansion were modelled, but goalcontraction was not.     

面向行动的信念更新

基于可能模型方法 ( possible m odel approach,简称 PMA) ,提出了面向行动的信念更新的概念 ,证明了在信息完备的情境演算系统中 ,一个一阶公式在情境 s下成立当且仅当它属于情境 s下的信念集 .这一结果为有效避免情境演算推理中二阶归纳公理的使用提供了一条可行的途径 ,也为基于意向驱动的 agent模型的建立以及面向 agent的程序设计语言 AOPL ID( agent-oriented programm ing language with intention driver)的提出提供了必要的理论基础.     

The Situation Calculus: A Case for Modal Logic

The situation calculus is one of the most established formalisms for reasoning about action and change. In this paper we will review the basics of Reiter’s version of the situation calculus, show how knowledge and time have been addressed in this framework, and point to some of the weaknesses of the situation calculus with respect to time. We then present a modal version of the situation calculus where these problems can be overcome with relative ease and without sacrificing the advantages of the original.     

Applying the persistent set approach in temporal reasoning

Since Hanks and McDermott raised the problem of temporal projection (e.g. the Yale shooting problem) and showed that classical nonmonotonic logics failed to solve it, many solutions have been proposed. However, as indicated by some researchers, most of them are not completely satisfactory. In Zhang and Foo [22], we presented a theory of actions called thepersistent set approach (PSA). In this paper, we extend our previous work to deal with temporal reasoning. Different from those minimality-based approaches, we propose a persistence-based formalization of actions within the situation calculus framework, and show that this gives natural and intuitive solutions to the problem of temporal projection in many cases. Explanations of some of the differences between persistence and minimality are given. We show that our approach also provides a unified framework for representing actions with disjunctive effects, while most of the current methods are inappropriate for dealing with these actions in the general case.     

基于情境演算的智能体结构

Agent结构的建立是Agent研究的重要内容.尝试着结合BDI结构和情境演算的优点,提出了一个能够刻画Agent的多种特征,尤其是自主性的智能体结构AASC(Agent architecture based on situation calculus).此结构既能表示Agent的信念、目标、策略等心智状态,又能进行行动推理和规划,为解释Agent的自主性、建构不同类型的Agent提供了统一的平台.     

Infobase Change: A First Approximation

Generalisations of theory change involving operations on arbitrary sets ofwffs instead of on belief sets (i.e., sets closed under a consequencerelation), have become known as base change. In one view, a base should bethought of as providing more structure to its generated belief set, whichmeans that it can be employed to determine the theory contraction operationassociated with a base contraction operation. In this paper we follow suchan approach as the first step in defining infobase change. We think of an infobase as a finite set of wffs consisting of independently obtainedbits of information. Taking AGM theory change (Alchourrón et al. 1985) as the general framework, we present a method that uses the structure of aninfobase B to obtain an AGM theory contraction operation for contractingthe belief set Cn(B). Both the infobase and the obtained theory contraction operation then play a role in constructing a unique infobasecontraction operation. Infobase revision is defined in terms of an analogueof the Levi Identity, and it is shown that the associated theory revisionoperation satisfies the AGM postulates for revision. Because every infobaseis associated with a unique infobase contraction and revision operation, the method also allows for iterated base change.     

Synthesizing advanced transaction models using the situation calculus

The situation calculus is a versatile logic for reasoning about actions and formalizing dynamic domains. Using the non-Markovian action theories formulated in the situation calculus, one can specify and reason about the effects of database actions under the constraints of the classical, flat database transactions, which constitute the state of the art in database systems. Classical transactions are characterized by the so-called ACID properties. With non-Markovian action theories, one can also specify, reason about, and even synthesize various extensions of the flat transaction model, generally called advanced transaction models (ATMs). In this paper, we show how to use non-Markovian theories of the situation calculus to specify and reason about the properties of ATMs. In these theories, one may refer to past states other than the previous one. ATMs are expressed as such non-Markovian theories using the situation calculus. We illustrate our method by specifying (and sometimes reasoning about the properties of) several classical models and known ATMs.     

Dynamic belief revision operators

The AGM approach to belief change is not geared to provide a decent account of iterated belief change. Darwiche and Pearl have sought to extend the AGM proposal in an interesting way to deal with this problem. We show that the original Darwiche-Pearl approach is, on the one hand excessively strong and, on the other rather limited in scope. The later Darwiche-Pearl approach, we argue, although it addresses the first problem, still remains rather permissive. We address both these issues by (1) assuming a dynamic revision operator that changes to a new revision operator after each instance of belief change, and (2) strengthening the Darwiche-Pearl proposal. Moreover, we provide constructions of this dynamic revision operator via entrenchment kinematics as well as a simple form of lexicographic revision, and prove representation results connecting these accounts.     

A Fuzzy Reasoning Model for Action and Change in Timed Domains

This paper proposes a fuzzy approach for reasoning about action and change in timed domains. In our method, actions and world states are modeled as fuzzy sets over time axis. Thus, their temporal relations and time constraints can be modeled as fuzzy rules. So, our method handles well the issue that action happens at an approximate time and then the states also change at an approximate time, which has not been solved well in the existing work. Finally, our method is used to solve the classic problem of rail‐road crossing control in a fuzzy environment. The theoretical and simulation analysis shows that the controller using our method works well.     

Reasoning about time in the situation calculus

We extend the ontology of the situation calculus to provide for the representation of time and event occurrences. We do this by defining a time line corresponding to a sequence of situations (calledactual situations) beginning with the initial situation. Actual situations are totally ordered and the actions that lead to different actual situations are said to haveoccurred. This extension to the situation calculus permits one to express truths about the state of the world at different times. For example, we can state that at some point in the future certain fluents will be true. We can also express constraints on the occurrences of events, for example, that after releasing a cup, it will eventually hit the floor. Our version of the situation calculus subsumes other temporal logics. In particular, we show that the modaltemporal logic of concurrency [4] can be embedded in the extended situation calculus. Our extension can also realize the essential features of other first-order proposals for reasoning about time commonly used for AI purposes (e.g. Allen [1], Kowalski and Sergot [6]).Part of this work was done while this author was with the Department of Computer Science, University of Toronto.     

Relation Algebras and their Application in Temporal and Spatial Reasoning

Qualitative temporal and spatial reasoning is in many cases based on binary relations such as before, after, starts, contains, contact, part of, and others derived from these by relational operators. The calculus of relation algebras is an equational formalism; it tells us which relations must exist, given several basic operations, such as Boolean operations on relations, relational composition and converse. Each equation in the calculus corresponds to a theorem, and, for a situation where there are only finitely many relations, one can construct a composition table which can serve as a look up table for the relations involved. Since the calculus handles relations, no knowledge about the concrete geometrical objects is necessary. In this sense, relational calculus is pointless. Relation algebras were introduced into temporal reasoning by Allen (1983, Communications of the ACM 26(1), 832–843) and into spatial reasoning by Egenhofer and Sharma (1992, Fifth International Symposium on Spatial Data Handling, Charleston, SC). The calculus of relation algebras is also well suited to handle binary constraints as demonstrated e.g. by Ladkin and Maddux (1994, Journal of the ACM 41(3), 435–469). In the present paper I will give an introduction to relation algebras, and an overview of their role in qualitative temporal and spatial reasoning.     

HYPOTHETICAL REASONING ABOUT ACTIONS: FROM SITUATION CALCULUS TO EVENT CALCULUS

Hypothetical reasoning about actions is the activity of preevaluating the effect of performing actions in a changing domain; this reasoning underlies applications of knowledge representation, such as planning and explanation generation. Action effects are often specified in the language of situation calculus, introduced by McCarthy and Hayes in 1969. More recently, the event calculus has been defined to describe actual actions, i.e., those that have occurred in the past, and their effects on the domain. Altough the two formalisms share the basic ontology of atomic actions and fluents, situation calculus cannot represent actual actions while event calculus cannot represent hypotethical actions. In this article, the language and the axioms of event calculus are extended to allow representing and reasoning about hypothetical actions, performed either at the present time or in the past, altough counterfactuals are not supported. Both event calculus and its extension are defined as logic programs so that theories are readily adaptable for Prolog query interpretation. For a reasonably large class of theories and queries, Prolog interpretation is shown to be sound and complete w.r.t. the main semantics for logic programs.     

A semantic characterization of a useful fragment of the situation calculus with knowledge

The situation calculus, as proposed by McCarthy and Hayes, and developed over the last decade by Reiter and co-workers, is reconsidered. A new logical variant called ES is proposed that captures much of the expressive power of the original, but where certain technical results are much more easily proved. This is illustrated using two existing non-trivial results: the determinacy of knowledge theorem of Reiter and the regression theorem, which reduces reasoning about the future to reasoning about the initial situation. Furthermore, we show the correctness of our approach by embedding ES in Reiter's situation calculus.     

Globally linear connection method

To model in a formal system the remarkable ability of human agents to reason about situations, actions, and causality has always been a major research goal in Intellectics. Most of the work towards this goal is based on the situation calculus which, however, has the disadvantage that it requires either to state frame axioms or to use non-monotonic logic and a commonsense law of inertia. A deductive approach which does not show this disadvantage is the linear connection method whose key idea is to treat facts about a situation as resources which can be consumed and produced by actions. It was shown that this approach properly handles planning problems which only allow deterministic actions, i.e. actions which are not allowed to have several alternative effects. In this paper we extend and revise the linear connection method to overcome this restriction. Stefan Brüning, Ph.D.: He received a M. Sc. in Computer Science from the Technical University of Darmstadt in 1992. From 1992 to present he has been a research officer in the Intellectics group at the same university where he received his Ph. D. in 1995. His thesis was entitled “Techniques for Avoiding Redundancy in Theorem Proving Based on the Connection Method”. His current research interests are in the development of efficient calculi for different kinds of deductive tasks, such as deductive planning or default reasoning.     

Fuzzy control of robot manipulator with a flexible tool

In some tasks, a rigid robot manipulator handles a long, slender, and flexible tool, which usually has not been equipped with vibration measuring devices. This situation makes a different tool tip position control problem. In this paper, a new method will be presented for simultaneous tip position and vibration suppression control of a flexible tool on a rigid‐link 3‐DOF robot. This approach uses fuzzy logic rule‐based controllers without using any sensors and actuators on the tool or a priori knowledge about the tool. Numerical simulation of robot and tool set has been accomplished and results support the fact that designed fuzzy controllers perform remarkably well in reducing vibrations and precision guidance of robot tool tip for tracking various trajectories. © 2005 Wiley Periodicals, Inc.     

Navigating the Gap Between Action and a Serving Information System

Creating, or adapting, information systems to support people undertaking purposeful action in organizational settings involves moving from: exploring the problem situation and thinking about what action to take, to thinking about how to support that action. In business settings this support will inevitably entail technology-based information systems. Most information system design approaches neglect the importance of the initial exploration and sense making phase and move directly to specifying the business process to be operationalised through the application of some software. The ideas described here have been developed with the intention of supporting a group of people navigating an inquiry through the shift in focus from: thinking about action, to thinking about support in a manner that promotes Client-led information system design. The ideas have been applied in practice through an Action Research field study in a UK banking organization and here we describe our navigational approach to IS design.     

Towards a Model of Learning through Communication

Communication is an interactive, complex, structured process involving agents that are capable of drawing conclusions from the information they have available about some real-life situations. Such situations are generally characterized as being imperfect. In this paper, we aim to address learning from the perspective of the communication between agents. To learn a collection of propositions concerning some situation is to incorporate it within one's knowledge about that situation. That is, the key factor in this activity is for the goal agent, where agents may switch role if appropriate, to integrate the information offered with what it already knows. This may require a process of belief revision, which suggests that the process of incorporation of new information should be modeled nonmonotonically. We shall employ for reasoning a three-valued based nonmonotonic logic that formalizes some aspects of revisable reasoning and it is accessible to implementation. The logic is sound and complete. A theorem-prover of the logic has successfully been implemented. Received 3 August 1999 / Revised 17 April 2000 / Accepted 6 May 2000     

事件演算在行动推理中的应用

事件演算是基于一阶谓词演算的行动推理理论.它可作为描述事件的一个工具,在行动推理的应用中显示出其强大的表示能力和实现能力.在事件演算中,可以对行动进行公理化,可以描述行动的时间性、并发性、连续变化及知识,而且还可用Prolog实现.讨论介绍与这些应用相关的基本概念、思想和方法等,并且通过一个送咖啡的例子说明了如何通过事件演算来描述和实现.