IV126 Umělá inteligence II Hana Rudová Fakulta informatiky, Masarykova univerzita 8. ledna 2021 Online výuka Web předmětu: http://www.fi.muni.cz/~hanka/ai materiály průběžně aktualizovány na webu předmětu zveřejnění cca týden před odpovídající přednáškou Průsvitky (slides) Videa ke každé přednášce ze starších běhů předmětu nebo nově připravené s pomocí OBS Studio Videokonference v době přednášky Zoom (link e-mailem) sada otázek předem + případné další dotazy odpovědi studentů nebo demonstračně bonusové body za aktivní účast pro vylepšení hodnocení až 24 bodů ke 100 běžným Hana Rudová, IV126, FI MU: IV126 Umělá inteligence II 2 8. ledna 2021 Hodnocení Online závěrečná písemná práce: 80 bodů vyžadována nadpoloviční znalost látky (více než 40 bodů) pravděpodobně (především vzhledem k počtu zapsaných) Domácí úkoly: 20 bodů 2 domácí úkoly po 10 bodech minimální počet bodů za domácí úkoly: 8 bodů úkol zadán na přednášce, řešení do přednášky za 2 týdny postup řešení musí být součástí odevzdaného úkolu Bonusové body: až 2 body za aktivní účast na 1 videokonferenci 1 bod: reakce na více jednoduchých dotazů nebo dotazy studentky/a na vyjasnění látky, reakce na jeden složitější dotaz 2 body: větší interakce Hodnocení: A 90 a více, B 80-89, C 70-79, D 60-69, E 50-59 Hana Rudová, IV126, FI MU: IV126 Umělá inteligence II 3 8. ledna 2021 Obsah přednášky Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, fourth edition. Prentice Hall, 2020. http://aima.cs.berkeley.edu/ Prohledávání a heuristiky: koncepty, práce s jedním řešením, s populací řešení Plánování: Klasické plánování, reprezentace problému. Plánování se stavovým prostorem, plánování s prostorem plánů Neurčitost: Bayesovské sítě, exaktní a aproximační odvozování. Čas a neurčitost. Užitek a rozvhodování. Sekvenční rozhodovací problémy, Markovské rozhodovací procesy. Robotika: Robot a jeho hardware. Vnímání robota, lokalizace a mapování Plánování pohybu robota, plánování s neurčitostí PB016 Umělá inteligence I IV126 volně navazuje na PB016, absolvování PB106 není podmínkou Hana Rudová, IV126, FI MU: IV126 Umělá inteligence II 4 8. ledna 2021 Metaheuristiky: úvod 8. ledna 2021 1 Přehled optimalizačních metod 2 Hlavní koncepty 3 Použití a implementace algoritmů Zdroj: El-Ghazali Talbi, Metaheuristics: From Design to Implementation. Wiley, 2009. http: // www. lifl. fr/ ~talbi/ metaheuristic/ Literatura Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, fourth edition. Prentice Hall, 2020. http://aima.cs.berkeley.edu/ El-Ghazali Talbi, Metaheuristics: From Design to Implementation. Wiley, 2009. http://www.lifl.fr/~talbi/metaheuristic/ FI:PA184 Heuristic Methods for Search and Optimization jaro 2010, https://is.muni.cz/auth/predmet/fi/jaro2010/PA184 Holger H. Hoos und Thomas Stützle, Stochastic Local Search. Morgan Kaufmann Publishers, 2005. http://iridia.ulb.ac.be/~stuetzle/Teaching/HO14/ Sörensen K., Sevaux M., Glover F., A History of Metaheuristics. In Handbook of Heuristics. Springer, Cham, 2018. https://arxiv.org/abs/1704.00853 Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 6 8. ledna 2021 Optimalizační metody Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 7 8. ledna 2021 Přehled optimalizačních metod Exaktní metody výpočet (globálně) optimálního řešení, garance optimality nevhodné pro velké problémy Aproximační metody → aproximační algoritmy garance na mez kvality vypočítaného řešení -aproximace př. problém plnění košů (bin packing) – stejné koše, různé předměty First Fit (FF) 17 10 opt + 1 (opt: počet košů v optim.řešení) First Fit Decreasing (FFD) 11 9 opt + 1 Aproximační metody → heuristické algoritmy ze staré řečtiny slovo „heuriskein” znamená: umění objevovat nové strategie/pravidla pro řešení problémů cíl generovat pro praktické použití „vysoce kvalitní” řešení v rozumném čase žádná garance na kvalitu (globálního) optima Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 8 8. ledna 2021 Heuristické algoritmy → metaheuristiky Metaheuristiky předpona meta opět z řečtiny: metodologie vyšší/obecnější úrovně představeny F. Gloverem v roce 1986 metaheuristika: metodologie (templát/šablona) vyšší obecnější úrovně, která může být použita jako řídící strategie pro návrh základní heuristiky pro řešení specifických optimalizačních problémů př. rozvrhování předmětů: simulované žíhání a výměna dvou předmětů reprezentují obecný přístup aplikovatelný na různé problémy Při návrhu metaheuristik nutno aplikovat dva protichůdné principy: průzkum (exploration), diversifikace vs. zužitkování (exploitation), intensifikace Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 9 8. ledna 2021 Klasifikace metaheuristik (Ne)inspirované přírodou přírodní procesy: evoluční algoritmy sociální vědy: mravenci, včelstva, roje fyzika: simulované žíhání (Ne)používající paměť tabu prohledávání (tabu seznam jako paměť) vs. simulované žíhání Deterministické vs. stochastické deterministická rozhodnutí (tabu prohledávání) použití náhodnosti (simulované žíhání) Založené na populaci vs. jednom řešení genetické algoritmy vs. simulované žíhání Iterativní vs. hladové iterativní: začneme s úplným řešením (nebo jejich populací) a provádíme jeho/jejich transformace hladové: začneme z prázdného řešení a v každém kroku přiřadíme jednu rozhodovací proměnnou, dokud nenalezneme úplné řešení většina metaheuristik iterativníHana Rudová, IV126, FI MU: Metaheuristiky: úvod 10 8. ledna 2021 Lokální prohledávání (local search, hill climbing, horolezecký algoritmus) Nejstarší a nejjednodušší metaheuristika Nahrazuje aktuální řešení zlepšujícím řešením s := s0; (generuj iniciální řešení s0) while není splněna podmínka ukončení do generuj(N(s)); (generování sousedů z okolí) if neexistuje lepší soused konec; s := s ; (vyber lepšího souseda s ∈ N(s)) end while výstup: finální nalezené řešení (lokální optimum) Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 11 8. ledna 2021 Hlavní koncepty pro metaheuristiky Reprezentace (kódování) jak reprezentovat řešení/přiřazení př. posloupnost: úlohy na jednom stroji naplánovány v pořadí (1,2,3) Účelová funkce (objektivní funkce, případně optimalizační kritérium) př. chceme minimalizovat čas dokončení poslední úlohy Manipulace s omezeními (constraint handling) omezení/podmínky musí být splněny, aby bylo řešení validní, tj. konzistentní konzistentní vs. nekonzistentní řešení př. úlohy naplánované na jednom stroji se nesmí překrývat Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 12 8. ledna 2021 Reprezentace Nutné charakteristiky reprezentace problému úplnost lze reprezentovat všechna řešení dosažitelnost ve stavovém prostoru musí existovat cesta mezi každými dvěma řešeními každé (zejména optimální) řešení je dosažitelné efektivita s reprezentací lze snadno manipulovat prohledávacími operátory minimalizace časové a prostorové složitosti operátorů Typy reprezentací lineární reprezentace řetězce symbolů dané abecedy binární kódování, diskrétní kódování, permutace, vektor reálných čísel nelineární reprezentace založené často na grafových strukturách, zejména použité stromy Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 13 8. ledna 2021 Binární kódování S každou rozhodovací proměnnou je spojena binární hodnota Řešení reprezentováno jako vektor bitových hodnot Příklad: problém batohu Máme n předmětů zadané velikosti a ceny. Vyberte do batohu velikosti m předměty tak, aby se do něj vešly a jejich cena byla maximální. Řešení reprezentuje vektor s = (s1, s2, . . . , sn) si = 1 pokud je předmět i v batohu 0 jinak Další příklady: SAT problém problémy celočíselného programování s binárními proměnnými Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 14 8. ledna 2021 Diskrétní kódování Zobecnění binárního kódování Řešení reprezentováno jako vektor diskrétních hodnot, tj. proměnné nabývají hodnoty z n-ární abecedy Pro problémy, kde proměnné nabývají hodnot z konečné domény, např. kombinatorické problémy Řada reálných optimalizačních problémů (např. alokace zdrojů) může být redukovaná na problém přiřazení Problém přiřazení: Máme zadánu množinu n úloh, kterým má být přiřazeno m agentů tak, abychom maximalizovali celkový zisk. Úloha může být přiřazena libovolnému agentovi. Řešení reprezentuje vektor s velikosti n, kde si reprezentuje agenta přiřazeného úloze i si = j pokud je agent j přiřazen úloze i Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 15 8. ledna 2021 Reprezentace permutací Permutační problémy seřazení (sequencing), směrování, plánování každý element problému se musí v reprezentací objevit pouze jednou Příklad: problém obchodního cestujícího (traveling salesman problem TSP) n měst, která musí obchodní cestující projít řešení reprezentuje permutace měst udávající pořadí jejich procházení Příklad: plánování úloh bez překrývání na jeden stroj řešení reprezentuje permutace úloh udávající pořádí prováděných úloh Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 16 8. ledna 2021 Redukce stavového prostoru vhodnou reprezentací Příklad: umístit 8 královen na šachovnici tak, aby na sebe neútočily Souřadnice v prostoru vektor (s1, . . . , s8) pozic na šachovnici, kde si = (xi , yi ) počet možností 648, tj. přes 4 miliardy Jedna královna ve sloupci vektor (y1, . . . , y8) umístění královny i v i-tém sloupci zakazuje více královen v jednom slouci počet možností 88, tj. přes 16 miliónů Permutace pokud zakážeme dvě královny ve stejném sloupci a řádku, pak se reprezentace redukuje na permutaci královen královna na sloupec, pro každou královnu různý řádek ⇒ permutace počet možností 8!, tj. 40 320 možností Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 17 8. ledna 2021 Účelová funkce Soběstačná účelová funkce účelová funkce problému lze rovnou použít při optimalizaci ideální situace soběstačná funkce: TSP min dist(x, y) ne-soběstačná funkce: SAT splnitelná formule (true/false) Směrující účelová funkce směrující funkce lze použít při optimalizaci soběstačná funkce lze přímo použít někdy je nutné účelovou funkci transformovat kvůli lepší konvergenci metaheuristiky např. ne-soběstačné funkce je nutné transformovat nová účelová funkce bude směřovat k efektivnějšímu prohledávání k-SAT: konjunkce m klauzulí (disjunkcí) nad k proměnnými (x1 ∨ x2) ∧ (x1 ∨ x2) ∧ (x1) pro (x1, x2) porovnej (0,0) a (1,0) nová účelová funkce: počet splněných klauzulí, cíl: maximalizace Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 18 8. ledna 2021 Další typy účelových funkcí Relativní a kompetitivní účelové funkce pokud nelze přiřadit funkcí absolutní hodnotu ke všem řešením příklad: teorie her, strategie A, B, C : A < B, B < C, C < A Meta-modelování při extrémně výpočetně náročné účelové funkci je navržen přibližný model a přibližná účelová funkce př. návrh telekomunikační sítě A další ... Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 19 8. ledna 2021 Manipulace s omezeními Zamítací strategie uchováváme pouze konzistentní řešení Penalizující strategie původní účelová funkce rozšířena o penalizaci nekonzistentních řešení uvažovány váhy nesplněných omezení řádově vyšší váha za nesplněná omezení ve srovnání s hodnotou účelové funkce Opravné strategie opravují nekonzistentní řešení aplikovány opravné strategie na vygenerované nekonzistentní přiřazení, které tedy opravíme, a pokračujeme s konzistentním řešením A další ... Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 20 8. ledna 2021 Ladění parametrů a analýza výkonosti Při návrhu algoritmů je důležité ladění parametrů algoritmů metaheuristiky mají mnoho parametrů optimální ladění záleží na problému a instanci Offline inicializace parametrů nastavíme parametry a spustíme algoritmus, příklady: nastavování jednoho parametru za druhým (neoptimální) Design of Experiments (DoE): k faktorů/parametrů s n možnými úrovněmi/hodnotami: nk experimentů (!) Přírodovědecká fakulta: FX003 Plánování a vyhodnocování experimentu Improving your statistical inferences https://www.coursera.org/learn/statistical-inferences/ strojové účení Online inicializace parametrů (paralelní) restartování algoritmu s různými parametry Velkou roli hraje experimentální analýza algoritmů Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 21 8. ledna 2021 Software Metaheuristic optimization frameworks: a survey and benchmarking, Soft Computing, 2012, Volume 16, Issue 3, pp 527-561. http://link.springer.com/article/10.1007/s00500-011-0754-8 PA184 Heuristic Methods for Search and Optimization, 2010 přednáška Sotware Libraries for Heuristics, http://is.muni.cz/el/ 1433/jaro2010/PA184/um/09_Lecture-Software-Libraries.pdf ParadisEO, A Software Framework for Metaheuristics http://paradiseo.gforge.inria.fr EasyLocal++ knihovna pro modelování a řešení kombinatorických optimalizačních problémů pomocí metaheuristic https://bitbucket.org/satt/easylocal-3 OptaPlanner sofware pro plánování, který využívá různé algoritmy lokálního prohledávání https://www.optaplanner.org/ Hana Rudová, IV126, FI MU: Metaheuristiky: úvod 22 8. ledna 2021 Metaheuristiky pracující s jedním řešením 8. ledna 2021 4 Základní algoritmus 5 Iniciální řešení 6 Okolí 7 Lokální prohledávání 8 Algoritmy s výběrem horšího řešení 9 Iterace s různými řešeními 10 Použití různých okolí 11 Změna účelové funkce 12 Hyper-heuristiky Zdroj: El-Ghazali Talbi, Metaheuristics: From Design to Implementation. Wiley, 2009. http: // www. lifl. fr/ ~talbi/ metaheuristic/ Kostra algoritmu pracující s jedním řešením Vstup: iniciální řešení s0 t = 0; repeat (generuj množinu kandidátních řešení – částečné nebo úplné okolí – z st) generate(C(st)); (vyber řešení z C(s) pro náhradu aktuálního řešení st) st+1 = select(C(st)); t = t + 1; until splněna podmínka ukončení Výstup: nejlepší nalezené řešení Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 24 8. ledna 2021 Iniciální řešení Hlavní strategie náhodné řešení heuristické řešení (např. pomocí hladového algoritmu) částečně nebo úplně inicializované uživatelem Kvalita vs. výpočetní čas Použití lepších iniciálních řešení nepovede vždy k lepšímu lokálnímu optimu Generování konzistentních náhodných řešení může být obtížné pro vysoce omezené problémy Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 25 8. ledna 2021 Okolí S: množina řešení Definice Okolí. Funkce okolí N je mapování N : S → 2S , která přiřadí každému řešení s z S množinu řešení N(s) ⊂ S. Definice V diskrétním optimalizačním problému je okolí N(s) řešení s reprezentováno množinou {s ∈ S | d(s , s) ≤ }, kde d reprezentuje vzdálenost svázanou s operátorem změny. Uzly reprezentují řešení problému Okolí řešení jsou sousední vrcholy v grafu d(s, s ) ≤ 1: měníme hodnotu jedné proměnné Pro (0, 1, 0) máme okolí {(0, 0, 0), (1, 1, 0), (0, 1, 1)} Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 26 8. ledna 2021 Lokální optimum Definice Lokální optimum. Řešení s ∈ S je lokální optimum vzhledem k dané funkci okolí N, pokud má lepší kvalitu než všichni jeho sousedi, tj. f (s) ≤ f (s ) pro všechna s ∈ N(s). (pro minimalizační problém) Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 27 8. ledna 2021 Příklad okolí: k-vzdálenost (k-distance) Permutační problémy, např. TSP: 2-distance vymění dvě města (k-distance vymění k měst) Velikost okolí pro 2-distance: n(n − 1)/2, kde n je počet měst Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 28 8. ledna 2021 Příklad okolí: k-výměna (k-opt) Permutační problémy, např. TSP k-opt smaže k hran a nahradí je dalšími k hranami Velikost okolí pro 2-opt: [n(n − 1)/2 − n], kde n je počet měst uvažujeme všechny páry hran kromě sousedních párů Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 29 8. ledna 2021 Permutační okolí pro rozvrhovací problémy Okolí založené na pozici operátor vložení Okolí založená na pořadí operátor výměny operátor inverze Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 30 8. ledna 2021 Přehled okolí Okolí, lokální optimum Malá okolí k-distance (k-vzdálenost) k-opt (k-výměna) permutační okolí operátor vložení operátor výměny operátor inverze Rozsáhlá okolí řetězec odstranění cyklická výměna Inkrementální evaluace okolí Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 31 8. ledna 2021 Rozsáhlá okolí (very large neighborhoods) Kompromis: velikost (diametr) okolí (výpočetní složitost na jeho prozkoumání) vs. kvalita řešení Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 32 8. ledna 2021 Efektivní algoritmy na prozkoumání rozsáhlých okolí Velikost okolí: polynom vyššího řádu (n>2) n. exponenciální Hlavní problém: identifikace zlepšujících okolí nebo nejlepšího souseda bez enumerace celého okolí Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 33 8. ledna 2021 Řetězec odstranění (ejection chain) (Capacitated) vehicle routing problem řetězec odstranění: posloupnost přesunů zákazníka z jednoho okruhu na následující každý řetězec odstranění zahrnuje k úrovní začínajících na okruhu 1 a končících na okruhu k vrchol je odstraněn z okruhu 1 a přesunut na okruh 2, vrchol z okruhu 2 přesunut na okruh 3, atd. až vrchol z k-1 na k, poslední vrchol z okruhu k přesunut do okruhu 1 úspěšná změna: žádný vrchol není v řešení více než jednou Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 34 8. ledna 2021 Cyklická výměna (cyclic exchange) ve skupinách Problémy rozdělení n prvků do q skupin (např. při vyvažování zátěže) prvky mají být rozděleny do skupin S = {S1, . . . , Sq} cyklická výměna 3 prvků (3-okolí): prvek a2 ∈ S2 je přesunut do S3, a3 ∈ S3 je přesunut do S4, a4 ∈ S4 přesunut do počáteční skupiny S2 velikost k-okolí pro n prvků:O(nk) pro výměnu dvojice prvků máme O(n2 ) Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 35 8. ledna 2021 Inkrementální evaluace okolí Evaluace řešení: nejdražší část výpočtu Naivní evaluace: úplná evaluace každého řešení v okolí Cíl: navrhnout vhodnou inkrementální evaluaci okolí Příklad: ∆f = distance(A, E) + distance(C, D) − distance(A, D) − distance(C, E) Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 36 8. ledna 2021 Pokročilé lokální prohledávání Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 37 8. ledna 2021 Lokální prohledávání (local search, hill climbing, horolezecký algoritmus) Opakování z minulé přednášky hill climbing, inicializace řešení, okolí Nejstarší a nejjednodušší metaheuristika Nahrazuje aktuální řešení zlepšujícím řešením s := s0; (generuj iniciální řešení s0) while není splněna podmínka ukončení do generuj(N(s)); (generování sousedů z okolí) if neexistuje lepší soused konec; s := s ; (vyber lepšího souseda s ∈ N(s)) end while výstup: finální nalezené řešení (lokální optimum) Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 38 8. ledna 2021 Lokální prohledávání: výběr souseda Výběr souseda z okolí: nejlepší zlepšující (steepest descent, metoda největšího spádu): výběr nejlepšího souseda (tj. nejvíce zlepšuje účelovou funkci) první zlepšující: systematický/deterministický výběr prvního souseda, který je lepší než aktuální řešení náhodný výběr: náhodný výběr mezi zlepšujícími sousedy Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 39 8. ledna 2021 Prohledávací prostor a krajina (fitness landscape) Definice: Prohledávací prostor je definován orientovaným grafem G = (S, E), kde množina vrcholů S odpovídá řešením problému definovaným jejich reprezentací a množina hran E je určena operátorem změny použitým pro generování sousedů z okolí. Poznámka: Sousedním vrcholem řešení v G jsou sousedé z okolí řešení. Definice: Krajina (daná vhodností) l je definována dvojicí G, f , kde G je prohledávací prostor a f účelová funkce, která řídí prohledávání. řešení s0 s f (s0) = 7 má v okolí 3 sousedy s hodnotou účelové funkce 10,9,10 Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 40 8. ledna 2021 Pokročilé lokální prohledávání Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 41 8. ledna 2021 Simulované žíhání (simulated annealing, SA) a spol. Klasický reprezentant lokálního prohledávání FI: IA101, PV027, PA167, PA163 viz také Talbi(ho) kniha a její průsvitky ke kapitole 2 Náhodný výběr souseda z okolí Výběr lepšího souseda je vždy akceptován jako u hill climbing Akceptuje i výběr horšího souseda Na začátku prohledávání je povolena větší pravděpodobnost zhoršení vybraného řešení, postupně se povoluje menší a menší pravděpodobnost zhoršení vybraného řešení Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 42 8. ledna 2021 Algoritmy založené na přijetí prahem (threshold accepting) Deterministická varianta simulovaného žíhání Akceptována i horší řešení s maximálnímí zhoršením o prahovou hodnotu Q Algoritmus přijetí prahem s = s0; (generování iniciálního řešení) Q = Qmax; (počáteční nastavení prahu) repeat repeat (při pevném prahu) generuj náhodně souseda s ∈ N(s); ∆E = f (s ) − f (s); if ∆E ≤ Q then s = s (akceptování souseda) until splněna podmínka rovnováhy (např. po pevném počtu iterací při každém Q) Q = g(Q); (aktualizace prahu, typicky zmenšení) until splněna podmínka ukončení (např. při Q ≤ Qmin) výstup: nejlepší nalezené řešení Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 43 8. ledna 2021 Great Deluge algoritmus (alg. velké potopy) Analogie s potopou a stoupající vodní hladinou Horolezec (kvalita řešení) „vždy zůstane nad vodní hladinou” Pozor, algoritmus uveden klasicky pro minimalizační problém, tj. hladinu (LEVEL) musíme redukovat a snažíme se zůstat pod LEVEL s = s0; (generování iniciálního řešení) zadej rychlost deště UP; (UP > 0) zadej počáteční úroveň vodní hladiny LEVEL; repeat generuj náhodného souseda s ∈ N(s); if f (s ) < LEVEL then s = s ; (akceptuj řešení) LEVEL = LEVEL − UP; (aktualizuj úroveň hladiny) until splněna podmínka ukončení výstup: nejlepší nalezené řešení UP je kritický parametr příliš vysoký ⇒ rychle nalezeno nekvalitní řešení nízký ⇒ lepší výsledky se zvyšujícími se časovými nároky Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 44 8. ledna 2021 Tabu prohledávání Deterministické rozšíření základního algoritmu lokálního prohledávání často kombinováno i s dalšími algoritmy Umožňuje akceptovat i horší řešení řešení horší/stejné kvality akceptováno, pokud neexistuje lepší cyklení je zabráněno prostřednictvím tzv. tabu seznamu Udržován tabu seznam seznam několika posledních změn, které jsou zakázány (typicky 5-9) např. problém obchodního cestujícího, 2-výměna měst, v tabu seznamu uloženy dvojice měst z N posledních změn Aspirační kritérium podmínka, za které je možné realizovat i změny z tabu seznamu např. povolení změn, které vedou k lepší hodnotě účelové funkce Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 45 8. ledna 2021 Algoritmus tabu prohledávání s := s0; (generuj iniciální řešení s0) inicializace tabu seznamu; repeat nalezni nejlepší přípustné s ∈ N(s); (přípustné řešení: není v tabu seznamu n. platí asp. kritérium) s := s ; aktualizace tabu seznamu a aspiračního kritéria; until splněna podmínka ukončení výstup: nejlepší nalezené řešení Poznámka: nejlepší přípustné řešení nemusí být nutně zlepšující je to „jen” nejlepší řešení z N(s) Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 46 8. ledna 2021 Iterativní lokální prohledávání (iterated local search) Multistart local search (opakované lokální prohledávání) opakování lokálních prohledávání iniciální řešení je generováno při další iteraci náhodně Iterativní lokální prohledávání vylepšení multistart local search nalezené lokální optimum změněno a použito při dalším lokálním prohledávání obecná kostra: lze použít libovolný alg. lokálního prohledávání Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 47 8. ledna 2021 Algoritmus iterativního lokálního prohledávání s = s0; (generuj iniciální řešení) s∗ = lokální_prohledávání(s); (aplikuj daný alg. lok. prohledávání) repeat s = změna(s∗, historie prohl.); (změň spočítané lokální minimum) s∗ = lokální_prohledávání(s ); (aplikuj lok. prohl. na změněné řešení) s∗ = akceptuj(s∗,s∗, paměť prohl.); (kritérium přijetí řešení) until splněna podmínka ukončení výstup: nejlepší nalezené řešení Změna velká náhodná změna v řešení část řešení zachována, část změněna použití efektivnějšího lokálního prohledávání vyžaduje větší změnu příliš velká změna povede k opakovanému lokálnímu prohledávání, kde při opakované iteraci začínáme s náhodným řešením Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 48 8. ledna 2021 Prohledávání s proměnlivým okolím (variable neighborhood search, VNS) Použití různých okolí: Komplementární okolí: lokální optimum okolí Ni nebude lokálním optimem okolí Nj (1) První lokální optimum získáno dle okolí 1 (2) Abychom z něj unikli, prohledáváme okolí 2 (3) Pomocí okolí 2 se dostaneme do lokálního optima okolí 2 Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 49 8. ledna 2021 Zlepšující prohledávání s proměnlivým okolím (variable neighborhood descent algorithm, VND) VNS založeno na zlepšujícím prohl. s proměnlivým okolím (VND) VND je deterministická verze VNS s = s0; (generuj iniciální řešení) l = 1; while l ≤ lmax do nalezni nejlepšího souseda s ∈ Nl (s); if f (s ) < f (s) then s = s ; l = 1; (máme lepší řešení) else l = l + 1; výstup: nejlepší nalezené řešení Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 50 8. ledna 2021 Základní verze algoritmu s proměnlivým okolím s = s0; (generuj iniciální řešení) repeat k = 1; repeat vyber náhodně s ∈ Nk(s); (zatřepání/shaking) s = lokální_prohledávání(s ); if f (s ) < f (s) then s = s ; k = 1; (máme lepší řešení) else k = k + 1; until k = kmax ; until splněna podmínka ukončení výstup: nejlepší nalezené řešení Okolí pro zatřepání typicky jsou postupně prozkoumávána vnořená okolí N1(s) ⊂ N2(s) ∪ · · · ∪ Nk (s), ∀s ∈ S příklad: problém obchodního cestujícího a k-opt (k-výměna) měst Komentář: v obecné verzi algoritmu je lokální prohledávání nahrazeno VND Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 51 8. ledna 2021 Pokročilé lokální prohledávání Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 52 8. ledna 2021 Řízené lokální prohledávání (guided local search, GLS) Opakovaná lokální prohledávání s upravenou hodnotou účelové funkce Každé řešení s ∈ S má množinu m charakteristik i s cenou ci Ii (s) = 1 pokud s má charakteristiku i 0 jinak snaha o prohledávání částí stav. prostoru s nižší cenou charakteristik př. problém obchodního cestujícího: zda je hrana (a, b) v řešení, cenu určuje délka hrany (vzdálenost měst) Nová účelová funkce f (s) = f (s) + λ m i=1 pi Ii (s) penalizace pi : význam charakteristiky (vysokou penalizaci nechceme) pi inicializováno na 0 pro všechna i λ se používá pro normalizaci užitek/hodnota Charakteristika i s nejvyšším užitkem ui (s) = Ii (s) ci 1+pi penalizována chceme se příště vyhnout charakteristikám s vysokou cenou charakteristiky použité v řešení penalizovány pro podporu diversifikace Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 53 8. ledna 2021 Algoritmus řízeného lokálního prohledávání s = s0; (generuj iniciální řešení) forall i do pi = 0; (inicializace penalizací) repeat s = lokální_prohledávání(s); (s upravenou účelovou funkcí) forall i do ui (s ) = Ii (s ) ci 1+pi ; (spočítej užitek pro všechny char.) uj = maxi=1,...m(ui (s )); (urči charakteristiku s max. užitkem) pj = pj + 1; (změň účelovou funkci penalizací char. j) until splněna podmínka ukončení výstup: nejlepší nalezené řešení Intensifikace GLS prohledává stavový prostor s nižšími cenami ci Diversifikace GLS penalizuje charakteristiky použité ve vygenerovaném lokálním optimu, abychom se jim vyhnuli Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 54 8. ledna 2021 Příklad: symetrický problém obchodního cestujícího di,j = dj,i udává vzdálenost mezi městy i, j (symetrická matice) Město t(i) následuje po trase za městem i Řešení zakódováno jako permutace měst Původní účelová funkce f (s) = n i=1 di,t(i) Indikace charakteristiky I(i,j)(s) = 1 pokud hrana (i, j) ∈ s 0 jinak Nová účelová funkce f (s) = n i=1 di,t(i) + λpi,t(i) pi,j udává penalizaci za hranu (i, j) Užitek ui (s, (i, j)) = I(i,j)(s) dij 1 + pij Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 55 8. ledna 2021 Příklad: TSP a GLS ui (s) = Ii (s) ci 1+pi TSP s hranami 1, 2, 3, 4 a cenou 10, 6, 3, 2 v řešení Funkce užitku pro hrany: 10/1, 6/1, 3/1, 2/1 pi iniciálně 0 Penalizována hrana s užitkem 10/1 Nové řešení s hranami 2, 3, 4, 5 a cenou 6, 3, 2, 3 Funkce užitku pro hrany: 6/1, 3/1, 2/1, 3/1 Penalizována hrana s užitkem 6/1 Nové řešení s hranami 1, 3, 4, 6 a cenou 10, 3, 2, 7 Funkce užitku pro hrany: 10/2, 3/1, 2/1, 7/1 Penalizována hrana s užitkem 7/1 hrana s cenou 10 se opakuje, je možná důležitá, proto ji zatím nepenalizujeme . . . Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 56 8. ledna 2021 Hyper-heuristiky Hyper-heuristiky prvotní myšlenka: heuristiky na výběr heuristik rozšířeno na: prohledávací metoda nebo učící mechanismus pro výběr nebo generování heuristik pro řešení obtížných prohledávacích problémů Kategorie hyper-heuristik výběr heuristik: snaha o nalezení vhodné sekvence aplikace existujících heuristik pro efektivní řešení problému generování heuristik: snaha o vývoj nových heuristik na základě komponent známých heuristik učení heuristik pomocí neuronových sítí, evolučních algoritmů, ... Hyper-heuristiky pracují nad prohledávacím prostorem heuristik (a ne přímo nad prohledávacím prostorem řešeného problému) Hyper-heuristics: a survey of the state of the art, Burke, Gendreau, Hyde, Kendal, Ochoa, Özcan, Qu, Journal of the Operational Research Society (2013), 64, 1695-1724. Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 57 8. ledna 2021 Problém: rozvrhování událostí jako barvení grafu Barvení grafu vrcholy = události hrany mezi událostmi, které nesmí být ve stejném časovém slotu barva říká, ve kterém čase událost rozvrhneme sousední vrcholy musí mít různou barvu / musí být v různém čase Jednoduché heuristiky, které konstruují řešení seřazením událostí: Stupeň saturace události seřazeny (1) ve vzrůstajícím pořadí podle počtu časových slotů, kam je lze umístit v aktuálním částečném rozvrhu (saturace), a pak (2) dle klesajícího stupně vrcholu v neobarveném podgrafu Počet účastníků (zapsaných studentů) události seřazeny v klesajícím pořadí podle počtu účastníků, resp. zapsaných studentů ... Náhodné pořadí dosud nerozvržené události seřazeny náhodně Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 58 8. ledna 2021 Grafová hyper-heuristika pro rozvrh událostí inicializace seznamu heuristik hl = {h1, . . . , hk }; for i = 0 to počet_iterací do h = hl se dvěma vyměněnými heuristikami; (lokální změna v tabu prohl.) if h není v „neúspěšném seznamu” if h není v tabu seznamu for j = 0 to j = k do (h použito pro konstrukci řešení) rozvrhuj prvních e událostí v seznamu událostí seřazených dle hj if neexistuje žádné řešení ulož h do „neúspěšného seznamu” (aktualizace „neúsp. seznamu”) else if cena řešení c < cbest ulož nejlepší řešení; cbest = c; smaž nejstarší položku z tabu seznamu, pokud je plný; přidej h do tabu seznamu; hl = h; hill climbing s výběrem nejlepšího souseda aplikovaný na nalezené řešení; výstup: nejlepší nalezené řešení s cenou cbest Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 59 8. ledna 2021 Poznámky k algoritmu Přístup: heuristika na výběr heuristik tabu prohledávání nad stavovým prostorem heuristik e × k odpovídá počtu událostí v rozvrhu k délka heuristického seznamu e událostí rozvrhnuto najednou stejnou heuristikou je známo, že heuristiky se při řešení po sobě často opakují ušetří čas na řešení v každé iteraci tak sestrojíme úplné řešení „Neúspěšný seznam” obsahuje začátek heuristického seznamu, kde došlo k chybě (nenalezeno řešení) př. při neúspěchu u seznamu „h1h2h3...” při aplikaci h3 zakážeme heuristické seznamy „h1h2h3h4...”, „h1h2h3h5...”, ... A graph-based hyper-heuristic for educational timetabling problems, E. Burke, B. McCollum, A. Meisels, S. Petrovic, R. Qu. European Journal of Operational Research 176 (2007) 177-192. Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 60 8. ledna 2021 Shrnutí 4 Základní algoritmus 5 Iniciální řešení 6 Okolí Malá okolí Rozsáhlá okolí 7 Lokální prohledávání Horolezecký algoritmus (hill climbing) 8 Algoritmy s výběrem horšího řešení Simulované žíhání Algoritmus přijetí prahem (threshold accepting) Algoritmus velké potopy (great deluge) Tabu prohledávání 9 Iterace s různými řešeními Opakované (multistart) a iterativní (iterated) lokální prohledávání 10 Použití různých okolí Prohledávání s proměnlivým okolím (variable neighborhood search) Zlepšující prohledávání s proměnlivým okolím (variable neighborhood descent) 11 Změna účelové funkceHana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 61 8. ledna 2021 Cvičení Máme zadán problém rozvrhování n předmětů do m učeben v p časových slotech. Každý předmět je vyučován v jednom slotu a v jedné učebně, přičemž dva předměty nesmí být ve stejném čase a místě. Jakým způsobem zakódujete řešení problému? Pro každý předmět je určena penalizace za přiřazení do daného času. Jak definujete účelovou funkci? Jak vygenerujete iniciální řešení? Jak spočítáte inkrementálně účelovou funkci, pokud je lokální změna dána výměnou dvou předmětů? Jaké další typy lokálních změn byste mohli aplikovat? Jak lze aplikovat změnu pomocí řetězce odstranění (ejection chain) na tento problém? A jak bude vypadat inkrementální výpočet účelové funkce v tomto případě? Jak velké je okolí u horolezeckého algoritmu (hill climbing), pokud hledáte nejlepšího zlepšujícího souseda (při výměně 2 předmětů)? Jak navrhnete prvky tabu seznamu, pokud je lokální změna dána výměnou dvou předmětů? Hana Rudová, IV126, FI MU: Metaheuristiky pracující s jedním řešením 62 8. ledna 2021 Metaheuristiky s populacemi 8. ledna 2021 13 Společné koncepty metaheuristik s populacemi 14 Evoluční algoritmy 15 Optimalizace mravenčí kolonie Zdroj: El-Ghazali Talbi, Metaheuristics: From Design to Implementation. Wiley, 2009. http: // www. lifl. fr/ ~talbi/ metaheuristic/ Metaheuristiky s populacemi (population-based metaheuristics) Genetické algoritmy, evoluční strategie, genetické programování, optimalizace mravenčí kolonie (ant colony optimization, ACO), optimalizace jedinců hejna (particle swarm optimization, PSO), včelí úl (bee colony), umělé imunitní systémy (artificial immune systems), odhad distribučními algoritmy (estimation of distribution algorithms, EDA), ... P = P0; (generuj počáteční populaci) t = 0; repeat generuj(Pt); (generuj novou populaci) Pt+1 = vyber_populaci(Pt ∪ Pt); (vyber novou populaci) t = t + 1; until splněna podmínka ukončení výstup: nejlepší nalezené/á řešení Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 64 8. ledna 2021 Populační metaheuristiky: evoluce vs. paměť Základní rozdělení algoritmů algoritmy využívající evoluci řešení v populaci vybírána a reprodukována s pomocí operátorů (zejména: mutace a křížení) př. genetické algoritmy, evoluční strategie algoritmy s pamětí (blackboard) řešení v populaci se účastní na konstrukci paměti, pomocí níž se vytváří noví jedinci př. feromonová matice (ACO), pravděpodobnostní model učení (EDA) Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 65 8. ledna 2021 Společné koncepty metaheuristik s populacemi: generování počáteční populace Náhodné generování Sekvenční diversifikace řešení generována postupně s maximální odlišností př. simple sequential inhibition (SSI) process každé následující řešení generováno tak, aby vzdálenost od všech předchozích řešení byla minimálně ∆ výpočetně náročné Paralelní diversifikace řešení generována nezávisle paralelně se snahou o celkovou maximální odlišnost řešení v populaci může být obtížnější než řešení původního problému! Heuristická inicializace jednotlivá řešení generována libovolnými heuristickými algoritmy (např. lokální prohledávání) nebezpečí v malé odlišnosti řešení v populaci Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 66 8. ledna 2021 Společné koncepty: podmínky ukončení Statická procedura konec prohledávání předem znám př. pevný počet iterací limit na CPU zdroje, maximální počet vyhodnocení účelové funkce Adaptivní procedura konec prohledávání předem neznámý př. pevný počet iterací bez zlepšení (populace), vypočítáno dostatečně kvalitní řešení, malá odlišnost řešení v populaci Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 67 8. ledna 2021 Základní koncepty evolučních algoritmů Reprezentace populace: množina řešení (cca 20-100) chromozom/jedinec: zakódované řešení gen: rozhodovací proměnná v rámci řešení alely: možné hodnoty rozhodovací proměnné Vhodnost (fitness) používaný termín pro účelovou funkci Strategie výběru rodičů (řešení) pro vytváření další populace Strategie reprodukce křížení a mutace: operace vytvářející nové jedince (potomky) Strategie náhrady výběr jedinců do nové populace Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 68 8. ledna 2021 Kostra evolučních algoritmů generování(P0); (generuj počáteční populaci) t = 0; while není splněna podmínka ukončení do vyhodnocení(Pt); Pt = výběr(Pt); (strategie výběru) Pt = reprodukce(Pt); (strategie reprodukce) vyhodnocení(Pt); Pt+1 = nahrazení(Pt, Pt); (strategie náhrady) t = t + 1; end while výstup: nejlepší nalezené/á řešení Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 69 8. ledna 2021 Evoluční algoritmy Na různých školách se vyvíjely různé typy evolučních algoritmů: Genetické algoritmy (Holland, Michigan, USA) Evoluční strategie (Rechenberg & Schwefel, Berlín, Německo) Evoluční programování (Fogel, San Diego, USA) spojitá optimalizace menší použítí pro velkou podobnost s evolučními strategiemi Genetické programování (Koza, Stanford, USA) jedinci jsou programy (nelinerální reprezentace založená na stromech) automatické generování programů řešících danou úlohu př. nalezení programu odpovídajícího matematické rovnici minimalizace odchylek součtů čtverců od testovacích bodů Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 70 8. ledna 2021 Genetické algoritmy Autor: Holland, Michigan, USA, sedmdesátá léta Prvotní reprezentace: binární dnes i další typy Typicky použití operátoru křížení nad dvěma řešeními Mutace využívána pro zlepšení diversifikace Pevná pravděpodobnost mutace pm a křížení pc Náhrada bývá generační: rodiče systematicky nahrazeni potomky Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 71 8. ledna 2021 Evoluční strategie (ES) Autoři: Rechenberg & Schwefel, Berlín, Německo, 1964 Většinou pro: spojité optimalizace, vektory reálných hodnot Křížení využito zřídka Obvykle: náhrada nejlepšími jedinci (elitismu) Populace rodičů velikosti µ, populace potomků velikosti λ ≥ µ inicializace populace µ jedinců vyhodnocení µ jedinců repeat generuj λ potomků z µ rodičů vyhodnocení λ potomků náhrada populace µ jedinců rodiči a potomky until splněna podmínka ukončení výstup: nejlepší jedinec nebo nalezená populace (1 + 1)-ES: jednoduchá verze, 1 rodič nahrazen 1 potomkem (µ + λ)-ES opakuj λ-krát: (náhodný výběr rodiče, vygenerován potomek) seřazení µ rodičů a λ potomků dle vhodnosti, náhrada nejlepšími (µ, λ)-ES: pro novou populaci se vybírá jen mezi λ potomky Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 72 8. ledna 2021 Výběr ruletovým kolem (roulette wheel selection) Výběr ruletovým kolem nejpoužívanější strategie výběru fi vhodnost jedince i v populaci pravděpodobnost výběru jedince dána jako pi = fi /( n j=1 fj ) analogie: ruletové kolo s díly pro všechny jedince v populaci velikost dílu ruletového kola pro jedince odpovídá pi Problémy: příliš velká snaha vybírat kvalitní jedince ⇒ předčasná konvergence Jedinci 1 2 3 4 5 6 7 Vhodnost 1 1 1 1.5 1.5 3 3 Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 73 8. ledna 2021 Pravděpodobnostní univerzální vzorkování (stochastic universal sampling) Jedinci 1 2 3 4 5 6 7 Vhodnost 1 1 1 1.5 1.5 3 3 Pravděpodobnostní univerzální vzorkování (řeší problémy rulet.kola) u ruletového kola dáme µ rovnoměrně rozložených ukazatelů jedno otočení ruletového kola vybírá µ jedinců Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 74 8. ledna 2021 Turnajový výběr, výběr rankováním Turnajový výběr náhodný výběr k jedinců turnaj: z těchto k jedinců je výbrán nejlepší jedinec pro výběr µ jedinců aplikujeme turnaj µ-krát Výběr rankováním (rank-based selection) pro každého jedince spočítán rank a dle něj jsou vybíráni jedinci rank může např. škálovát linerárně se závislostí na snaze o výběr nejlepšího jedince rank použit pro výpočet pravděpodobnosti a aplikován stejně jako u ruletového kola Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 75 8. ledna 2021 Mutace Vlastnosti mutace operátor mutace mění jedince v populaci a způsobí jeho malou změnu pravděpodobnost mutace genu pm ∈ [0.001, 0.01] př. inicializace pm na 1/k, kde k je počet genů (rozhodovacích proměnných), tj. v průměru zmutovaná 1 proměnná Mutace v binární reprezentaci prohození (flip) hodnoty binární proměnné Mutace v diskrétní reprezentaci změna hodnoty prvku za jinou hodnotu v abecedě Mutace v permutacích vložení, výměna, inverze hodnot(y) př. viz permutační okolí pro rozvrhovací problémy (1.přednáška) Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 76 8. ledna 2021 Křížení Vlastnosti křížení binární (někdy n-ární) operátor cíl: zdědit vlastnosti rodičů potomkem pravděpodobnost křížení rodičů pc ∈ [0, 1], běžně pc ∈ [0.45, 0.95] Linerární reprezentace (vyjma permutací) 1-bodové křížení (1-point crossover) podle vybrané pozice k v potomcích prohozeny hodnoty dvou rodičů 10011100|1001 1-bodové křížení 10011100|0111 rodiče: | ————————> potomci: | 01110010|0111 01110010|1001 2-bodové (a n-bodové) křížení vybrány dvě (n) pozice a provedeno prohození hodnot 100|1110010|01 2-bodové křížení 100|1001001|01 rodiče: | ————————> potomci: | | 011|1001001|11 011|1110010|11 Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 77 8. ledna 2021 Křížení (pokračování) Linerární reprezentace (vyjma permutací) uniformní křížení (uniform crossover) jedinci kombinováni bez ohledu na velikost segmentů každý gen potomka náhodně vybrán z rodiče každý rodič rovnoměrně přispívá ke generování potomků stejně 111111111111 uniformní křížení 100111000111 rodiče: ————————> potomci: 000000000000 011000111000 Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 78 8. ledna 2021 Křížení (dokončení) Reprezentace permutacemi křížení je složitější, jedince nelze takto jednoduše kombinovat, protože každá alela (hodnota) se musí výskytnout v jedinci právě jednou (používány různé formy mapování) Křížení dané pořadím (Order crossover, OX) vybrány náhodně dva body křížení z rodiče 1 hodnoty mezi nimi zkopírovány na stejné pozice v potomkovi z rodiče 2 začneme od druhého bodu křížení vybírat prvky, které již nebyly vybrány z rodiče 1, a dávame je do potomka od 2. bodu křížení Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 79 8. ledna 2021 Cvičení: strategie reprodukce Plánování úloh na jednom stroji bez překrytí v čase každá úloha má určen: nejdřívější čas provádění, dobu provádění minimalizujeme čas dokončení poslední úlohy Reprezentace jedince permutace úloh určuje pořadí provádění na stroji pozor: nejdřívější čas příchodu nutno dodržet Křížení 2 jedinci: 12|34567|89, 13|57924|68 potomci pomocí OX křížení: 365792481, 923456781 Mutace vložení úlohy 123456789 → 124567389 vyměna úloh 123456789 → 127456389 Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 80 8. ledna 2021 Strategie náhrady Vybíráme mezi rodiči a potomky další populaci Extrémní strategie náhrady (nepříliš používané) úplná náhrada (generational replacement) potomky bude nahrazena systematicky celá populace rodičů ztrácíme i nejlepší jedince náhrada jednotlivce (steady-state replacement) bude vytvořen pouze jediný potomek, který nahradí např. nejhoršího jedince populace tj. degradace genetických algoritmů, otázka smyslu práce s populací Používány strategie na pomezí mezi těmito krajními přístupy, např. náhrada pevného množství jedinců pro náhradu vybíráno λ jedinců populace při velikosti populace µ 1 < λ < µ elitářský model výběr nejlepších jedinců mezi rodiči a potomky rychlá avšak předčasná konvergence Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 81 8. ledna 2021 Inteligence hejna (swarm intelligence) Algoritmy inspirované skupinových chováním druhů jako jsou mravenci, včely, vosy, termiti, ryby nebo ptáci Původ v sociální chování těchto druhů při hledání potravy Základní charakteristika algoritmů jedinci jsou jednodušší nesofistikovaní agenti jedinci kooperují nepřímo pomocí média Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 82 8. ledna 2021 Optimalizace mravenčí kolonie (Ant Colony Optimization, ACO) Myšlenky inspirující algoritmus mravenčí kolonie schopna najít nejkratší cestu mezi dvěma body mravenci během cesty nechávají na zemi chemickou stopu (feromony) feromony vedou mravence v cíli feromony se postupně vypařují Algoritmus inicializace feromonů iterace: konstrukce řešení mravencem, aktualizace feromonů inicialiace feromonové stopy; repeat for každého mravence do konstrukce řešení pomocí feromonové stopy; (aktualizace feromonové stopy:) vypařování; zesílení feromonové stopy; until splněna podmínka ukončení výstup: nejlepší nalezené řešení nebo množina řešení Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 83 8. ledna 2021 Optimalizace mravenčí kolonie (pokračování) Feromonové informace τ typicky jako matice/vektor hodnot obsahující feromonovou stopu př. matice jako reprezentace grafu obsahuje feromony na hranách Vypařování feromonů τij = (1 − ρ)τij realizuje pro každé i, j vypařování feromonů ρ ∈ [0, 1] Zesilování feromonů online aktualizace: τij aktualizováno v každém kroku online pozdržená aktualizace: τ aktualizováno po nalezení úplného řešení jedním mravencem př. čím lepší řešení, tím více feromony zesíleny off-line aktualizace: τ aktualizováno po nalezení úplného řešení všemi mravenci nejpopulárnější přístup př. aktualizace feromonů dle kvality feromony aktualizovány dle nejlepšího (nebo několika nejlepších) řešení ∀i, j v řešení: τi,j = τi,j + ∆ Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 84 8. ledna 2021 Optimalizace mravenčí kolonie pro problém obchodního cestujícího inicialiace feromonové stopy; repeat for každého mravence do (konstrukce řešení pomocí feromonové stopy) S = {1, 2, . . . , n}; (množina měst na výběr); náhodně vyber město i; S = S − {i}; repeat vyber město j s pravděpodobnosti pij ; S = S − {j}; i = j; until S = ∅ end for (aktualizace feromonové stopy) for i, j ∈ [1, n] do τij = (1 − ρ)τij ; (vypařování) for i, j v nejlepším řešení iterace do τij = τij + ∆; (zesílení feromonů) until splněna podmínka ukončení výstup: nejlepší nalezené řešení nebo množina řešení Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 85 8. ledna 2021 Pravděpodobnost pij výběru dalšího města na cestě Základní výpočet pravděpodobnosti: pij = τij k∈S τik ∀j ∈ S př. jsme ve městě 1 (i = 1) a můžeme pokračovat do měst S = {2, 3, 4, 5, 6} τ12 = 3, τ13 = 2, τ14 = 2, τ15 = 1, τ16 = 2 p12 = 3 3+2+2+1+2 = 0.3, p13 = 2 3+2+2+1+2 = 0.2, . . . Problémově závislá heuristika: využití hodnot ηij = 1/dij , kde dij udává vzdálenost mezi městy i, j pij = τα ij × ηβ ij k∈S τα ik × ηβ ik ∀j ∈ S kde α a β určují relativní vliv feromonové hodnoty a heuristické hodnoty η α = 0: stochastický hladový algoritmus β = 0: základní výpočet pravděpodobností pouze pomocí feromonů Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 86 8. ledna 2021 Cvičení: ACO Aplikujte ACO algoritmus na problém obchodního cestujícího s n městy se vzdálenosti mezi nimi určenou úplným hranově ohodnoceným grafem. Předpokládejte, že pracujete s m mravenci iniciální feromonová stopa je matice, jejíž hodnoty jsou nepřímo úměrné vzdálenosti mezi městy, při náhodném výběru měst vyberte vždy město s nejmenším indexem, koeficient vypařování je ρ = 0.01, koeficient pro zesílení feromonů je ∆ = 1 a aplikujte k kroků algoritmu. Hana Rudová, IV126, FI MU: Metaheuristiky s populacemi 87 8. ledna 2021 Plánování: reprezentace problému 8. ledna 2021 16 Úvod 17 Konceptuální model 18 Množinová reprezentace 19 Klasická reprezentace Zdroj: Roman Barták, přednáška Plánování a rozvrhování, Matematicko-fyzikální fakulta, Karlova univerzita v Praze, 2014. http: // kti. ms. mff. cuni. cz/ ~bartak/ planovani Plánování: příklad Plán: zvedni(C) polož_na(C,stůl) zvedni(B) polož_na(B,D) zvedni(C) polož_na(C,B) Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 89 8. ledna 2021 Plánování v kostce Vstup: počáteční (současný) stav světa popis akcí schopných měnit stav světa požadovaný stav světa Výstup: seznam akcí (plán) Příklady problémů a velikost řízení výtahu: 6.92 · 1019 dosažitelných stavů automatizace skleníku: 1.68 · 1021 dosažitelných stavů logistika dopravy: 6.31 · 10218 dosažitelných stavů Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 90 8. ledna 2021 Plánování v kostce: klasické plánování Stavové proměnné x ∈ {a, b, c}, y ∈ {a, b}, z ∈ {a, b, c} Počáteční stav {x → a, y → a, z → a} Cílový stav {x → c, z → b} Akce a.k.a. operátory a1 : x → a, z → c 4 → z := b (akce s cenou 4) a2 : x → a, y → a 3 → y := b, z := c . . . Problém nalézt posloupnost akcí, které transformují počáteční stav na stav, který je konzistentní s cílovým stavem účelová funkce: součet ceny akcí Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 91 8. ledna 2021 Plánování v kostce: STRIPS plánování (varianta klasického plánování) Všechny proměnné mají doménu {T, F} V podmínce akce a v cílovém stavu pouze v → T Notace a : x → T, y → T 5 → w := F, y := F, z := T zapsaná jako precond(a) = {x, y}, effects+(a) = {z}, effects−(a) = {w, y}, cost(a) = 5 Příklad: zvedneme ležící kostku B nahoru precond(zvedni-B) = {lezi-B}, effects+ (zvedni-B) = {nahore-B}, effects− (zvedni-B) = {lezi-B} Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 92 8. ledna 2021 Plánování a rozvrhování Plánování (planning) rozhodování, jaké akce jsou potřeba pro dosažení daných cílů složitost: často horší než NP-úplné rozhodnutelnost? Rozvrhování (scheduling) rozhodování, jak zpracovat dané akce použitím omezených zdrojů a času složitost: typicky NP-úplné Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 93 8. ledna 2021 Plánování: rozhodnutelnost Problémy 1 PlanSAT: Existuje plán, který řeší zadaný plánovací problém? 2 BoundedPlanSAT: Existuje plán délky k nebo kratší, který řeší zadaný plánovací problém? Oba problémy rozhodnutelné pro klasické plánování ⇐ počet stavů je konečný Přidání funkčních symbolů do jazyka počet stavů je nekonečný PlanSAT částečně rozhodnutelný existuje algoritmus, který skončí pro řešitelné problémy pro neřešitelné problémy nemusí skončit BoundedPlanSAT zůstává rozhodnutelný Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 94 8. ledna 2021 Plánování: obsah Klasické plánování Konceptuální model Reprezentace problému Plánovací algoritmy plánování se stavovým prostorem plánování s prostorem plánů Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 95 8. ledna 2021 Formalizace: konceptuální model Plánování se zabývá volbou a organizací akcí, které mění stav systému Systém Σ modelující stavy a přechody: množina stavů S (rekurzivně spočetná) množina akcí A (rekurzivně spočetná) plánovač kontroluje akce! no-op (prázdná akce) množina událostí E (rekurzivě spočetná) událost mimo kontrolu plánovače! neutrální událost ε přechodová funkce γ : S × A × E → P(S) někdy se akce a události aplikují odděleně γ : S × (A ∪ E) → P(S) Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 96 8. ledna 2021 Cíle plánování Cílem plánování je zjistit, jaké akce a na které stavy se mají aplikovat, abychom za dané situace dosáhli požadovaných cílů. Co je cílem plánování? cílový stav nebo množina cílových stavů splnění dané podmínky nad posloupností stavů, přes které systém prochází např. stavy, kterým se vyhnout, nebo stavy, které se musí navštívit optimalizace dané objektivní funkce nad posloupností stavů např. maximum nebo součet ohodnocení stavů Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 97 8. ledna 2021 Příklad Σ = (S, A, E, γ) S = {s0, . . . , s5} E = {} resp. {ε} A = {move1, move2, put, take, load, unload} γ: obrázek počáteční stav: s0 cíl: s5 Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 98 8. ledna 2021 Jak to funguje? Plánovač generuje plány Řadič se stará o jejich realizaci pro daný stav určí akci k provedení pozorování převádějí reálný stav na modelovaný stav Dynamické plánování umožňuje přeplánování na základě aktuálního stavu provádění Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 99 8. ledna 2021 Zjednodušení modelu Systém je konečný Systém je „plně pozorovatelný” máme úplné informace o stavu systému Systém je deterministický ∀s ∈ S ∀u ∈ (A ∪ E) : |γ(s, u)| ≤ 1 Systém je statický množina událostí je prázdná, tj. E = ∅ Cíle jsou omezené cílem je dosažení některého stavu z množiny cílových stavů Plány jsou sekvenční plánem je úplně uspořádaná posloupnost akcí Čas je implicitní akce i události jsou instantní (okamžité, tj. nemají žádné trvání) Plánujeme offline stav systému se nemění v průběhu plánování Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 100 8. ledna 2021 Klasické plánování (STRIPS plánování) Pracujeme s deterministickým, statickým, konečným a plně pozorovatelným stavovým modelem s omezenými cíli a implicitním časem Σ = (S, A, γ). Plánovací problém P = (Σ, s0, g): s0 je počáteční stav g charakterizuje cílové stavy Řešením plánovacího problému P je posloupnost akcí a1, a2, . . . , ak odpovídající posloupnosti stavů s0, s1, . . . , sk takové, že 1 si = γ(si−1, ai ), 2 sk splňuje g Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 101 8. ledna 2021 Zjednodušení? Plánování ve zjednodušeném modelu je „pouhé” hledání cesty v grafu. Je to opravdu tak jednoduché? 5 míst, 3 hromady na každém místě, 100 kontejnerů, 3 roboti ⇒ 10277 stavů, tj. 10190 krát více než jsou největší odhady počtu částic ve vesmíru Co tedy potřebujeme? Jak tedy reprezentovat stavy a akce tak, aby nebylo třeba vyjmenovat množiny A a S? nemůžeme přímo pracovat s 10277 stavy ... Jak efektivně hledat řešení plánovacího problému? Jak najít cestu v grafu s 10277 uzly? Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 102 8. ledna 2021 Klasické plánování: množinová reprezentace Stav systému je popsán množinou výroků např. {onground, at2} Každá akce je syntaktický výraz specifikující: jaké výroky musí patřit do stavu, aby na něj byla akce aplikovatelná např. take: {onground} jaké výroky akce přidá a jaké výroky smaže, aby vytvořila nový stav např. take: {onground}− , {holding}+ Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 103 8. ledna 2021 Množinová reprezentace: příklad L = {onground, onrobot, holding, at1, at2} s0 = {onground, at2} g = {onrobot} load = ( {holding, at1}, {holding}, {onrobot}) take, move1, load, move2 je plán, ale není minimální (není nutné move2, v g není podmínka na location) Pozor na velikost množinové reprezentace Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 104 8. ledna 2021 Klasická reprezentace Klasická reprezentace zobecňuje množinovou reprezentaci směrem k predikátové logice: stavy jsou množiny logických atomů (místo výroků u množ.rep.), které jsou v dané interpretaci buď pravda nebo nepravda akce jsou reprezentovány plánovacími operátory, které mění pravdivostní hodnotu těchto atomů Přesněji: L (jazyk) je konečná množina predikátových symbolů a konstant (nemáme funkce!) atom je predikátový symbol s argumenty např. on(c3, c1) můžeme používat proměnné např. on(x,y) Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 105 8. ledna 2021 Klasická reprezentace: reprezentace stavů Stav je množina instanciovaných atomů (bez proměnných). Opět jich je konečně mnoho! Pravdivostní hodnota některých atomů se mění flexibilní atomy (fluent) např. at(r1,loc2) Některé atomy nemění svoji pravdivostní hodnotu s různými stavy neměnné atomy (rigid) např. adjacent(loc1,loc2) Předpoklad uzavřeného světa (closed world assuption): atom, který není ve stavu explicitně uveden, neplatí! Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 106 8. ledna 2021 Klasická reprezentace: plánovací operátory Operátor o je trojice: (name(o), precond(o), effects(o)) name(o): jméno operátoru ve tvaru n(x1, . . . , xk) n: symbol operátoru (jednoznačný pro každý operátor) x1, . . . , xk : symboly proměnných (parametry operátoru) musí obsahovat všechny symboly proměnných v operátoru! precond(o): předpoklady literály, které musí být splnitelné, aby šlo operátor použít effects(o): důsledky literály, které se stanou pravdivými aplikací operátoru nesmí být něměnné atomy! Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 107 8. ledna 2021 Klasická reprezentace: akce Akce jsou plně instanciované operátory – za proměnné jsou dosazeny konstanty Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 108 8. ledna 2021 Klasická reprezentace: aplikace akce Notace: S+ = {pozitivní atomy v S} S− = {atomy, jejichž negace je v S} Akce a je použitelná na stav s právě když precond+(a) ⊆ s ∧ precond− (a) ∩ s = ∅ Výsledkem aplikace akce a na s je γ(s, a) = (s − effects− (a)) ∪ effects+ (a) Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 109 8. ledna 2021 Klasická reprezentace: plánovací doména Nechť L je jazyk a O je množina operátorů. Plánovací doména Σ nad jazykem L a s operátory O je trojice (S, A, γ): stavy S ⊆ P({všechny instanciované atomy nad L}) akce A = {všechny instanciované operátory z O nad L} akce a je použitelná na stav s, pokud precond+ (a) ⊆ s ∧ precond− (a) ∩ s = ∅ přechodová funkce γ: γ(s, a) = (s − effects− (a)) ∪ effects+ (a), je-li a použitelná na s S je uzavřená vzhledem ke γ pokud s ∈ S, potom pro každou akci a aplikovatelnou na s platí γ(s, a) ∈ S Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 110 8. ledna 2021 Klasická reprezentace: plánovací problém Plánovací problém P je trojice (Σ, s0, g): Σ = (S, A, γ) je plánovací doména s0 je počáteční stav, s0 ∈ S g ⊆ L je množina instanciovaných literálů stav s splňuje g právě tehdy, když g+ ⊆ s ∧ g− ∩ s = ∅ Sg = {s ∈ S | s splňuje g} je množina cílových stavů Zápis plánovacího problému je trojice (O, s0, g) Plán π je posloupnost akcí a1, a2, . . . , ak Plán π je řešením P, právě když γ(s0, π) splňuje g Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 111 8. ledna 2021 Klasická reprezentace: ukázka plánu Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 112 8. ledna 2021 Cvičení Navrhněte množinovou a klasickou reprezentaci pro svět kostek. Svět kostek (the blocks world) nekonečně velký stůl, konečný počet kostek poloha kostky na stole nás nezajímá kostka může ležet buď na stole nebo na jiné kostce při plánování chceme přesouvat kostky tak, že v dané chvíli můžeme držet maximálně jednu kostku Příklad: Hana Rudová, IV126, FI MU: Plánování: reprezentace problému 113 8. ledna 2021 Plánování se stavovým prostorem 8. ledna 2021 20 Dopředné plánování 21 Zpětné plánování 22 Doménově závislé plánování Zdroj: Roman Barták, přednáška Plánování a rozvrhování, Matematicko-fyzikální fakulta, Karlova univerzita v Praze, 2014. http: // kti. ms. mff. cuni. cz/ ~bartak/ planovani Plánování se stavy Prohledávaný prostor odpovídá stavovému prostoru plánovacího problému uzly odpovídají stavům hrany odpovídají stavovým přechodům pomocí akcí cílem je najít cestu mezi počátečním stavem a některým koncovým stavem Typy prohledávání dopředné (forward search) zpětné (backward search) liftovaná verze STRIPS problémově závislé (svět kostek) Poznámka: algoritmy budeme uvádět pro klasickou reprezentaci Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 115 8. ledna 2021 Dopředné plánování Začínáme v počátečním stavu a jdeme k některému cílovému stavu Je potřeba umět: rozhodnout, zda je daný stav cílový nebo ne najít množinu akcí aplikovatelných na daný stav vypočítat stav, do kterého se dostaneme aplikací akce Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 116 8. ledna 2021 Algoritmus dopředného plánování vstup: (O, s0, g) Pozn. používáme spojení plánů, např. π1.π2, a.π, π.a s = s0; π = prázdný plán; loop if s splňuje g then return π; E = {a | a je instance operátoru v O bez proměnných a precond(a) je pravdivé v s}; if E = ∅ then return failure; nedeterministicky vyber akci a ∈ E; s = γ(s, a); π = π.a; (π rozšíříme o a) Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 117 8. ledna 2021 Dopředné plánování: příklad {belong(crane1, loc1), adjacent(loc2,loc1), holding(crane1,c3), unloaded(r1), at(r1,loc2), occupied(loc2), ...} a occupied(loc1) nepatří do tohoto stavu move(r1, loc2, loc1) {belong(crane1, loc1), adjacent(loc2,loc1), holding(crane1,c3), unloaded(r1), at(r1,loc1), occupied(loc1), ...} load(crane1, loc1, c3, r1) {belong(crane1, loc1), adjacent(loc2,loc1), empty(crane1), loaded(r1,c3), at(r1,loc1), occupied(loc1), ...} Cíl = {at(r1, loc1), loaded(r1, c3)} splněn Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 118 8. ledna 2021 Dopředné plánování: vlastnosti Procedura dopředného plánování je korektní pokud vrátí nějaký plán, potom je řešením stačí si uvědomit, že s = γ(s0, π) Procedura dopředného plánování je úplná pokud existuje plán, potom ho alespoň jedna z nedeterministických větví najde indukcí podle délky plánu v každém kroku má algoritmus šanci zvolit správnou akci (pokud v přechozích krocích volil akce z plánu) Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 119 8. ledna 2021 Deterministické implementace Algoritmus dopředného prohledávání můžeme implementovat deterministicky: korektnost, úplnost, paměť? prohledávání do šířky korektní, úplné, ale paměťově náročné prohledávání do hloubky korektní, úplnost lze zajistit kontrolou cyklů (stav se na cestě neopakuje) A* algoritmus nejčastěji používaný přístup je třeba vhodná heuristika, která směruje k nalezení kvalitního řešení v daném uzlu stromu odhadujeme celkovou cenu jako f (n) = g(n) + h(n) a jdeme větví s minimálním odhadem g(n) aktuální cena uzlu (např. dosavadní délka cesty) h(n) odhad ceny pro výpočet úplného řešení (heuristika) pro optimum nutná přípustná heuristika: cena nikdy nenadhodnocena př. vzdálenost přímé cesty z aktuálního bodu do cíle podrobně viz např. PB016 Umělá inteligence I Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 120 8. ledna 2021 Větvení V čem je problém dopředného prohledávání? Vysoký větvící faktor: počet možností k výběru to vadí u determinismu, který může ztrácet čas zkoušením irelevantních akcí Řešení heuristika doporučující výběr akce ořezání prohledávacího prostoru Např. pokud plány π1 a π2 dosáhly stejného stavu, potom víme, že také plány π1π3 a π2π3 dosáhnou stejného stavu. Delší z plánů π1 a π2 tedy nemusíme rozvíjet. Je potřeba pamatovat si všechny navštívené stavy . Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 121 8. ledna 2021 Cvičení Navrhněte množinovou a klasickou reprezentaci pro svět kostek. Svět kostek (the blocks world) nekonečně velký stůl, konečný počet kostek poloha kostky na stole nás nezajímá kostka může ležet buď na stole nebo na jiné kostce při plánování chceme přesouvat kostky tak, že v dané chvíli můžeme držet maximálně jednu kostku Příklad: Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 122 8. ledna 2021 Svět kostek: klasická reprezentace Konstanty bloky: a,b,c,d,e Predikáty ontable(x) kostka x je na stole on(x,y) kostka x je na kostce y clear(x) kostka x na sobě nic nemá holding(x) robotova ruka drží kostku x handempty robotova ruka nic nedrží Operátory Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 123 8. ledna 2021 Svět kostek: množinová reprezentace Výroky pro 5 kostek máme 36 výroků ontable-a (5x) kostka a je na stole on-c-a (20x) kostka c je na kostce a clear-c (5x) kostka c na sobě nic nemá holding-d (5x) robotova ruka drží kostku d handempty (1x) robotova ruka nic nedrží Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 124 8. ledna 2021 Cvičení: výměna hodnot proměnných Plánovací problém: s0 = {value(v1,3), value(v2,5), value(v3,0)} g = {value(v1,5), value(v2,3)} assign(v, w, x, y) precond: value(v, x), value(w, y) effects: ¬ value(v, x), value(v, y) Otázky: Kolik iterací poběží algoritmus dopředného prohledávání minimálně? Kolik existuje minimálních plánů a které to jsou? Můžeme provést assign(v1,v1,3,3)? Můžeme provést assign(v1,v2,3,3)? Jakým způsobem je prohledáván stavový prostor při prohledávání do šířky? Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 125 8. ledna 2021 Zpětné plánování Začínáme s cílem (pozor to není stav, ale reprezentace množiny stavů!) a jdeme přes podcíle k počátečnímu stavu Je potřeba umět: zjistit, zda daný stav odpovídá cíli pro daný cíl najít relevantní akce vypočítat podcíl umožňující aplikovat danou akci Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 126 8. ledna 2021 Zpětné plánování: relevantní akce Příklad: cíl: {on(a,b), on(b,c)} akce stack(a,b) je relevantní její „zpětnou aplikací” dostaneme nový cíl: {holding(a), clear(b), on(b,c)} Akce a je relevantní pro cíl g právě když: akce přispívá do g: g ∩ effects(a) = ∅ efekty akce nejsou v konfliktu s g: g− ∩ effects+ = ∅ g+ ∩ effects− = ∅ Regresní (zpětná) množina cíle g pro (relevantní) akci a: γ−1(g, a) = (g − effects(a)) ∪ precond(a) Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 127 8. ledna 2021 Algoritmus zpětného plánování vstup: (O, s0, g) π = prázdný plán; loop if s0 splňuje g then return π; A = {a | a je instance operátoru v O bez proměnných a γ−1(g, a) je definováno}; if A = ∅ then return failure; nedeterministicky vyber akci a ∈ A; π = a.π; (a je poslední akcí vzniklého plánu π) g = γ−1(g, a); Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 128 8. ledna 2021 Zpětné prohledávání: příklad Cíl = {at(r1, loc1), loaded(r1,c3)} load(crane1, loc1, c3, r1) {at(r1, loc1), belong(crane1, loc1), holding(crane1, c3), unloaded(r1)} move(r1, loc2, loc1) {belong(crane1, loc1), holding(crane1,c3), unloaded(r1), adjacent(loc2, loc1), at(r1, loc2), ¬ occupied(loc1)} Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 129 8. ledna 2021 Zpětné prohledávání: vlastnosti Procedura zpětného prohledávání je korektní a úplná Můžeme ji implementovat deterministicky pro úplnost potřebujeme detekci cyklů mějme (g1, . . . , gk ) posloupnost cílů: pokud ∃i < k gi ⊆ gk , pak můžeme prohledávání této cesty ukončit Větvení může být menší než u prohledávání dopředu (zacílení) pořád ale zbytečně velké Chceme-li, aby byl robot v pozici loc51, do které existují cesty z loc1, . . . , loc50, dostaneme 50 možných podcílů. Nám je ale pro splnění cíle jedno, odkud robot příjel! Částečné instanciování akcí (místo úplného) dále zmenší velikost větvení, tzv liftování (lifting). Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 130 8. ledna 2021 Zpětné plánování: liftovaná verze vstup: (O, s0, g) π = prázdný plán; loop if s0 splňuje g then return π; A = {(o, θ) | o vznikne přejmenováním proměnných operátoru v O, substituce θ je MGU atomu v g a atomu v effects(o), a γ−1(θ(g), θ(o)) je definováno}; if A = ∅ then return failure; nedeterministicky vyber pár (o, θ) ∈ A; π = spojení θ(o) a θ(π); g = γ−1(θ(g), θ(o)); Poznámky: o je kopie operátoru s přejmenovanými (=novými) proměnnými MGU = největší společný unifikátor, tj. nejobecnější substituce atomů použití volných proměnných zmenšuje větvení, ale komplikuje detekci cyklů Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 131 8. ledna 2021 Zpětné plánování v liftované verzi: příklad Cíl: at(robot,loc1) Operátor: move(r, l, m) precond: adjacent(l, m), at(r, l), ¬occupied(m) effects: at(r, m), occupied(m), ¬occupied(l), ¬at(r, l) Akce: move(robot, l, loc1) l= ? (příliš mnoho voleb zvětšuje faktor větvení) Vstup (O, s0, g) = ({move(r, l, m)}, s0, {at(robot,loc1)}) nechť s0 nesplňuje cíl Prvek A: (o, θ) = (move(r1, l1, m1),{r1 → robot, m1 → loc1}) θ je MGU atomu v cíli at(robot,loc1) a atomu at(r1, l1) v effects(o) Plán π = move(robot,l1,loc1) g = γ−1 (θ(g), θ(o)) = {adjacent(l1,loc1), at(robot,l1), ¬occupied(loc1)} Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 132 8. ledna 2021 STRIPS Dosud probrané plánovací algoritmy sdílejí stejný problém – jak zlepšit efektivitu redukcí prohledávacího prostoru STRIPS algoritmus redukuje prohledávaný prostor zpětného plánování, a to takto: z podcílů řeší vždy jen část odpovídající předpokladům poslední přidané akce tj. místo γ−1 (s, a) se jako nový cíl použije precond(a) vede k neúplnosti algoritmu pokud aktuální stav splňuje všechny předpoklady operátoru, daný operátor se použije a tento závazek nebude rušen při backtrackingu Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 133 8. ledna 2021 STRIPS algoritmus Originální algoritmus STRIPS je liftovanou verzí níže popsaného algoritmu function Ground-STRIPS(O, s, g) π = prázdný plán; loop if s splňuje g then return π; A = {a | a je instance operátoru v O bez proměnných a a je relevantní pro g}; if A = ∅ then return failure; nedeterministicky vyber akci a ∈ A; π = Ground-STRIPS(O, s, precond(a)); if π = failure then return failure; (pokud jsme zde, pak π dosáhlo precond(a) z s) s = γ(s, π ); ∗ (s nyní splňuje precond(a)) s = γ(s, a); π = π.π .a; ∗ g2 = (g − (effects)(a2)) ∪ precond(a2) π = a6, a4 je plán pro cíl precond(a2) s = γ(γ(s0, a6), a4) je stav splňující precond(a2) Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 134 8. ledna 2021 Sussmanova anomálie Pravděpodobně nejznámější problém, který STRIPS neumí efektivně řešit (najde pouze redundantní plány) Svět kostek Plán vytvořený STRIPSem může vypadat takto: unstack(c,a), putdown(c), pickup(a), stack(a,b) nyní jsme splnili cíl on(a,b) Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 135 8. ledna 2021 Podrobněji: plán vytvořený STRIPSem pro on(a,b) Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 136 8. ledna 2021 Dokončení: Sussmanova anomálie Pravděpodobně nejznámější problém, který STRIPS neumí efektivně řešit (najde pouze redundantní plány) Svět kostek Plán vytvořený STRIPSem může vypadat takto: unstack(c,a), putdown(c), pickup(a), stack(a,b) nyní jsme splnili cíl on(a,b) unstack(a,b), putdown(a), pickup(b), stack(b,c) nyní jsme splnili cíl on(b,c), ale musíme se vrátit k on(a,b) pickup(a), stack(a,b) podtržené akce se mohou vyřadit tj. postupně řešíme cíle on(a,b) a on(b,c), při tom si ale on(a,b) pokazíme Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 137 8. ledna 2021 Jak na svět kostek? Řešení Sussmanovy anomálie prolínání plánů plánování v prostoru plánů použití doménově závislé informace Kdy má problém ve světě kostek řešení? v cíli nesmí být kostky, které nejsou v počátečním stavu kostka nesmí najednou stát na dvou jiných kostkách . . . Jak to řešení najdeme? Celkem snadno a rychle! dámě všechny kostky (samostatně) na stůl postavíme požadované věže S dalšími znalostmi to můžeme udělat ještě lépe! Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 138 8. ledna 2021 Doménové znalosti (pro svět kostek) Kdy musíme pohnout kostkou x? Pokud platí některé z následujících: s obsahuje ontable(x) a g obsahuje on(x,y) s obsahuje on(x,y) a g obsahuje ontable(x) s obsahuje on(x,y) a g obsahuje on(x,z) pro nějaké y=z s obsahuje on(x,y) a y se musí pohnout Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 139 8. ledna 2021 Doménově specifický algoritmus procedure Block-stacking loop if existuje volný blok x tak, že x se musí přesunout and x lze přesunout na místo, ze kterého ho už nemusíme přesouvat then přesuň x na toto místo else if existuje volný blok x tak, že x se musí přesunout then přesuň x na stůl else if cíl splněn then return plán else return failure Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 140 8. ledna 2021 Vlastnosti algoritmu Korektní, úplný, garance ukončení Časová složitost O(n3) lze modifikovat s výslednou složitostí O(n) Často nalezne optimální (nejkratší) řešení delka plánu pro svět kostek je NP-úplná Hana Rudová, IV126, FI MU: Plánování se stavovým prostorem 141 8. ledna 2021 Plánování v prostoru plánů 8. ledna 2021 Zdroj: Roman Barták, přednáška Umělá inteligence II, Matematicko-fyzikální fakulta, Karlova univerzita v Praze, 2014. http: // kti. ms. mff. cuni. cz/ ~bartak/ ui2 Plánování v prostoru plánů: základní myšlenka Princip podobný zpětnému plánování ve stavovém prostoru: začínáme z „prázdného plánu” obsahujícího popis počátečního stavu a cíle přidáváme další akce, které plní dosud nesplněné (otevřené) cíle případně přidáváme vazby mezi již přítomnými akcemi Na plánování se můžeme dívat jako na opravování kazů v částečném plánu přecházíme od jednoho částečného plánu k dalšímu, dokud nenajdeme úplný plán Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 143 8. ledna 2021 Plánování v prostoru plánů: příklad Předpokládejme, že v částečném plánu zatím máme akce take(k1, c1, p1, l1) (jeřáb k1 na l1 vezme c1 z p1) load(k1, c1, r1, l1) (k1 na l1 naloží c1 na r1) Možné úpravy plánu: 1 přidání akce aby šlo použít akci „load”, musí být robot r1 na místě l1 přesuň robota r1 na místo l1 ... move(r1, l, l1) 2 svázání proměnných akce move se týka správného robota na správném místě 3 přidání podmínky uspořádání přesunutí robota se musí uskutečnit před akcí load na pořadí vzhledem k akci „take” ale nezáleží 4 přidání kauzální (příčinné) vazby nová akce byla přidána, aby se robot dostal tam, kam má kauzální vazba mezi „move” a „load” nám zjistí, že mezi těmito akcemi robota někdo zase neodvolá Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 144 8. ledna 2021 Plánování v prostoru plánů: počáteční plán Počáteční stav i cíl zakódujeme jako speciální akce, které jsou v prvotním částečném plánu: akce a0 reprezentuje počáteční stav tak, že nemá žádné předpoklady a počáteční stav je zakódován jako efekt; tato akce je před všemi ostatními akcemi př. effects(a0): in(c1,p1), at(r1,l3) akce a∞ reprezentuje cíl, který je zakódován jako předpoklad, efekt akce je prázdný; tato akce je za všemi ostatními akcemi př. precond(a∞): in(c1,p2) Plánování bude založeno na odstraňování kazů (flaws) v částečném plánu budeme přecházet od jednoho částečného plánu k dalšímu, dokud nenajdeme řešící plán Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 145 8. ledna 2021 Uzly jsou plány Uzly prohledávaného prostoru jsou tvořeny částečnými plány Částečný plán Π je čtveřice (A, <, B, L), kde A je množina částečně instanciovaných plánovacích operátorů {a1, . . . , ak} < je částečné uspořádání na A (ai < aj ) B je množina vazeb tvaru x = y, x = y nebo x ∈ Di L je množina kauzálních vztahů tvaru (ai p → aj ) ai , aj jsou akce uspořádané ai < aj p je výraz, který je efektem ai a předpokladem aj v B jsou vazby svazující příslušné proměnné v p Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 146 8. ledna 2021 Částečný plán: příklad Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 147 8. ledna 2021 Otevřený cíl Otevřený cíl (open goal) je kazem plánu Jedná se o předpoklad p nějakého operátoru b, o kterém zatím nebylo rozhodnuto, jak ho splnit (neexistuje kauzální vazba ai p → b) Odstranění otevřeného cíle p akce b: najdi operátor a (buď již přítomný v plánu nebo nový), který lze použít na splnění p (má p mezi efekty a může být před b) svaž proměnné vytvoř kauzální vazbu Příklad: předpoklad p: at(r1,l1) operátor a: move(r,l,m) svázání proměnných: r/r1, l1/m kauzální vazba: move(r1,l,l1) < load(k1,c1,r1,l1) Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 148 8. ledna 2021 Hrozba Hrozba (threat) je dalším kazem plánu Jedná se o akci, která může porušit kauzální vazbu přesněji, je-li ai p → aj kauzální vazba a akce b ma efekt unifikovatelný s negací p a může se nacházet mezi ai a aj , potom je b hrozbou (může porušit platnost kauzální vazby) pozn. x je unifikovatelné s y? Existuje substituce, která ztotožní x s y Odstranění hrozby lze udělat třemi způsoby: uspořádání b před ai uspořádáním b za aj navázáním proměnných v b tak, že neruší platnost p Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 149 8. ledna 2021 Řešící plán Částečný plán Π = (A, <, B, L) je řešícím plánem pro problém P = (Σ, s0, g), pokud: částečné uspořádání < a vazby B jsou globálně konzistentní v částečném uspořádání nejsou cykly mohu proměnné přiřadit hodnotu z příslušné domény tak, že najdu hodnoty ostatních proměnných splňující B libovolná lineárně uspořádaná posloupnost plně instanciovaných akcí A splňující < a vazby B vede z s0 do stavu splňujícího g Definice nám bohužel přímo nedává výpočtovou proceduru, jak ověřit, zda je plán řešící! Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 150 8. ledna 2021 Řešící plán – konstruktivní pohled Jak efektivně ověřit, zda je daný plán řešící? Tvrzení: Částečný plán Π = (A, <, B, L) je řešící, pokud: nemá žádné kazy, tj. otevřené cíle a hrozby částečné uspořádání < a vazby B jsou globálně konzistentní Důkaz indukcí podle délky plánu {a0, a1, a∞} je řešící plán pro větší množiny akcí vyber libovolnou z možných prvních akcí a spoj ji s akcí a0 Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 151 8. ledna 2021 Algoritmus plánování v prostoru plánů (PSP) function PSP(π): kazy = otevřené-cíle(π) ∪ hrozby(π); if kazy = ∅ then return(π) vyber libovolný kaz φ ∈ kazy zjemnění = odstraň-kaz(φ, π); (vrací množinu možností odstraňujících φ) if zjemnění = ∅ then return(failure); nedeterministicky vyber ρ ∈ zjemnění; π = použij-zjemnění(ρ, π); return(PSP(π )); Determinismus: volba kazu je deterministická musí se odstranit všechny kazy volba zjemnění je nedeterministická v případě neúspěchu se zkouší další alternativa Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 152 8. ledna 2021 Podrobnosti k algoritmu PSP Otevřené cíle lze efektivně zjistit udržováním agendy předpokladů akcí přidání kauzální vazby pro p vyřadí p z agendy Všechny hrozby lze najít prozkoumáním všech trojic akcí (O(n3)) nebo inkrementálně: ai p → aj , efekt ¬p? po přidání akce se zjistí, komu je hrozbou (O(n2 )), a po přidání kauzální vazby se ověří její hrozby (O(n)) Pro odstranění otevřených cílů a hrozeb se používají pouze konzistentní zjemnění plánu konzistence uspořádání buď detekcí cyklů nebo lépe udržováním tranzitivního uzávěru konzistence vztahů B pokud není negace, lze rychle (například pomocí hranové konzistence – základní technika z oblasti programování omezujících podmínek pro zajištění konzistence) je-li přítomna negace, jedná se o NP-úplný problém Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 153 8. ledna 2021 Vlastnosti PSP Algoritmus PSP je korekní a úplný korektnost pokud program skončí, pak v něm není žádný kaz a plán je konzistentní úplnost pokud existuje plán, má algoritmus PSP vždy možnost vybrat ty správné akce Pozor na deterministickou implementaci! prostor plánů není konečný! úplná deterministická procedura musí garantovat prohledání všech plánů dané délky např. iterativní prohlubování (iterative deepening) prohledávání do hloubky s omezenou hloubkou prohledávání prohledávaná hloubka se může postupně zvětšovat Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 154 8. ledna 2021 Algoritmus PoP PoP je konkrétní (a populární) instance algoritmu PSP function PoP(π,agenda) (kde π = (A, <, B, L)) if agenda = ∅ then return(π); vyber libovolný pár (aj , p) a smaž ho z agenda relevant = pokryj-předpoklad(p, π); if relevant = ∅ then return(failure); nedeterministicky vyber akci ai ∈ relevant; L = L ∪ { ai p → aj }; aktualizuj B se svázanými omezeními této kauzální vazby; if ai je nová akce v A then aktualizuj A s ai ; aktualizuj < s (ai < aj ), (a0 < ai < a∞) aktualizuj agenda se všemi předpoklady ai ; for každou hrozbu v ai p → aj nebo kvůli ai do zjemnění = množina možností odstraňující tuto hrozbu; if zjemnění = ∅ then return(failure); nedeterministicky vyber ρ ∈ zjemnění; přidej ρ do < nebo do B; return(PoP(π,agenda)); agenda je množina dvojic (a, p), kde p je otevřený předpoklad akce a nejprve hledá akci ai pro pokrytí nějakého p z agendy ve druhé fázi řeší všechny hrozby, které vznikly přidáním akce ai , resp. kauzální vazby s ai Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 155 8. ledna 2021 Příklad Počáteční stav: At(Home), Sells(OBI, Drill), Sells(Tesco, Milk), Sells(Tesco, Banana) tj. akce Start precond: none effects: At(Home), Sells(OBI, Drill), Sells(Tesco, Milk), Sells(Tesco, Banana) Cíl: Have(Drill), Have(Milk), Have(Banana), At(Home) tj. akce Finish precond: Have(Drill), Have(Milk), Have(Banana), At(Home) effects: none Máme k dispozici následující operátory: Go(l,m) (jdi z místa l do místa m) precond: At(l) effects: At(m), ¬ At(l) Buy(p,s) (na místě s kup p) precond: At(s), Sells(s, p) effects: Have(p) Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 156 8. ledna 2021 Příklad Počáteční plán Operátory: Go(l,m) precond: At(l) effects: At(m), ¬ At(l) Buy(p,s) precond: At(s), Sells(s, p) effects: Have(p) Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 157 8. ledna 2021 Příklad Jediný způsob, jak splnit otevřené cíle Have, je akcemi Buy (které netvoří žádné hrozby) Operátory: Go(l,m) precond: At(l) effects: At(m), ¬ At(l) Buy(p,s) precond: At(s), Sells(s, p) effects: Have(p) Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 158 8. ledna 2021 Příklad Jediný způsob, jak splnit předpoklady Sells je dosazení příslušných konstant Operátory: Go(l,m) precond: At(l) effects: At(m), ¬ At(l) Buy(p,s) precond: At(s), Sells(s, p) effects: Have(p) Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 159 8. ledna 2021 Příklad Jediný způsob, jak splnit otevřené cíle At, je přidání akcí Go přibyly nové hrozby (I., II., III.)! Operátory: Go(l,m) precond: At(l) effects: At(m), ¬ At(l) Buy(p,s) precond: At(s), Sells(s, p) effects: Have(p) Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 160 8. ledna 2021 Příklad Třetí hrozbu můžeme odstranit uspořádáním akce Buy(Drill) před Go(Tesco) to fakticky řeší všechny hrozby Operátory: Go(l,m) precond: At(l) effects: At(m), ¬ At(l) Buy(p,s) precond: At(s), Sells(s, p) effects: Have(p) Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 161 8. ledna 2021 Příklad Otevřený cíl At(l1) můžeme splnit přiřazením l1=Home z akce Start Operátory: Go(l,m) precond: At(l) effects: At(m), ¬ At(l) Buy(p,s) precond: At(s), Sells(s, p) effects: Have(p) Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 162 8. ledna 2021 Příklad Otevřený cíl At(l2) můžeme splnit přiřazením l2=OBI z akce Go(Home, OBI) Operátory: Go(l,m) precond: At(l) effects: At(m), ¬ At(l) Buy(p,s) precond: At(s), Sells(s, p) effects: Have(p) Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 163 8. ledna 2021 Příklad Otevřený cíl At(Home) z Finish splníme akcí Go(l3, Home) vzniknou nové hrozby (I., II., III.) Operátory: Go(l,m) precond: At(l) effects: At(m), ¬ At(l) Buy(p,s) precond: At(s), Sells(s, p) effects: Have(p) Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 164 8. ledna 2021 Příklad Hrozby na At(Tesco) (I., II.) odstraníme uspořádáním akce Go(Home) za obě akce Buy to vyřeší i poslední hrozbu Operátory: Go(l,m) precond: At(l) effects: At(m), ¬ At(l) Buy(p,s) precond: At(s), Sells(s, p) effects: Have(p) Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 165 8. ledna 2021 Příklad Otevřený cíl At(l3) splníme přiřazením l3=Tesco z akce Go(OBI, Tesco) Operátory: Go(l,m) precond: At(l) effects: At(m), ¬ At(l) Buy(p,s) precond: At(s), Sells(s, p) effects: Have(p) Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 166 8. ledna 2021 Srovnání technik Plánování se stavy Plánování s plány prohled. prostor konečný nekonečný uzly jednoduché komplikovanější (stavy světa) (částečné plány) stavy světa explicitní nejsou částečný plán uspořádání a volba volba akcí a jejich akcí se dělá najednou pořadí oddělené struktura plánu lineární bez vazeb kauzální vazby Díky doménově specifickým heuristikám je dnes plánování se stavy výrazně rychlejší. Ale, plánování v prostoru plánů: vytváří flexibilnější plány díky částečnému uspořádání umožňuje další rozšíření, např. přidání času a zdrojů Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 167 8. ledna 2021 Cvičení: výměna hodnot proměnných Plánovací problém: s0 = {value(v1,3), value(v2,5), value(v3,0)} g = {value(v1,5), value(v2,3)} assign(v, w, x, y) precond: value(v, x), value(w, y) effects: ¬ value(v, x), value(v, y) Částečný plán: Otázky: Které jsou zde hrozby? Kolik přímých následníků má tento částečný plán? Provádějte operace algoritmem PSP počínaje uvedeným plánem. Který běh nalezne řešení s nejmenším možným počtem akcí? Hana Rudová, IV126, FI MU: Plánování v prostoru plánů 168 8. ledna 2021 Neurčitost: Bayesovské sítě 8. ledna 2021 23 Opakování: pravděpodobnost 24 Bayesovská síť 25 Sémantika sítě 26 Konstrukce sítě 27 Odvozování v Bayesovských sítích Zdroj: Roman Barták, přednáška přednáška Umělá inteligence II, Matematicko-fyzikální fakulta, Karlova univerzita v Praze, 2015. http: // kti. ms. mff. cuni. cz/ ~bartak/ ui2 Neurčitost a umělá inteligence: krátké historické shrnutí Pro modelování neurčitosti použijeme teorii pravděpodobnosti (podobně jako ve fyzice či ekonomii), ale bylo tomu tak vždy? První expertní systémy (kolem roku 1970) používali čistě logický přístup bez práce s neurčitostí, což se ukázalo nepraktické Další generace expertních systému zkusila pravděpodobnostní techniky, ale ty měly problém se škálovatelností (efektivní odvozování na Bayesovských sítích ještě nebylo známé) Proto byly zkoušeny alternativní přístupy (1975-1988) pro modelování neurčitosti, ignorance a vágnosti pravidlově orientované systémy, Dempster-Shaferova teorie, fuzzy logika Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 170 8. ledna 2021 Opakování: Podmíněná pravděpodobnost Podmíněná pravděpodobnost P(x|y) = P(x ∧ y)/P(y) Příklad: Jaká je pravděpodobnost, že na dvou kostkách hodíme pár, pokud víme, že na kostce 1 padla 5? P(dvojice|Hod1 = 5) = 1/36 1/6 = 1/6 Podmíněnou pravděpodobnost často zapisujeme v podobě součinového pravidla: P(x ∧ y) = P(x|y) × P(y) P(X, Y ) = P(X|Y ) × P(Y ) P znamená, že výsledek je vektor čísel P(X|Y ) dává hodnoty P(X = xi |Y = yj ) pro každý možný pár i, j P(x, y) odpovídá P(X = x ∧ Y = y) P(X, Y ) označuje pravděpodobnosti pro všechny kombinace hodnot X, Y (Úplná) nezávislost: náhodné proměnné jsou na sobě nezávislé P(X|Y ) = P(X) nebo P(Y |X) = P(Y ) nebo P(X, Y ) = P(X) P(Y ) Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 171 8. ledna 2021 Opakování: Úplná sdružená distribuce (joint probability distribution), marginalizace Pravděpodobnosti elementárních jevů můžeme popsat tabulkou, tzv. úplnou sdruženou distribucí P(Toothache, Cavity, Catch) toothache ¬toothache catch ¬catch catch ¬catch cavity 0.108 0.012 0.072 0.008 ¬cavity 0.016 0.064 0.144 0.576 Chceme-li znát pravděpodobnost nějakého tvrzení, sečteme pravděpodobnosti všech „světů”, kde tvrzení platí (marginalizace) P(Y) = z∈Z P(Y, z) pozn. Y značí množinu proměnných vs. Y značí jednu proměnnou př. P(tootchache = true) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2 Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 172 8. ledna 2021 Opakování: Diagnostická vs. kauzální vazba Odhalení zdrojů dle symptomů, tj. diagnostická vazba P(nemoc|symptomy), tj. P(pricina|nasledek) Z analýzy předchozích nemocí, spíš však máme k dispozici pravděpodobnost nemoci P(nemoc) pravděpodobnost symptomu P(symptom) kauzální vztah nemocí a symptomu P(symptomy|nemoc), tj. P(nasledek|pricina) Jak využít tyto znalosti ke zjištění P(nemoc|symptomy)? Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 173 8. ledna 2021 Opakování: Bayesova věta Víme, že platí P(a ∧ b) = P(a|b) P(b) = P(b|a) P(a) Můžeme odvodit Bayesovu větu v obecné podobě: P(Y |X) = P(X|Y ) P(Y ) P(X) = α P(X|Y ) P(Y ) α je normalizační konstanta, zajišťující, že položky v P(Y |X) jsou sumarizovány na 1 př. α 0.2, 0.3 = 0.4, 0.6 1/P(X) vlastně dočasně zanedbáme podobně u podmíněné pravděpodobnosti P(Y |X) = P(Y , X) P(X) = α P(Y , X) Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 174 8. ledna 2021 Obsah přednášky Bayesovské sítě efektivní způsob reprezentace podmíněných pravděpodobností a nezávislostí Sémantika sítě vztah k úplně sdružené distribuci Konstrukce sítě Odvozování v Bayesovských sítích exaktní metody enumerace, eliminace proměnných aproximační metody vzorkovací techniky (sampling techniques) Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 175 8. ledna 2021 Bayesovská síť (BS) Zachycuje závislosti mezi náhodnými proměnnými Orientovaný acyklický graf (DAG) uzel odpovídá náhodné proměnné předchůdci uzlu v grafu se nazývají rodiče každý uzel má přiřazenu tabulku podmíněné pravděpodobnostní distribuce P(X|Parents(X)) Jiné názvy belief network, probabilistic network, causal network (speciální případ BS), knowledge map Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 176 8. ledna 2021 Bayesovská síť: modelová situace Máme v domě zabudovaný alarm, který se spustí při vloupání ale někdy také při zemětřesení Sousedi Mary a John slíbili, že vždy, když alarm uslyší, tak nám zavolají John volá skoro vždy, když slyší alarm, ale někdy si ho splete s telefonním zvoněním Mary poslouchá hlasitou hudbu a někdy alarm přeslechne Zajímá nás pravděpodobnost vloupání, pokud John i Mary volají Další předpoklady sousedi přímo nevidí vloupání ani necítí zemětřesení sousedi se nedomlouvají (volají nezávisle na sobě) Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 177 8. ledna 2021 Bayesovská síť: příklad Náhodné boolovské proměnné reprezentují možné události některé události (zvonění telefonu, přelet letadla, vadu alarmu, ...) ignorujeme Pravděpodobnostní tabulky reprezentují vztah podmíněné pravděpodobnosti stačí reprezentovat hodnoty true Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 178 8. ledna 2021 Sémantika sítě Bayesovská síť kompaktním způsobem reprezentuje úplnou sdruženou distribuci P(x1, . . . , xn) = i P(xi |parents(Xi )) př. P(j, m, a, ¬b, ¬e) = P(j|a) P(m|a) P(a|¬b ∧ ¬e) P(¬b) P(¬e) = 0.90 × 0.70 × 0.001 × 0.999 × 0.998 = 0.000628 Zpětně lze ukázat, že tabulky P(X|Parents(X)) jsou podmíněné pravděpodobnosti podle výše uvedené sdružené distribuce Protože úplnou sdruženou distribuci lze použít pro odpověď na libovolnou otázku v dané doméně, lze stejnou dopověď získat z Bayesovské sítě (marginalizací) Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 179 8. ledna 2021 Konstrukce sítě Jak konstruovat Baysovské sítě? Rozepíšeme P(x1, . . . , xn) pomocí tzv. řetězcového pravidla n = 4 : P(X4, X3, X2, X1) = P(X4|X3, X2, X1) P(X3|X2, X1) P(X2|X1) P(X1) P(x1, . . . , xn) = i P(xi |xi−1, . . . x1) Dále dostaneme P(Xi |Xi−1, . . . X1) = P(Xi |Parents(Xi )) za předpokladu Parents(Xi ) ⊆ {Xi−1, . . . , X1}, což platí, pokud je očíslování uzlů konzistentní s uspořádáním uzlů v síti pozn. P(X4|X3, X2, X1) = P(X4|X3, X2) pokud X4 nezávisí na X1 tj. Bayesovská síť je korektní, pokud je každý uzel nezávislý na ostatních předchůdcích v uspořádání Tj. sdružená distribuce P(x1, . . . , xn) = i P(xi |parents(Xi )) odpovídá přidání P(Xi |Parents(Xi )) pro každý uzel sítě Xi . Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 180 8. ledna 2021 Konstrukce sítě: algoritmus Uzly: rozhodněte, jaké náhodné proměnné jsou potřeba a uspořádejte je funguje libovolné uspořádání, ale pro různá uspořádání dostaneme různě kompaktní sítě doporučené uspořádání je takové, kdy příčiny předcházejí efekty Hrany: bereme proměnné Xi v daném pořadí od 1 do n v množině {X1, . . . , Xi−1} vybereme nejmenší množinu rodičů Xi tak, že platí P(Xi |Parents(Xi )) = P(Xi |Xi−1, . . . X1) intuitivně: rodiči Xi jsou pouze ty uzly, které přímo ovlivňují Xi M ovlivněno B a E ale nepřímo, tj. věříme, že P(M|J, A, E, B) = P(M|A) z rodičů vedeme hranu do Xi vypočteme podmíněné pravděpodobnostní tabulky P(Xi |Parents(Xi )) Vlastnosti síť je z principu konstrukce acyklická síť neobsahuje redundantní informaci a tudíž je vždy konzistentní (splňuje axiomy pravděpodobnosti) Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 181 8. ledna 2021 Konstrukce sítě: poznámky Bayesovská síť může být mnohem kompaktnější než úplná sdružená distribuce, pokud je síť řídká (je lokálně strukturovaná) náhodná proměnná často závisí jen na omezeném počtu jiných proměnných nechť je takových proměnných k a celkem máme n proměnných, pak potřebujeme prostor n.2k pro Bayesovskou síť 2n pro uplnou sdruženou distribuci můžeme ignorovat „slabé vazby”, čímž budeme mít menší přesnost reprezentace, ale reprezentace bude kompaknější př. nebudeme brát v úvahu, zda Mary nebo John volají kvůli zemětřesení samozřejmě kompaktnost sítě hodně závisí na vhodném uspořádání proměnných Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 182 8. ledna 2021 Konstrukce sítě: příklad Nechť jsme zvolili pořadí MarryCalls, JohnCalls, Alarm, Burglary, Earthquake MarryCalls nemá rodiče pokud volá Marry, je zřejmě aktivní alarm, což ovlivňuje Johnovo zavolání Alarm asi zní, pokud volá Marry nebo John pokud známe stav Alarmu, tak vloupání nezávisí na tom, zda volá Marry nebo John P(Burglary|Alarm, JohnCalls, MarryCalls) = P(Burglary|Alarm) Alarm je svým způsobem detektor zemětřesení, ale pokud došlo k vloupání, tak pravděpodobně nebylo zemětřesení Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 183 8. ledna 2021 Konstrukce sítě: uspořádání proměnných Máme sice jen dvě hrany navíc oproti původnímu návrhu, ale problém je vyplnění tabulek podmíněných závislostí stejný problém jako u kauzální vs. diagnostické vazby diagnostickou vazbu P(pricina|nasledek) často neznáme je lepší držet se kauzální vazby (příčina před následkem) P(nasledek|pricina) dává menší sítě a je snažší vyplnit tabulky podmíněných závislostí Při „špatném” uspořádání proměnných nemusíme nic uspořit vzhledem k úplné sdružené distribuci MarryCalls, JohnCalls, Eartquake, Burglary, Alarm Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 184 8. ledna 2021 Odvozování v Bayesovských sítí pomocí enumerace Připomeňme, k čemu mají Bayesovské sítě sloužit: zjistit pravděpodobnostní distribuce náhodných proměnných X v dotazu za předpokladu znalosti hodnot e proměnných z pozorování (ostatní proměnné jsou skryté). P(X|e) = α P(X, e) = α y P(X, e, y) Hodnotu P(X, e, y) zjistíme z Bayesovské sítě P(x1, . . . , xn) = i P(xi |parents(Xi )) Můžeme ještě vhodně přesunout některé členy P(xi |parents(Xi )) před součty viz příklad na další straně Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 185 8. ledna 2021 Odvozování enumerací: příklad Nechť máme dotaz, zda došlo k vloupání, pokud Marry i John volají P(b|j, m) = α e a P(b) P(e) P(a|b, e) P(j|a) P(m|a) = αP(b) e P(e) a P(a|b, e) P(j|a) P(m|a) Earthquake a Alarm jsou skryté proměnné Strukturu výpočtu můžeme zachytit stromovou strukturou je to hodně podobné řešení CSP a SAT Všimněme si, že některé části výpočtu se opakují! Evaluace se provádí shora dolů násobením hodnot po každé cestě a sečítáním hodnot v „+” uzlech Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 186 8. ledna 2021 Odvozování enumerací: algoritmus function enumerace(X, e, bn) returns distribuci pro X (X: náhodná proměnná e: hodnoty proměnných z pozorování pro E bn: BS s proměnnými {X} ∪ E ∪ Y, kde Y jsou skryté proměnné) Q(X) = distribuce pro X, iniciálně prázdná; forall hodnoty xi proměnné X do Q(xi ) = enumerace-hodnot(bn.VARS, exi ), kde exi je e rozšířeno o X = xi ; return normalizace(Q(X)) function enumerace-hodnot(vars, e) returns reálné číslo if vars = ∅ then return 1.0; Y = first(vars); if Y má hodnotu y v e then return P(y|parents(Y )) × enumerace-hodnot(rest(vars), e) else return y P(y|parents(Y )) × enumerace-hodnot(rest(vars), ey ) kde ey je e rozšířeno o Y = y; Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 187 8. ledna 2021 Eliminace proměnných Enumerační metoda zbytečně opakuje některé výpočty Stačí si výsledek zapamatovat a následně použít fi spočítáme jednou a uschováme pro budoucí použití dynamické programování P(B|j, m) = α P(B) e P(e) a P(a|B, e) P(j|a) P(m|a) = α f1(B) e f2(E) a f3(A, B, E) f4(A) f5(A) Činitelé fi jsou matice (tabulky) pro dané proměnné Vyhodnocení provedeme zprava doleva (viz příklad dále) násobení činitelů je násobení po prvcích (ne násobení matic) vysčítáním činitelů eliminujeme příslušnou proměnnou na závěr provedeme normalizaci tj. bottom-up přístup pro předchozí graf u odvozování enumerací Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 188 8. ledna 2021 Eliminace proměnných: operace s tabulkami Máme-li dvě tabulky, potom jejich součin je tabulka nad sjednocením proměnných z obou tabulek f(A1, . . . , Aj , B1, . . . , Bk , C1, . . . , Cl ) = f1(A1, . . . , Aj , B1, . . . , Bk ) × f2(B1, . . . , Bk , C1, . . . , Cl ) Při vysčítání dojde k eliminaci proměnné f(B, C) = a f3(A, B, C) = f3(a, B, C) + f3(¬a, B, C) 0.06 0.24 0.42 0.28 + 0.18 0.72 0.06 0.04 = 0.24 0.96 0.48 0.32 Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 189 8. ledna 2021 Cvičení: eliminace proměnných Spočtěte hodnodu P(B|j, m) Máme: P(B|j, m) = α f1(B) × e f2(E) × a f3(A, B, E) × f4(A) × f5(A) Odvodíme (eliminujeme A): f6(B, E) = (f3(a, B, E) × f4(a) × f5(a)) + (f3(¬a, B, E) × f4(¬a) × f5(¬a)) Tedy: P(B|j, m) = α f1(B) × e f2(E) × f6(B, E) Dále (eliminujeme E): f7(B) = e f2(E) × f6(B, E) = f2(e) × f6(B, e) + f2(¬e) × f6(B, ¬e) Tedy: P(B|j, m) = α f1(B) × f7(B) Zkuste: P(B|j, m) = α f1(B) × a f4(A) × f5(A) × e f2(E) × f3(A, B, E) Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 190 8. ledna 2021 Eliminace proměnných: algoritmus function eliminace(X, e, bn) returns distribuci pro X (X: náhodná proměnná e: hodnoty proměnných z pozorování pro E bn: BS s úplnou sdruženou distribucí P(X1, . . . , Xn)) tabulky = []; forall var ∈ order(bn.VARS) do tabulky = [vytvoř-tabulku(var, e)|tabulky]; if var je skrytá proměnná then tabulky = marginalizace(var, tabulky); return normalizace(součin-po-prvcích(tabulky)) Algoritmus funguje pro libovolné uspořádání proměnných (order) Složitost je dána velikostí největšího činitele (tabulky) v průběhu výpočtu Vhodné je proto pro eliminaci vybrat proměnnou, jejíž eliminací vznikne nejmenší tabulka Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 191 8. ledna 2021 Složitost problému Eliminace proměnných urychluje odvozování, ale jak moc? Pokud je Bayesovská síť poly-strom (mezi každými dvěma vrcholy vede maximálně jedna neorientovaná cesta), potom je časová a prostorová složitost odvozování lineární vzhledem k velikosti sítě (tj. velikosti tabulek) Pro více-propojené sítě je to horší 3SAT lze redukovat na odvození v Bayesovské síti, takže odvození je NP-těžké odvozování v Bayesovské síti je ekvivalentní zjištění počtu řešení SAT-formule, je tedy striktně těžší než NP-úplné problémy Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 192 8. ledna 2021 Vzorkovací metody Exaktní odvozování je výpočetně náročné, můžeme ale použít aproximační techniky založené na metodě Monte Carlo Monte Carlo algoritmy slouží pro odhad hodnot, které je těžké spočítat exaktně vygeneruje se množství vzorků vzorek = ohodnocení náhodných proměnných hledaná hodnota se zjistí statisticky více vzorků = větší přesnost Pro Bayesovské sítě ukážeme přístupy příme vzorkování vzorkování se zamítáním vzorkování s vážením věrohodností Další zajímavé metody (viz Russel & Norvig) vzorkování s Markovovskými řetězci Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 193 8. ledna 2021 Přímé vzorkování Vzorkem pro nás bude ohodnocení náhodných proměnných Vzorek je potřeba generovat tak, aby „odpovídal” tabulkám v Bayesovské síti uzly (proměnné) bereme v topologickém uspořádání ohodnocení rodičů nám dá pravděpodobnostní distribuci hodnot aktuální náhodné proměnné náhodně vybereme hodnotu podle této distribuce Nechť N je počet vzorků a N(x1, . . . , xn) vyjadřuje počet výskytů jevu x1, . . . , xn, potom P(x1, . . . , xn) = limN→∞(N(x1, . . . , xn)/N) function vzorky(bn) returns vzorek získaný dle bn (bn: BS specifikující úplnou sdruženou distribuci P(X1, . . . , Xn)) forall proměnnou Xi z X1, . . . , Xn do xi = náhodný vzorek z P(Xi |parents(Xi )); return x Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 194 8. ledna 2021 Přímé vzorkování: příklad Vybereme hodnotu pro Cloudy z distribuce P(Cloudy) = 0.5, 0.5 nechť je true Vybereme hodnotu pro Sprinkler z distribuce P(Sprinkler|Cloudy = true) = 0.1, 0.9 nechť je false Vybereme hodnotu pro Rain z distribuce P(Rain|Cloudy = true) = 0.8, 0.2 nechť je true Vybereme hodnotu pro WetGrass z distribuce P(WetGrass|Sprinkler = false, Rain = true) = 0.9, 0.1 nechť je true Získali jsme vzorek Cloudy = true, Sprinkler = false, Rain = true, WetGrass = true Pravděpodobnost jeho získání je zřejmě 0.5 ∗ (1 − 0.1) ∗ 0.8 ∗ 0.9 = 0.324 Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 195 8. ledna 2021 Vzorkování se zamítáním Nás ale zajímá P(X|e)! Ze vzorků, které vygenerujeme, vezmeme jen ty, které jsou kompatibilní s e (ostatní zamítneme) P(X|e) ≈ α N(X, e) = N(X, e)/N(e) function vzorky-zamítání(X, e, bn, N) returns odhad pro P(X|e) (X: náhodná proměnná e: hodnoty proměnných z pozorování pro E bn: BS s úplnou sdruženou distribucí P(X1, . . . , Xn) N: celkový počet vzorků, který máme generovat) forall hodnotu x v X do N[x] = 0; (vektor počtu hodnot inicializujeme na 0) for j = 1 to N do x = vzorky(bn); if x je konzistentní s e then N[x] = N[x] + 1, kde x je hodnota X v x; return normalizace(N) Nechť v našem příkladu vygenerujeme 100 vzorků, z toho u 27 platí Sprinkler = true a z nich u 8 je Rain = true a u 19 je Rain = false. Potom P(Rain|Sprinkler = true) ≈ normalizace( 8, 19 ) = 0.296, 0.704 Hlavní nevýhoda metody je zamítání příliš mnoha vzorků! Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 196 8. ledna 2021 Vážení věrohodností Místo zamítání vzorků je efektivnější: generovat pouze vzorky vyhovující pozorování e Zafixujeme hodnoty z pozorování e a vzorkujeme pouze ostatní proměnné Pravděpodobnost získání vzorku je (mezi rodiči máme i pozorování) SWS (z, e) = i P(zi |parents(Zi )) To ale není to, co potřebujeme! Ještě nám chybí w(z, e) = j P(ej |parents(Ej )) (mezi rodiči máme i Zi ) Tedy SWS (z, e)w(z, e) = i P(zi |parents(Zi )) j P(ej |parents(Ej )) = P(z, e) Každý vzorek tedy doplníme o příslušnou váhu P(X|e) ≈ α y N(X, y, e) w(X, y, e) Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 197 8. ledna 2021 Vážení věrohodností: příklad Nechť zpracováváme dotaz P(Rain|Sprinkler = true, WetGrass = true) Počáteční váha vzorku w = 1.0 Vybereme hodnotu pro Cloudy z distribuce P(Cloudy) = 0.5, 0.5 nechť je true Hodnotu Sprinkler = true známe, ale upravíme váhu w = w × P(Sprinkler = true|Cloudy = true) = 0.1 Vybereme hodnotu pro Rain z distribuce P(Rain|Cloudy = true) = 0.8, 0.2 nechť je true Hodnotu WetGrass = true známe, ale upravíme váhu w = w × P(WetGrass = true|Sprinkler = true, Rain = true) = 0.099 Získali jsme vzorek Cloudy = true, Sprinkler = true, Rain = true, WetGrass = true, který má váhu 0.099 Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 198 8. ledna 2021 Vážení věrohodností: algoritmus function vážení-věrohodností(X, e, bn, N) returns odhad pro P(X|e) (X: náhodná proměnná e: hodnoty proměnných z pozorování pro E bn: BS s úplnou sdruženou distribucí P(X1, . . . , Xn) N: celkový počet vzorků, který máme generovat) forall hodnotu x v X do W[x] = 0; (vektor vah inicializujeme na 0) for j = 1 to N do x, w = vážený-vzorek(bn, e); W[x] = W[x] + w, kde x je hodnota X v x; return normalizace(W) function vážený-vzorek(bn, e) returns vzorek a váhu forall Xi v X1, . . . , Xn do if Xi má v e hodnotu xi then w = w × P(Xi = xi |parents(Xi )) else xi = náhodný vzorek z P(Xi |parents(Xi )); returns x, w Hana Rudová, IV126, FI MU: Neurčitost: Bayesovské sítě 199 8. ledna 2021 Čas a neurčitost 8. ledna 2021 28 Reprezentace přechodů s pravděpodobností 29 Filtrace 30 Predikce 31 Vyhlazování Zdroje: Roman Barták, přednáška přednáška Umělá inteligence II, Matematicko-fyzikální fakulta, Karlova univerzita v Praze, 2015. http: // kti. ms. mff. cuni. cz/ ~bartak/ ui2 Pravděpodobnostní uvažování o čase Agent pracující v částečně pozorovatelném prostředí udržuje na základě senzorického modelu domnělý stav a na základě přechodového modelu odhaduje, jak se svět může vyvíjet domnělý stav reprezentuje možné skutečné stavy světa buď výčtově nebo logickou formulí (přes vlastnosti stavu) pomocí teorie pravděpodobnosti umíme kvantifikovat, které z domnělých stavů jsou pravděpodobnější teď přidáme pravděpodobnost k přechodům mezi stavy Pravděpodobnostní uvažování o čase: obsah přednášky reprezentace přechodů s pravděpodobností typy řešených úloh (otázek) základní odvozovací algoritmy Hana Rudová, IV126, FI MU: Čas a neurčitost 201 8. ledna 2021 Čas a neurčitost Dynamiku světa budeme modelovat sérií časových řezů t je označení časového řezu uvažujeme tedy diskrétní čas se stejnýmí časovými kroky Každý řez/stav bude popsán (stejnou) množinou náhodných proměnných, které se dělí na nepozorovatelné náhodné proměnné Xt pozorované náhodné proměnné Et (observable evidence variables) konkrétní pozorovanou množinu hodnot označíme et Notace Xt1:t2 označujeme množinu proměnných od Xt1 po Xt2 Hana Rudová, IV126, FI MU: Čas a neurčitost 202 8. ledna 2021 Modelová situace Uvažujme agenta pracujícího na tajné podzemní základně, ze které nikdy nevychází Zajímá ho, zda venku prší náhodná nepozorovatelná proměnná Rt Jediné pozorování, které má k dispozici, říká, zda ráno ředitel přišel s deštníkem nebo bez deštníku náhodná pozorovaná proměnná Ut Hana Rudová, IV126, FI MU: Čas a neurčitost 203 8. ledna 2021 Přechodový model Přechodový model popisuje, jak je stav ovlivněn předchozími stavy Přesněji popisuje pravděpodobnostní distribuci P(Xt|X0:t−1) 1. problém: s rostoucím t neomezeně roste množina X0:t−1 použijeme Markovský předpoklad: současný stav závisí pouze na pevně daném konečném počtu předchozích stavů – hovoříme potom o obecných Markovských řetězcích/procesech např. současný stav závisí pouze na předchozím stavu – Markovský proces prvního řádu P(Xt|X0:t−1) = P(Xt|Xt−1) Markovský proces prvního řádu Markovský proces druhého řádu 2. problém: pořád máme nekonečně mnoho různých přechodů použijeme předpoklad stacionárního procesu, tj. stav se vždy mění podle stejných pevně daných pravidel distribuce P(Xt|Xt−1) je stejná pro všechny časy t Hana Rudová, IV126, FI MU: Čas a neurčitost 204 8. ledna 2021 Senzorický model Senzorický model popisuje, na čem závisí pozorované náhodné proměnné Et Ty mohou záviset i na proměnných z předchozích stavů, ale uděláme Markovský senzorický předpoklad – pozorované proměnné závisí pouze na nepozorovatelných proměnných Xt ze stejného stavu P(Et|X0:t, E1:t−1) = P(Et|Xt) Hana Rudová, IV126, FI MU: Čas a neurčitost 205 8. ledna 2021 Bayesovské sítě pro přechodový a senzorický model Přechodový a senzorický model můžeme popsat Bayesovskou sítí Kromě tabulek P(Xt|Xt−1) a P(Et|Xt) musíme ještě zadat, jak to vše začalo: P(X0) Z vlastností Bayesovských sítí víme P(X0:t, E1:t) = P(X0) t i=1 P(Xi |Xi−1) P(Ei |Xi ) Hana Rudová, IV126, FI MU: Čas a neurčitost 206 8. ledna 2021 Zpřesnění modelu Markovský proces prvního řádu předpokládá, že stavové proměnné obsahují veškerou informaci pro charakteristiku pravděpodobnostní distribuce dalšího stavu Co když je tento předpoklad nepřesný? můžeme zvýšit řád Markovského procesu můžeme rozšířit množinu stavových proměnných např. přidáme proměnnou Season nebo sadu proměnných Temperaturet, Humidityt, Pressuret první případ (větší řád) lze vždy převést na druhý případ (více proměnných) Hana Rudová, IV126, FI MU: Čas a neurčitost 207 8. ledna 2021 Řešené úlohy Odhad stavu (filtrace): cílem je zjištění pravděpodobnosti aktuálního stavu na základě dosavadních pozorování: P(Xt|e1:t) Predikce: cílem je zjištění pravděpodobnosti budoucího stavu na základě dosavadních pozorování: P(Xt+k|e1:t) pro k > 0 Vyhlazování: cílem je zjištění pravděpodobnosti minulého stavu na základě dosavadních pozorování: P(Xk|e1:t) pro k, kde 0 ≤ k < t Nejpravděpodobnější průchod: na základě posloupnosti pozorování chceme zjistit nejpravděpodobnější posloupnost stavů, která tato pozorování generuje: argmaxx1:t P(x1:t|e1:t) Hana Rudová, IV126, FI MU: Čas a neurčitost 208 8. ledna 2021 Odhad stavu (filtrace) Úkolem je zjistit pravděpodobnost aktuálního stavu na základě dosavadních pozorování: P(Xt|e1:t) Dobrý filtrační algoritmus odhaduje aktuální stav z odhadu předchozího stavu a aktuálního pozorování (rekurzivní odhad) P(Xt+1|e1:t+1) = f (et+1, P(Xt|e1:t)) Jak najdeme funkci f ? P(Xt+1|e1:t+1) = P(Xt+1|e1:t, et+1) = = α P(et+1|Xt+1, e1:t) P(Xt+1|e1:t) z Bayesovy věty P(Y |X) = α P(X|Y ) P(Y ), kde Y = Xt+1 a X = et+1 = α P(et+1|Xt+1) P(Xt+1|e1:t) z Mark. senzorického předpokladu, kde P(Xt+1|e1:t ) je jednokroková predikce následujícího stavu = α P(et+1|Xt+1) xt P(Xt+1|xt, e1:t) P(xt|e1:t) z marginalizace P(Y) = z P(Y, z) = z P(Y|z) P(z) a podmíněné pst. kde Y = Xt+1 a z = xt = α P(et+1|Xt+1) xt P(Xt+1|xt) P(xt|e1:t) z Mark.procesu 1.řádu Hana Rudová, IV126, FI MU: Čas a neurčitost 209 8. ledna 2021 Filtrace (dokončení) Máme tedy: P(Xt+1|e1:t+1) = α P(et+1|Xt+1) xt P(Xt+1|xt) P(xt|e1:t) α normalizuje pravděpodobnosti, aby byl součet 1 P(et+1|Xt+1): známe ze senzorického modelu P(Xt+1|xt): známe z přechodového modelu P(xt|e1:t): z rekurze Tedy získali jsme rekurzivní formulaci vhodnou pro dopřednou propagaci zprávy: P(Xt|e1:t) = f1:t f1:t+1 = α forward(f1:t, et+1) f1:0 = P(X0) Hana Rudová, IV126, FI MU: Čas a neurčitost 210 8. ledna 2021 Filtrace: příklad P(Rt+1|u1:t+1) = Umbrella1=true, Umbrella2=true α P(ut+1|Rt+1) P(Rt+1|u1:t) = α P(ut+1|Rt+1) rt P(Rt+1|rt) P(rt|u1:t) P(R0) = 0.5, 0.5 P(R1) = r0 P(R1|r0)P(r0) = 0.7,0.3 ×0.5+ 0.3,0.7 ×0.5 = 0.5, 0.5 P(R1|u1) = αP(u1|R1) P(R1) = α 0.9, 0.2 0.5, 0.5 ≈ 0.818, 0.182 P(R2|u1) = r1 P(R2|r1)P(r1|u1) = 0.7, 0.3 × 0.818 + 0.3, 0.7 × 0.182 ≈ 0.627, 0.372 P(R2|u1, u2) = P(R2|u1:2) = αP(u2|R2) P(R2|u1) = α 0.9, 0.2 0.627, 0.372 ≈ 0.883, 0.117 Hana Rudová, IV126, FI MU: Čas a neurčitost 211 8. ledna 2021 Predikce Úkolem je zjistit pravděpodobnost budoucího stavu na základě dosavadních pozorování: P(Xt+k|e1:t) pro k > 0 Jedná se v podstatě o filtraci bez přidávání dalších pozorování P(Xt+k+1|e1:t) = xt+k P(Xt+k+1|xt+k) P(xt+k|e1:t) (rozšíření jednokrokové predikce z odvození filtrace) Po určité době (mixing time) konverguje předpovězená distribuce ke stacionární distribuci a nadále zůstane stejná příklad: pravděpodobnost deště konverguje k 0.5, 0.5 Hana Rudová, IV126, FI MU: Čas a neurčitost 212 8. ledna 2021 Vyhlazování Úkolem je zjistit pravděpodobnost minulého stavu na základě dosavadních pozorování: P(Xk|e1:t), kde 0 ≤ k < t Opět použijeme rekurzivní předávání zpráv, tentokrát ve dvou směrech P(Xk |e1:t) = P(Xk |e1:k , ek+1:t) = = α P(Xk |e1:k ) P(ek+1:t|Xk , e1:k ) z Bayesovy věty = α P(Xk |e1:k ) P(ek+1:t|Xk ) z podmíněné nezávislosti = αf1:k × bk+1:t (tj. spočítáme rekurzí přes čas: dopředně od 1 do k, zpětně od t ke k + 1) P(ek+1:t|Xk ) = xk+1 P(ek+1:t|Xk , xk+1) P(xk+1|Xk ) z marginalizace P(Y) = z P(Y, z) = z P(Y|z) P(z) a podmíněné pst. kde Y = ek+1:t a z = xk+1 = xk+1 P(ek+1:t|xk+1) P(xk+1|Xk ) z podmíněné nezávislosti = xk+1 P(ek+1, ek+2:t|xk+1) P(xk+1|Xk ) = xk+1 P(ek+1|xk+1)P(ek+2:t|xk+1) P(xk+1|Xk ) z podmíněné nezávislosti Hana Rudová, IV126, FI MU: Čas a neurčitost 213 8. ledna 2021 Vyhlazování (dokončení) Máme tedy: P(ek+1:t|Xk) = xk+1 P(ek+1|xk+1)P(ek+2:t|xk+1) P(xk+1|Xk) P(ek+1|xk+1): známe ze senzorického modelu P(ek+2:t|xk+1): zpětný chod P(xk+1|Xk): známe z přechodového modelu Můžeme tedy použít techniku zpětné propagace zprávy: P(ek+1:t|Xk) = bk+1:t bk+1:t = backward(bk+2:t, ek+1) bt+1:t = P(et+1:t|Xt) = P( |Xt)1 = 1 vzhledem k tomu, že et+1:t je prázdná posloupnost Hana Rudová, IV126, FI MU: Čas a neurčitost 214 8. ledna 2021 Vyhlazování: příklad P(Rk |u1:t+1) = α P(Rk |u1:k ) P(uk+1:t|Rk ), např. P(R1|u1:2) = αP(R1|u1)×P(u2|R1) P(uk+1:t|Rk ) = rk+1 P(uk+1|rk+1)P(uk+2:t|rk+1) P(rk+1|Rk ) P( |R2) = 1 Umbrella1=true, Umbrella2=true P(u2|R1) = r2 P(u2|r2) P( |r2) P(r2|R1) = = 0.9 × 1 × 0.7, 0.3 + 0.2 × 1 × 0.3, 0.7 = 0.69, 0.41 P(R1|u1) × P(u2|R1) = 0.818, 0.182 × 0.69, 0.41 ≈ 0.883, 0.117 = P(R1|u1, u2) tj. vyhlazený odhad (0.883) je vyšší než filtrovaný odhad (0.818 z P(R1|u1)) vzhledem k dešti v den 2 Hana Rudová, IV126, FI MU: Čas a neurčitost 215 8. ledna 2021 Užitek a rozhodování 8. ledna 2021 32 Užitek 33 Rozhodovací sítě Zdroje: Roman Barták, přednáška přednáška Umělá inteligence II, Matematicko-fyzikální fakulta, Karlova univerzita v Praze, 2015. http: // kti. ms. mff. cuni. cz/ ~bartak/ ui2 Úvod Cílem je tvorba racionálních agentů maximalizujících očekávanou míru užitku Teorie pravděpodobnosti říká, čemu máme věřit na základě pozorování Teorie užitku (utility theory) popisuje, co chceme a jak máme ohodnotit rozhodnutí Teorie rozhodování (decision theory) spojuje obě teorie dohromady a popisuje, jak bychom měli vybrat akci s největším očekávaným užitkem podíváme se na statický případ (jedno rozhodnutí) i na posloupnost rozhodnutí Hana Rudová, IV126, FI MU: Užitek a rozhodování 217 8. ledna 2021 Teorie užitku (Agentovy) preference lze zaznamenat funkcí užitku U(s), která mapuje stavy s na reálné číslo Očekávaný užitek (expected utility) potom spočteme jako průměrný užitek přes všechny možné stavy vážené pravděpodobností výsledků EU(a|e) = s P(Result(a) = s|a, e)U(s) e pozorování, a akce Result(a) náhodná proměnná, jejíž hodnoty jsou možné výsledné stavy Racionální agent potom volí akci maximalizující očekávaný užitek MEU akce = argmaxaEU(a|e) MEU formalizuje racionalitu, ale jak budeme celý postup operačně realizovat? Tj. budeme se zabývat: jak volit akci při jednom rozhodnutí? jak volit postupně akce při posloupnosti rozhodnutí? Hana Rudová, IV126, FI MU: Užitek a rozhodování 218 8. ledna 2021 Užitek a preference Cíl: hledáme funkci užitku popisující preference Agentovy preference se často vyjadřují relativním porovnáním A > B: agent preferuje A před B A < B: agent preferuje B před A A ∼ B: agent mezi A a B nemá žádnou preferenci (nerozlišuje A a B) Co je A nebo B? mohou to být stavy světa, ale pro neurčité výstupy se používají loterie loterie popisuje možné výstupy S1, . . . , Sn, které se vyskytují s danými pravděpodobnostmi p1, . . . , pn [p1, S1; . . . , pn, Sn] Příklad loterie (nabídka jídla v letadle): Chcete kuře nebo těstoviny? [0.8, dobré kuře; 0.2 připečené kuře] [0.7, dobré těstoviny; 0.3, rozvařené těstoviny] Hana Rudová, IV126, FI MU: Užitek a rozhodování 219 8. ledna 2021 Funkce užitku Existuje funkce užitku vracející pro danou loterii reálné číslo tak, že U(A) < U(B) ⇔ A < B U(A) = U(B) ⇔ A ∼ B Očekáváný užitek loterie lze spočítat: U([p1, S1; . . . , pn, Sn]) = i pi U(Si ) Racionální agent ani nemusí svoji funkci užitku znát, ale pozorováním jeho preferencí ji lze zrekonstruovat Jak zjistit funkci užitku konkrétního agenta (preference elicitation)? budeme hledat normalizovanou funkci užitku uvažujme nejlepší možný stav Smax a dejme mu užitek 1: U(Smax) = 1 podobně pro nejhorší možný stav Smin a dejme užitek 0: U(Smin) = 0 nyní se pro libovolný stav S ptejme agenta na porovnání S a standardní loterie [p, Smax; 1 − p, Smin] podle výsledku upravíme pravděpodobnost p a ptáme se znova, dokud agent vztah A a standardní loterie nepovažuje za nerozlišitelný získané p je užitkem S: U(S) = p Hana Rudová, IV126, FI MU: Užitek a rozhodování 220 8. ledna 2021 Peníze jako užitek? V běžném životě používáme peníze pro ohodnocení různého zboží a služeb agent zpravidla preferuje více peněz před méně penězi, je-li vše ostatní stejné Proč nejsou peníze přímo mírou užitku? Uvažujme, že jsme vyhráli 1 mil USD a můžeme si ho buď nechat nebo přimeme sázku na hod mincí – padne-li orel, dostaneme 2,5 mil. USD, jinak nic. Co zvolíte? očekávaný peněžní zisk při sázce je 1,25 mil USD většina lidí ale volí jistotu 1 mil. USD, je to snad iracionální? Hana Rudová, IV126, FI MU: Užitek a rozhodování 221 8. ledna 2021 Užitek z peněz Volba v předchozí hře závisí nejen na hře samé, ale i na současném majetku hráče! Nechť Sn je stav označující majetek n USD Potom můžeme očekávaný užitek (EU) akcí popsat takto EU(Accept) = 1 2 U(Sk ) + 1 2 U(Sk+2 500 000) EU(Decline) = U(Sk+1 000 000) Nechť U(Sk)=5, U(Sk+1 000 000)=8, U(Sk+2 500 000)=9 tj. EU(Accept) = 7, EU(Decline) = 8 Potom je rozhodnutí odmítnout sázku zcela racionální! Hana Rudová, IV126, FI MU: Užitek a rozhodování 222 8. ledna 2021 Více atributů V praxi se často vyskytuje více atributů užitku, např. cena, nebezpečnost, užitečnost – víceatributová funkce užitku Budeme uvažovat, že každý atribut má definované preferované pořadí hodnot, vyšší hodnoty odpovídají lepšímu řešení Jak definovat preference pro více atributů dohromady? přímo bez kombinace hodnot atributů – dominance pokud je ve všech atributech řešení A horší než řešení B, potom B je lepší i celkově – striktní dominance lze použít i pro nejisté hodnoty atributů – stačí, když každá možná hodnota všech atributů A je horší, než každá možná hodnota odpovídajících atributů B striktní dominance není moc obvyklá, ale může alespoň odfiltrovat špatná řešení kombinací hodnot atributů do jedné hodnoty pokud jsou atributy (preferenčně) nezávislé, lze použít aditivní oceňovací funkci U(x1, . . . , xn) = i Ui (xi ) může se jednat např. o vážený součet atributů Hana Rudová, IV126, FI MU: Užitek a rozhodování 223 8. ledna 2021 Rozhodovací sítě Jak obecně popsat mechanismus rozhodování? Rozhodovací síť (influenční diagram) popisuje vztahy mezi vstupy (současný stav), rozhodnutími (budoucí stav) a užitkem (budoucího stavu) Náhodné uzly (ovál) reprezentují náhodné proměnné stejně jako v Bayesovských sítích Rozhodovací uzly (obdélníky) popisují rozhodnutí (výběr akce), které může agent udělat (zatím uvažujeme jednoho agenta) Uzly užitku (kosočtverce) popisují funkci užitku zjednodušená rozhodovací síť eliminující budoucí stavy (nelze pozorovat hodnoty) Hana Rudová, IV126, FI MU: Užitek a rozhodování 224 8. ledna 2021 Rozhodovací sítě: vyhodnocovací algoritmus Akce jsou vybrány na základě vyzkoušení všech možných hodnot rozhodovacího uzlu 1. nastavíme hodnoty pozorovaných proměnných 2. pro každou možnou hodnotu rozhodovacího uzlu 2.1 nastavíme rozhodovací uzel na danou hodnotu 2.2 použitím pravděpodobnostní inference vypočteme pravděpodobnosti rodičů uzlu užitku 2.3 vypočteme užitek pomocí funkce užitku 3. vybereme akci s největším užitkem Pro případy, kde je více uzlů užitku používáme při výběru akce techniky pro víceatributové funkce užitku Přímé rozšíření algoritmu pro Bayesovské sítě při rozhodování agenta vybíráme akci s největším užitkem Zajímavější problém až při vykonávání posloupnosti rozhodnutí Hana Rudová, IV126, FI MU: Užitek a rozhodování 225 8. ledna 2021 Rozhodovací sítě: konstrukce a příklad Vytvoření kauzálního modelu určení symptomů, nemocí, léčby a vztahů mezi nimi (dom.experti, literatura) Zjednodušení kvalitativního modelu pokud nám jde o léčbu, můžeme odstranit uzly, které s nimi nesouvisí některé uzly lze spojit (léčba Treatment a její načasování Timing) Přiřazení pravděpodobností – z kauzálních vazeb, diagnostické vazby z BS: vyplnění pravděpodobnostních tabulek jako v Bayesovské síti (dle učebnic, databází pacientů,rozhodnutí experta) Navržení funkce užitku můžeme enumerovat možné výstupy (záleží nejen na lékaři ale i na pacientovi, který může mít jiné preference) Verifikace a doladění modelu výsledky se porovnají se zlatým standardem, např. skupinou lékařů Analýza citlivosti kontrola, zda výsledky systému nejsou citlivé na drobné změny vstupu (malé změny vstupu vedoucí k velkým rozdílům výstupu indikují problém v modelu) Hana Rudová, IV126, FI MU: Užitek a rozhodování 226 8. ledna 2021 Shrnutí Teorie pravděpodobnosti nám umožní kvantifikovat, jak máme danému tvrzení věřit na základě pozorování Bayesovské sítě a odvozování pomocí nich staticky v daném čase Pravděpodobnostní uvažování o čase reprezentace přechodů s pravděpodobností: Markovský proces zjištění pravděpodobnosti stavu vzhledem k probíhajícímu času Teorie užitku pro ohodnocení rozhodnutí Teorie rozhodování pro jedno rozhodnutí (statický případ) příště: pro posloupnost rozhodnutí Hana Rudová, IV126, FI MU: Užitek a rozhodování 227 8. ledna 2021 Sekvenční rozhodovací problémy 8. ledna 2021 34 Markovský rozhodovací proces 35 Užitek v čase 36 Iterace hodnot 37 Iterace strategie Zdroje: Roman Barták, přednáška přednáška Umělá inteligence II, Matematicko-fyzikální fakulta, Karlova univerzita v Praze, 2015. http: // kti. ms. mff. cuni. cz/ ~bartak/ ui2 Úvod Cílem je tvorba racionálních agentů maximalizujících očekávanou míru užitku Teorie pravděpodobnosti říká, čemu máme věřit na základě pozorování Teorie užitku (utility theory) popisuje, co chceme a jak máme ohodnotit rozhodnutí Teorie rozhodování (decision theory) spojuje obě teorie dohromady a popisuje, jak bychom měli vybrat akci s největším očekávaným užitkem minule: statický případ (jedno rozhodnutí) dnes: i na posloupnost rozhodnutí Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 229 8. ledna 2021 Sekvenční rozhodovací problémy Doposud jedno rozhodnutí → nyní posloupnost rozhodnutí užitek bude záviset na posloupnosti rozhodnutí Uvažujme agenta pohybujícího se v prostředí o rozměrech 3 × 4 Prostředí je plně pozorovatelné (agent vždy ví, kde se nachází) Agent se chce dostat do stavu +1 a vyhnout se stavu -1 Agent může provést akce Up, Down, Left, Right množinu akcí pro stav s značíme A(s) výsledek akce je ale nejistý s pravděpodobností 0.8 půjde správným směrem s pravděpodobností 0.1 půjde kolmo k požadovanému směru (resp. stojí na místě, pokud narazí na zeď) pravděpodobnost [Up, Up, Right, Right, Right]: 0.85 celkem ze START do cíle (stav +1): 0.85 + 0.14 ∗ 0.8 = 0.32776 (+ cesta dokola [Right, Right, Up, Up, Right]) Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 230 8. ledna 2021 Příklad: pravděpodobnost dosažení stavu Na která pole a s jakou pravděpodobností můžete dojít z pole (1,1) posloupností [Up, Up, Right, Right, Right]? Nápověda: nakreslete si strom se stavy dosaženými po každém kroku s pravděpodobnostmi přechodu do daného stavu. Dále: Pravděpodobnost dosažení listu je součin pravděpodobností po cestě (pravděpodobnosti jsou Markovské). Pokud se stejný stav vyskytuje ve více listech, pravděpodobnosti sečteme (cesty jsou disjunktní). Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 231 8. ledna 2021 Markovský rozhodovací proces (MDP) Pro popis přechodů (aplikace akce) použijeme pravděpodobnostní distribuci P(s |s, a) – pravděpodobnost přechodu z s do s akcí a opět uvažujeme Markovský předpoklad (pravděpodobnost přechodu nezávisí na předchozích navštívených stavech) Užitek tentokrát závisí na prošlých stavech každý stav má přiřazeno ocenění (reward) R(s) např. +1 (cíl), -1 (nežádoucí stav), -0.04 (ostatní stavy) funkce užitku bude (zatím) součet ocenění navštívených stavů funkce užitku je zde podobná jako při hledání nejkratší cesty do cíle (plus máme stochastický charakter akcí) Markovský rozhodovací proces (Markov Decision Process MDP) sekvenční rozhodovací problém v plně pozorovatelném stochastickém prostředí s Markovským přechodovým modelem a aditivní funkcí užitku tvořen množinou stavů s počátečním stavem s0 množinou akcí v každém stavu A(s) přechodovým modelem P(s |s, a) oceněním R(s) Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 232 8. ledna 2021 Řešení MDP Ve stochastickém prostředí nemůžeme pracovat s pevným pořadím akcí (plánem) agent se může vydat jinam, než bylo naplánováno Protože předem nevíme, kam akce agenta zavede potřebujeme v každém stavu vědět, co dělat (kam jít) Řešením MDP je strategie (policy) π(S), což je funkce určující pro každý stav doporučenou akci hledáme strategii s největším očekávaným užitkem = optimální strategie Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 233 8. ledna 2021 Optimální strategie Optimální strategie maximalizuje očekávaný užitek záleží samozřejmě na ocenění stavů Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 234 8. ledna 2021 Užitek v čase: horizont Jak obecně definovat funkci užitku pro posloupnost stavů? je to podobné jako pro víceatributové funkce užitku U([s0, s1, . . . , sn]) (stavy jsou atributy), ale jaký máme horizont? Konečný horizont máme daný pevný termín N a po něm už na ničem nezáleží U([s0, s1, . . . , sN+k]) = U([s0, s1, . . . , sN]) optimální strategie záleží na termínu (není stacionární) pro N = 3 volí ze stavu (3,1) akci Up pro N = 100 volí ze stavu (3,1) bezpečnou akci Left Nekonečný horizont to neznamená nutně nekonečné posloupnosti stavů, pouze zde není žádný deadline není důvod se ve stejném stavu chovat v různé časy různě optimální strategie je stacionární Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 235 8. ledna 2021 Užitek v čase: definice funkce Funkce užitku se chová jako víceatributová funkce užitku U([s0, s1, . . . , sn]) Pro získání jednoduchého vztahu pro výpočet funkce užitku uvažujme stacionární preference preference posloupnosti stavů [s0, s1, s2, . . .] a [s0, s1, s2, . . .] stejné jako preference [s1, s2, . . .] k [s1, s2, . . .] naše preference „zítra a dnes” jsou stejné V případě stacionárních preferencí jsou dva způsoby, jak rozumně definovat funkci užitku aditivní funkce užitku U([s0, s1, . . . , sn]) = R(s0) + R(s1) + R(s2) + · · · kumulovaná (discounted) funkce užitku U([s0, s1, . . . , sn]) = R(s0) + γR(s1) + γ2 R(s2) + · · · faktor slevy γ ∈ (0, 1) preference mezi aktuálním a budoucím oceněním – γ blízko 0: budoucnost není důležitá, – γ blízko 1: budoucnost je stejně důležitá jako součastnost, tj. obdržíme aditivní funkci užitku Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 236 8. ledna 2021 Užitek v čase: vlastnosti Budeme používat kumulovanou funkci užitku pro světy bez cílového stavu a nekonečný horizont by aditivní funkce užitku byla problémová pro nekonečné posloupnosti stavů dává +∞ nebo −∞ užitek v kumulované funkci užitku je konečný (uvažujeme omezené ocenění s maximem Rmax) U([s0, s1, . . . , sn]) = t=0,...+∞ γt R(st ) ≤ t=0,...+∞ γt Rmax = Rmax/(1 − γ) plyne ze součtu nekonečné geometrické posloupnosti pokud má prostředí cílový stav, do kterého se agent garantovaně může dostat, nebudeme potřebovat pracovat s nekonečnými posloupnostmi řádná (proper) strategie – garantuje dosažení cílového stavu můžeme používat aditivní funkci užitku strategie, které nejsou řádné (improper), mají nekonečný celkový užitek u nekonečné posloupnosti lze porovnat průměrné ocenění lepší je zůstat ve stavu s oceněním 0.1 než ve stavu s oceněním 0.01 analýza tohoto chování však náročná Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 237 8. ledna 2021 Optimální strategie: vlastnosti I. Hledáme očekávaný užitek (střední hodnotu E) strategie π pro počáteční stav s : Uπ (s) = E   t=0,...,+∞ γt R(St)   St je náhodná proměnná popisující stav v čase t připomenutí: používáme kumulovanou funkci užitku Optimální strategie pro počáteční stav s: πs = argmaxπUπ (s) tj. strategie, která maximalizuje očekávaný užitek pro poč.stav s Záleží ale na počátečním stavu? když se strategie πa a πb sejdou v nějakém stavu c, není důvod, aby pokračovaly různě, tj. můžeme používat pouze π Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 238 8. ledna 2021 Optimální strategie: vlastnosti II. Můžeme definovat užitek stavu U(s) = Uπ (s) připomeňme, že Uπ (s) je očekávaný užitek z optimální strategie R(s) je „krátkodobé” ocenění vs. U(s) je „dlouhodobé” ocenění Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 239 8. ledna 2021 Opakování: očekávaný užitek Očekávaný užitek (expected utility) spočteme jako průměrný užitek přes všechny možné stavy vážené pravděpodobností výsledků EU(a|e) = s P(Result(a) = s|a, e)U(s) e pozorování, a akce Result(a) náhodná proměnná, jejíž hodnoty jsou možné výsledné stavy Racionální agent potom volí akci maximalizující očekávaný užitek MEU akce = argmaxaEU(a|e) Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 240 8. ledna 2021 Optimální strategie: vlastnosti II. (pokračování) Můžeme definovat užitek stavu U(s) = Uπ (s) připomeňme, že Uπ (s) je očekávaný užitek z optimální strategie R(s) je „krátkodobé” ocenění vs. U(s) je „dlouhodobé” ocenění akce budeme vybírat na základě principu maximalizace očekávaného užitku v následujícím stavu π (s) = argmaxa∈A(s) s P(s |s, a)U(s ) připomeňme, že P(s |s, a) je pravděpodobnost přechodu z s do s akcí a pozor, to nemusí být akce vedoucí do stavu s největším U(s)! Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 241 8. ledna 2021 Bellmanova rovnice Navrhnout algoritmus pro řešení MDP? spočítáme užitek každého stavu použijeme ho pro výběr optimální akce v každém stavu Užitek stavu přímo závisí na užitku okolních stavů (pokud agent volí optimální akci) U(s) = R(s) + γ max a∈A(s) s P(s |s, a) U(s ) Tomuto vztahu se říká Bellmanova rovnice U((1, 1)) = −0.04 + γ max[ 0.8U(1, 2) + 0.1U(2, 1) + 0.1U(1, 1), (Up) 0.9U(1, 1) + 0.1U(1, 2), (Left) 0.9U(1, 1) + 0.1U(2, 1), (Down) 0.8U(2, 1) + 0.1U(1, 2) + 0.1U(1, 1)] (Right) Po doplnění čísel z obrázku dostaneme Up jako nejlepší akci Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 242 8. ledna 2021 Iterace hodnot (užitku) Na základě Bellmanovy rovnice U(s) = R(s) + γ max a∈A(s) s P(s |s, a) U(s ) můžeme navrhnout algoritmus pro řešení MDP pro n stavů máme n rovnic s n proměnnými proměnná pro stav s = užitek stavu s Problém je, že máme soustavu nelineárních rovnic pozn. max není lineární operátor Použijeme iterativní postup 1 začneme s libovolnými vstupními hodnotami U(s) (např. nulovými) 2 U(s) upravíme na základě Bellmanových rovnic (Bellmanův update) Ui+1(s) = R(s) + γ max a∈A(s) s P(s |s, a) Ui (s ) Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 243 8. ledna 2021 Iterace hodnot (užitku): algoritmus Tedy použijeme už popsaný iterativní postup 1 začneme s libovolnými vstupními hodnotami U(s) (např. nulovými) 2 U(s) upravíme na základě Bellmanových rovnic (Bellmanův update) Ui+1(s) = R(s) + γ max a∈A(s) s P(s |s, a) Ui (s ) function iterace-hodnot(mdp, ) returns funkci užitku (mdp: MDP a jeho stavy S, akce A(s), přechodový model P(s |s, a) ocenění R(s), faktor slevy γ : maximální dovolená chyba v užitku libovolného stavu U, U : vektory užitku pro stavy v S, iniciálně 0 δ: maximální změna užitku libovolného stavu v iteraci) repeat U = U ; δ = 0; for each stav s ∈ S do U [s] = R(s) + γ maxa∈A(s) s P(s |s, a) U[s ]; if |U [s] − U[s]| > δ then δ = |U [s] − U[s]|; until δ < (1 − γ)/γ; return U Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 244 8. ledna 2021 Iterace hodnot: konvergence a příklad Graf vývoje hodnot užitku po jednotlivých iteracích při ocenění R(s): 1/-1/-0.04 pro dané stavy (4,1), (3,1), (1,1), ... grafy (4,1), (3,1), (1,1) na začátku klesají, protože nevíme, že jdeme do cíle Jak můžeme garantovat konvergenci iterace hodnot ke skutečné hodnotě užitku stavu? Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 245 8. ledna 2021 Iterace hodnot: konvergence Bellmanův update splňuje vlastnost kontrakce (|f (x) − f (x)| < c|x − x |, kde 0 ≤ c < 1) má jediný pevný bod po každé iteraci se přiblížíme k pevnému bodu Vzdálenost měříme jako maximální vzdálenost odpovídajících prvků vektoru |U − U | := maxs |U(s) − U (s)| Nechť BU je Bellmanův update vektoru U a Ui vektor užitku v iteraci i, potom Ui+1 ← BUi lze ukázat: |BUi − BUi | ≤ γ|Ui − Ui | (Bellm.update je kontrakcí o faktor γ) tj. |BUi − U| ≤ γ|Ui − U|, kde U je hledaný užitek stavu (pevný bod) Z kontrakce lze odvodit počet kroků pro přiblížení se k U na vzdálenost ukončovací podmínku pro dosažení vzdálenosti od U |Ui+1 − Ui | ≤ (1 − γ)/γ Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 246 8. ledna 2021 Iterace hodnot: ztráta strategie Agenta fakticky zajímá, jak dobrá je strategie πi dle aktuální hodnoty Ui vzhledem k optimální strategii π Uπi (s) užitek získaný prováděním πi ze stavu s definujeme ztrátu strategie πi jako |Uπi − U| pokud |Ui − U| < , potom |Uπi − U| < γ/(1 − γ) V praxi strategie často konverguje k optimální strategii rychleji než funkce užitku a pevného bodu dosáhne dříve Viz náš příklad s γ = 0.9: Max error |Ui − U| Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 247 8. ledna 2021 Iterace hodnot: cvičení Uvažujte 3×3 svět. Přechodový model je stejný jako v původním 3×4 světě: 80% času jde agent směrem, který si vybere, a zbytek času se pohybuje v pravých úhlech směrem k předpokládanému směru. Realizujte iteraci hodnot pro každou uvedenou hodnotu r. Používejte faktor slevy 0.99 a vypočítejte strategii pro každé r. Vysvětlete intuitivně, proč jednotlivé hodnoty r vedou k dané strategii. r = −100 r = −3 r = 0 r = +3 Výsledné strategie r = −100 → → . ↓ → ↑ → → ↑ r = −3 → → . → → ↑ → → ↑ r = 0 → → . ↑ ↑ ↑ ↑ ↑ ↑ r = 3 ↑ ← . ↑ ← ↓ ↑ ← ← Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 248 8. ledna 2021 Iterace strategie: princip Optimální strategii můžeme získat, i když je funkce užitku ještě nepřesná pokud jedna akce jasně lepší než ostatní, pak užitek stavu nemusí být přesný To můžeme využít u jiného algoritmu řešení MDP, tzv. iterace strategie, který je založený na opakování následujících kroků 1 evaluace strategie – výpočet Uπi pro strategii πi protože známe akce, řešíme zjednodušené (lineární) Bellmanovy rovnice Uπi (s) = R(s) + γ s P(s |s, πi (s)) Uπi (s ) zjednodušeno z Ui+1(s) = R(s) + γ maxa∈A(s) s P(s |s, a) Ui (s ), protože použijeme přímo stav π(s) Příklad: Uvažujme ocenění stavů −0.04 a strategii na obrázku Pak máme πi (1, 1) = Up, πi (1, 2) = Up, ... a zjednodušené rovnice Ui (1, 1) = −0.04 + 0.8Ui (1, 2) + 0.1Ui (1, 1) + 0.1Ui (2, 1) Ui (1, 2) = −0.04 + 0.8Ui (1, 3) + 0.2Ui (1, 2) ...Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 249 8. ledna 2021 Iterace strategie: princip (pokračování) Optimální strategii můžeme získat, i když je funkce užitku ještě nepřesná pokud jedna akce jasně lepší než ostatní, pak užitek stavu nemusí být přesný To můžeme využít u jiného algoritmu řešení MDP, tzv. iterace strategie, který je založený na opakování následujících kroků 1 evaluace strategie – výpočet Uπi pro strategii πi protože známe akce, řešíme zjednodušené (lineární) Bellmanovy rovnice Uπi (s) = R(s) + γ s P(s |s, πi (s)) Uπi (s ) zjednodušeno z Ui+1(s) = R(s) + γ maxa∈A(s) s P(s |s, a) Ui (s ), protože použijeme přímo stav π(s) pro malý počet stavů lze použít přesný výpočet metodami lineární algebry s časovou složitostí O(n3 ) pro větší počet stavů použijeme několik kroků zjednodušené iterace hodnot (zjednodušení ∼ strategie je zafixována): Uj+1(s) = R(s) + γ s P(s |s, πi (s)) Uj (s ) 2 zlepšení strategie πi+1(s) = argmaxa∈A(s) s P(s |s, a)Uπi (s ) Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 250 8. ledna 2021 Iterace strategie: algoritmus (se zjednodušenou iterací hodnot) function iterace-strategie(mdp) returns strategii (mdp: MDP a jeho stavy S, akce A(s), přech. model P(s |s, a) U: vektor užitku pro stavy v S, iniciálně 0 π: vektor strategie pro stavy v S, iniciálně náhodný) repeat U = evaluace-strategie(π, U, mdp); zmena = false; for each stav s ∈ S do (existuje lepší akce pro s než aktuální π[s]?) if max a∈A(s) s P(s |s, a) U[s ] > s P(s |s, π[s]) U[s ] then π[s] = argmaxa∈A(s) s P(s |s, a) U[s ]; zmena = true; until not(zmena); return π Strategií konečně mnoho, při každém kroku strategii zlepšena ⇒ alg. musí skončit Často mnohem efektivnější než iterace hodnot Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 251 8. ledna 2021 Práce s neurčitostí: shrnutí Teorie pravděpodobnosti nám umožní kvantifikovat, jak máme danému tvrzení věřit na základě pozorování Bayesovské sítě a odvozování pomocí nich staticky v daném čase Pravděpodobnostní uvažování o čase reprezentace přechodů s pravděpodobností: Markovský proces zjištění pravděpodobnosti stavu vzhledem k probíhajícímu času Teorie užitku pro ohodnocení rozhodnutí Teorie rozhodování pro jedno rozhodnutí (statický případ) pro posloupnost rozhodnutí Hana Rudová, IV126, FI MU: Sekvenční rozhodovací problémy 252 8. ledna 2021 Robotika 8. ledna 2021 Zdroje: Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, third edition. Prentice Hall, 2010. http: // aima. cs. berkeley. edu/ Steven M. LaValle, Planning algorithms, Cambridge University Press, 2006. http: // planning. cs. uiuc. edu/ Robotika: obsah 38 Robot, hardware 39 Vnímání robota 40 Rozvrhování robotů 41 Plánování pohybu robota Konfigurační prostor Plánování na grafech Prohledávací algoritmy Kombinatorické přístupy k plánování pohybu Graf viditelnosti Voroného diagram Buňková dekompozice Potenční funkce Pravděpodobnostní přístupy k plánování pohybu Vzorkování Pravděpodobnostní cestovní mapa (PRM) Rychle prozkoumávající náhodný strom (RRT) Shrnutí 42 Pohyb robota Hana Rudová, IV126, FI MU: Robotika 254 8. ledna 2021 Robot Robot: fyzický agent, který vykonává úlohy manipulací s fyzickým světem pro realizaci úloh robot vybaven efektory např. nohy, kola, klouby, chapadla účelem efektoru je uplatnění fyzických sil na prostředí dále robot vybaven senzory, které umožňují vnímání např. kamery a lasery pro pozorování prostředí, gyroskopy a akcelerometry pro měření pohybu robota Typy robotů manipulátor: fyzicky připevněné k pracovnímu místu robotická ruka mobilní robot: pohybují se v prostředí pomocí kol, nohou apod. bezpilotní pozemní vozidlo (unmanned ground vehicle UGV) pro autonomní jízdu planetární vozidlo (planetary rover) bezpilotní letadlo (unmanned air vehicle UAV) bezpilotní ponorka (autonomous underwater vehicle AUV) mobilní manipulátor: kombinace mobility s manipulací – humanoidní roboti Hana Rudová, IV126, FI MU: Robotika 255 8. ledna 2021 Mobilní manipulátor: příklady NASA Mars Exploration Rover (vesmír) 2003: odlet na Mars dvojice robotů, přistání 2004 výzkum skal, půdy, dřívější vodní aktivity (robotické paže) DLR Rollin’ Justin (profesionální a domácí služby) představen 2008 firmou DLR, poloviční humanoid, posun na kolech 2012: rychlejší paže (ruce se 4 prsty) pro interakci se všemi typy objektů Hana Rudová, IV126, FI MU: Robotika 256 8. ledna 2021 Mobilní manipulátor: příklady – armáda Detekce a zneškodňování těžkých výbušných zbraní a improvizovaných výbušných zařízení ECA Group TSR202 představen 2009 (ECA Group) 70 kg kapacita Iguana E představen 2015 (ECA Group) lehký modulární robot (20 kg zdvih) obtížně dosažitelné prostory Hana Rudová, IV126, FI MU: Robotika 257 8. ledna 2021 Mobilní manipulátor: příklady – průmysl Automatizace průmyslové výroby Neobotix MM-800 2010: použití v továrně Audi AG KMR iiwa představen 2016 (KUKA AG) Hana Rudová, IV126, FI MU: Robotika 258 8. ledna 2021 Konfigurace mobilního manipulátoru: příklad Mobilní platforma: pohyb, navigace, plánování cesty (překážky) Manipulace robota: robotická paže pro montážní úkony Pořízení a zpracování obrazu Práce s nástrojem: 2 „prsty” Hana Rudová, IV126, FI MU: Robotika 259 8. ledna 2021 Sociální robot – příklad z FI Robot Pepper: https://nlp.fi.muni.cz/trac/pepper/ https://nlp.fi.muni.cz/trac/pepper/chrome/site/pepper/ 2019-02-04-m2u00747-meet-and-can.ogg Hana Rudová, IV126, FI MU: Robotika 260 8. ledna 2021 Robotický hardware: senzory Senzory představují rozhraní mezi robotem a prostředím pasivní senzory slouží k pozorování prostředí, kdy zachycují signály generovanými dalšími zdroji v prostředí aktivní senzory vysílají energii do prostředí (např. sonar) založeny na tom, že je energie reflektována senzoru zpět poskytují více informací než pasivní senzory náročnější na energii než pasivní senzory hrozí nebezpečí interfence při použití více aktivních senzorů zároveň Senzory dělíme v závislosti na tom, zda určeny pro vnímání prostředí, tj. dálkoměry pro měření vzdálenosti od blízkých objektů robotova umístění, tj. lokační senzory časté řešení lokalizačního problému: Global Positioning System (GPS) robotovy vnitřní konfigurace, např. pro měření přesné konfigurace robotických kloubů, motorů gyroskopy – pro udržení referenčního směru snímače točivého momentu – pro práci s křehkými objekty Hana Rudová, IV126, FI MU: Robotika 261 8. ledna 2021 Robotický hardware: efektory Efektory umožňují robotovi pohyb a změnu tvaru těla Stupeň volnosti (degree of freedom DOF) umožňuje pochopit návrh efektoru jeden DOF pro každý nezávislý směr, ve kterém se robot nebo jeden z jeho efektorů může pohybovat R RR P R R robotická paže s 6 DOFs klouby pro rotační pohyb (R) kloub pro posun (P) Hana Rudová, IV126, FI MU: Robotika 262 8. ledna 2021 Efektory, kinematický a dynamický stav Kinematický stav: určen DOFs u AUV určen 6 DOFs: (x, y, z) + úhlová orientace yaw, roll, pitch Dynamický stav: zahrnuje DOF kinematického stavu + dimenze pro rychlost změny kinematické dimenze (např. 6+6) Počet DOFs nemusí být stejný jako počet ovládaných prvků (mobilní roboti) př. auto: pohyb dopředu/dozadu, otáčení, tj. 2 DOFs kinematická konfigurace třídimenzionální – na otevřeném plochém povrchu pohyb do libovolného (x, y) v libovolné orientaci θ 3 skutečné DOFs avšak jen 2 regulovatelné DOFs (non-holonomic) pokud by byl počet ovládaných a skutečných DOFs stejný, robot by se snáze ovládal (např. auto by šlo posunout do strany) Hana Rudová, IV126, FI MU: Robotika 263 8. ledna 2021 Příklad: VALERI OmniRob Robotická paže s 12 DOFs: 3 DOFs (2 translační, 1 rotační) pro základnu s koly pro přesun robota v libovolném směru 2 DOFs pro sloupec (1 translační – nahoru a dolu, 1 rotační) 7 DOFs pro robotickou paži (1 rotační pro každý spoj – viz vpravo) Hana Rudová, IV126, FI MU: Robotika 264 8. ledna 2021 Vnímání robota Vnímání: proces, kdy robot mapuje měření senzorů na vnitřní reprezentaci prostředí obtížné, protože senzory jsou nepřesné (šum), prostředí je částečně pozorovatelné, nepředvídatelné a často dynamické tj. robot řeší problémy filtrace/odhadu stavu (viz přednáška Čas a neurčitost: P(Xt|e1:t)), kdy je cílem zjištění pravděpodobnosti aktuálního stavu na základě dosavadních pozorování Robotovo vnímání můžeme chápat jako temporální odvozování z posloupnosti akcí a pozorování Xt+1Xt At−2 At−1 At Zt−1 Xt−1 Zt Zt+1 Xt stav prostředí (včetně robota) v čase t Zt pozorování zjištěné v čase t At akce realizovaná po zjištění pozorování Hana Rudová, IV126, FI MU: Robotika 265 8. ledna 2021 Dynamické Bayesovské sítě Připomenutí: Bayesovské sítě – DAG s tabulkami pravděpodobnostní distribuce P(X|Parents(X)) pro uzly reprezentující náhodné proměnné příklad s agentem a pozorováním počasí Dynamická Bayesovská síť (DBN) reprezentuje temporální pravděpodobnostní model skládá se z opakujících se vrstev proměnných stačí tedy popsat první vrstvu apriorní distribuci P(X0) přechodový model P(X1|X0) senzorický model P(E1|X1) dle Markovkých předpokladů má každá proměnná rodiče buď ve stejné nebo předchozí vrstvě Filtrace: P(Xt+1|e1:t+1) = α P(et+1|Xt+1) xt P(Xt+1|xt) P(xt|e1:t) Hana Rudová, IV126, FI MU: Robotika 266 8. ledna 2021 Odhad stavu (filtrace) Dynamická Bayesovská síť reprezentuje přechodový model (model pohybu) a senzorický model v částečně pozorovaném prostředí přechodový model P(Xt+1|xt, at) senzorický model P(zt+1|Xt+1) popisuje na čem závisí nové pozorování zt+1 Xt+1Xt At−2 At−1 At Zt−1 Xt−1 Zt Zt+1 Zajímá nás pravděpodobnost nového stavu Xt+1 na základě dosavadních pozorování (pomocí senzorů) z1:t+1 a akcí a1:t, tj. P(Xt+1|z1:t+1, a1:t) př. Xt+1 může určovat umístění fotbalového míče relativně k robotovi na rozdíl od dříve uvažované filtrace musíme kromě pozorování zahrnout i akce a také spojité místo diskrétních náhodných proměnných tj. odvození je stejné jako u filtrace, ale místo součtu používáme integraci P(Xt+1|z1:t+1, a1:t) = α P(zt+1|Xt+1) P(Xt+1|xt, at)P(xt|z1:t, a1:t−1) dxt máme tak rekurzivní filtrační rovnici, kdy se pravděpodobnost X v čase t + 1 spočítá na základě odhadu o časovou jednotku dříve Hana Rudová, IV126, FI MU: Robotika 267 8. ledna 2021 Typy vnímání Lokalizace: problém zjišťování polohy objektů včetně robota můžeme znát mapu, a pak hledáme pozici na mapě (úloha mapování) mapa nemusí být k dispozici, pak je realizována současně lokalizace a mapování Vnímání teploty, pachů, akustických signálů apod. Lze vyhodnotit pomocí dynamických Bayesovských sítí, např. Monte Carlo lokalizace potřebujeme znát podmíněné pravděpodobnostní distribuce charakterizující evoluci stavu proměnných v čase a senzorické modely, které popisují vztahy k pozorovaným proměnným použitelné pro diskrétní proměnné Kalmanových filtrů vhodné pro spojité proměnné strojového učení Více např. Norvig & Russel nebo Barták, UI II Hana Rudová, IV126, FI MU: Robotika 268 8. ledna 2021 Příklad DBN: robot a jeho pozice + rychlost Popis chování robota poloha robota Xt = (Xt, Yt) rychlost robota ˙Xt = ( ˙Xt, ˙Yt) pozorování polohy pomocí GPS Zt Přidáme baterii stav baterie Batteryt další poloha záleží na rychlosti a původní poloze další rychlost záleží na předchozí rychlosti a stavu baterie senzor BMetert pozorování stavu baterie Hana Rudová, IV126, FI MU: Robotika 269 8. ledna 2021 Rozvrhování robotů v továrně Job shop problém s transportem a zpracováním roboty Stroje rozmístěné v továrně dle matice vzdáleností jeden stroj může zpracovávat nejvýše jednu úlohu Úlohy: výroba výrobků nepřekrývající se operace určeno pořadí operacích na stroji odlišný stroj pro každou operaci Roboti: identiční převáží vyráběné výrobky zpracovávají některé operace se stroji Hana Rudová, IV126, FI MU: Robotika 270 8. ledna 2021 Jednoduchý příklad Machine L/U M1 M2 M3 M4 L/U 0 6 8 10 12 M1 12 0 6 8 10 M2 10 6 0 6 8 M3 8 8 6 0 6 M4 6 10 8 6 0 Op.1 Op.2 Op.3 Job 1 M1(8) M2(16) M4(12) Job 2 M1(20) M3(10) M2(18) Job 3 M3(12) M4(8) M1(15) Job 4 M4(14) M2(18) – Job 5 M3(10) M1(15) – Cíl přiřazení startovního času a robota pro operace a transport minimalizovat čas dokončení výroby, tzv. makespan Cmax Hana Rudová, IV126, FI MU: Robotika 271 8. ledna 2021 Genetický algoritmus kombinovaný s tabu prohledáváním t ← 1 initialize Pt (Pt population of individuals/solutions) tabu search Pt; evaluate Pt while t ≤ maxGenerations do if partial reinitialization then initialize It to become a part of Pt tabu search It; evaluate It create Ct by crossover of individuals from Pt tabu search Ct; evaluate Ct replace the worst inidividuals from Pt by Ct create Mt by mutation of individuals from Pt tabu search Mt; evaluate Mt replace the chosen inidividuals in Pt by Mt decrease population size of Pt by eliminationg the worst individuals update and keep the best individuals in Pt t ← t + 1 Hana Rudová, IV126, FI MU: Robotika 272 8. ledna 2021 Řešení (jedinci/chromozomy), funkce vhodnosti (fitness) Chromozom e e1 e2 e3 e4 e5 e6 Posloupnost j,o 2,1 1,1 3,1 1,2 2,2 3,2 Transportní robot 1 2 1 2 1 1 Zpracovávající robot – 2 – – 2 1 Stroj 1 3 2 1 2 3 Hana Rudová, IV126, FI MU: Robotika 273 8. ledna 2021 Tabu prohledávání na robotech t ← 1 initialize Pt tabu search Pt; evaluate Pt while t ≤ maxGenerations do . . . update and keep the best individuals in Pt t ← t + 1 tabu search Pt: forall individuals e in Pt repeat random change of transporting robot in e random change of processing robot in e assigned robots stored in tabu list not to be selected repeatedly if new better individual e then e = e Hana Rudová, IV126, FI MU: Robotika 274 8. ledna 2021 Reinicializace t ← 1 initialize Pt tabu search Pt; evaluate Pt while t ≤ maxGenerations do if partial reinitialization then initialize It to become a part of Pt tabu search It; evaluate It create Ct by crossover of individuals from Pt tabu search Ct; evaluate Ct replace the worst inidividuals from Pt by Ct create Mt by mutation of individuals from Pt tabu search Mt; evaluate Mt replace the chosen inidividuals in Pt by Mt decrease population size of Pt by eliminationg the worst individuals update and keep the best individuals in Pt t ← t + 1 Hana Rudová, IV126, FI MU: Robotika 275 8. ledna 2021 Křížení & mutace pro posloupnosti operací t ← 1 initialize Pt tabu search Pt; evaluate Pt while t ≤ maxGenerations do update and keep the best individuals in Pt if partial reinitialization then initialize It to become a part of Pt tabu search It; evaluate It create Ct by crossover of individuals from Pt tabu search Ct; evaluate Ct replace the worst inidividuals from Pt by Ct create Mt by mutation of individuals from Pt tabu search Mt; evaluate Mt replace the chosen inidividuals in Pt by Mt decrease population size of Pt by eliminationg the worst individuals t ← t + 1 Hana Rudová, IV126, FI MU: Robotika 276 8. ledna 2021 Posloupnost operací: operátor křížení & mutace Křížení Pravděpodobnost křížení a mutace Mutace náhodná operace j,o vložena náhodně mezi předchůdce j,o-1 a následníka j,o+1 Hana Rudová, IV126, FI MU: Robotika 277 8. ledna 2021 Různé metody řešení Heuristické přístupy Genetický algoritmus s tabu prohledáváním [1] Adaptivní prohledávání s velkým okolím [2] sada heuristik pro výběr souseda výpočet váhy pro heuristiky dle úspěšnosti výběr heuristiky dle jejich váhy Exaktní přístupy Celočíselné programování [1] Programování s omezujícími podmínkami [3] 1. Dang, Nguyen, Rudová, Scheduling of mobile robots for transportation and manufacturing tasks. Journal of Heuristics, 25(2):175–213, 2019. 2. Dang, Rudová, Nguyen, Adaptive large neighborhood search for scheduling of mobile robots. In Genetic and Evolutionary Computation Conference (GECCO), pages 224-232, 2019. 3. Murín and Rudová, Scheduling of Mobile Robots using Constraint Programming. In 25th International Conference on Principles and Practice of Constraint Programming (CP), pages 456–471. Springer LNCS 11802, 2019. Hana Rudová, IV126, FI MU: Robotika 278 8. ledna 2021 Plánování pohybu robota: konfigurační prostor Základem je rozhodování, jakým způsobem přesunout efektory Pohyb z bodu do bodu: přesun robota (nebo jeho efektoru) do cíle Koordinovaný pohyb (compliant motion) robot se přesunuje v kontaktu s předmětem např. šroubování žárovky, přesun krabice na stůl Konfigurační prostor (configuration space, C-space) používá se pro reprezentaci plánovacího problému je to prostor stavů robota definovaný jeho umístěním, orientací a úhly kloubů vhodnější reprezentace než původní 3D prostor (viz dále robotická paže) tzv. pracovní prostor Hana Rudová, IV126, FI MU: Robotika 279 8. ledna 2021 Reprezentace pracovního prostoru Robotická paže se dvěma klouby pohyb kloubů mění (x, y) souřadnice kolena a chapadla (souřadnice z se nemění) jak popsat konfiguraci paže? (xe , ye ) umístění kolena (xc , yc ) umístění chapadla Souřadnice určují reprezentaci pracovního prostoru (workspace representation), tj. shou elb shoshoshoshoshoshoshoshoshoshoshoshosho elbelbelbelbelbelbelbelbelbelbelbelbelbelb reálného prostoru, kdy jsou souřadnice robota zadány stejným souřadným systémem jako objekty, kterými manipulujeme reprezentace vhodná pro kontrolu kolizí zejména robota a objektů zadaných jednoduchými polygonálními modely problémy: všechny souřadnice pracovního prostoru nejsou dosažitelné i díky omezením daným vazbami např. fixní vzdálenost (xk , yk ) a (xc , yc ) generování cest, které dodržují tato omezení je velmi náročné! plyne ze spojitého prostoru a nelinearity omezení Hana Rudová, IV126, FI MU: Robotika 280 8. ledna 2021 Reprezentace konfiguračního prostoru Reprezentace pomocí robotových kloubů stav reprezentován úhly ϕs a ϕe ϕs úhel ramena, ϕe úhel kolena tj. určuje konfigurační prostor pokud neuvažujeme překážky, každá kombinace hodnot ϕs a ϕe je možná plánování cesty: spojíme aktuální pozici a cíl rovnou čarou a robot se po ní pohybuje konstatní rychlostí, dokud nedorazí do cíle e table table left wall vertical obstacle s e s problém: úloha robota většinou zadána v pracovním a ne v konfig. prostoru transformace souřadnic z konfiguračního prostoru do pracovního prostoru, tzv. kinematika je jednoduchá lineární transformace pro otočné klouby inverzní kinematika (opačná transformace) obtížná (zejména při více DOFs) zřídka jedno řešení, např. pozice chapadla (viz obrázek dříve) umožňují dvě konfigurace (koleno pod ramenem) Hana Rudová, IV126, FI MU: Robotika 281 8. ledna 2021 Překážky conf-3 conf-1 conf-2 conf-3 conf-2 conf-1 e ss e Pracovní prostor (vlevo) překážky mají jednoduchý geometrický tvar Konfigurační prostor (vpravo) díky překážkám je prostor členěn na obsazený (tmavé odstíny) a volný (bílá) Konstrukce volného prostoru náročná, místo toho: plánovač generuje konfiguraci a testuje, zda je ve volném prostoru (aplikací kinematiky robota a kontrolou kolize v souřadnicích pracovního prostoru) Hana Rudová, IV126, FI MU: Robotika 282 8. ledna 2021 Konfigurační prostor s překážkami Jak získat konfigurační prostor s překážkami? Plánování pohybu diskového robota A s poloměrem ρ geometrická reprezentace pracovního prostoru konfigurační prostor s překážkami Konfigurační prostor získán zvětšením překážek diskem A s poloměrem ρ pomocí Minkowského sumy Hana Rudová, IV126, FI MU: Robotika 283 8. ledna 2021 Minkowského suma Minkowského suma dvou množin P a Q značená P ⊕ Q definovaná P ⊕ Q = {p + q | p ∈ P, q ∈ Q} p q Minkowského suma dvou konvexních polygonů P a Q s m a n vrcholy je polygon P ⊕ Q s m + n vrcholy vrcholy P ⊕ Q jsou „součty” vrcholů P a Q Použití složitost: časová O(n + m), prostorová O(n + m) nekonvexní překážky dekompozice na konvexní polygony, výpočet Minkowského sumy a spojení; složitostO(n2 m2 ) 3D prostor Hana Rudová, IV126, FI MU: Robotika 284 8. ledna 2021 Shrnutí: dnes a příště Robot, hardware typy robotů senzory (rozhraní robot-prostředí) efektory (pro pohyb a změnu tvaru) Vnímání robota odhad stavu (dynamické Bayesovské sítě) lokalizace a mapování Rozvrhování robotů rozvrhování transportu a zpracování roboty v továrně genetický algoritmus kombinovaný s tabu prohledáváním Plánování pohybu robota konfigurační prostor (reprezentace, překážky, Minkowského suma) prohledávání v grafu (typy grafů, jump-point prohledávání) přístupy k plánování pohybu (kombinatorické, pravděpodobnostní) Pohyb robota Hana Rudová, IV126, FI MU: Robotika 285 8. ledna 2021 (Diskrétní) plánování pohybu robota Plánování cesty (path planning) problém nalezení cesty z jedné konfigurace do druhé v konfig. prostoru na rozdíl od klasického hledání cesty v diskrétním prostoru se pohybujeme ve spojitém prostoru Redukce plánování cesty ve spojitém prostoru na diskrétní problémy prohledávání v grafu kombinatorické metody pravděpodobnostní metody Prohledávání váženého grafu reprezentující konfigurační prostor Dijkstrův algoritmus, A* (známe) Jump-point search Spojitá reprezentace konfiguračního prostoru ⇓ Diskretizace ⇓ Prohledávání grafu Hana Rudová, IV126, FI MU: Robotika 286 8. ledna 2021 Spojité plánování pohybu vs. diskrétní aproximace volného prostoru point cloud voxel map Hana Rudová, IV126, FI MU: Robotika 287 8. ledna 2021 Plánování na grafech Nalezení nejkratší cesty mezi dvěma uzly grafu Buňková dekompozice a cestovní mapy dávají diskrétní reprezentaci (ve formě váženého grafu) konfiguračního prostoru Hana Rudová, IV126, FI MU: Robotika 288 8. ledna 2021 Částečně obsazené buňky E prázdná M obsazená M částečně obsazená Zpracování částečně obsazených buněk: 1 neprocházet tyto buňky neúplné: nemusí existovat cesta 2 procházet tyto buňky nekorektní: může vrátit cestu, která neexistuje 3 zvětšít rozlišení mřížky drahé: zejména ve vyšší dimenzi 4 adaptivní diskretizace ztráta uniformní velikosti mřížky Hana Rudová, IV126, FI MU: Robotika 289 8. ledna 2021 4-connected vs. 8-connected graf 4-connected graf: každý uzel spojený se 4 sousedy 8-connected graf: každý uzel spojený s 8 sousedy Hana Rudová, IV126, FI MU: Robotika 290 8. ledna 2021 Prohledávací algoritmy Dijkstrův algoritmus A*: rozšíření Dijkstrova algoritmu prohledává nejprve uzly v s lepší f (v) = g(v) + h(v) f (v): cena cesty do v h(v): heuristický odhad ceny z v do cíle přípustná heuristika: cena odhadu není výšší než reálná cena Jump-point search: zrychlení A* expanzí vybraných uzlů pro efektivní prohledávání prostoru se čtvercovou mřížkou podrobně viz http: //zerowidth.com/2013/05/05/jump-point-search-explained.html Hana Rudová, IV126, FI MU: Robotika 291 8. ledna 2021 Jump-point search (JPS) jako vylepšení A∗ Existuje mnoho „symetrických” cest stejné ceny A∗ expanduje všechny sousedy aktuálního uzlu pro přímé cesty: expanze příliš mnoha uzlů Cíl: zrychlit A∗ výběrem uzlů pro expanzi Předpoklady: uniformní, 8-connected graf (ve 2D) cena přesunu rovně: 1, diagonální přesun: √ 2 Hana Rudová, IV126, FI MU: Robotika 292 8. ledna 2021 JPS: motivace a myšlenka Nechť x je aktuální uzel a p[x] jeho předchůdce Pak můžeme ignorovat všechny šedé uzly, protože mohou být optimálně dosaženy z p[x] bez cesty přes x Myšlenka: Hana Rudová, IV126, FI MU: Robotika 293 8. ledna 2021 JPS: příklad Vynucený uzel nelze přes něj pokračovat dál zastavíme "skákání", přidáme ho do množiny otevřených uzlů pokračujeme v další iteraci A* Pokračování příkladu viz: https: //zerowidth.com/2013/a-visual-explanation-of-jump-point-search.html Hana Rudová, IV126, FI MU: Robotika 294 8. ledna 2021 JPS: algoritmus (hledání následníků v A*) function identify_successors(G, v, vs, vg ) (v aktuální uzel, vs start, vg cíl) S = ∅; (následníci) N = prune(v, neighbors(v)); (sousedé) for each n ∈ N n = jump(G, v, direction(v, n), vs, vg ); S = S ∪ {n}; return S; function jump(G, v, d, vs, vg ) (v aktuální uzel, d směr, vs start, vg cíl) n = step(v, d); if n ∈ G then return ∅; (překážka nebo venku z mapy) if n = vg then return n; if ∃n’ ∈ neighbors(n) such that n’ vynucen then return n; if d diagonální then for each i ∈ 1,2 then (podívej se horizontálně/vertikálně) if jump(n, di , vs, vg ) = ∅ then return n; return jump(n, d, vs, vg ); Hana Rudová, IV126, FI MU: Robotika 295 8. ledna 2021 JPS: shrnutí Optimální algoritmus Bez preprocesingu Bez navýšení paměti Zrychlení A∗ prohledávání 10x nebo více Daniel Damir Harabor, Alban Grastien, Online graph pruning for pathfinding on grid maps. AAAI 2011. Tutoriály o JPS http://zerowidth.com/2013/05/05/jump-point-search-explained.html https://harablog.wordpress.com/2011/09/07/jump-point-search/ Hana Rudová, IV126, FI MU: Robotika 296 8. ledna 2021 Problém plánování pohybu (motion planning) Základní problém plánování pohybu: nalezení spojité posloupnosti konfigurací, která převede robota z iniciální konfigurace qI do cílové konfigurace qG tak, že se žádná konfigurace po cestě nepřekrývá s překážkou. Cfree volný prostor Cobs překážky Hana Rudová, IV126, FI MU: Robotika 297 8. ledna 2021 Plánování pohybu: postup řešení 1 Předzpracování / učící fáze / konstrukce grafu vypočítání grafu – často označován jako cestovní mapa (roadmap) graf viditelnosti Voroného diagram buňková dekompozice potenční funkce 2 Zpracování dotazu 1 spojení počáteční a cílové konfigurace s grafem 2 identifikace počáteční a cílové buňky 3 prohledávání grafu NEBO Inkrementální konstrukce grafu směrem k cíli rychle prozkoumávající náhodný strom (RRT) Hana Rudová, IV126, FI MU: Robotika 298 8. ledna 2021 Cestovní mapa jako graf viditelnosti (visibility graph) 1 Spojíme všechny páry vrcholů plus iniciální a cílové konfigurace 2 Eliminujeme hrany, které protínají překážky 3 Graf viditelnosti vždy zahrnuje nejkratší cestu konfiguračním prostorem Konstrukce grafu viditelnosti popsaný (naivní) postup pro n vrcholů O(n3 ) s pomocí rotačního stromu pro množinu segmentů O(n2 ) Hana Rudová, IV126, FI MU: Robotika 299 8. ledna 2021 Cestovní mapa: Voroného diagram (VD) Voroného diagram dělí prostor R2 na oblasti podle zadaných objektů, např. bodů x ∈ M každý bod x má přiřazenu Voroného oblast V (x) pro každý bod y ∈ V (x) je x nejbližší bod z M Hana Rudová, IV126, FI MU: Robotika 300 8. ledna 2021 Cestovní mapa jako Voroného diagram Cestovní mapa jako VD, který maximalizuje vzdálenost od překážek body zobecněného VD s cestovní mapou jsou ekvidistantní od dvou bodů hranice Cobs 1 Robot změní konfiguraci na bod ve VD toto lze realizovat pohybem po rovné čáře v konfiguračním prostoru 2 Robot se pohybuje ve VD, dokud nedosáhne bod, který je nejbližší cílové konfiguraci 3 Robot opustí VD a přesune se do cíle opět rovnou čarou v konfiguračním prostoru Hana Rudová, IV126, FI MU: Robotika 301 8. ledna 2021 Graf viditelnosti vs. Voroného diagram Graf viditelnosti nejkratší cesta, ale blízko k překážkám nutno uvažovat bezpečnost cesty komplikované ve vyšší dimenzi Voroného diagram maximalizuje vzdálenost od překážek, což poskytuje konzervativní cesty malé změny překážek mohou vést k velkým změnám VD komplikované ve vyšší dimenzi Pro vyšší dimenze se používají jiné typy cestovních map Hana Rudová, IV126, FI MU: Robotika 302 8. ledna 2021 Buňková dekompozice (cell decomposition) Dekompozice volného prostoru na konečný počet spojitých regionů nazvaných buňky Předpoklad: problém plánování cesty v jedné buňce je jednoduchý např. posun podél rovné čáry Základní buňková dekompozice: pravidelná mřížka úroveň šedi buňky určuje hodnotu buňky = cenu nejkratší cesty do cíle hodnoty spočítáme deterministickou verzí algoritmu iterace hodnot (viz přednášky Nejistota) nebo (upraveným) A* algoritmem start goal start goal Hana Rudová, IV126, FI MU: Robotika 303 8. ledna 2021 Vertikální dekompozice (vertical decomposition) Exaktní buňková dekompozice (př. vertikální/lichoběžníková, triangulace): volný prostor Cfree reprezentován kolekcí nepřekrývajících se buněk, jejichž spojení reprezentuje přesně Cfree 1. Rozdělíme prostor vertikálně dle překážek 2. Centroid reprezentuje buňku 4. Hledáme cestu v grafu 3. Spojíme hranami centroidy sousedních buněk ⇒ graf Hana Rudová, IV126, FI MU: Robotika 304 8. ledna 2021 Konstrukce vertikální dekompozice Jak prostor vertikálně rozdělit dle překážek? plane sweep/sweep line algoritmus z výpočetní geometrie přímka/rovina prochází prostorem přes body, kde dochází ke kritické změně informace kritické změny Hana Rudová, IV126, FI MU: Robotika 305 8. ledna 2021 Oktalová dekompozice (octree decomposition) Metoda přibližné buňkové dekompozice volný prostor Cfree reprezentován kolekcí nepřekrývajících se buněk, jejichž spojení je obsaženo v Cfree příklady: quadtree, 2n-tree, oktalová (octree) dekompozice, pravidelná mřížka Hana Rudová, IV126, FI MU: Robotika 306 8. ledna 2021 Buňková dekompozice: náčrt algoritmu 1 Spočítej buňkovou dekompozici až k danému rozlišení 2 Idenfikuj startovní a cílovou buňku 3 Prohledávej posloupnost prázdných a smíšených (mixed) buněk mezi startem a cílem 4 Pokud posloupnost neexistuje, vrať „cesta neexistuje” 5 Pokud existuje posloupnost prázdných buněk, vrať „řešení” 6 Pokud dosažena hranice rozlišení 1 Dekomponuj dále smíšené buňky 2 Vrať se do bodu 2. Hana Rudová, IV126, FI MU: Robotika 307 8. ledna 2021 Potenční funkce (potential field/navigation function) Prvotní použití: cesta by neměla vést těsně vedle překážky podobně jako neprojedeme autem, pokud máme přesně tolik místa jako je šířka auta Řešení: zavedeme dodatečnou cenovou funkci, tzv. potenční funkce hodnota funkce narůstá ze vzdáleností od nejbližší překážky potenční funkce je pak využita jako dodatečná cenová funkce při výpočtu nejkratší vzdálenosti start goal Hana Rudová, IV126, FI MU: Robotika 308 8. ledna 2021 Potenční funkce Mnoho dalších prací zobecňuje využití potenční funkce pro prohledávání celého prostoru Latombe 1991 odpuzující potenční pole pro překážky equi-potenciál pro kontury atraktivní potenční pole pro cíl atraktivní + odpuzující potenční pole vynucená pole Hana Rudová, IV126, FI MU: Robotika 309 8. ledna 2021 Obsah: jak pokračujeme 38 Robot, hardware 39 Vnímání robota 40 Rozvrhování robotů 41 Plánování pohybu robota Konfigurační prostor Plánování na grafech Prohledávací algoritmy Kombinatorické přístupy k plánování pohybu Graf viditelnosti Voroného diagram Buňková dekompozice Potenční funkce Pravděpodobnostní přístupy k plánování pohybu Vzorkování Pravděpodobnostní cestovní mapa (PRM) Rychle prozkoumávající náhodný strom (RRT) Shrnutí 42 Pohyb robota Hana Rudová, IV126, FI MU: Robotika 310 8. ledna 2021 Plánování pohybu založené na vzorkování (sampling-based) Vyhýbá se explicitní reprezentaci překážek v konfiguračním prostoru black-box funkce použita pro vyhodnocení, zda je konfigurace bez kolizí, založeno např. na geometrických modelech a testování kolizí modelů Vytvoří diskrétní reprezentaci Cfree Konfigurace v Cfree jsou náhodně vzorkovány a spojeny do pravděpodobnostní cestovní mapy (probabilistic roadmap) Není úplné jako doposud uvažované metody, ale jedná se o pravděpodobnostní úplnost pravděpodobnostně úplný algoritmus: se vzrůstajícím počtem vzorků nalezene přípustné řešení (pokud existuje) Hana Rudová, IV126, FI MU: Robotika 311 8. ledna 2021 Náhodné vzorkování Mohou být použity různé vzorkovací strategie (distribuce) Hlavní problém přístupů založených na náhodném vzorkování spočívá v zahrnutí úzkých pasáží Různé modifikace vzorkovacích strategií navrženy v poslední dekádě, studuje je teorie vzorkování Hana Rudová, IV126, FI MU: Robotika 312 8. ledna 2021 Náhodné vzorkování (dokončení) Řešení může být nalezeno s použitím pouze pár vzorků Vzorkovací strategie jsou důležité blízké překážky úzké pasáže mřížkově založené uniformní strategie musí být pečlivě zváženy Kuffner, Effective sampling and distance metrics for 3D rigid body path planning. ICRA, 2004. naivní vzorkování uniformní vzorkování s použitím Eulerových úhlů Hana Rudová, IV126, FI MU: Robotika 313 8. ledna 2021 Pravděpodobnostní cestovní mapa – probabilistic roadmap Diskrétní reprezentace spojitého konfiguračního prostoru generována náhodným vzorkováním konfigurací v Cfree, které spojíme do grafu vrcholy: přípustné konfigurace robota (milestones) hrany: reprezentují platnou cestu (trajektorii) mezi konfiguracemi Nevyžaduje explicitní popis Cobs Cesta (trajektorie) ze startu do cíle: grafové prohledávací algoritmy Hana Rudová, IV126, FI MU: Robotika 314 8. ledna 2021 Jeden vs. více dotazů (single-query vs. multi-query) Více dotazů na pravděpodobnostní cestovní mapu generování jedné cestovní mapy, která je používána pro plánovací dotazy vícekrát Reprezentativní technika Probabilistic RoadMap (PRM) Probabilistic roadmaps for path planning in high dimensional configuration spaces, Kavraki, Svestka, Latombe, Overmars. IEEE Transactions on Robotics and Automation, 12(4):566–590, 1996. . . . první plánovač, který ukázal, že je schopen řešit problém ve 4-5 dimenzích Jeden dotaz na pravděpodobnostní cestovní mapu pro každý plánovací problém konstruována nová cestovní mapa charakteristická pro podprostor konfiguračního prostoru relevantní pro problém rychle prozkoumávající náhodný strom (RRT) LaValle, 1998 Hana Rudová, IV126, FI MU: Robotika 315 8. ledna 2021 Strategie pro více dotazů Vytvoření cestovní mapy (grafu), který reprezentuje prostředí 1 Učící fáze 1 Vzorkování n bodů v Cfree 2 Spojení náhodných konfigurací s použitím lokálního plánovače (lokální plánovač hledá lokální cesty, např. přímé) 2 Dotazovací fáze 1 Spojení počáteční a cílové konfigurace s PRM (např. lokálním plánovačem) 2 Použití prohledávání grafu k nalezení cesty Hana Rudová, IV126, FI MU: Robotika 316 8. ledna 2021 Konstrukce PRM Hana Rudová, IV126, FI MU: Robotika 317 8. ledna 2021 sPRM – zjednodušený (simplified) PRM function sPRM(qinit, počet vzorků n, poloměr ρ) V = {qinit} ∪ {SampleFreei }i=1,...,n−1; E = ∅; foreach v ∈ V do U = Near((V , E), v, ρ)\{v}); (vrcholy v radiusu ρ od v) foreach u ∈ U do if CollisionFree(v, u) then E = E ∪ {(v, u), (u, v)}; return G = (V , E); Hana Rudová, IV126, FI MU: Robotika 318 8. ledna 2021 Praktická PRM Inkrementální konstrukce Spojení uzlů v radiusu ρ Lokální plánovač testuje kolize vzhledem k danému rozlišení δ Cesty mohou být hledány Dijkstrovým algoritmem Hana Rudová, IV126, FI MU: Robotika 319 8. ledna 2021 PRM vs. sPRM function sPRM(qinit , počet vzorků n, poloměr ρ) V = {qinit } ∪ {SampleFreei }i=1,...,n−1; E = ∅; foreach v ∈ V do U = Near((V , E), v, ρ)\{v}); (vrcholy v radiusu ρ od v) foreach u ∈ U do if CollisionFree(v, u) then E = E ∪ {(v, u), (u, v)}; return G = (V , E); function PRM(qinit , počet vzorků n, poloměr ρ) V = ∅; E = ∅; for i = 0, . . . , n do qrand = SampleFree; (vzorek z Cfree ) U = Near((V , E), qrand , ρ); (vrcholy v radiusu ρ of qrand ) V = V ∪ {qrand }; foreach u ∈ U se vzrůstající |u − qrand | do if qrand a u nejsou ve stejné spojené komponentě (V , E) then if CollisionFree(qrand , u) then E = E ∪ {(qrand , u), (u, qrand )}; return G = (V , E); Hana Rudová, IV126, FI MU: Robotika 320 8. ledna 2021 PRM vlastnosti Úplnost pro standardní PRM nediskutována Většinou studována sPRM, která je pravděpodobnostně úplná a asymptoticky optimální složitost konstrukce grafu (učící fáze) O(n2 ) složitost dotazu O(n2 ) prostorová složitost O(n2 ) Často prakticky používány heuristiky pro funkci Near k-nearest (k-nejbližších) sousedů od v variable connection radius (proměnlivý radius) ρ jako funkce n k-nearest sPRM, variable radius sPRM nejsou pravděpodobnostně úplné Hana Rudová, IV126, FI MU: Robotika 321 8. ledna 2021 Rychle prozkoumávající náhodný strom – Rapidly exploring random tree (RRT) Algoritmus pro jeden dotaz Motivací je hledání cesty založené na řízení Inkrementální konstrukce grafu (stromu) směrem k cílové oblasti negarantuje přesnou cestu k cílové konfiguraci Postup tvorby stromu 1 Začni s počáteční konfigurací qinit, která je kořenem konstruovaného stromu 2 Generuj náhodnou konfiguraci qnew v Cfree 3 Nalezni nejbližší uzel qnear ke qnew ve stromě např. použitím implementace k-dimensionálních stromů jako je ANN nebo FLANN knihovna 4 Rozšiř qnear směrem ke qnew strom rozšiřujeme v malých krocích, ale často s přímou kontrolou výběru vrcholu tak, abychom posunuli robota na nejbližší pozici ke qnew 5 Pokud není strom v dostatečné vzdálenosti od cílové konfigurace, běž na krok 2. Hana Rudová, IV126, FI MU: Robotika 322 8. ledna 2021 Konstrukce RRT Hana Rudová, IV126, FI MU: Robotika 323 8. ledna 2021 RRT algoritmus function RRT(qinit, počet vzorků n) returns cestovní mapa G = (V , E) V = {qinit}; E = ∅; for i = 1, . . . , n do qnew = SampleFree; (bezkolizní náhodná konfigurace) qnear = Nearest((V , E), qnew ); (nejbližší vrchol ve V of qnew ) Nqnear = množina náhodně získaných vzorků blízko qnear ; u = bezkolizní vzorek z Nqnear blízko qnew ; V = V ∪ {u}; E = E ∪ {(qnear , u)}; return G = (V , E); Vyvinut S. LaValle a spolupracovníky, 2001-2003 LaValle, Planning algorithms. Cambridge University Press, 2006. http: // planning. cs. uiuc. edu/ Hana Rudová, IV126, FI MU: Robotika 324 8. ledna 2021 Vlastnosti RRT algoritmu Rychle prozkoumává prostor qnew bude pravděpodobně generováno ve velké dosud neprozkoumané části Umožňuje uvažování kinodynamických/dynamických omezení (během expanze) Umí nalézt trajektorie nebo posloupnosti přímou kontrolou příkazů robotových ovladačů Test na detekci kolize obvykle jako black-box např. RAPID, Bullet knihovny Podobně jako PRM má RRT problémy s úzkými pasážemi RRT nalezne proveditelnou cestu bez garance kvality cesta může být relativně daleko od optimální cesty dané např. délkou cesty navzdory tomu je úspěšně používán v mnoha praktických aplikacích Navrženo mnoho variant RRT Hana Rudová, IV126, FI MU: Robotika 325 8. ledna 2021 RRT: příklady Plánování pro robota typu auta Plánování na 3D povrchu Plánování s dynamikou V.Vonásek & P.Vaněk Hana Rudová, IV126, FI MU: Robotika 326 8. ledna 2021 Přístupy k plánování pohybu: shrnutí Metody pro více dotazů Graf viditelnosti Voroného diagram Buňková dekompozice exaktní metody: vertikální dekompozice přibližné metody: pravidelná mřížka, oktalová dekompozice Potenční funkce Pravděpodobnostní mapy: algoritmy sPRM, PRM Metody pro jeden dotaz Rychle prozkoumávající náhodný strom (RRT) Hana Rudová, IV126, FI MU: Robotika 327 8. ledna 2021 Úplnost plánovačů pohybu Plánovač pohybu je úplný, pokud nalezne bezkolizní cestu vždy, když existuje a jinak selže. graf viditelnosti Voroného diagram přesná buňková dekompozice potenční funkce Pravděpodobnostně úplný plánovač pohybu vrací cestu s vysokou pravděpodobností, pokud existuje, nemusí však skončit, pokud cesta neexistuje. sPRM Rozlišením úplný (resolution complete) plánovač pohybu diskretizuje prostor a vrací cestu, pokud existuje v této reprezentaci. přibližná buňková dekompozice Hana Rudová, IV126, FI MU: Robotika 328 8. ledna 2021 Porovnání plánovačů pohybu Přesná buňk. Přibližná G.viditel. Pravděp. Potenční dekomp. buňk. dekomp. VD metody funkce praktické pro velmi pomalé pomalé, paměť velmi rychlé rychlé 2-3 dimenze paměť mn požadavek1 pomalé praktické nad ne snad ne ne ano ano 5 dimenzí nejasné optimální ano ano, po ano pravděp. ne rozlišení garance snadná ne ano ne ano ano implementace úplné ano ano, po ano pravděp. ne2 rozlišení úplné 1 m buněk mřížky každá s n osami 2 navigační funkce pro některé třídy problémů poskytují teoretické záruky Hana Rudová, IV126, FI MU: Robotika 329 8. ledna 2021 Pohyb: kinematický vs. dynamický stav Zatím jsme pohyb pouze plánovali avšak nerealizovali Předpokládali jsme, že robot je schopen následovat navrženou cestu V reálu však není pravda, je třeba počítat se setrvačností robota Roboti spíš vyvíjejí síly než určují pozice Jak počítat tyto síly? Popsali jsme dynamický stav (kromě kinematiky zahrnuje rychlost změny) přechodový model pro dynamický stav zahrnuje účinek sil na rychlost změny nutné modely vyjádřené diferenciálními rovnicemi, které provážou kvantitu (např. kinematický stav) s odpovídající změnou v čase (např. rychlost) pokud bychom uměli generovat takové plány, roboti by měli skvělý výkon dynamický stav má však více dimenzí než kinematický, plánovací algoritmy by byly použitelné pouze pro nejjednodušší roboty ⇒ robotické systémy v praxi se spoléhají na jednodušší kinematické plánovače cest Hana Rudová, IV126, FI MU: Robotika 330 8. ledna 2021 Regulátor Regulátor kompenzuje limitace kinematických plánů, aby byla zachována cesta Referenční (reference) regulátor: snaží se robota udržet na naplánované cestě (referenční cestě) Cesta robota, který se snaží sledovat kinematickou cestu: KP = 1 KP = 0.1 jakmile nastane odchylka (díky šumu nebo omezením sil, které může robot uplatnit), robot vyvine opačnou sílu – vede k vibracím, které jsou důsledkem setrvačnosti P regulátor (P proporční): řízení je proporční chybě manipulace robota řízení at generované P regulátorem má tvar at = KP (y(t) − xt) y(t) referenční cesta parametrizovaná časem xt je stav robota v čase t KP parametr zisku ovlivňující, jak silně změnit odchylku mezi xt a y(t) pomůže nižší hodnota KP (0.1) zlepšit chování? Ne, pouze vibrace zpomalí Hana Rudová, IV126, FI MU: Robotika 331 8. ledna 2021 PD regulátor P proporční člen, D derivační člen nejjednodušší regulátor, který zachovává striktní stabilitu v naší doméně at = KP(y(t) − xt) + KD ∂(y(t) − xt) ∂t druhý člen součtu je proporční první derivaci chyby y(t) − xt v čase t pokud se chyba y(t) − xt výrazně mění v čase ⇒ derivace této chyby bude neutralizovat první člen pokud bude chyba přetrvávat a nebude se měnit: ⇒ derivace zmizí a první člen bude dominovat KP = 0.3, KD = 0.8 Hana Rudová, IV126, FI MU: Robotika 332 8. ledna 2021 PID regulátor I integrační člen, P proporční člen, D derivační člen umožňuje odstranit chybové chování PD regulátoru v některých případech chybové chování jako důsledek systematické vnější síly, která není součástí modelu např. opotřebení robotické paže at = KP(y(t) − xt) + KI (y(t) − xt)dt + KD ∂(y(t) − xt) ∂t dlouhotrvající odchylky mezi referenčním a aktuálním stavem opraveny regulátor tak řeší systematické chyby na úkor zvýšeného nebezpečí oscilací Hana Rudová, IV126, FI MU: Robotika 333 8. ledna 2021 Další způsoby řízení pohybu: řízení pomocí potenční funkce Řízení pomocí potenční funkce podobně jako při plánování pohybu Řízení pomocí refenční cesty a potenční funkce nemusí: být postačující v komplexním a vzdáleném prostředí (Mars) mít dostatečnou přesnost př. hexapod kráčející na hrbolatém terénu nemá postačující senzory pro získání modelu terénu vhodného pro plánování a 12 DOFs (2 pro každou nohu) jsou příliš mnoho pro efektivní plánování Hana Rudová, IV126, FI MU: Robotika 334 8. ledna 2021 Další způsoby řízení pohybu: reaktivní řízení Reaktivní řízení můžeme specifikovat regulátor bez explicitního modelu prostředí nejprve si určíme vzor posunu končetin a pak už reaktivně reagujeme na daný stav když je noha blokována, dej ji zpět, zdvihni ji výše a zkus to znova tj. definujeme konečně stavový automat Hana Rudová, IV126, FI MU: Robotika 335 8. ledna 2021 Další způsoby řízení pohybu: zpětnovazební učení Zpětnovazební učení př. otočení helikoptéry postup zaznamenání řízení lidského pilota a stavu proměnných helikoptéry získáme prediktivní model pro simulaci pohybu Hana Rudová, IV126, FI MU: Robotika 336 8. ledna 2021 Robotika: shrnutí Robot a jeho hardware typy robotů senzory, efektory Vnímání robota dynamické Bayesovské sítě a odhad stavu lokalizace a mapování Plánování pohybu robota konfigurační prostor prohledávání v grafu diskretizace spojitého problému Pohyb robota regulátory Hana Rudová, IV126, FI MU: Robotika 337 8. ledna 2021 Zdroje, ze kterých průsvitky čerpají, a poděkování V průsvitkách jsou použity obrázky a texty z uvedených zdrojů Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, third edition. Prentice Hall, 2010. http://aima.cs.berkeley.edu/ El-Ghazali Talbi, Metaheuristics: From Design to Implementation. Wiley, 2009. http://www.lifl.fr/~talbi/metaheuristic/ Roman Barták, Plánování a rozvrhování. Přednáška na MFF UK, http://ktiml.mff.cuni.cz/~bartak/planovani Roman Barták, Umělá inteligence II. Přednáška na MFF UK, http://ktiml.mff.cuni.cz/~bartak/ui2 Steven M. LaValle, Planning algorithms, Cambridge University Press, 2006. http://planning.cs.uiuc.edu/ Přednáška MEAM 620: Robotics, University of Pennsylvania, 2017. https://alliance.seas.upenn.edu/~meam620/wiki/index.php?n=Main.Schedule Jan Faigl, Robot Motion Planning, přednáška Planning and Games na FEL, ČVUT, 2016. Hana Rudová, IV126, FI MU: Robotika 338 8. ledna 2021