The Dynamic Logic of Policies and Contingent Planning

Thomas Bolander, Thorsten Engesser, Andreas Herzig, Robert Mattmüller, Bernhard Nebel

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

16 Downloads (Pure)


In classical deterministic planning, solutions to planning tasks are simply sequences of actions, but that is not sufficient for contingent plans in non-deterministic environments. Contingent plans are often expressed through policies that map states to actions. An alternative is to specify contingent plans as programs, e.g. in the syntax of Propositional Dynamic Logic (PDL). PDL is a logic for reasoning about programs with sequential composition, test and non-deterministic choice. However, as we show in the paper, none of the existing PDL modalities directly captures the notion of a solution to a planning task under non-determinism. We add a new modality to star-free PDL correctly capturing this notion. We prove the appropriateness of the new modality by showing how to translate back and forth between policies and PDL programs under the new modality. More precisely, we show how a policy solution to a planning task gives rise to a program solution expressed via the new modality, and vice versa. We also provide an axiomatisation of our PDL extension through reduction axioms into standard star-free PDL.
Original languageEnglish
Title of host publicationProceedings of European Conference on Logics in Artificial Intelligence
Publication date2019
ISBN (Print)9783030195694
Publication statusPublished - 2019
EventEuropean Conference on Logics in Artificial Intelligence - University of Calabria , Rende, Italy
Duration: 7 May 201911 May 2019


ConferenceEuropean Conference on Logics in Artificial Intelligence
LocationUniversity of Calabria
SeriesLecture Notes in Computer Science

Fingerprint Dive into the research topics of 'The Dynamic Logic of Policies and Contingent Planning'. Together they form a unique fingerprint.

Cite this