Automated Planning:
Theory and Practice

COURSE OBJECTIVES AND LEARNING OUTCOMES

Planning and Scheduling is the task of thinking before you act: use knowledge about the world to determine what and when to do an action to achieve a given goal. Automated planning and scheduling is a central topic in Artificial Intelligence (AI), and task and motion planning capabilities are essential to the construction of many robust autonomous systems. Research in planning and scheduling is active and exciting. Planning and scheduling problems have been tackled with a variety of new approaches to address efficiency, expressivity, and practical applicability. Planning and scheduling technologies are currently used with great success in several real applications ranging from production lines and elevators to unmanned aerial and sub-sea vehicles (UAVs) and space applications. The aim of this course is to provide a comprehensive theoretical view of a wide range of planning and scheduling techniques, as well as hands-on experience in constructing and modeling planning domains to solve specific planning problems, and if time allows to experiment the control of robotic agents.

After the course, the student will be able to:

• Evaluate and apply a variety of planning techniques and tools for classical planning and scheduling as well as planning and scheduling under different kind uncertainty (temporal and discrete).

• Explain the practical advantages and disadvantages of different levels of expressivity in planning and scheduling models.

• Model classical planning and scheduling problems in commonly used domain definition languages (e.g. PDDL), and if time allows, we will consider probabilistic planning problems as well.

• Evaluate and apply common techniques for goal-directed planning, such as various forms of heuristics and control rules.

• Experiment with realistic robotic agents (depending on time and availability of the robotic agents in the Robotic Lab or through simulations within ROS infrastructure).

If time allows, explain the commonly used path and motion planning techniques.

REQUIREMENTS

Basic knowledge and understanding of data structures and algorithms as well as propositional logic and satisfiability and discrete mathematics. Knowledge and understanding of basic artificial intelligence techniques and concepts, including state-space search, heuristics, and the A* search algorithm.

CONTENTS

• Introduction to planning and scheduling

• The classical planning paradigm

• Algorithms for classical and neo-classical planning

• Planning with time and resource constraints

• Planning and scheduling with rich domain knowledge

• Planning and scheduling under uncertainty

• Planning and Scheduling problem description languages (E.g. PDDL, …)

• Introduction to ROSPlan//PlanSys2 - ROS2 Planning System infrastructure

• Optional: Path planning and motion planning

TEACHING AND LEARNING METHODS AND ACTIVITIES

A series of frontal lectures to introduce the theory behind planning and scheduling as well as many practically useful techniques for plan generation and plan verification under varying assumptions about the environment.

A set of laboratory exercises provide hands-on experience using several state-of-the-art planning and scheduling paradigms and planning and scheduling systems and tools. In addition to developing domain models for a set of interesting planning problems, participants will explore how different heuristics and approaches can be used to improve plan quality as well as performance.

If time allow and if the Robotic lab will be fully operative, it will also be possible to practically interact with robotic platforms, or with robotic simulators through ROS framework.

TEST AND ASSESSMENT CRITERIA

• Written and possible oral exam (2/3)

• Practical work in the lab (1/3)

• It will be considered, as alternative to the written exam, also the possibility to perform a small project to be performed alone or in group possibly using the Robotic Lab/Robotic Simulators within ROS and/or existing open source planners.

BIBLIOGRAPHY

• Malik Ghallab, Dana S. Nau, Paolo Traverso: Automated Planning and Acting. Cambridge University Press 2016, ISBN 978-1-107-03727-4

• Malik Ghallab, Dana S. Nau, Paolo Traverso: Automated planning - theory and practice. Elsevier 2004, ISBN 978-1-55860-856-6, pp. I-XXVIII, 1-635

• Hector Geffner, Blai Bonet: A Concise Introduction to Models and Methods for Automated Planning. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers 2013, ISBN 9781608459698, pp. 1-141

• Patrik Haslum, Nir Lipovetzky, Daniele Magazzeni, Christian Muise: An Introduction to the Planning Domain Definition Language. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers 2019

WIP