The Experts below are selected from a list of 2292 Experts worldwide ranked by ideXlab platform
Giuseppe De Giacomo - One of the best experts on this subject based on the ideXlab platform.
-
Non-terminating processes in the Situation Calculus
Annals of Mathematics and Artificial Intelligence, 2019Co-Authors: Giuseppe De Giacomo, Eugenia Ternovska, Ray ReiterAbstract:By their very design, many robot control programs are non-terminating. This paper describes a Situation Calculus approach to expressing and proving properties of non-terminating programs expressed in Golog , a high level logic programming language for modeling and implementing dynamical systems. Because in this approach actions and programs are represented in classical (second-order) logic, it is natural to express and prove properties of Golog programs, including non-terminating ones, in the very same logic. This approach to program proofs has the advantage of logical uniformity and the availability of classical proof theory.
-
hybrid temporal Situation Calculus
Canadian Conference on Artificial Intelligence, 2019Co-Authors: Vitaliy Batusov, Giuseppe De Giacomo, Mikhail SoutchanskiAbstract:We present a hybrid discrete-continuous extension of Reiter’s temporal Situation Calculus, directly inspired by hybrid systems in control theory. While keeping to the foundations of Reiter’s approach, we extend it by adding a time argument to all fluents that represent continuous change. Thereby, we ensure that change can happen not only because of actions, but also due to the passage of time. We present a systematic methodology to derive, from simple premises, a new group of axioms which specify how continuous fluents change over time within a Situation. We study regression for our new hybrid action theories and demonstrate what reasoning problems can be solved. Finally, we show that our hybrid theories indeed capture hybrid automata.
-
hybrid temporal Situation Calculus
ACM Symposium on Applied Computing, 2019Co-Authors: Vitaliy Batusov, Giuseppe De Giacomo, Mikhail SoutchanskiAbstract:We extend Reiter's temporal Situation Calculus by introducing continuous change due to passage of time in addition to discrete change due to actions. We define regression for hybrid action theories and show that hybrid action theories can capture hybrid automata.
-
SAC - Hybrid temporal Situation Calculus
Proceedings of the 34th ACM SIGAPP Symposium on Applied Computing - SAC '19, 2019Co-Authors: Vitaliy Batusov, Giuseppe De Giacomo, Mikhail SoutchanskiAbstract:We extend Reiter's temporal Situation Calculus by introducing continuous change due to passage of time in addition to discrete change due to actions. We define regression for hybrid action theories and show that hybrid action theories can capture hybrid automata.
-
hybrid temporal Situation Calculus
arXiv: Artificial Intelligence, 2018Co-Authors: Vitaliy Batusov, Giuseppe De Giacomo, Mikhail SoutchanskiAbstract:The ability to model continuous change in Reiter's temporal Situation Calculus action theories has attracted a lot of interest. In this paper, we propose a new development of his approach, which is directly inspired by hybrid systems in control theory. Specifically, while keeping the foundations of Reiter's axiomatization, we propose an elegant extension of his approach by adding a time argument to all fluents that represent continuous change. Thereby, we insure that change can happen not only because of actions, but also due to the passage of time. We present a systematic methodology to derive, from simple premises, a new group of axioms which specify how continuous fluents change over time within a Situation. We study regression for our new temporal basic action theories and demonstrate what reasoning problems can be solved. Finally, we formally show that our temporal basic action theories indeed capture hybrid automata.
Mikhail Soutchanski - One of the best experts on this subject based on the ideXlab platform.
-
hybrid temporal Situation Calculus
Canadian Conference on Artificial Intelligence, 2019Co-Authors: Vitaliy Batusov, Giuseppe De Giacomo, Mikhail SoutchanskiAbstract:We present a hybrid discrete-continuous extension of Reiter’s temporal Situation Calculus, directly inspired by hybrid systems in control theory. While keeping to the foundations of Reiter’s approach, we extend it by adding a time argument to all fluents that represent continuous change. Thereby, we ensure that change can happen not only because of actions, but also due to the passage of time. We present a systematic methodology to derive, from simple premises, a new group of axioms which specify how continuous fluents change over time within a Situation. We study regression for our new hybrid action theories and demonstrate what reasoning problems can be solved. Finally, we show that our hybrid theories indeed capture hybrid automata.
-
hybrid temporal Situation Calculus
ACM Symposium on Applied Computing, 2019Co-Authors: Vitaliy Batusov, Giuseppe De Giacomo, Mikhail SoutchanskiAbstract:We extend Reiter's temporal Situation Calculus by introducing continuous change due to passage of time in addition to discrete change due to actions. We define regression for hybrid action theories and show that hybrid action theories can capture hybrid automata.
-
SAC - Hybrid temporal Situation Calculus
Proceedings of the 34th ACM SIGAPP Symposium on Applied Computing - SAC '19, 2019Co-Authors: Vitaliy Batusov, Giuseppe De Giacomo, Mikhail SoutchanskiAbstract:We extend Reiter's temporal Situation Calculus by introducing continuous change due to passage of time in addition to discrete change due to actions. We define regression for hybrid action theories and show that hybrid action theories can capture hybrid automata.
-
hybrid temporal Situation Calculus
arXiv: Artificial Intelligence, 2018Co-Authors: Vitaliy Batusov, Giuseppe De Giacomo, Mikhail SoutchanskiAbstract:The ability to model continuous change in Reiter's temporal Situation Calculus action theories has attracted a lot of interest. In this paper, we propose a new development of his approach, which is directly inspired by hybrid systems in control theory. Specifically, while keeping the foundations of Reiter's axiomatization, we propose an elegant extension of his approach by adding a time argument to all fluents that represent continuous change. Thereby, we insure that change can happen not only because of actions, but also due to the passage of time. We present a systematic methodology to derive, from simple premises, a new group of axioms which specify how continuous fluents change over time within a Situation. We study regression for our new temporal basic action theories and demonstrate what reasoning problems can be solved. Finally, we formally show that our temporal basic action theories indeed capture hybrid automata.
-
on the undecidability of the Situation Calculus extended with description logic ontologies
International Conference on Artificial Intelligence, 2015Co-Authors: Diego Calvanese, Giuseppe De Giacomo, Mikhail SoutchanskiAbstract: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.
Fabio Patrizi - One of the best experts on this subject based on the ideXlab platform.
-
Situation Calculus for Synthesis of Manufacturing Controllers
arXiv: Artificial Intelligence, 2018Co-Authors: Giuseppe De Giacomo, Brian Logan, Paolo Felli, Fabio Patrizi, Sebastian SardinaAbstract:Manufacturing is transitioning from a mass production model to a manufacturing as a service model in which manufacturing facilities 'bid' to produce products. To decide whether to bid for a complex, previously unseen product, a manufacturing facility must be able to synthesize, 'on the fly', a process plan controller that delegates abstract manufacturing tasks in the supplied process recipe to the appropriate manufacturing resources, e.g., CNC machines, robots etc. Previous work in applying AI behaviour composition to synthesize process plan controllers has considered only finite state ad-hoc representations. Here, we study the problem in the relational setting of the Situation Calculus. By taking advantage of recent work on abstraction in the Situation Calculus, process recipes and available resources are represented by ConGolog programs over, respectively, an abstract and a concrete action theory. This allows us to capture the problem in a formal, general framework, and show decidability for the case of bounded action theories. We also provide techniques for actually synthesizing the controller.
-
bounded Situation Calculus action theories
Artificial Intelligence, 2016Co-Authors: Giuseppe De Giacomo, Yves Lesperance, Fabio PatriziAbstract:In this paper,1 we investigate bounded action theories in the Situation Calculus. A bounded action theory is one which entails that, in every Situation, the number of object tuples in the extension of fluents is bounded by a given constant, although such extensions are in general different across the infinitely many Situations. We argue that such theories are common in applications, either because facts do not persist indefinitely or because the agent eventually forgets some facts, as new ones are learned. We discuss various classes of bounded action theories. Then we show that verification of a powerful first-order variant of the µ-Calculus is decidable for such theories. Notably, this variant supports a controlled form of quantification across Situations. We also show that through verification, we can actually check whether an arbitrary action theory maintains boundedness.
-
on first order μ Calculus over Situation Calculus action theories
Principles of Knowledge Representation and Reasoning, 2016Co-Authors: Diego Calvanese, Giuseppe De Giacomo, Marco Montali, Fabio PatriziAbstract:In this paper we study verification of Situation Calculus action theories against first-order μ-Calculus with quantification across Situations. Specifically, we consider μLa and μLp, the two variants of μ-Calculus introduced in the literature for verification of data-aware processes. The former requires that quantification ranges over objects in the current active domain, while the latter additionally requires that objects assigned to variables persist across Situations. Each of these two logics has a distinct corresponding notion of bisimulation. In spite of the differences we show that the two notions of bisimulation collapse for dynamic systems that are generic, which include all those systems specified through a Situation Calculus action theory. Then, by exploiting this result, we show that for bounded Situation Calculus action theories, μLa and μLp have exactly the same expressive power. Finally, we prove decidability of verification of μLa properties over bounded action theories, using finite faithful abstractions. Differently from the μLp case, these abstractions must depend on the number of quantified variables in the μLa formula.
-
bounded Situation Calculus action theories
arXiv: Artificial Intelligence, 2015Co-Authors: Giuseppe De Giacomo, Yves Lesperance, Fabio PatriziAbstract:In this paper, we investigate bounded action theories in the Situation Calculus. A bounded action theory is one which entails that, in every Situation, the number of object tuples in the extension of fluents is bounded by a given constant, although such extensions are in general different across the infinitely many Situations. We argue that such theories are common in applications, either because facts do not persist indefinitely or because the agent eventually forgets some facts, as new ones are learnt. We discuss various classes of bounded action theories. Then we show that verification of a powerful first-order variant of the mu-Calculus is decidable for such theories. Notably, this variant supports a controlled form of quantification across Situations. We also show that through verification, we can actually check whether an arbitrary action theory maintains boundedness.
-
bounded epistemic Situation Calculus theories
International Joint Conference on Artificial Intelligence, 2013Co-Authors: Giuseppe De Giacomo, Yves Lesperance, Fabio PatriziAbstract:We define the class of e-bounded theories in the epistemic Situation Calculus, where the number of fluent atoms that the agent thinks may be true is bounded by a constant. Such theories can still have an infinite domain and an infinite set of states. We show that for them verification of an expressive class of first-order µ-Calculus temporal epistemic properties is decidable. We also show that if the agent's knowledge in the initial Situation is e-bounded and the objective part of an action theory maintains boundedness, then the entire epistemic theory is e-bounded.
Yves Lesperance - One of the best experts on this subject based on the ideXlab platform.
-
bounded Situation Calculus action theories
Artificial Intelligence, 2016Co-Authors: Giuseppe De Giacomo, Yves Lesperance, Fabio PatriziAbstract:In this paper,1 we investigate bounded action theories in the Situation Calculus. A bounded action theory is one which entails that, in every Situation, the number of object tuples in the extension of fluents is bounded by a given constant, although such extensions are in general different across the infinitely many Situations. We argue that such theories are common in applications, either because facts do not persist indefinitely or because the agent eventually forgets some facts, as new ones are learned. We discuss various classes of bounded action theories. Then we show that verification of a powerful first-order variant of the µ-Calculus is decidable for such theories. Notably, this variant supports a controlled form of quantification across Situations. We also show that through verification, we can actually check whether an arbitrary action theory maintains boundedness.
-
KR - Infinite paths in the Situation Calculus: axiomatization and properties
2016Co-Authors: Shakil M. Khan, Yves LesperanceAbstract:The Situation Calculus has proved to be a very popular formalism for modeling and reasoning about dynamic systems. This otherwise elegant and refined language however lacks a natural way of dealing with "infinite future histories". To this end, in this paper we introduce a new sort ranging over infinite paths in the Situation Calculus and propose an axiomatization for infinite paths. We thus obtain a convenient way of specifying several kinds of notions that involve infinite futures such as temporal properties of non-terminating executions of agents or programs and mental attitudes such as desires and intentions. We prove the correctness of the axiomatization and show that our formalization has some intuitively desirable properties.
-
bounded Situation Calculus action theories
arXiv: Artificial Intelligence, 2015Co-Authors: Giuseppe De Giacomo, Yves Lesperance, Fabio PatriziAbstract:In this paper, we investigate bounded action theories in the Situation Calculus. A bounded action theory is one which entails that, in every Situation, the number of object tuples in the extension of fluents is bounded by a given constant, although such extensions are in general different across the infinitely many Situations. We argue that such theories are common in applications, either because facts do not persist indefinitely or because the agent eventually forgets some facts, as new ones are learnt. We discuss various classes of bounded action theories. Then we show that verification of a powerful first-order variant of the mu-Calculus is decidable for such theories. Notably, this variant supports a controlled form of quantification across Situations. We also show that through verification, we can actually check whether an arbitrary action theory maintains boundedness.
-
synchronous games in the Situation Calculus
Adaptive Agents and Multi-Agents Systems, 2015Co-Authors: Giuseppe De Giacomo, Yves Lesperance, Adrian R PearceAbstract:We develop a Situation Calculus-based account of multi-player synchronous games. These are represented as action theories called Situation Calculus synchronous game structures (SCSGSs) that involve a single action tick whose effects depend on the combination of moves chosen by the players. Properties of games, e.g., winning conditions, playability, weak and strong winnability, etc. can be expressed in a first-order variant of alternating-time mu-Calculus. Computationally effective verification can be performed. SCSGSs can be viewed as a variant of the Game Description Language (GDL) where states are represented by first-order theories.
-
AAMAS - Synchronous Games in the Situation Calculus
2015Co-Authors: Giuseppe De Giacomo, Yves Lesperance, Adrian R PearceAbstract:We develop a Situation Calculus-based account of multi-player synchronous games. These are represented as action theories called Situation Calculus synchronous game structures (SCSGSs) that involve a single action tick whose effects depend on the combination of moves chosen by the players. Properties of games, e.g., winning conditions, playability, weak and strong winnability, etc. can be expressed in a first-order variant of alternating-time mu-Calculus. Computationally effective verification can be performed. SCSGSs can be viewed as a variant of the Game Description Language (GDL) where states are represented by first-order theories.
Hector J Levesque - One of the best experts on this subject based on the ideXlab platform.
-
decidable reasoning in a fragment of the epistemic Situation Calculus
Principles of Knowledge Representation and Reasoning, 2014Co-Authors: Gerhard Lakemeyer, Hector J LevesqueAbstract:The Situation Calculus is a popular formalism for reasoning about actions and change. Since the language is first-order, reasoning in the Situation Calculus is undecidable in general. An important question then is how to weaken reasoning in a principled way to guarantee decidability. Existing approaches either drastically limit the representation of the action theory or neglect important aspects such as sensing. In this paper we propose a model of limited belief for the epistemic Situation Calculus, which allows very expressive knowledge bases and handles both physical and sensing actions. The model builds on an existing approach to limited belief in the static case. We show that the resulting form of limited reasoning is sound with respect to the original epistemic Situation Calculus and eventually complete for a large class of formulas. Moreover, reasoning is decidable.
-
incorporating action models into the Situation Calculus
Johan van Benthem on Logic and Information Dynamics, 2014Co-Authors: Hector J LevesqueAbstract:While both Situation Calculus and dynamic epistemic logics (DELs) are concerned with reasoning about actions and their effects, historically, the emphasis of Situation Calculus was on physical actions in the single-agent case, in contrast, DELs focused on epistemic actions in the multi-agent case. In recent years, cross-fertilization between the two areas has begun to attract attention. In this paper, we incorporate the idea of action models from DELs into the Situation Calculus to develop a general multi-agent extension of it. We analyze properties of beliefs in this extension, and prove that action model logic can be embedded into the extended Situation Calculus. Examples are given to illustrate the modeling of multi-agent scenarios in the Situation Calculus.
-
Johan van Benthem on Logic and Information Dynamics - Incorporating Action Models into the Situation Calculus
Outstanding Contributions to Logic, 2014Co-Authors: Hector J LevesqueAbstract:While both Situation Calculus and dynamic epistemic logics (DELs) are concerned with reasoning about actions and their effects, historically, the emphasis of Situation Calculus was on physical actions in the single-agent case, in contrast, DELs focused on epistemic actions in the multi-agent case. In recent years, cross-fertilization between the two areas has begun to attract attention. In this paper, we incorporate the idea of action models from DELs into the Situation Calculus to develop a general multi-agent extension of it. We analyze properties of beliefs in this extension, and prove that action model logic can be embedded into the extended Situation Calculus. Examples are given to illustrate the modeling of multi-agent scenarios in the Situation Calculus.
-
iterated belief change in the Situation Calculus
Artificial Intelligence, 2011Co-Authors: Steven Shapiro, Yves Lesperance, Maurice Pagnucco, Hector J LevesqueAbstract: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.
-
goal change in the Situation Calculus
Journal of Logic and Computation, 2007Co-Authors: Steven Shapiro, Yves Lesperance, Hector J LevesqueAbstract:Although there has been much discussion of belief change (e.g. [4, 21]), goal change has not received much attention. In this paper, we propose a method for goal change in the framework of Reiter's; [12] theory of action in the Situation Calculus [8, 10], and investigate its properties. We extend the framework developed by Shapiro et al. [17] and Shapiro and Lesperance [16], where goals and goal expansion were modelled, but goal contraction was not.
