Plánování a hry

• Stránky předmětu: Plánování a hry
• Přednášející: Pěchouček, Domshlak
• Cvičící: L.Chrpa, Vokřínek J.

• více zde

Historie zadání

Tak co, jak vidite zkousku? Chapu to dobre tak, ze to teda bude akorat ustni zkouska s Pechouckem za 70% cely znamky? Ten prvni a posledni pokus..

75 minut času, ale nestíhali jsme to tak nám dal navíc půl hodiny.

4 příklady po 15 bodech

1. Formální definice STRIPS, definovat v něm problém přenášení kostek (pomocí propositions, není to to samé jako predikáty) a napsat plán co to vyřeší
2. Vypočítat h_max a h_add pro zadaný problém. Definovat admissible heuristiku. Jsou h_max a h_add admissible?
3. Co je to space search planning, nakreslit příklad grafu pro přenášení kostek a ukázat tam causal link, threat a contraint.
4. Napsat metody pro plánování robota v ohradě (něco jako Karel) v STN. Jak se to bude lišit v HTN?

Nakonec 5 krátkých otázek po dvou bodech: dominance heuristik, reactive planning, assignable job, atd.

1. otazky (pet otazek, uz si je moc nepamatuju, treba je dame dohromady)
   1. z jakych casti se sklada takovyten samoopravovaci planovac
2. nakopnete me.. co byla ta dvojka?
3. strips
   • vypocitat dostali jsme STRIPS zadani (tedy definovano vsechno: P,A,I,G) a meli spocitat h_max h_ff, urcit ktera z nich je admisivni a co to vlastne znamena
4. takovety stavove grafy (uloha balik se stavy {L,R,A,B}, auto A {L,R} a auto B {L,R}, mame definovany stavovy grafy pro balik a pro auto A)
   1. zmergovat dva grafy (kartezsky soucin uzlu a pak mezi nima natahate ty hrany presne jak byly v pudvonich grafech)
   2. shrinknout dva uzly dohromady (misto dvou kolecek nakreslite jedno s labelama obou puvodnich, hrany je treba pak spravne ohvezdickovat)
5. rozvrhovani (zadany ceny jobu a jejich posloupnost)
   1. najdete kritickou cestu (proste sestavit graf podle naslednostii, najit nejdelsi ze vsech paralelnich vetvi)
   2. jak dlouho to bude trvat pro nekonecno procesoru (cena kriticke cesty)
   3. jak dlouho pro jeden (soucet vsech cen)

20% semestralka, 80% ustni zkouska

Okruhy jsou zde (a na strankach), pokud se vam bude chtit, muzem to zkusit vyplnovat pri procitani slidu

Okruhy ke zkoušce

1. Úvod do automatizovaného plánování
   • plánovací problém, jeho varianty
   • explicit deliberation process that chooses and organizes actions by anticipating their outcomes
   • aims at achieving some pre-stated objectives
   • AI planning: computational study of this deliberation process
   • plánovací systém, řídící systém a prostředí
   • rozdíl mezi plánováním a rozvrhováním
   • typy plánovačů s ohledem na doménovou závislost
   • splnitelnost a složitost plánovacího problému
2. metody reprezentace plánování
   • klasický stavový model,
   • SAS a STRIPS
   • PDDL
   • lineární a nelineární plán (total, partial order plan)
   • relaxace plánovacího problému a požití heuristik při plánování
   • reprezentace pomocí plánovacího grafu
   • reprezentace pomocí HTN a STN
3. plánovače
   • plánovač v prostoru stavů
   • plánovač v prostoru plánů (POP, POCL algoritmy), kauzální linka, ohrožení
   • plánovač založený na CSP
   • plánovač založený na SAT
   • GRAPHPLAN
   • Partial ordered STN (PFD) a jeho zobecnění na TFD
4. logika
   • LTL
   • modální logika - operátory box, diamond, next, untill
5. teorie her
   • dvouhráčové hry
   • algoritmy pro dvouhráčové hry
   • Nashovo equilibrium
   • Pareto-optimalita

gl