navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pah [2012/06/12 18:55] houp |
courses:a4m33pah [2025/01/03 18:23] (aktuální) |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| - | ====== Plánování a hry ====== | + | ====== Planning for Artificial Intelligence ====== |
| - | * Stránky předmětu: [[http://cw.felk.cvut.cz/doku.php/courses/a4m33pah/start| Plánování a hry]] | + | * Stránky předmětu: [[https://cw.fel.cvut.cz/wiki/courses/pui/start|Planning for Artificial Intelligence]] |
| - | * Přednášející: [[http://agents.felk.cvut.cz/pechoucek/|Pěchouček]], [[http://iew3.technion.ac.il/~dcarmel/|Domshlak]] | + | * 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://agents.felk.cvut.cz/members/#chrpa |L.Chrpa]], [[http://agents.felk.cvut.cz/members/#vokrinek |Vokřínek J.]] | + | * 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í ===== | ===== Cvičení ===== | ||
| Řádek 11: | Řádek 11: | ||
| [[courses/a4m33pah/zkousky|Historie zadání]] | [[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í | ||
| + | * <del>napsat zdali h_lmcut je vždy admissible</del> (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 h<sub>max</sub> a h<sub>FF</sub> | ||
| + | - Co je to přípustná heuristika a rozhodnout, zdali jsou h<sub>max</sub> a h<sub>FF</sub> 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.. | 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.. | ||
| Řádek 30: | Řádek 125: | ||
| - otazky (pet otazek, uz si je moc nepamatuju, treba je dame dohromady) | - otazky (pet otazek, uz si je moc nepamatuju, treba je dame dohromady) | ||
| - z jakych casti se sklada takovyten samoopravovaci planovac | - 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 | - 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) | * aximatizovat pomocí výroků, které budou potřeba a popsat je (onKL, onKM, onKT, ..., cleanK, cleanL, cleanM) | ||
| Řádek 45: | Řádek 143: | ||
| - jak dlouho to bude trvat pro nekonecno procesoru (cena kriticke cesty) | - jak dlouho to bude trvat pro nekonecno procesoru (cena kriticke cesty) | ||
| - jak dlouho pro jeden (soucet vsech cen) | - 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 ==== | ==== 2011 ==== | ||
| Řádek 88: | Řádek 198: | ||
| gl | gl | ||
| - | ~~DISCUSSION~~ | + | ===== 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~~ | ||
