Dagstuhl Seminar 14032
Planning with epistemic goals
( Jan 12 – Jan 15, 2014 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/14032
Organizers
- Thomas Agotnes (University of Bergen, NO)
- Gerhard Lakemeyer (RWTH Aachen, DE)
- Benedikt Löwe (University of Amsterdam, NL)
- Bernhard Nebel (Universität Freiburg, DE)
Contact
The seminar brings together the communities of so far relatively separate research areas related to artificial intelligence and logic: automated planning on the one hand, and dynamic logics of interaction on the other. There is significant overlap in motivation, theory and methods, and, we believe, a good potential for cross fertilization.
Automatic planning is a subarea of Artificial Intelligence that was initiated in the 70s. The main idea was to develop efficient methods to generate action plans, for example for robot missions. The initial attempts were based on first order logic. However, most approaches quickly adapted simpler logics and focused on search techniques. The recent years have brought a huge advance on scalability by employing smart search techniques such as heuristic search, SAT, BDDs, and other techniques. Currently, planning researchers explore widening the scope of planning tasks and to connect back to logic oriented approaches of describing dynamics such as GOLOG. At the same time, planning researchers strive to capture planning settings that are more challenging than the classical setting. For instance, planning under uncertainty and planning taking into account beliefs are current research topics.
The research area of dynamic logics of interaction is part of the larger field of applied and interactive logic: the use of logical methods in order to formalize procedures in social and communication contexts. The systems are typically based on the semantics of modal logic, and often focus on information (ex)change and the dynamics of knowledge and beliefs. Paradigmatic examples are public announcement logic and dynamic epistemic logic. One of the main technical features is the incorporation of agency and events into the modal framework as encapsulated by the notion of product update. Recently, some authors have proposed to use the ideas (or, more generally, the methodology) of dynamic approaches to logic for planning.
Epistemic goals, or more generally, goals that have to be expressed in some intensional language (epistemic, doxastic, deontic, others) have been discussed in several papers in the logic community, but are mostly absent from automatic planning. We think that the development of a research community dealing with these goals in planning will require a close interaction between the two involved communities. The seminar aims to initiate research working towards concrete goals, including but not limited to the following:
- developing a framework for planning formalisms for epistemic planning problems
- new logical formalisms for extended planning problems
- formalizing planning domains
- developing benchmarks
- restrictions that make DEL planning decidable
Automatic planning is a subarea of Artificial Intelligence that was initiated in the 70s. The main idea was to develop efficient methods to generate action plans, for example for robot missions. The initial attempts were based on first order logic. However, most approaches quickly adapted simpler logics and focused on search techniques. The recent years have brought a huge advance on scalability by employing smart search techniques such as heuristic search, SAT, BDDs, and other techniques. Currently, planning researchers explore widening the scope of planning tasks and to connect back to logic oriented approaches of describing dynamics such as GOLOG. At the same time, planning researchers strive to capture planning settings that are more challenging than the classical setting. For instance, planning under uncertainty and planning taking into account beliefs are current research topics.
The research area of dynamic logics of interaction is part of the larger field of applied and interactive logic: the use of logical methods in order to formalize procedures in social and communication contexts. The systems are typically based on the semantics of modal logic, and often focus on information (ex)change and the dynamics of knowledge and beliefs. Paradigmatic examples are public announcement logic and dynamic epistemic logic. One of the main technical features is the incorporation of agency and events into the modal framework as encapsulated by the notion of product update. Recently, some authors have proposed to use the ideas (or, more generally, the methodology) of dynamic approaches to logic for planning.
Epistemic goals, or more generally, goals that have to be expressed in some intensional language (epistemic, doxastic, deontic, others) have been discussed in several papers in the logic community, but are mostly absent from automatic planning. The development of a research community dealing with these goals in planning will require a close interaction between the two involved communities. The main goal of this workshop was to bring the two communities together and develop a vision of the mid-term goals of such a collaboration. In order to facilitate this, the organizers decided to arrange the workshop around work in four groups: after four tutorial lectures by Gerhard Lakemeyer, Hans van Ditmarsch, Thomas Bolander, and Hector Geffner on Monday, the participants were split up into four groups labelled APPL, BENCH, COMP, and LANG. Tuesday was largely reserved for work in the groups and for preparing the group reports included in this report. Tuesday evening also saw a concert in the Weisser Saal with Francois Schwarzentruber playing the piano and Hans van Ditmarsch playing the cello. The final day had some short presentations and a closing discussion.
For the four themes, the organizers had provided some guiding questions, but left the discussion open for the group participants:
- [APPL] Applying epistemic planning in the real world. Theme coordinator: Ron Petrick; group participants: Maduka Attamah, Christian Becker-Asano, Martin Holm Jensen, Benedikt L"owe, Sheila McIlraith, Leora Morgenstern, and Francois Schwarzentruber. Guiding questions: What are promising applications that will convince the outside world to use epistemic planning? Which areas outside of academia could be interested in epistemic planning? How do we get other academic disciplines (such as roboticists) interested in epistemic planning? Can we come up with a concrete research plan for such an application within the next three years?
- [BENCH] Establishing benchmarks and concrete goals for epistemic planning. Theme coordinator: Bernhard Nebel; group participants: Carmel Domshlak, Hector Geffner, Malte Helmert, Andreas Herzig, Jörg Hoffmann, Jérôme Lang, and Hans van Ditmarsch. Guiding questions: Can we come up with standardized problems to measure and compare systems for epistemic planning? Which standardized problems could help to calibrate the expressive power of epistemic planning formalism? What currently unsolved problems will serve as milestones and success criteria for the next three to five years?
- [COMP] Taming the complexity of epistemic planning. Theme coordinator: Thomas Bolander; group participants: Gerhard Lakemeyer, Yongmei Liu, Robert Mattmüller, Sunil Simon, Jan van Eijck, and Yanjing Wang. Guiding questions: Which aspects of epistemic planning are responsible for the increase of computational complexity? Are there fragments of epistemic planning that allow for an efficient implementation? Can we devise sufficiently expressive planning formalisms that still have acceptable complexity?
- [LANG] Finding adequate languages for epistemic planning. Theme coordinator: Thomas Agotnes; group participants: Guillaume Aucher, Mikkel Birkegaard Andersen, Jens Claßen, Tiago de Lima, Valentin Goranko, and Gabriele Röger. Guiding questions: Which formalisms are adequate to represent epistemic planning problems? Can we devise languages for epistemic planning that are intuitive to understand and use? Can we extend existing plan definition languages with epistemic features? Are the epistemic logics we have sufficiently expressive to serve as a basis for such planning formalisms?
In the final discussion, the participants discussed the immediate future of the interaction between the two fields. One idea was to edit a special issue of the journal Annals of Mathematics and Artificial Intelligence, and the seminar organisers are currently in negotiation with the journal editors about that. Thomas Bolander, Hans van Ditmarsch, Jan van Eijck, and R. Ramanujam are planning a follow-up meeting at the Lorentz Center in Leiden in the spring of 2015, and we hope to reconvene with many of the Dagstuhl participants at that meeting.
Creative Commons BY 3.0 Unported license
Thomas Agotnes, Gerhard Lakemeyer, Benedikt Löwe, and Bernhard Nebel
- Thomas Agotnes (University of Bergen, NO) [dblp]
- Maduka Attamah (University of Liverpool, GB) [dblp]
- Guillaume Aucher (INRIA Rennes - Bretagne Atlantique, FR) [dblp]
- Christian Becker-Asano (Universität Freiburg, DE) [dblp]
- Mikkel Birkegaard Andersen (Technical University of Denmark - Lyngby, DK) [dblp]
- Thomas Bolander (Technical University of Denmark - Lyngby, DK) [dblp]
- Jens Claßen (RWTH Aachen, DE) [dblp]
- Tiago de Lima (CNRS - Lens, FR) [dblp]
- Carmel Domshlak (Technion - Haifa, IL) [dblp]
- Hector Geffner (UPF - Barcelona, ES) [dblp]
- Valentin Goranko (Technical University of Denmark - Lyngby, DK) [dblp]
- Malte Helmert (Universität Basel, CH) [dblp]
- Andreas Herzig (Paul Sabatier University - Toulouse, FR) [dblp]
- Jörg Hoffmann (Universität des Saarlandes, DE) [dblp]
- Martin Holm Jensen (Technical University of Denmark - Lyngby, DK) [dblp]
- Gerhard Lakemeyer (RWTH Aachen, DE) [dblp]
- Jérôme Lang (University Paris-Dauphine, FR) [dblp]
- Yongmei Liu (Sun Yat-sen University - Guangzhou, CN) [dblp]
- Benedikt Löwe (University of Amsterdam, NL) [dblp]
- Robert Mattmüller (Universität Freiburg, DE) [dblp]
- Sheila McIlraith (University of Toronto, CA) [dblp]
- Leora Morgenstern (New York University, US) [dblp]
- Bernhard Nebel (Universität Freiburg, DE) [dblp]
- Ron Petrick (University of Edinburgh, GB) [dblp]
- Gabriele Röger (Universität Basel, CH) [dblp]
- Francois Schwarzentruber (IRISA - Rennes, FR) [dblp]
- Sunil Easaw Simon (Indian Institute of Technology - Kanpur, IN) [dblp]
- Hans Van Ditmarsch (LORIA - Nancy, FR) [dblp]
- Jan van Eijck (CWI - Amsterdam, NL) [dblp]
- Yanjing Wang (Beijing University - Beijing, CN) [dblp]
Related Seminars
- Dagstuhl Seminar 17231: Epistemic Planning (2017-06-05 - 2017-06-09) (Details)
Classification
- artificial intelligence / robotics
- semantics / formal methods
- verification / logic
Keywords
- Planning
- epistemic logic
- modal logic
