Seminar Homepage : Druckversion


http://www.dagstuhl.de/17231

05. – 09. Juni 2017, Dagstuhl Seminar 17231

Epistemic Planning

Organisatoren

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)

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Report, Volume 7, Issue 6 Dagstuhl Report
Motivationstext
Teilnehmerliste
Gemeinsame Dokumente
Programm des Dagstuhl Seminars [pdf]

Summary

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.

  1. 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?
  2. 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?
  3. 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.
  4. 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.
  5. 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?
License
  Creative Commons BY 3.0 Unported license
  Chitta Baral, Thomas Bolander, Sheila McIlraith, and Hans Van Ditmarsch

Related Dagstuhl Seminar

Classification

Keywords



Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Seminar Homepage : Letzte Änderung 22.02.2018, 17:33 Uhr