Planning for Artificial Intelligence
Cvičení
Zkouška
1. 6. 2018
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)
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?
MCTS
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)
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?
6. 6. 2016
5 hlavních otázek většinou po 12 bodech, poslední za dva body za otázku
zadaný STRIPS
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
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)
MCTS
MDP
spočítat celou policy iteration pro robota (takový ten 80% jde daným směrem, 10% se odchýlí, zlato, past..)
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
19. 6. 2013
STRIPS
Co je to regresní úloha a jak souvisí s backward algoritmem
BlockWorld Problem (pozor na správné použití výroků, nikoliv predikátů)
TEORIE
Jaký je rozdíl mezi relaxací a abstrakcí
Jak poznáme, že Graphplan nemá řešení
Co jsou to hry s nulovým součtem a uvést dva příklady takových her
Uvést alespoň dvě roadmap metody vyjma Visibility Graph
RELAXACE
Spočítat hmax a hFF
Co je to přípustná heuristika a rozhodnout, zdali jsou hmax a hFF přípustné
STN/HTN
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)
Rozdíl mezi STN a HTN
TRAJEKTORIÁLNÍ PLÁNOVÁNÍ
Do tří obrázků s překážkou nakreslit Visibility Graph, Voronoi Diagram a Probabilistic Roadmap
5.6.2013
26.5.2013
Zadana PDDL domena a problem, v jakem stavu bude system po vykonani zadaneho planu? (3 akce)
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
Zadana domena a akce ve vyrokove logice, spocitat h_add a h_max, jsou admissible, co znamena admissible
Zadane dve atomicke projekce (2 trucks (A,B), 1 package, 2 locations(L,R)). Udelejte merge (synchronized product). Zmergujte 2 stavy
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)
4 male otazky (za 2-3 body)
co je to Visibility graph, co nebo kde jsou uzly a kde hrany (nezapomente na pridani startu a cile)
jak definujete hledani planu jako prohledavani stavoveho prostoru (nebo nejak podobne to bylo), co jsou uzly a co a kde jsou hrany
jaky vyznam maji alfa a beta v Alfa-beta algoritmu
jak se zkonstruuje graf v Graphplanu
Ustni od 13h, zkousel Vokrinek
2012
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..
31.5.2012
75 minut času, ale nestíhali jsme to tak nám dal navíc půl hodiny.
4 příklady po 15 bodech
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ší
Vypočítat h_max a h_add pro zadaný problém. Definovat admissible heuristiku. Jsou h_max a h_add admissible?
Co je to space search planning, nakreslit příklad grafu pro přenášení kostek a ukázat tam causal link, threat a contraint.
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.
11.6.2012
otazky (pet otazek, uz si je moc nepamatuju, treba je dame dohromady)
z jakych casti se sklada takovyten samoopravovaci planovac
popsat visibility graph
co je to unární zdroj
co je alfa a beta v MiniMaxu
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í
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
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)
zmergovat dva grafy (kartezsky soucin uzlu a pak mezi nima natahate ty hrany presne jak byly v pudvonich grafech)
shrinknout dva uzly dohromady (misto dvou kolecek nakreslite jedno s labelama obou puvodnich, hrany je treba pak spravne ohvezdickovat)
rozvrhovani (zadany ceny jobu a jejich posloupnost)
najdete kritickou cestu (proste sestavit graf podle naslednostii, najit nejdelsi ze vsech paralelnich vetvi)
jak dlouho to bude trvat pro nekonecno procesoru (cena kriticke cesty)
jak dlouho pro jeden (soucet vsech cen)
20.6.2012
male otazky po dvou bodech
bude plan z preplanovani optimalni pokud je planovac optimalni?
alfabeta prorezavani vzdy prohleda mensi prostor nez minimax?
co je to kriticka cesta v schedulingu?
definice planovaciho grafu
dalsi 2 roadmap techniky krome visibility graphu
svet kostek, propositional, definovat logicke promenne, akce, napsat plan
spocitat h_add a h_ff, napsat jestli jsou admissible
POP algoritmus na problem vlk,koza,zeli, demonstrovat kauzalni linku, hrozbu, ordering constraing
abstrakce, 3 lokace, 2 baliky, 1 truck
2011
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
Ú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
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
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
logika
teorie her
gl
Studijní materiály
POMDP for dummies - skvělý tutorial na POMDP (jen doporučuji v prohlížeči zapnout Reader mode, jinak se to nedá číst :D )
Nahoru