Plánování a rozvrhování / Planning and Scheduling
NAIL071, 2/0 Ex, summer semester

Roman Barták, KTIML


Resources  |  Lectures  |  Exam  |  Contact

Planning is the reasoning part of acting. It deals with selecting and organizing actions to achieve a given goal. Scheduling then decides about (optimal) allocation of given actions to limited time and resources.


Resources:

The course (its planning part) is based on the book M. Ghallab, D. Nau, P. Traverso: Automated Planning: Theory and Practice, Morgan Kaufmann, 2004. Some resources for the book are availabe on web.

Parts of the course (mostly its scheduling part) are available with even more details at some conference tutorials:

  • Constraint Satisfaction for Planning and Scheduling [WWW], ICAPS 2004
  • Filtering Techniques in Planning and Scheduling [slides], ICAPS 2006
  • Constraint-based Temporal Reasoning [WWW], ICAPS 2014/AAAI 2015

Additional (up-to-date) information can also be found at conferences ICAPS and MISTA.


Lectures (summer semester 2023/2024):
Tuesday 09:00 - 10:30, lecture hall S3 (Malá Strana, 3rd floor)

The course can be given in Czech or in English (default). The languge wil be decided a  the first lecture.

A preliminary schedule.

       
Date Topic
lecture
quiz
20. 02. 2024

Introduction to planning and scheduling, examples of applications. Summary of basic solving techniques (search algorithms, CSP, SAT).

pdf

Formalisation of planning problems. Set and classical representations.

27. 02. 2024

Cancelled due to foreign trip

05. 03. 2024

State space planning (forward, backward, lifting, STRIPS).

12. 03. 2024 Plan space planning (partial order planning).
19. 03. 2024

Neoclassical planning. Planning graph, Graphplan.

26. 03. 2024

Compilation of planning to SAT and to CSP.
02. 04. 2024

Modelling time (point algebra, interval algebra, temporal networks).[video][tutorial]

09. 04. 2024 Planning with time and resources.

16. 04. 2024

Planning heuristics, control rules, hierarchical task networks.
23. 04. 2024

Classical scheduling approaches. Scheduling problems with a single resource and parallel resources, shop scheduling.

30. 04. 2024

Constraint-based scheduling. Global constraints for scheduling problems, scheduling strategies.[video]

07. 05. 2024 Cancelled due to foreign trip
14. 05. 2024 Cancelled due to rector's day 
 
21. 05. 2024 Cancelled due to foreign trip
  Planning in Games (Martin Černý) - additional material on applications 
 

Slajdy v českém jazyce.

Úvod, plánovací vs. rozvrhovací problém, ukázky aplikací. Obecné prohledávací algoritmy, omezující podmínky a SAT.

Formalizace plánovacího problému. Množinová a klasická reprezentace.

Plánování se stavovým prostorem (dopředné, zpětné, STRIPS).

Plánovaní s prostorem plánů.

Neoklasické plánování. Plánovací graf, Graphplan.
Plánování jako SAT. Plánování jako CSP.
Modely času (algebra okamžiků, algebra intervalů, temporální sítě).
Plánování s časem a se zdroji.
Plánovací heuristiky a řídící pravidla.
Klasické rozvrhovací problémy a řešící techniky. Problémy s jedním zdrojem a paralelními zdroji, multi-operační rozvrhování.
Rozvrhování jako splňování omezujících podmínek. Globální podmínky pro rozvrhování a rozvrhovací strategie.[video]
Plánování v praxi (Martin Černý)
Úpravy přednášky v letech 2011/12 a 2012/13 byly částečně podpořeny projektem CZ.2.17/3.1.00/33274, který je financován Evropským sociálním fondem a rozpočtem hlavního města Prahy.
logo
Evropský sociální fond
Praha & EU: Investujeme do vaší budoucnosti

Exam:

Students register to exams (select the examination date) via Student Information System. Exams will be in person, but on-line exam is possible in special situations and upon prior request. Each student will be given one question/topic based on what has been covered by lectures. The student will have 15 minutes to write the answer/solution and then 15 minutes to (orally) defend the answer. Be at the assigned location 10-15 minutes before your term. Students can answer in Czech/Slovak or English depending on their own choice.


Contact:
 

prof. RNDr. Roman Barták, Ph.D.

Katedra teoretické informatiky a matematické logiky
Matematicko-fyzikální fakulta Univerzity Karlovy

Malostranské nám. 2/25, 118 00 Praha 1
Czech Republic

e-mail: bartak (AT) ktiml.mff.cuni.cz
tel: +420 951 554 242

If you need consultancy regarding the course topic or you are interested in doing your bachelor, master, or PhD thesis in the areas of planning and scheduling, contact me by e-mail.

Also, if you have any comment about the course, specifically, if you find any bugs or issues, contact me as well.