MAFTEC @ IJCAI-PRICAI
MAFTEC @ IJCAI-PRICAI
IJCAI-PRICAI has been postponed to January 2021 due to the COVID-19 pandemic. Please find updated information about new dates and location in the conference website (https://ijcai20.org/, Covid Update).
This tutorial covers the theoretical foundations of multi-agent, flexible, temporal, epistemic and contingent aspects of planning (decentralized partially observable Markov decision processes, dynamic epistemic logic, temporal planning). The tutorial relies on pedagogical tools Hintikka's world and TouIST.
Automated planning is a classic problem which has been studied since the beginnings of Artificial Intelligence. The traditional focus of the planning community is the generation of plans for an individual agent, with a plan being a sequence of physical actions. This basic problem, known as classical planning, assumes that the agent's actions are described by their positive and negative effects in terms of addition and deletion of atomic propositions, and that the planning agent has perfect information (complete knowledge of the current world state).
Beyond classical planning, the generation of plans for an individual agent having incomplete information has also been investigated: the subfield of conformant planning allows for agents with incomplete knowledge of the initial state but without observation actions, while contingent planning also allows for such actions. Temporal planning is an important extension of classical planning, in which actions have durations and may overlap. An important aspect of temporal planning is that, unlike classical planning, it permits the modelling of problems that can only be solved by executing two or more actions in parallel. The planning community is also increasingly interested in multi-agent tasks, involving, for example, robot swarms or robot-human interactions. A key issue in multi-agent planning is to anticipate interactions between the agents so as to compute coordinated individual policies. Most of the time, the agents have partial observability about the system state (including the other agents) and are uncertain about action outcomes. Computing coordinated behavior thus requires the agents to reason about the other agents' possible states, knowledge and beliefs. Reasoning about an agent's knowledge and belief (including higher-order beliefs, i.e., beliefs about other agents' knowledge) is the traditional subject of epistemic logic. Dynamic epistemic logics also take into account the effects of actions on agents' knowledge. Recently some authors have started to consider epistemic planning problems in this framework. It is the aim of this tutorial to give an overview of these different avenues of research.
In this tutorial, we first introduce DecPOMDP (decentralized partially observable Markov decision processes) and address the generation of decentralized policies. Then, we will show how knowledge based-programs, based on epistemic logic, can succinctly represent plans. We then introduce Dynamic Epistemic Logic to represent actions that cannot be modelled in DecPOMDP such as public/private announcements of complex statements. We end the tutorial with temporal planning.
The potential target audience should be interested in the relevance of formal methods and planning techniques to improve decision making in a multi-agent system.
Prerequisite knowledge: basic background in complexity theory, computability, logic (basics in propositional and first-order logic). However, we will make a strong effort to make the content to a broad audience at IJCAI-PRICAI 2020, especially persons that are not familiar with logic and theoretical computer science. In particular, one of the pedagogical tool we use (Hintikka's World) draws Kripke models by means of comic strips.
Aurélie Beynier
(LIP6, Sorbonne Université, Paris, France)
E-mail: aurelie [dot] beynier [at] lip6 [dot] fr
Home page: http://www-desir.lip6.fr/~beyniera/
My research interests are in coordination, distributed decision-making and multi-agent planning. My work has focused on Markovian models for decentralized sequential decision-making in uncertain and partially observable environments.