Planning for Artificial Intelligence

• Stránky předmětu: Planning for Artificial Intelligence
• Přednášející: Antonín Komenda, Bronislav Bošanský, Lukáš Chrpa, Michal Štolba
• Cvičící: Daniel Fišer, Jan Mrkos

• více zde

Historie zadání

1. Relaxation (LM-cut) (12 bodu), zadaný STRIPS včetně cost jednotlivých akcí
   • spočítat hMax(Δ0) pro všechny akce a stavy
   • nakreslit justification graph
   • určit landmarku a její cost
   • aktualizovat cost vektor akcí
   • napsat zdali h_lmcut je vždy admissible (já jsem tam tohle teda neměl)
2. Abstraction (Merge and Shrink) (12 bodu), zadany FDR (v1 = {A,B}, v2 = {C,D,E}, a1 = {v1=A —> v1=B},a2={v1=A,v2=C —> v1=2,v2=D},a3,a4)
   • spočítat atomické projekce (tj. jedna na v1 a druhá na v2)
   • provést Merge těchto projekcí (= původní problém)
   • provést libovolný Shrink na 4 stavy
   • jaká je nyní hodnota h_ms pro počáteční stav?
   • je h_ms vždy admissible?
3. MCTS
   • popsat 4 základní kroky MC algoritmu (3 body)
   • spočítat tři iterace na zadaném stromě (9 bodu)
4. MDP
   • spočítat policy iteration (2 iterace) pro robota (takový ten 80% jde daným směrem, 10% se odchýlí, zlato, past..) (12 bodu)
5. Otázky (6 otázek po 2 bodech):
   • definovat optimal heuristic, admissible heuristic, consistent heuristic, safe heuristic, goal-aware heuristic
   • převést PDDL do tvaru bez podmínek
   • co je potential heuristics? jak se spocita?
   • něco s multiagentním plánováním (základní princip + kdy si posílají agenti stavy?)
   • POMDP, definovat omega funkci (omega: AxOxC → [0,1])
   • co je to mutex group? v cem je dobra?

5 hlavních otázek většinou po 12 bodech, poslední za dva body za otázku

1. zadaný STRIPS
   • nakreslit RPG
   • spočítat hFF
   • je hFF admissible + důkaz
   • myslím že tu byl ještě jeden bod.. někdo?
2. Relaxace : zadaný STRIPS včetně cost jednotlivých akcí
   • spočítat hMax(s0) pro všechny akce a stavy
   • nakreslit Justification graph
   • určit landmarku a její cost
   • aktualizovat cost vektor
   • obecně definovat admissible heuristiku
3. RRT
   • popsat, jak by se našla nejkratší cesta v prostředí s polygon obstacles
   • na obrázku nakreslit, jak by vypadal RRT pro 5 zadaných bodů (otázka stejná jak z fotky 5.6.2013, jen body jinak očíslované a za 12b celkem)
4. MCTS
   • popsat 4 základní kroky MC algoritmu
   • spočítat tři iterace na zadaném stromě
5. MDP
   • spočítat celou policy iteration pro robota (takový ten 80% jde daným směrem, 10% se odchýlí, zlato, past..)
6. Otázky:
   • ?
   • převést metodu z PDDL do čistého STRIPS (v PDDL byly podmínky)
   • Vehicle Trajectory Prediction - dávali bod zdarma (ze dvou a pouze nad 30 celkem), neučilo se to
   • POMDP
   • spočítat nějakou omega funkci

1. STRIPS
   1. Co je to regresní úloha a jak souvisí s backward algoritmem
   2. BlockWorld Problem (pozor na správné použití výroků, nikoliv predikátů)
2. TEORIE
   1. Jaký je rozdíl mezi relaxací a abstrakcí
   2. Jak poznáme, že Graphplan nemá řešení
   3. Co jsou to hry s nulovým součtem a uvést dva příklady takových her
   4. Uvést alespoň dvě roadmap metody vyjma Visibility Graph
3. RELAXACE
   1. Spočítat h_max a h_FF
   2. Co je to přípustná heuristika a rozhodnout, zdali jsou h_max a h_FF přípustné
4. STN/HTN
   1. Navrhnout v STN metody pro Karla (jednu též v HTN) a nakreslit hierarchický strom (nezapomenout na ukončovací metodu s prázdným listem podúloh)
   2. Rozdíl mezi STN a HTN
5. TRAJEKTORIÁLNÍ PLÁNOVÁNÍ
   1. Do tří obrázků s překážkou nakreslit Visibility Graph, Voronoi Diagram a Probabilistic Roadmap

1. Zadana PDDL domena a problem, v jakem stavu bude system po vykonani zadaneho planu? (3 akce)
2. Block world zapsat v PROPOSITIONAL jazyce (tedy vyrokovem, tedy vlastne BDR, booleanovske promenne za kazdou moznou pozici kazde kostky), konkretne poc. stav, konc. stav, vyresit (najit plan) z poc. stavu do ciloveho a napsat definice akci, ktere sme v tom planu nasli
3. Zadana domena a akce ve vyrokove logice, spocitat h_add a h_max, jsou admissible, co znamena admissible
4. Zadane dve atomicke projekce (2 trucks (A,B), 1 package, 2 locations(L,R)). Udelejte merge (synchronized product). Zmergujte 2 stavy
5. V STN (jednodussi hierarchicky planovani) definvat akce a vyresit problem robota Karla (nekde na wiki je neco podobneho). Jak by se lisila a zapiste jednu (vhodnou) akci v HTN (nejsou preconditions, jsou jen constraints)
6. 4 male otazky (za 2-3 body)
   1. co je to Visibility graph, co nebo kde jsou uzly a kde hrany (nezapomente na pridani startu a cile)
   2. jak definujete hledani planu jako prohledavani stavoveho prostoru (nebo nejak podobne to bylo), co jsou uzly a co a kde jsou hrany
   3. jaky vyznam maji alfa a beta v Alfa-beta algoritmu
   4. jak se zkonstruuje graf v Graphplanu

Ustni od 13h, zkousel Vokrinek

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. dalsi 2 roadmap techniky krome visibility graphu
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

POMDP for dummies - skvělý tutorial na POMDP (jen doporučuji v prohlížeči zapnout Reader mode, jinak se to nedá číst :D )