Mikhail Soutchanski

AAAI Conference 2022 Conference Paper

From Actions to Programs as Abstract Actual Causes

• Bita Banihashemi
• Shakil M. Khan
• Mikhail Soutchanski

Causality plays a central role in reasoning about observations. In many cases, it might be useful to define the conditions under which a non-deterministic program can be called an actual cause of an effect in a setting where a sequence of programs are executed one after another. There can be two perspectives, one where at least one execution of the program leads to the effect, and another where all executions do so. The former captures a “weak” notion of causation and is more general than the latter stronger notion. In this paper, we give a definition of weak potential causes. Our analysis is performed within the situation calculus basic action theories and we consider programs formulated in the logic programming language ConGolog. Within this setting, we show how one can utilize a recently developed abstraction framework to relate causes at various levels of abstraction, which facilitates reasoning about programs as causes.

ECAI Conference 2020 Conference Paper

Necessary and Sufficient Conditions for Actual Root Causes

• Shakil M. Khan 0001
• Mikhail Soutchanski

Reasoning about actual causes of an observed effect is fundamental to many applications. Batusov and Soutchanski (2018) recently presented a first-order logic approach to compute actual causes. Built on a formal theory of action and change, namely the situation calculus, their approach is quite expressive, as it can be used to determine the causes of quantified effects. However, their approach does not find causes from a counterfactual perspective, nor does it link with the regularity approach to causation. This paper proposes a new analysis of actual achievement causes in the situation calculus. We study the natural properties that are necessary for actual causes and conditions that are sufficient for the achievement of an observed (possibly quantified) effect. We identify a property that is both necessary and sufficient for actual achievement causes. This is one of our main contributions. Our discussion leads to a new definition of actual achievement causes that includes the root cause together with a chain of relevant events. We show when our definition is closely related to the recent one proposed by Batusov and Soutchanski (2018).

ICAPS Conference 2019 Conference Paper

A Logical Semantics for PDDL+

• Vitaliy Batusov
• Mikhail Soutchanski

PDDL+ is an extension of PDDL2. 1 which incorporates fully-featured autonomous processes and allows for better modelling of mixed discrete-continuous domains. Unlike PDDL2. 1, PDDL+ lacks a logical semantics, relying instead on state-transitional semantics enriched with hybrid automata semantics for the continuous states. This complex semantics makes analysis and comparisons to other action formalisms difficult. In this paper, we propose a natural extension of Reiter’s situation calculus theories inspired by hybrid automata. The kinship between PDDL+ and hybrid automata allows us to develop a direct mapping between PDDL+ and situation calculus, thereby supplying PDDL+ with a logical semantics and the situation calculus with a modern way of representing autonomous processes. We outline the potential benefits of the mapping by suggesting a new approach to effective planning in PDDL+.

AAAI Conference 2018 Conference Paper

Situation Calculus Semantics for Actual Causality

• Vitaliy Batusov
• Mikhail Soutchanski

The definitions of actual cause given by Pearl and Halpern (HP) in the framework of causal models provided vital computational insight into an old philosophical problem but by no means resolved it. One source of concern is the lack of objective criteria for selecting possible worlds to be admitted into the counterfactual analysis, epitomized by the competition between multiple proposals by HP and others. Another concern is due to the modest expressivity of propositionallevel structural equations which limits their applicability and, arguably, contributes to the the former problem. We tackle both of these issues using a novel approach. We build our definition of actual cause from first principles in the context of atemporal situation calculus (SC) action theories with sequential actions. As a result, we can successfully identify actual causes of conditions expressed in first-order logic. We validate the HP approach by providing a formal translation from causal models to SC and proving a relationship between our definitions of actual cause and that of HP. Using wellknown and new examples, we show that long-standing disagreements between alternative definitions of actual causality can be mitigated by faithful SC modelling of the domains.

IJCAI Conference 2015 Conference Paper

On the Undecidability of the Situation Calculus Extended with Description Logic Ontologies

• Diego Calvanese
• Giuseppe De Giacomo
• Mikhail Soutchanski

In this paper we investigate situation calculus action theories extended with ontologies, expressed as description logics TBoxes that act as state constraints. We show that this combination, while natural and desirable, is particularly problematic: it leads to undecidability of the simplest form of reasoning, namely satisfiability, even for the simplest kinds of description logics and the simplest kind of situation calculus action theories.

AAAI Conference 2013 Conference Paper

Progression of Decomposed Situation Calculus Theories

• Denis Ponomaryov
• Mikhail Soutchanski

In many tasks related to reasoning about consequences of a logical theory, it is desirable to decompose the theory into a number of components with weakly-related or independent signatures. This facilitates reasoning when signature of a query formula belongs to only one of the components. However, an initial theory may be subject to change due to execution of actions affecting features mentioned in the theory. Having once computed a decomposition of a theory, one would like to know whether a decomposition has to be computed again for the theory obtained from taking into account the changes resulting from execution of an action. In the paper, we address this problem in the scope of the situation calculus, where change of an initial theory is related to the wellstudied notion of progression. Progression provides a form of forward reasoning; it relies on forgetting values of those features which are subject to change and computing new values for them. We prove new results about properties of decomposition components under forgetting and show when a decomposition can be preserved in progression of an initial theory.

AAAI Conference 2011 Conference Paper

Causal Theories of Actions Revisited

• Fangzhen Lin
• Mikhail Soutchanski

It has been argued that causal rules are necessary for representing both implicit side-effects of actions and action quali- fications, and there have been a number different approaches for representing causal rules in the area of formal theories of actions. These different approaches in general agree on rules without cycles. However, they differ on causal rules with mutual cyclic dependencies, both in terms of how these rules are supposed to be represented and their semantics. In this paper we show that by adding one more minimization to Lin’s circumscriptive causal theory in the situation calculus, we can have a uniform representation of causal rules including those with cyclic dependencies. We also demonstrate that sometimes causal rules can be compiled into logically equivalent (under a proposed semantics) successor state axioms even in the presence of cyclical dependencies between fluents.

ECAI Conference 2008 Conference Paper

Reasoning about Dynamic Depth Profiles

• Mikhail Soutchanski
• Paulo E. Santos

Reasoning about perception of depth and about spatial relations between moving physical objects is a challenging problem. We investigate the representation of depth and motion by means of depth profiles whereby each object in the world is represented as a single peak. We propose a logical theory, formulated in the situation calculus (SC), that is used for reasoning about object motion (including motion of the observer). The theory proposed here is comprehensive enough to accommodate reasoning about both sensor data and actions in the world. We show that reasoning about depth profiles is sound and complete with respect to actual motion in the world. This shows that in the conceptual neighbourhood diagram (CND) of all possible depth perceptions, the transitions between perceptions are logical consequences of the proposed theory of depth and motion.

IJCAI Conference 2007 Conference Paper

• Yilan Gu
• Mikhail Soutchanski

We consider a modified version of the situation calculus built using a two-variable fragment of the first-order logic extended with counting quantifiers. We mention several additional groups of axioms that can be introduced to capture taxonomic reasoning. We show that the regression operator in this framework can be defined similarly to regression in the Reiter's version of the situation calculus. Using this new regression operator, we show that the projection and executability problems are decidable in the modified version even if an initial knowledge base is incomplete and open. For an incomplete knowledge base and for ontext-dependent actions, we consider a type of progression that is sound with respect to the classical progression. We show that the new knowledge base resulting after our progression is definable in our modified situation calculus if one allows actions with local effects only. We mention possible applications to formalization of Semantic Web services.

ECAI Conference 2006 Conference Paper

Decision Making in Large-Scale Domains: A Case Study

• Mikhail Soutchanski
• Huy Pham
• John Mylopoulos

Planning under uncertainty attracted significant attention in AI and in other fields. To overcome computational problems associated with Markov Decision Processes (MDPs) in large scale domains researchers often take advantage of structural properties and look for approximately optimal solutions. DTGolog, a decision-theoretic agent programming language based on the situation calculus, was proposed to ease some of the computational difficulties by using natural ordering constraints on execution of actions. Using DTGolog, domain specific constraints on the set of available policies can be expressed in a high-level program and this program helps to reduce significantly computation required to find a policy optimal in this set. Our paper explores whether the DTGolog framework can be used to evaluate different designs of a decision making agent in a large real-world domain. Each design is understood as combination of a template (expressed as a Golog program) for available policies and a reward function. To evaluate and compare alternative designs we estimate the probability of goal satisfaction for each design. As a domain, we choose the London Ambulance Service (LAS) case study that is well known in software engineering, but remains unknown in AI. In our paper we demonstrate that DTGolog can be applied successfully to quantitative evaluation of alternative designs in terms of their ability to satisfy a system goal with a high probability. We provide a detailed axiomatization of the domain in the temporal situation calculus with stochastic actions. The main advantage of this representation is that neither actions, not states require explicit enumeration. We do an experimental analysis using an on-line implementation of DTGolog coupled with a simulator that models real time actions of many external agents.

AAAI Conference 2006 Conference Paper

Decision Making in Uncertain Real-World Domains Using DT-Golog

• Mikhail Soutchanski

DTGolog, a decision-theoretic agent programming language based on the situation calculus, was proposed to ease some of the computational difficulties associated with Markov Decision Processes (MDPs) by using natural ordering constraints on execution of actions. Using DTGolog, domain specific constraints on a set of policies can be expressed in a high-level program to reduce significantly computations required to find a policy optimal in this set. We explore whether the DTGolog framework can be used to evaluate different designs of a decision making agent in a large real-world domain. Each design is understood as combination of a template (expressed as a Golog program) for available policies and a reward function. To evaluate and compare alternative designs we estimate the probability of goal satisfaction for each design. As a domain, we choose the London Ambulance Service (LAS) case study that is well known in software engineering, but remains unknown in AI. We demonstrate that DTGolog can be applied successfully to quantitative evaluation of alternative designs in terms of their ability to satisfy a system goal with a high probability. The full version of this paper includes a detailed axiomatization of the domain in the temporal situation calculus with stochastic actions. The main advantage of this representation is that neither actions, nor states require explicit enumeration. We do an experimental analysis using an on-line implementation of DTGolog coupled with a simulator that models real time actions of many external agents.