Toto je starší verze dokumentu!
Plánování a hry
Cvičení
Zkouška
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
Nahoru