Plánování a rozvrhování / Planning and Scheduling
NAIL071, 2/0 Zk, letní semestr

Roman Barták, KTIML


Zdroje  |  Přednáška  |  Zkouška  |  Kontakt

Plánování je rozumovou složkou konání. Jeho cílem je vybrat a uspořádat akce tak, aby se co nejlépe dosáhlo vytyčeného cíle. Rovrhování se potom stará o optimální realizaci plánu v prostředí s omezenými zdroji a časem.


Zdroje:

Přednáška je připravena převážně podle knihy M. Ghallab, D. Nau, P. Traverso: Automated Planning: Theory and Practice, Morgan Kaufmann, 2004. Materiály ke knize jsou dostupné na webu.

Některé pasáže jsou podrobněji zpracovány v anglických tutoriálech:

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

Další informace lze čerpat ze stránek sítě excelence PLANET, konferencí ICAPS a MISTA.


Přednáška (LS 2019/2020):
pondělí 15:40 - 17:10, posluchárna S5 (Malá Strana, 2. patro)
Monday 15:40 - 17:10, lecture hall S5 (Malá Strana, 2nd floor)

The course can be given in Czech (default) or in English. In case you want to have the course in English, please contact the lecturer prior the first lecture.

Due to COVID-19 decease, oral lectures are temporally suspended. Students are advised to self-study from the slides that are availabe on this web. Each lecture is accompanied by a set of quiz questions to highlight some important or hidden aspects of the topic and I strongly suggest going through them. Students can contact me via e-mail in case of any question. We now use Microsoft Teams as an on-line communication forum to discuss the course topics, you can enroll here.

A preliminary schedule.

    lecture quiz
17. 02. 2020

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

pdf
24. 02. 2020

Formalisation of planning problems. Set and classical representations.

02. 03. 2020

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

09. 03. 2020

Plan space planning (partial order planning).

16. 03. 2020 Neoclassical planning. Planning graph, Graphplan.

23. 03. 2020

Compilation of planning to SAT and to CSP.

30. 03. 2020 Modelling time (point algebra, interval algebra, temporal networks).[video][tutorial]
06. 04. 2020 Planning with time and resources.
13. 04. 2020 Easter holidays
 

20. 04. 2020

Planning heuristics, control rules, hierarchical task networks.
27. 04. 2020 Classical scheduling approaches. Scheduling problems with a single resource and parallel resources, shop scheduling.
04. 05. 2020 Constraint-based scheduling. Global constraints for scheduling problems, scheduling strategies.[video]
11. 05. 2020 TBA
 
18. 05. 2020 TBA
 
  Planning in Games (Martin Černý)
 

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

Zkouška / Exam:

Zkoušena bude látka probraná na přednášce, podrobnosti a termíny budou vypsány před zkouškovým obdobím. Na zkoušku se zapisuje prostřednictvím Studijního informačního systému.

Students register to exams (select the exam date) via Student Information System. Each student will be given one question/topic based on what has been covered by lectures. The student will have 30 minutes to write the answer/solution and then 15 minutes to (orally) defend the answer. The schedule of exams (exact times) will be sent to students the day before the exam so check your e-mail. Be at the assigned location 10-15 minutes before your term. Students can answer in Czech/Slovak or English depending on their own choice.

The exam dates will be in June, July, and September. Do not wait till last moment as later exam dates might be full. We will follow hygienic restrictions as required at the date of exam.


Kontakt:
 

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

V případě potřeby je možné domluvit individuální konzultace k přednášce, případně témata projektů, bakalářských či diplomových prací vycházejících z témat přednášky.

Samozřejmě veškeré komentáře k přednášce, hlášení chyb, nejasných pasáží apod. jsou vítány.