Lorentz Center - To Be Announced! Synthesis of Epistemic Protocols from 17 Aug 2015 through 21 Aug 2015
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    To Be Announced! Synthesis of Epistemic Protocols
    from 17 Aug 2015 through 21 Aug 2015


Titles and abstracts of keynote talks for Lorentz workshop To Be Announced

  • Natasha Alechina, University of Nottingham, United Kingdom
    title: When observation and communication have cost
    abstract: I will review work (by other people as well as my own) on logical modelling of observation and/or communication action that cost agents some resources. Then I review work on Alternating-Time Temporal Logic (ATL) where actions have costs. The last part of the talk will be a synthesis where I propose a way to model costs of observation and communication in ATL extended with syntactic or standard epistemic operators.
    Two relevant papers for this subject are:
  • Guillaume Aucher, IRISA / University of Rennes, France
    Title: Automata Techniques for Epistemic Protocol Synthesis
    Abstract: In this work we aim at applying automata techniques to problems studied in Dynamic Epistemic Logic, such as epistemic planning. To do so, we first remark that repeatedly executing ad infinitum a propositional event model from an initial epistemic model yields a relational structure that can be finitely represented with automata. This correspondence, together with recent results on uniform strategies, allows us to give an alternative decidability proof of the epistemic planning problem for propositional events, with as by-products accurate upper-bounds on its time complexity, and the possibility to synthesize a finite word automaton that describes the set of all solution plans. In fact, using automata techniques enables us to solve a much more general problem, that we introduce and call epistemic protocol synthesis. (This is joint work with Bastien Maubert and Sophie Pinchinat).
  • Valentin Goranko, Stockholm University, Sweden
    title: Secure aggregation of distributed information
    abstract: We consider the generic problem of Secure Aggregation of Distributed Information (SADI), where a group of agents have information distributed amongst them, i.e., included in their collective knowledge, while each agent has only partial knowledge of it. The agents act as a team that has to exchange and aggregate that information, either as common knowledge within the group or in the individual knowledge of at least one of them. The exchange is performed over insecure communication channels and is presumed intercepted by an adversary 'eavesdropper'. The task of the team is to achieve the aggregation of the distributed information, following a prearranged protocol, in such a way that the adversary does not learn important information.
    We model the SADI problem by assuming that the information that each agent has is encoded by a set of 'cards' that she holds in her hands. The cards are drawn from a publicly known deck and every card is in the hands of exactly one agent of the team and can only be seen by that agent. The goal of the team is to exchange and spread across the whole team the information about how the cards are distributed amongst the agents. The agents can only communicate by making public announcements over insecure channels and the goal of the eavesdropper is to learn the location of at least one of the cards by intercepting and analysing the announcements exchanged by the agents.
    The problem described above is a variation of the well-known 'Russian cards problem'. Here we, on the one hand, generalize it to any number of agents, but on the other hand we restrict it essentially by assuming that the eavesdropper has no cards in his hands. In this work we present a combinatorial construction of protocols that provides a direct solution of a class of SADI problems and develop a technique of iterated reduction of SADI problems to 'simpler' ones which are eventually solvable directly. We show that our methods provide a solution to all SADI problems of sufficiently large size.
  • Jérôme Lang, Université Paris Dauphine, France
    title: Knowledge-based programs and epistemic planning
    abstract: This work is based on several papers with Bruno Zanuttini and Anaëlle Wilczynski. Knowledge-based programs (Fagin, Halpern, Moses and Vardi, 95) are high-level protocols for specifying sequences of actions that an agents performs in function of her knowledge about the state of the world and (when applicable) the knowledge state of other agents. The specificity of such programs is that branching conditions are purely subjective epistemic formulas (of S5, or more generally S5n when there are several agents). We will see why and how knowledge-based programs (called 'plans' in this context) are a powerful tool for AI planning. The talk will first focus on single-agent knowledge-based programs; we will discuss expressivity, succinctness, and complexity issues, and will show how knowledge-based plans can be synthesized from the specification of a goal,of the available actions, and of the initial knowledge state. Then we we will introduce probabilistic knowledge-based programs, as well as multi-agent knowledge-based planning problems.
  • Robert Mattmüller, University Freiburg, Germany
    title: Cooperative Epistemic Multi-Agent Planning With Implicit Coordination
    abstract: Epistemic Planning has been used to achieve ontic and epistemic control in multi-agent situations. We extend the formalism to include perspective shifts, allowing us to define a class of cooperative problems in which both action planning and execution is done in a purely distributed fashion, meaning coordination is only allowed implicitly by means of the available (epistemic) actions.
  • Sheila McIlraith, University of Toronto, Canada
    title: Planning Over Multi-Agent Epistemic States via State-of-the-Art Automated Planning Techniques
    abstract: Many AI applications involve the interaction of multiple autonomous agents, requiring those agents to reason about their own beliefs, as well as those of other agents. Unfortunately, planning involving nested beliefs is known to be computationally challenging. In this work, we address the task of synthesizing plans that necessitate reasoning about the beliefs of other agents. We plan from the perspective of a single agent with the potential for goals and actions that involve nested beliefs, non-homogeneous agents, co-present observations, and the ability for one agent to reason as if it were another. We formally characterize our notion of planning with nested belief, and subsequently demonstrate how to automatically convert such problems into problems that appeal to state-of-the-art classical planning technology. Our approach represents an important first step towards applying the well-established field of AI automated planning to the challenging task of planning involving nested beliefs of multiple agents.
  • Yoram Moses, Israel Institute of Technology, Israel
    title: Protocol Design using the Knowledge of Preconditions Principle
    abstract: This talk will introduce and discuss a fundamental connection between knowledge and action called the knowledge of preconditions principle (KoP). It will then proceed to illustrate how the KoP can be used to derive an efficient solution to a well-known problem from basic principles. While this talk will not be in the DEL framework, it will not assume prior familiarity with the runs and systems framework used in the design and analysis of distributed systems.
  • Ron Petrick, Edinburgh University, United Kingdom
    title: PKS (Planning with Knowledge and Sensing) is a knowledge-level planner that builds plans by reasoning directly about what the planner knows and does not know, and how the planner's knowledge changes due to action.
    abstract: While the basic planner provided a first-person, single agent view of planning with incomplete information and sensing, recent work has aimed to improve the planner's representational and inferential ability through extensions like interval-valued epistemic fluents, knowledge decay, program-like constructs, and the integration of external reasoning engines. In addition, the first steps have been taken to extend the PKS approach to nested multiagent knowledge. In this talk I will review the basic PKS planner and highlight details of some of the planner's recent extensions. This work has partly been motivated by robotics applications and examples of such domains will be presented, notably a scenario involving human-robot interaction with a robot bartender.
  • Sophie Pinchinat, IRISA / University of Rennes, France
    title: Relating paths in transition systems: the fall of the modal mu-calculus
    abstract: We revisit Janin and Walukiewicz's classic result on the expressive completeness of the modal mu-calculus w.r.t. Monadic Second Order Logic (MSO), when transition systems are equipped with a binary relation over paths. We obtain two natural extensions of MSO and of the mu-calculus: MSO with path relation and the jumping mu-calculus. While "bounded-memory" binary relations bring about no extra expressivity to either of the two logics, "unbounded-memory" binary relations make the bisimulation-invariant fragment of MSO with path relation more expressive than the jumping mu-calculus: the existence of winning strategies in games with imperfect-information inhabits the gap. This is joint work with Catalin Dima and Bastien Maubert.
  • Matthijs Spaan, Delft University, Netherlands
    title: Multiagent Planning under Uncertainty with Communication
    abstract: We consider decision-theoretic approaches to multiagent planning under uncertainty, formalized as extensions of the Partially Observable Markov Decision Process (POMDP) model. In cooperative settings, communication between agents has the potential to significantly improve team performance. For instance, a higher degree of coordination can often be obtained by sharing local information. A common objective, however, is to minimize the level of communication required for satisfying performance. In this talk, we discuss different models of communication that have been explored and pair them with appropriate solution techniques.
  • Yanjing Wang, Peking University, China
    Title: Epistemic logics of  `knowing what'
    Standard epistemic logic focuses on 'knowing that'. However, in protocol synthesis and epistemic planning, it is also important to handle 'knowing what', 'knowing how' and 'knowing who' formally. For example, it is often assumed in security protocols that each agent knows what its own private key is but does not know others' private keys; it is also intuitive for a security protocol to guarantee that the malicious agent does not know how to get certain information; an authentication protocol needs to make sure the agent knows who it is talking to. In this talk, we survey our recent work on non-standard epistemic logics and focuses on the logics of `knowing what'.