2nd Semester 2021/22: Automated Planning with Temporal Logic Goals

Instructors

Gregor Behnke

ECTS

6

Description

Planning asks to find a sequence of actions that will lead to achieving a given objective. Traditionally, this means that we are given an initial state (in terms of facts over some function-free first-order logic), (first-order) actions that can modify the state, and a goal state, i.e. a set of facts that we want to achieve simultaneously. For most algorithmic purposes, this first-order description is usually flattened (grounded) into a purely propositional representation.

In some scenarios the simple definition of the objective as a single goal state does not suffice. For example, we might want to describe that we shall first achieve objective A and only afterwards B, or that we want to achieve A without ever achieving B in the mean time. Further one might also want to describe infinite behaviour, i.e., a plan for running a factory machine indefinitely.

For this purpose, the description of the objective can be formulated using Temporal Logic, which can be viewed as an instantiation of Modal Logic. In this project, we will study planning problems with such "Temporally Extended Goals". The main focus will be on algorithmic questions, i.e. how to find plans when given such goal descriptions.

I will start with a few introductory lectures on planning, temporal logic, and techniques for solving planning problems. Students will choose research papers (a list of possible options will be provided) and present them orally in the project's last week. In addition students will model example problems using Temporally Extended Goals and if possible run available planners on them.

Organisation

Week 1:
3 lectures (Introduction to planning and Temporal Logic)

Week 2:
3 lectures (Algorithmics of Temporal Logic and Planning)

Week 3:
Individual consultation (on-demand)

Week 4:
Presentations, to be scheduled at the end of week 2.

Prerequisites

Familiarity with first-order logic and automata.
Familiarity with modal logic might be helpful.
No prior knowledge of planning or temporal logic is required.

Assessment

Oral presentation (week 4), modelled planning problem(s), attendance in the lectures.

References

For Planning in general:
Nau, Ghallab, Traverso: Automated Planning: Theory and Practice. Morgan Kaufmann, 2004
Haslum, Lipovetzky, Magazzeni, Muise: An Introduction to the Planning Domain Definition Language. Morgan & Claypool, 2019

Examples for Planning with temporally extended goals:
Planning for temporally extended goals Fahiem Bacchus / Froduald Kabanza, Annals of Mathematics and Artificial Intelligence 22 (1998) 5–27
Automata-Theoretic Approach to Planning for Temporally Extended Goals, Giuseppe De Giacomo / Moshe Y. Vardi , ECP 1999
Planning with First-Order Temporally Extended Goals Using Heuristic Search, Jorge A. Baier / Sheila A. McIlraith, AAAI 2006