====== Planning for Artificial Intelligence ====== * Stránky předmětu: [[https://cw.fel.cvut.cz/wiki/courses/pui/start|Planning for Artificial Intelligence]] * Přednášející: [[http://cs.fel.cvut.cz/en/people/komenant/|Antonín Komenda]], [[http://cs.fel.cvut.cz/en/people/bosanbra/|Bronislav Bošanský]], [[http://cs.felk.cvut.cz/en/people/chrpaluk/|Lukáš Chrpa]], [[http://cs.felk.cvut.cz/en/people/stolbmic/|Michal Štolba]] * Cvičící: [[http://cs.fel.cvut.cz/en/people/fiserdan/|Daniel Fišer]], [[http://cs.felk.cvut.cz/en/people/mrkosja1/|Jan Mrkos]] ===== Cvičení ===== * více [[courses/a4m33pah/cviceni|zde]] ===== Zkouška ===== [[courses/a4m33pah/zkousky|Historie zadání]] ==== 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 * popsat 4 základní kroky MC algoritmu (3 body) * spočítat tři iterace na zadaném stromě (9 bodu) - 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 * nakreslit RPG * spočítat hFF * je hFF admissible + důkaz * myslím že tu byl ještě jeden bod.. někdo? - 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 * popsat 4 základní kroky MC algoritmu * spočítat tři iterace na zadaném stromě - 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 ==== {{:courses:pah_skuska_5_6_2013_str1.jpg?100}} {{:courses:pah_skuska_5_6_2013_str2.jpg?100}} ==== 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 * LTL * modální logika - operátory box, diamond, next, untill - teorie her * dvouhráčové hry * algoritmy pro dvouhráčové hry * Nashovo equilibrium * Pareto-optimalita gl ===== Studijní materiály ===== [[http://cs.brown.edu/research/ai/pomdp/tutorial/|POMDP for dummies]] - skvělý tutorial na POMDP (jen doporučuji v prohlížeči zapnout Reader mode, jinak se to nedá číst :D ) ~~DISCUSSION~~