Dagstuhl Seminar 17231
Epistemic Planning
( Jun 05 – Jun 09, 2017 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/17231
Organizers
- Chitta Baral (Arizona State University - Tempe, US)
- Thomas Bolander (Technical University of Denmark - Lyngby, DK)
- Sheila McIlraith (University of Toronto, CA)
- Hans Van Ditmarsch (LORIA - Nancy, FR)
Contact
- Annette Beyer (for administrative matters)
Impacts
- EFP and PG-EFP : article in Twenty-Eighth International Conference on Automated Planning and Scheduling - Le, Tiep; Fabiano, Francesco; Son, Tran Cao; Pontelli, Enrico - Menlo Park : AAAI Press, 2018. - 10 pp..
- Game Description Language and Dynamic Epistemic Logic Compared : article in Proceedings of International Joint Conference on Artificial Intelligence (IJCAI 2018) - Engesser, Thorsten; Mattmüller, Robert; Nebel, Bernhard; Thielscher, Michael - IJCAI, 2018. - pp. 1795-1802.
Schedule
This seminar brings together three independent research communities: Dynamic Epistemic Logic (DEL), Knowledge Representation (KR) and Automated Planning. All three have a tradition of investigating the interaction between dynamical systems and epistemic states, but with a different focus and by different means. Despite occasional overlap, DEL has mainly investigated the formal semantics of communication and communicative actions, KR mainly the expressivity of theories of action and change, and Planning mainly computational techniques to automatically generate plans. This seminar aims to encourage and nurture increasing synergies between these three strong and independent research communities leading to frameworks for Epistemic Planning: planning with epistemic states, actions and goals. It will thus strengthen and broaden the cross-disciplinary research community that emerged after a prior Dagstuhl Seminar on the subject, entitled “Planning with Epistemic Goals”, that was held in January 2014 (seminar number 14032). This follow-up seminar should lead to better understanding and articulation of commonalities, synergies, and deficits between the DEL, KR and Planning communities.
The seminar will address the following important goals in epistemic planning of joint interest to all of the DEL, KR and Planning communities:
1. Developing benchmark problems for epistemic planning. In the planning community benchmarks are common, but in the epistemic planning community they are not. A list of ten benchmark epistemic planning problems will be formulated, in view of setting goals that can evolve into competitions. In particular, we will be targeting planning problems that are truly epistemic, meaning problems in which the epistemic dimension – knowledge and ignorance – cannot easily be compiled away.
2. Exploring the relation between knowledge and belief in multi-agent epistemic planning. In multi-agent planning an important problem is that knowledge may turn into false belief for some agents after a partially observable action has taken place. We will address approaches to solve this problem. It relates to the general issues of devising appropriate formalisms for doxastic planning (treating beliefs instead of knowledge) and how to deal with belief revision in such settings. We will relate this to the modelling of lying and deception in epistemic/doxastic planning.
3. Developing models of agency and capability in epistemic planning. In multi-agent epistemic planning, agents need to be able to reason about the agent types and capabilities of other agents. Modelling first-order knowledge and, especially, higher-order knowledge of capability opens up new application scenarios of interest to all three core communities. Knowing that someone has the capability of doing a certain action enables new and interesting types of goals in planning which could be used in practical applications.
4. Exploring action types and their representations. It is important to identify and broaden the list of action types relevant to epistemic planning. In terms of communicative actions we can for instance at least distinguish between announcements, questions, requests and instructions. How these actions are best represented is also an important issue. It should be explored whether formalisations in dynamic epistemic logic are appropriate for planning or whether a more simplified way of representing multi-agent actions is needed.
5. Identifying practical tools and resources. We will identify practical tools and resources that facilitate the development and experimental evaluation of automated techniques for epistemic planning. We envision these tools and resources potentially including a Planning Domain Definition Language (PDDL) extension that encompasses epistemic planning, a web page for distributing benchmark problems and open source planners, and potentially the development of an International Planning Competition (IPC) track on epistemic planning.
Creative Commons BY 3.0 DE
Chitta Baral, Thomas Bolander, Sheila McIlraith, and Hans Van Ditmarsch
This seminar brought together three largely independent research communities: Dynamic Epistemic Logic (DEL), Knowledge Representation and Reasoning (KR&R, subsequently KR) and Automated Planning. All three communities have a tradition of investigating the interaction between dynamical systems and epistemic states, but with a different focus and by different means. In the context of this seminar, despite occasional overlap, DEL has mainly investigated the formal semantics of communication and communicative actions, KR&R has mainly focussed on the theories of action and change, and AP has mainly focussed on computational techniques to automatically generate plans. This seminar aimed to encourage and nurture increasing synergies between these three strong and largely independent research communities leading to frameworks for Epistemic Planning: planning with epistemic states, actions, and goals. The seminar succeeded in strengthening and broadening the cross-disciplinary research community that emerged after a prior Dagstuhl Seminar on the subject, entitled "Planning with Epistemic Goals", that was held in January 2014 (seminar number 14032). This follow-up seminar led to a better understanding and articulation of commonalities, synergies, and deficits between the DEL, KR and Planning communities.
The main components of the seminar were tutorial talks and group work. There were four tutorials, by Andreas Herzig, Bernhard Nebel, Tran Cao Son and Ramaswamy Ramanujam. The four tutorial talks presented epistemic planning from the perspective of four different research communities. Andreas Herzig presented epistemic planning from a knowledge representation perspective, Bernhard Nebel from a classical planning perspective, Tran Cao Son from a theories of action and change perspective, and Ramaswamy Ramanujam from a distributed systems and temporal logic perspective. Abstracts for the four tutorials are included in Section 3.
The group work was performed in five separate working groups, each addressing a distinct important objective in epistemic planning of shared interest to the DEL, KR and Planning communities. Specifically, the five groups worked on (1) Developing Benchmarks for Epistemic Planning, (2) Exploring Action Types and their Representations, (3) Exploring the Relations Between Knowledge and Belief in Multi-Agent Epistemic Planning, (4) Practical Tools, Resources and Computational Techniques, and (5) Correspondence Between Planning Problems and Games. These group themes are briefly described below, and the outcome of the work in each group is documented in Section 4.
- Developing Benchmarks for Epistemic Planning. In the planning community benchmarks are common, but in the epistemic planning community they are not. The overall goal of the group working on this theme was to formulate a list of ten benchmark epistemic planning problems, in view of setting goals that can evolve into competitions. In particular, the focus was on targeting planning problems that are truly epistemic, meaning problems in which the epistemic dimension - knowledge and ignorance - cannot easily be disregarded. Guiding questions for the work in this group were: What problems help define and circumscribe what we are studying? What are specific tasks that motivate this area of study, e.g. epistemic planning, protocol synthesis, automated diagnosis, verification, and communication? What problems can help drive future research in developing formalisms and implementing systems of epistemic planning? What are the features of the relevant planning problems in terms of knowledge vs. belief, single- vs. multi-agent, communicative vs. sensing vs. ontic actions, deterministic vs. non-deterministic actions, etc. How do we evaluate "hardness" of problems, e.g. in terms of level of nesting of belief/knowledge, types of actions, size of problem, scalability, and quality of solution. Do benchmarks for some of these problems already exist?
- Exploring Action Types and their Representations. It is important to identify and broaden the list of action types relevant to epistemic planning. In terms of communicative actions we can for instance at least distinguish between announcements, questions, requests and instructions. How these actions are best represented is also an important issue. It should be explored whether formalizations in dynamic epistemic logic are appropriate for planning or whether a more simplified way of representing multi-agent actions is needed. The overall goal of the group working on this theme was to identify, classify and possibly broaden the list of action types relevant to epistemic planning, as well as to explore formalisms for representing these action types. Guiding questions for the work in this group were: What are the relevant distinctions between types of actions, e.g. epistemic vs. ontic, deterministic vs. non-deterministic vs. probabilistic, instantaneous vs. durative, sensing vs. announcements, degree of observability (public, private, semi-private), etc. What formalisms can support expressing and distinguishing between these action types (e.g. DEL, Situation Calculus, Knowledge-based Programs)? How are multi-agent actions represented, in particular how are conflicts between concurrently occurring actions specified, and how is observability of concurrent actions specified in terms of the observability of the constituting actions?
- Exploring the Relations Between Knowledge and Belief in Multi-Agent Epistemic Planning. In multi-agent planning an important problem is that knowledge may turn into false belief for some agents after a partially observable action has taken place. This is a problem for several formalisms for epistemic planning, e.g. dynamic epistemic logic, since agents might not be able to recover from false beliefs. It relates to the general issues of devising appropriate formalisms for doxastic planning (treating beliefs instead of knowledge) and how to deal with belief revision in such settings. The overall goal of the work in this group was to identify the theoretical and computational challenges in planning with knowledge vs. planning with belief; when one or the other is appropriate, or both are needed. Guiding questions for the work in this group were: How are knowledge and beliefs represented and distinguished from representations of the actual world? How do we formally handle that knowledge may turn into false belief after a partially observable action has occurred? What are the relevant formalisms for planning with knowledge and/or belief and what are their theoretical and computational properties? How do we deal with belief revision in planning? Are there specific types of interesting goals for epistemic planning? For example, in planning with beliefs, goals can be about making some agents have false beliefs. This necessitates formalizing false-belief tasks, lying and deception.
- Practical Tools, Resources and Computational Techniques. The goal of the group working on this theme was to identify practical tools and resources that facilitate the development and experimental evaluation of automated techniques for epistemic planning. Guiding questions for the work in this group were: What tools and computational techniques already exist in epistemic planning? What are the models and formulas used? What are the shortcomings and challenges of these tools and computational techniques? Are there tools or computational techniques from other communities that we are not availing ourselves of to the fullest extent (e.g., for the planning people model checking)? What are the trade-offs between different tools? What are the computational complexities of the different approaches and under different assumptions.
- Correspondence Between Planning Problems and Games. This working group was introduced as an additional discussion topic during the seminar, since several participants found it very relevant and important to epistemic planning. The issue is that (epistemic) game theory studies many of the same problems as (epistemic) planning, but mainly by separate research communities using separate vocabularies. The goal of the group working on this theme was to establish formal connections between the area of automated planning and the area of game theory. Guiding questions for the work in this group were: What are the formalisms, tools and results from game theory relevant to automated planning? Symmetrically, what are the formalisms, tools and results from automated planning relevant to game theory? Can problems formulated in one of the settings easily be translated into the other? What is gained and lost in such translations?
Chitta Baral, Thomas Bolander, Sheila McIlraith, and Hans Van Ditmarsch
- Guillaume Aucher (IRISA - Rennes, FR) [dblp]
- Chitta Baral (Arizona State University - Tempe, US) [dblp]
- Vaishak Belle (University of Edinburgh, GB) [dblp]
- Thomas Bolander (Technical University of Denmark - Lyngby, DK) [dblp]
- Tran Cao Son (New Mexico State University, US) [dblp]
- Tristan Charrier (INRIA - Rennes, FR) [dblp]
- Jens Claßen (RWTH Aachen, DE) [dblp]
- Thorsten Engesser (Universität Freiburg, DE) [dblp]
- Esra Erdem (Sabanci University - Istanbul, TR) [dblp]
- Tim French (The Univ. of Western Australia, AU) [dblp]
- Malvin Gattinger (University of Amsterdam, NL) [dblp]
- Nina Gierasimczuk (Technical University of Denmark - Lyngby, DK) [dblp]
- Malte Helmert (Universität Basel, CH) [dblp]
- Andreas Herzig (Paul Sabatier University - Toulouse, FR) [dblp]
- Mathias Justesen (Technical University of Denmark - Lyngby, DK)
- Ioannis Kokkinis (LORIA - Nancy, FR) [dblp]
- Filippos Kominis (UPF - Barcelona, ES) [dblp]
- Barteld Kooi (University of Groningen, NL) [dblp]
- Louwe B. Kuijer (University of Liverpool, GB) [dblp]
- Jérôme Lang (University Paris-Dauphine, FR) [dblp]
- Yves Lesperance (York University - Toronto, CA) [dblp]
- Kai Li (Peking University, CN)
- Yongmei Liu (Sun Yat-sen University - Guangzhou, CN) [dblp]
- Robert Mattmüller (Universität Freiburg, DE) [dblp]
- Bastien Maubert (University of Napoli, IT) [dblp]
- Sheila McIlraith (University of Toronto, CA) [dblp]
- Tim Miller (The University of Melbourne, AU) [dblp]
- Bernhard Nebel (Universität Freiburg, DE) [dblp]
- Andrés Occhipinti Liberman (Technical University of Denmark - Lyngby, DK) [dblp]
- Ron Petrick (Heriot-Watt University - Edinburgh, GB) [dblp]
- Sophie Pinchinat (IRISA - Rennes, FR) [dblp]
- Ramaswamy Ramanujam (Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Torsten Schaub (Universität Potsdam, DE) [dblp]
- Richard Scherl (Monmouth Univ. - West Long Branch, US) [dblp]
- Francois Schwarzentruber (IRISA - ENS Rennes, FR) [dblp]
- Maayan Shvo (Utrecht University, NL) [dblp]
- Sunil Easaw Simon (Indian Institute of Technology Kanpur, IN) [dblp]
- Michael Thielscher (UNSW - Sydney, AU) [dblp]
- Hans Van Ditmarsch (LORIA - Nancy, FR) [dblp]
- Jan van Eijck (CWI - Amsterdam, NL) [dblp]
- Ivan José Varzinczak (CRIL, University Artois & CNRS, FR) [dblp]
- Yanjing Wang (Peking University - Beijing, CN) [dblp]
- Bruno Zanuttini (Caen University, FR) [dblp]
Related Seminars
- Dagstuhl Seminar 14032: Planning with epistemic goals (2014-01-12 - 2014-01-15) (Details)
Classification
- artificial intelligence / robotics
- data structures / algorithms / complexity
- verification / logic
Keywords
- Automated planning
- multi-agent systems
- epistemic logic
- dynamic epistemic logic
- temporal epistemic logic
- knowledge representation
