Time filter

Source Type


Gasquet O.,University Paul Sabatier | Goranko V.,University of Stockholm | Goranko V.,University of Johannesburg | Schwarzentruber F.,ENS Rennes
Autonomous Agents and Multi-Agent Systems | Year: 2015

We consider multi-agent scenarios where each agent controls a surveillance camera in the plane, with fixed position and angle of vision, but rotating freely. The agents can thus observe the surroundings and each other. They can also reason about each other’s observation abilities and knowledge derived from these observations. We introduce suitable logical languages for reasoning about such scenarios which involve atomic formulae stating what agents can see, multi-agent epistemic operators for individual, distributed and common knowledge, as well as dynamic operators reflecting the ability of cameras to turn around in order to reach positions satisfying formulae in the language. We also consider effects of public announcements. We introduce several different but equivalent versions of the semantics for these languages, discuss their expressiveness and provide translations in PDL style. Using these translations we develop algorithms and obtain complexity results for model checking and satisfiability testing for the basic logic BBL that we introduce here and for some of its extensions. Notably, we show that even for the extension with common knowledge, model checking and satisfiability testing remain in PSPACE. We also discuss the sensitivity of the set of validities to the admissible angles of vision of the agents’ cameras. Finally, we discuss some further extensions: adding obstacles, positioning the cameras in 3D or enabling them to change positions. Our work has potential applications to automated reasoning, formal specification and verification of observational abilities and knowledge of multi-robot systems. © 2015 The Author(s)

Schwarzentruber F.,ENS Rennes | Semmling C.,Ruhr University Bochum
Frontiers in Artificial Intelligence and Applications | Year: 2014

STIT is a potential logical framework to capture responsibility, counterfactual emotions and norms, which are main ingredients for specifying behaviors of virtual agents. We identify here a new fragment and its satisfiability problem is NP-complete and in Σ3 when the number of agents is unbounded. We also identify a slightly more expressive fragment which is undecidable. © 2014 The Authors and IOS Press.

Van Eijck J.,CWI and ILLC | Schwarzentruber F.,ENS Rennes
Advances in Modal Logic | Year: 2014

We propose a simplified logic for reasoning about (multi-agent) epistemic probability models, and for epistemic probabilistic model checking. Epistemic probability models are multi-agent Kripke models that assign to each agent an equivalence relation on worlds, together with a function from worlds to positive rationals (a lottery). The difference with the usual approach is that probability is linked to knowledge rather than belief, and that knowledge is equated with certainty. A first contribution of the paper is a comparison of a semantics for epistemic probability in terms of models with multiple lotteries and models with a single lottery. We give a proof that multiple lottery models can always be replaced by single lottery models. As multiple lotteries represent multiple subjective probabilities, our result connects subjective and intersubjective probability. Next, we define an appropriate notion of bisimulation, and use it to prove an adaptation of the Hennessy-Milner Theorem and to prove that some finite multiple lottery models only have infinite single lottery counterparts. We then prove completeness, and state results about model checking complexity. In particular, we show the PSPACE-completeness of the model checking in the dynamic version with action models. The logic is designed with model checking for epistemic probability logic in mind; a prototype model checker for it exists. This program can be used to keep track of information flow about aleatory acts among multiple agents.

Hunter A.,British Columbia Institute of Technology | Schwarzentruber F.,ENS Rennes
CEUR Workshop Proceedings | Year: 2015

Public announcements cause each agent in a group to modify their beliefs to incorporate some new piece of information, while simultaneously being aware that all other agents are doing the same. Given some fixed goal formula, it is natural to ask if there exists an announcement that will make the formula true in a multi-agent context. This problem is known to be undecidable in a general modal setting, where the presence of nested beliefs can lead to complex dynamics. In this paper, we consider not necessarily truthful public announcements in the setting of propositional belief revision. We are given a goal formula for each agent, and we are interested in finding a single announcement that will make each agent believe the corresponding goal following AGM-style belief revision. If the goals are inconsistent, then this can be seen as a form of ampliative reasoning. We prove that determining if there is an arbitrary public announcement in this setting is not only decidable, but that it is simpler than the corresponding problem in the most simplified modal logics. Moreover, we argue that propositional announcements and beliefs are sufficient for modelling many practical problems, including simple robot controllers.

Grossi D.,University of Liverpool | Lorini E.,University Paul Sabatier | Schwarzentruber F.,ENS Rennes
Journal of Artificial Intelligence Research | Year: 2015

The article introduces a ceteris paribus modal logic, called CP, interpreted on the equivalence classes induced by finite sets of propositional atoms. This logic is studied and then used to embed three logics of strategic interaction, namely atemporal STIT, the coalition logic of propositional control (CL-PC) and the starless fragment of the dynamic logic of propositional assignments (DL-PA). The embeddings highlight a common ceteris paribus structure underpinning the key operators of all these apparently very different logics and show, we argue, remarkable similarities behind some of the most influential formalisms for reasoning about strategic interaction. © 2015 AI Access Foundation. All rights reserved.

Discover hidden collaborations