Automated Planning Tools for Intelligent Decision Making (2021)
Section outline
-
Welcome to Automated Planning Tools for Intelligent Decision Making (2021)
Description: Planning deals with intelligent decision making to decide which actions to perform and how to schedule them during execution. This includes a broad class of problems that has all kinds of applications in different fields. Some examples include scheduling jobs in factory control, finding sequences of chemistry reactions, discourse planning in natural language generation, finding weaknesses in network security, etc. Despite these applications look completely different from each other, they can be solved with general planning tools that anyone can apply to their own problems.This course introduces several planning tools to a broad audience so that in the future experts on different areas can apply them in their own field of expertise. We cover three different perspectives: AI planning, model checking, and operational research.
Students will learn the basics of how each area models planning problems. There will be hands-on sessions where students will familiarize themselves with the tools and will apply them to solve some exercises, possibly related to their own areas.
Organizer: Associate Professor Alvaro Torralba - alto@cs.aau.dk
Lecturers: Assistant Professor Peter Gjøl Jensen - pgj@cs.aau.dk, Professor Kim Guldstrand Larsen - kgl@cs.aau.dk, Assistant Professor Inkyung Sung - inkyung_sung@mp.aau.dk, Associate Professor Alvaro Torralba - alto@cs.aau.dk, Peter Nielsen
ECTS: 3.0
Time: April 29 and May 4, 6, 11, 20, and 25 (to be confirmed).
Place: Aalborg University
Zip code: 9220
City: Aalborg
Number of seats: 50 - There are still available seats. Send a mail to chvass@adm.aau.dk if you wish to be enrolled.
Deadline: 06 April 2021
Link to Teams group
Important information concerning PhD courses: We have over some time experienced problems with no-show for both project and general courses. It has now reached a point where we are forced to take action. Therefore, the Doctoral School has decided to introduce a no-show fee of DKK 3.000 for each course where the student does not show up. Cancellations are accepted no later than 2 weeks before start of the course. Registered illness is of course an acceptable reason for not showing up on those days. Furthermore, all courses open for registration approximately four months before start. This can hopefully also provide new students a chance to register for courses during the year. We look forward to your registrations. -
Lecture 1 (April 29)
Planning using UPPAAL, UPPAAL CORA and UPPAAL TIGA
Lectures: Peter Gjøl Jensen, Kim G Larsen- Timed automata and time-optimal plans (reachability). Zones.
- Priced timed automata and cost-optimal and time-constrained plans (reachability). Priced Zones.
- Optimal infinite plans (optimal cost/time in the limit).
- Timed games and adaptive plans (reachability or safety strategies).
- Survey of applications
Reading Material
- Frits Vaandrager: A first introduction to UPPAAL (unpublished note form Quasimodo project)
- Alexandre David, Kim G Larsen: More features in UPPAAL (unpublished note from Quasimodo project)
- Johan Bengtsson, Wang Yi: Timed Automata: Semantics, Algorithms and Tools (if you want to know about the underlying zone algorithms)
- Patricia Bouyer, Uli Fahrenberg, Kim G Larsen, Nicolas Markey: Quantitative Analysis of Real-Time Systems Using Priced Timed Automata. Commun. ACM 54(9): 78-87 (2011)
- Gerd Behrmann, Kim G Larsen, Jakob Illum Rasmussen: Optimal scheduling using priced timed automata. SIGMETRICS Performance Evaluation Review 32(4): 34-40 (2005)
- Franck Cassez, Kim Larsen, Jean-Francois Raskin, and Pierre-Alain Reynier: An Introduction to Automatic Synthesis of Discrete and Timed Controllers (unpublished note from Quasimodo project)
Introductory Videos
- UPPAAL: Basic Usage (Microsoft Stream, Marius Mikucionis)
- Introduction to UPPAAL (Microsoft Stream, Kenneth Yrke Jørgensen)
- The Viking Problem in UPPAAL (Microsoft Stream, Kenneth Yrke Jørgensen)
Please install UPPAAL 4.1.24 on your laptop before lecture (see www.uppaal.org). We will need it during the exercises.
Slides
- Timed Automata and Time-Optimal Planning
- Priced Timed Automata and Cost-Optimal Planning
- Timed Games and Adaptive Planning. Applications.
Exercises
- Collection of Exercises that we will point to
- Model Checking (optional)
- Planning (mandatory)
- 28 (Jobshop Scheduling) full solution can be found here.
- Exercise 22 (Crossing River) OR Exercise 21 (Rush Hour) -- homework for Lecture 2.
Lecture 2 (May 4)
Planning using UPPAAL SMC & UPPAAL Stratego
Lectures: Peter Gjøl Jensen, Kim G Larsen- Stochastic Priced Timed Automata and performance evaluation of plans.
- Statistical model checking.
- Stochastic Priced Timed Games and expected cost-optimal adaptive plans (strategies)
- Reinforcement (Q-, M-, ..) learning.
- Strategy representaiton.
- ..
READING Material
Slides
Exercises
- See slides
-
-
-
-
-Julia Tutorial for integer programming formulation
Please test first if you can make a formulation for the target problem (described in the attached Pluto notebook "ip tutorial.jl") as an integer program.
This includes 1) to define decision variables for the problem, 2) to represent an objective function as a linear function of the decision variables defined, and 3) to formulate constraints of the problem also as linear functions of the decision variables.
With the understanding or questions on the solution, please review the attached file, coded using the JuMP package in Julia. Note that to run the file, you need to run Julia and Pluto first (check the video uploaded), and please open the file from the web-browser page where Pluto is running.
-
Julia tutorial
-
-
-
-
-
-
-
Lecturer: Alvaro Torralba (alto@cs.aau.dk)
Lecture 1 (May 20, 12:30 - 16:15):
- Introduction to AI Planning
- Classical Planning: STRIPS models
- Planning Domain Definition Language (PDDL)
- Classical Planning Tools
Lecture 2 (May 25, 12:30 - 16:15):
- Open Discussion
- Classical Planners
- Non-classical Planning Tools
-
-
-
-
-
-