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. popsat visibility graph
   3. co je to unární zdroj
   4. co je alfa a beta v MiniMaxu
2. strips - svět tří kostek K, L, M a stolu
   • aximatizovat pomocí výroků, které budou potřeba a popsat je (onKL, onKM, onKT, …, cleanK, cleanL, cleanM)
   • byl dán obrázek ukazující počátení a koncový stav - pomocí výroků ze shora popsat počáteční a koncový stav
   • napsat plán, který řeší úlohu
   • definovat použité akce (např moveKLT (vezmi kostku K ležící na L a dej ji na T) - precond. : onKL, clearK,eff+ onKT, clearL, eff- onKL)
   • + teoretická otázka, popsat regresní plánování
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)

1. male otazky po dvou bodech
   1. bude plan z preplanovani optimalni pokud je planovac optimalni?
   2. alfabeta prorezavani vzdy prohleda mensi prostor nez minimax?
   3. co je to kriticka cesta v schedulingu?
   4. definice planovaciho grafu
   5. jeste neco
2. svet kostek, propositional, definovat logicke promenne, akce, napsat plan
3. spocitat h_add a h_ff, napsat jestli jsou admissible
4. POP algoritmus na problem vlk,koza,zeli, demonstrovat kauzalni linku, hrozbu, ordering constraing
5. abstrakce, 3 lokace, 2 baliky, 1 truck

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