Causality and Counterfactuals in the Situation Calculus

Structural causal models offer a popular framework for exploringcausal concepts. However, due to their limited expressiveness,structural models have difficulties coping with such conceptsas actual (event-to-event) causation. In this article, we proposea new type of causal model, based on embedding structural considerationsin the language of situation calculus. By using situation calculusas a basic language, we leverage its power to express complex,dynamically changing situations and, by relying on structuralconsiderations, we can formulate an effective theory of counterfactualswithin the situation-calculus.     

OSC:一个开放式情景演算系统的研究

在经典情景演算系统的基础上引入了广义信念修正理论,构建了一个开放式情景演算系统OSC(open situation calculus),克服了经典情景演算系统不能刻画交互通信能力以及对事件的响应处理能力的缺陷．OSC系统保留了经典情景演算系统中的情景流result-of(a,s),用以刻画行动的影响;同时又引入了新的情景流bel-rev(φ,s),用以刻画通信交互以及对事件的响应处理等具有开放性信息的活动．OSC系统采用了离线规划与在线执行相结合的运行方式,为面向agent程序设计语言、面向agent智能系统的设计开发等应用提供了有效途径．     

Compiling Ramification Constraints into Effect Axioms

We present a method to derive a solution to the combined frame and ramification problems for certain classes of theories of action written in the situation calculus. The theories of action considered include the causal laws of the domain, in the form of a set of effect axioms, as well as a set of ramification state constraints. The causal laws state the direct effects that actions have on the world, and ramification state constraints allow one to derive indirect effects of actions on the domain.
To solve the combined frame and ramification problems, the causal laws and ramification state constraints are replaced by a set of successor state axioms . Given a state of the world, these axioms uniquely determine the truth value of dynamic properties after an action is performed. In this article, we extend previous work by formulating an approach for the mechanical generation of these successor state axioms. We make use of the notions of implicate and support that have been developed in the context of propositional theories. The approach works for classes of syntactically restricted sets of ramification state constraints.
     

Iterated belief change in the situation calculus

John McCarthy's situation calculus has left an enduring mark on artificial intelligence research. This simple yet elegant formalism for modelling and reasoning about dynamic systems is still in common use more than forty years since it was first proposed. The ability to reason about action and change has long been considered a necessary component for any intelligent system. The situation calculus and its numerous extensions as well as the many competing proposals that it has inspired deal with this problem to some extent. In this paper, we offer a new approach to belief change associated with performing actions that addresses some of the shortcomings of these approaches. In particular, our approach is based on a well-developed theory of action in the situation calculus extended to deal with belief. Moreover, by augmenting this approach with a notion of plausibility over situations, our account handles nested belief, belief introspection, mistaken belief, and handles belief revision and belief update together with iterated belief change.     

Probabilistic Situation Calculus

In this article we propose a Probabilistic Situation Calculus logical language to represent and reason with knowledge about dynamic worlds in which actions have uncertain effects. Uncertain effects are modeled by dividing an action into two subparts: a deterministic (agent produced) input and a probabilistic reaction (produced by nature). We assume that the probabilities of the reactions have known distributions.Our logical language is an extension to Situation Calculae in the style proposed by Raymond Reiter. There are three aspects to this work. First, we extend the language in order to accommodate the necessary distinctions (e.g., the separation of actions into inputs and reactions). Second, we develop the notion of Randomly Reactive Automata in order to specify the semantics of our Probabilistic Situation Calculus. Finally, we develop a reasoning system in MATHEMATICA capable of performing temporal projection in the Probabilistic Situation Calculus.     

基于情景演算的多个智能虚拟人协作行为描述语言

在情景演算的框架内引入真并发动作和相应的语义,参照 FIPA-ACL 增加了请求、承诺、结果等通信动作,将 ConGolog 扩展为 CTConGolog,并且基于 CTConGolog 提出一个请求/服务协作模型及相应语义.在此基础上,引入用于表示复杂行为动画的元动作,提出并且实现了一种多个智能虚拟人协作行为描述语言--CBDL.实验结果表明,CBDL 能够较好地描述多个智能虚拟人在动态环境下通过推理和协作而表现出的行为.     

Proof Complexity of the Cut-free Calculus of Structures

We investigate the proof complexity of analytic subsystems ofthe deep inference proof system SKSg (the calculus of structures).Exploiting the fact that the cut rule (i) of SKSg correspondsto the ¬-left rule in the sequent calculus, we establishthat the ‘analytic'system KSg+c has essentially the samecomplexity as the monotone Gentzen calculus MLK. In particular,KSg+c quasipolynomially simulates SKSg, and admits polynomial-sizeproofs of some variants of the pigeonhole principle.     

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.     

Bisimilarity for the Region Calculus

A region calculus is a programming language calculus with explicit instrumentation for memory management. Every value is annotated with a region in which it is stored and regions are allocated and deallocated in a stack-like fashion. The annotations can be statically inferred by a type and effect system, making a region calculus suitable as an intermediate language for a compiler of statically typed programming languages.Although a lot of attention has been paid to type soundness properties of different flavors of region calculi, it seems that little effort has been made to develop a semantic framework. In this paper, we present a theory based on bisimulation, which serves as a coinductive proof principle for showing equivalences of polymorphically region-annotated terms. Our notion of bisimilarity is reminiscent of open bisimilarity for the -calculus and we prove it sound and complete with respect to Morris-style contextual equivalence.As an application, we formulate a syntactic equational theory, which is used elsewhere to prove the soundness of a specializer based on region inference. We use our bisimulation framework to show that the equational theory is sound with respect to contextual equivalence.     

用Spi演算描述和验证密码学安全协议

讨论了针对共享密钥安全协议的Ｓｐｉ演算,而且对安全协议的Ｓｐｉ演算描述和验证进行了深入的探讨。     

A Full Formalization of SLD-Resolution in the Calculus of Inductive Constructions

This paper presents a full formalization of the semantics of definite programs, in the calculus of inductive constructions. First, we describe a formalization of the proof of first-order terms unification: this proof is obtained from a similar proof dealing with quasi-terms, thus showing how to relate an inductive set with a subset defined by a predicate. Then, SLD-resolution is explicitely defined: the renaming process used in SLD-derivations is made explicit, thus introducing complications, usually overlooked, during the proofs of classical results. Last, switching and lifting lemmas and soundness and completeness theorems are formalized. For this, we present two lemmas, usually omitted, which are needed. This development also contains a formalization of basic results on operators and their fixpoints in a general setting. All the proofs of the results, presented here, have been checked with the proof assistant Coq.     

独立于设计者的行动推理

高水平的智能机器人要求能够独立地对环境进行感知并进行正确的行动推理.在情境演算行动理论中表示带有感知行动及知识的行动推理需要外部设计者为agent写出背景公理、感知结果及相应的知识变化,这是一种依赖于设计者的行动推理.情境演算行动理论被适当扩充,感知器的表示被添加到行动理论的形式语言中,并把agent新知识的产生建立在感知器的应用结果之上.扩充后的系统能够形式化地表示机器人对环境的感知并把感知结果转换为知识,还能进行独立于设计者的行动推理,同时让感知行动的“黑箱”过程清晰化.     

Cut-Rule Axiomatization of the Syntactic Calculus NL0

An axiomatics of the product-free syntactic calculus L ofLambek has been presented whose only rule is the cut rule. It was alsoproved that there is no finite axiomatics of that kind. The proofs weresubsequently simplified. Analogous results for the nonassociativevariant NL of L were obtained by Kandulski. InLambek's original version of the calculus, sequent antecedents arerequired to be nonempty. By removing this restriction, we obtain theextensions L ₀ and NL ₀ ofL and NL, respectively. Later, the finiteaxiomatization problem for L ₀ andNL ₀ was partially solved, viz., for formulas withoutleft (or, equivalently, right) division and an (infinite) cut-ruleaxiomatics for the whole of L ₀ has been given. Thepresent paper yields an analogous axiomatics forNL ₀. Like in the author's previous work, the notionof rank of an axiom is introduced which, although inessentialfor the results given below, may be useful for the expectednonfinite-axiomatizability proof.     

Cut-Rule Axiomatization of the Syntactic Calculus L0

In Zielonka (1981a, 1989), I found an axiomatics for the product-free calculus L of Lambek whose only rule is the cut rule. Following Buszkowski (1987), we shall call such an axiomatics linear. It was proved that there is no finite axiomatics of that kind. In Lambek's original version of the calculus (cf. Lambek, 1958), sequent antecedents are non empty. By dropping this restriction, we obtain the variant L ₀ of L. This modification, introduced in the early 1980s (see, e.g., Buszkowski, 1985; Zielonka, 1981b), did not gain much popularity initially; a more common use of L ₀ has only occurred within the last few years (cf. Roorda, 1991: 29). In Zielonka (1988), I established analogous results for the restriction of L ₀ to sequents without left (or, equivalently, right) division. Here, I present a similar (cut-rule) axiomatics for the whole of L ₀. This paper is an extended, corrected, and completed version of Zielonka (1997). Unlike in Zielonka (1997), the notion of rank of an axiom is introduced which, although inessential for the results given below, may be useful for the expected non-finite-axiomatizability proof. The paper follows the same way of subject exposition as Zielonka (2000) but it is technically much less complicated. I restrict myself to giving bare results; all the ideological background is exactly the same as in case of the non-associative calculusNL ₀ and those who are interested in it are requested to consult the introductory section of Zielonka (2000). This revised version was published online in August 2006 with corrections to the Cover Date.