Inductive situation calculus

Temporal reasoning has always been a major test case for knowledge representation formalisms. In this paper, we develop an inductive variant of the situation calculus in ID-logic, classical logic extended with inductive definitions. This logic has been proposed recently and is an extension of classical logic. It allows for a uniform representation of various forms of definitions, including monotone inductive definitions and non-monotone forms of inductive definitions such as iterated induction and induction over well-founded posets. We show that the role of such complex forms of definitions is not limited to mathematics but extends to commonsense knowledge representation. In the ID-logic axiomatization of the situation calculus, fluents and causality predicates are defined by simultaneous induction on the well-founded poset of situations. The inductive approach allows us to solve the ramification problem for the situation calculus in a uniform and modular way. Our solution is among the most general solutions for the ramification problem in the situation calculus. Using previously developed modularity techniques, we show that the basic variant of the inductive situation calculus without ramification rules is equivalent to Reiter-style situation calculus.     

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.     

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.     

Multi-Agent Systems Specification and Certification: A Situation and State Calculus Approach

We address the topic of specifying multi-agent systems using the situation and state calculus (SSC). SSC has been proposed as an extension of the situation calculus to overcome some limitations of the usual notion of state. The envisaged multi-agent system specification framework allows the uniform treatment of both local and global properties, providing also techniques for reasoning about such specifications. When a certain intended property is not inferred from a specification, we cannot always just add to it the corresponding formula. Indeed, it is often the case that specification axioms are required to be formulae of a certain kind. The task of identifying the new axioms that should be added to the specification in order to ensure the intended property has an abductive nature. Herein, we develop abductive reasoning techniques to tackle this problem.     

SCDBR: An Automated Reasoner for Specifications of Database Updates

In this paper we describe SCDBR, a system that is able to reason automatically from specifications of database updates written in the situation calculus, a first–order language originally proposed by John McCarthy for reasoning about actions and change. The specifications handledby the system are written in the formalism proposed by Ray Reiter for solving the frame problem that appears when one expresses the effects on the database predicates of the execution of atomic transactions.SCDBR is written in PROLOG, and can solve several reasoning tasks, among others,it is able to derive the final specification from effect axioms, to answerqueries to virtually updated databases, to check legality of transactions,to prove integrity constraints from the specification, to modify thespecification in order to embed a desired integrity constraint, and to answer historical queries. For some of these tasks SCDBR can call othersystems, like relational database systems, automated theorem provers, andconstraint solvers.     

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.     

Specifying and computing preferred plans

In this paper, we address the problem of specifying and computing preferred plans using rich, qualitative, user preferences. We propose a logical language for specifying preferences over the evolution of states and actions associated with a plan. We provide a semantics for our first-order preference language in the situation calculus, and prove that progression of our preference formulae preserves this semantics. This leads to the development of PPlan, a bounded best-first search planner that computes preferred plans. Our preference language is amenable to integration with many existing planners, and beyond planning, can be used to support a diversity of dynamical reasoning tasks that employ preferences.     

Towards a Hybrid Dynamic Logic for Hybrid Dynamic Systems

We introduce a hybrid variant of a dynamic logic with continuous state transitions along differential equations, and we present a sequent calculus for this extended hybrid dynamic logic. With the addition of satisfaction operators, this hybrid logic provides improved system introspection by referring to properties of states during system evolution. In addition to this, our calculus introduces state-based reasoning as a paradigm for delaying expansion of transitions using nominals as symbolic state labels. With these extensions, our hybrid dynamic logic advances the capabilities for compositional reasoning about (semialgebraic) hybrid dynamic systems. Moreover, the constructive reasoning support for goal-oriented analytic verification of hybrid dynamic systems carries over from the base calculus to our extended calculus.     

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.     

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.     

Existential rigidity and many modalities in order-sorted logic

Order-sorted logic is a useful tool for knowledge representation and reasoning because it enables representation of sorted terms and formulas along with partially ordered sorts (called sort-hierarchy). However, this logic cannot represent more complex sorted expressions when they are true in any possible world (as rigid) or some possible worlds (as modality) such as time, space, belief, or situation. In this study, we extend order-sorted logic by introducing existential rigidity and many modalities. In the extended logic, sorted modal formulas are interpreted over the Cartesian product of sets of possible worlds. We present a new labeled tableau calculus to check the (un)satisfiability and validity of sorted modal formulas.     

A Calculus and logic of resources and processes

Recent advances in logics for reasoning about resources provide a new approach to compositional reasoning in interacting systems. We present a calculus of resources and processes, based on a development of Milner’s synchronous calculus of communication systems, SCCS, that uses an explicit model of resource. Our calculus models the co-evolution of resources and processes with synchronization constrained by the availability of resources. We provide a logical characterization, analogous to Hennessy–Milner logic’s characterization of bisimulation in CCS, of bisimulation between resource processes which is compositional in the concurrent and local structure of systems. An erratum to this article can be found at     

Merging deductive and inductive reasoning for processing textual descriptions of inter-human conflicts

We report on a novel approach to modeling a dynamic domain with limited knowledge. A domain may include participating agents where we are uncertain about motivations and decision-making principles of some of these agents. Our reasoning setting for such domains includes deductive, inductive, and abductive components. The deductive component is based on situation calculus and describes the behavior of agents with complete information. The machine learning-based inductive and abductive components involve the previous experience with the agents, whose actions are uncertain to the system. Suggested reasoning machinery is applied to the problem of processing customer complaints in the form of textual messages that contain a multiagent conflict. The task is to predict the future actions of an opponent agent to determine the required course of action to resolve a multiagent conflict. This study demonstrates that the hybrid reasoning approach outperforms both stand-alone deductive and inductive components. Suggested methodology reflects the general situation of reasoning in dynamic domains in the conditions of uncertainty, merging analytical (rule-based) and analogy-based reasoning.     

An order-sorted query system for sort, predicate, and meta-predicate hierarchies

This paper presents a decidable order-sorted query system for reasoning between ontologies and rules. We describe order-sorted logic programming with sort, predicate, and meta-predicate hierarchies (OSL_3h), which derives predicate and meta-predicate assertions. Meta-level predicates (predicates of predicates) are useful for representing relationships between predicate formulas, and further, they conceptually yield a hierarchy similar to the hierarchies of sorts and predicates. By extending the order-sorted Horn-clause calculus, we develop a query-answering system in OSL_3h that can answer queries such as atoms and meta-atoms generalized by containing predicate variables. We show that the expressive query-answering system computes every generalized query in single exponential time, that is, the complexity of our query system is equal to that of DATALOG.     

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.     

独立于设计者的行动推理

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

Ontology-based semantic search on the Web and its combination with the power of inductive reasoning

Semantic Web search is currently one of the hottest research topics in both Web search and the Semantic Web. In previous work, we have presented a novel approach to Semantic Web search, which allows for evaluating ontology-based complex queries that involve reasoning over the Web relative to an underlying background ontology. We have developed the formal model behind this approach, and provided a technique for processing Semantic Web search queries, which consists of an offline ontological inference step and an online reduction to standard Web search. In this paper, we continue this line of research. We further enhance the above approach by the use of inductive rather than deductive reasoning in the offline inference step. This increases the robustness of Semantic Web search, as it adds the important ability to handle inconsistencies, noise, and incompleteness, which are all very likely to occur in distributed and heterogeneous environments such as the Web. The inductive variant also allows to infer new (not logically deducible) knowledge (from training individuals). We report on a prototype implementation of (both the deductive and) the inductive variant of our approach in desktop search, and we provide extensive new experimental results, especially on the running time and the precision and the recall of our new?approach.