Uvod do umělé inteligence, řešení problémů Aleš Horák E-mail: hales@fi.muni.cz http://nip.fi.muni.cz/uui/ Obsah: • Co je "umělá inteligence" • Organizace předmětu PB016 • Řešení problémů Úvod do umělé inteligence 1/12 1/21 Co je "umělá inteligence" Co je "umělá inteligence" ? ■ Úvod do umělé inteligence 1/12 2/21 Co je "umělá inteligence" Co je "umělá inteligence" ? ■ > sli.do/uui Úvod do umělé inteligence 1/12 2/21 Co je "umělá inteligence" Co je "umělá inteligence" Communication on Al for Europe, COM 2018/237 final Artificial intelligence (Al) refers to systems that display intelligent behaviour by analysing their environment and taking actions - with some degree of autonomy - to achieve specific goals. Al-based systems can be purely software-based, acting in the virtual world (e.g. voice assistants, image analysis software, search engines, speech and face recognition systems) or Al can be embedded in hardware devices (e.g. advanced robots, autonomous cars, drones or Internet of Things applications). Úvod do umělé inteligence 1/12 3/21 Co je "umělá inteligence" Co je "umělá inteligence" High Level Expert Group, A definition of AI, 2019 Artificial intelligence (Al) systems are software (and possibly also hardware) systems designed by humans that, given a complex goal, act in the physical or digital dimension by perceiving their environment through data acquisition, interpreting the collected structured or unstructured data, reasoning on the knowledge, or processing the information, derived from this data and deciding the best action(s) to take to achieve the given goal. Al systems can either use symbolic rules or learn a numeric model, and they can also adapt their behaviour by analysing how the environment is affected by their previous actions. Úvod do umělé inteligence 1/12 3/21 Co je "umělá inteligence" Co je "umělá inteligence" o systém, který se chová jako člověk Úvod do umělé inteligence 1/12 4/21 Co je "umělá inteligence" Co je "umělá inteligence" 9 systém, který se chová jako člověk Turingův test (1950) zahrnuje: • zpracování přirozeného jazyka (NLP) • reprezentaci znalostí (KRepresentation) • vyvozování znalostí (KReasoning) • strojové učení (počítačové vidění) • (robotiku) od 1991 - Loebnerova cena (Loebner Prize) —± každý rok $4.000 za "nejlidštější" program, nabízí $100.000 a zlatá medaile za složení celého Turingova testu (od 2019 bez odměn) Úvod do umělé inteligence 1/12 4/21 Co je "umělá inteligence" • systém, který myslí jako člověk • snaha porozumět postupům lidského myšlení - kognitivní (poznávací) věda • využívá poznatků neurologie, neurochirurgie,.. . Úvod do umělé inteligence 1/12 6/21 Co je "umělá inteligence" • systém, který myslí jako člověk • snaha porozumět postupům lidského myšlení - kognitivní (poznávací) věda • využívá poznatků neurologie, neurochirurgie,.. . např. Angela Friederici: Language Processing in the Human Brain Max Planck Institute of Cognitive Neuroscience, Leipzig měření "Event Related Potentials" (ERP) v mozku -jako potvrzení oddělení syntaxe a sémantiky při zpracování věty 2013-2023 Human Brain Project, Geneva, Švýcarsko Úvod do umělé inteligence 1/12 6/21 Co je "umělá inteligence" • systém, který myslí rozumně od dob Aristotela (350 př.n.l.) o náplň studia logiky • problém - umět najít řešení teoreticky x prakticky (složitost a vyčíslitelnost) problém - neúplnost a nejistota vstupních dat Úvod do umělé inteligence 1/12 7/21 Co je "umělá inteligence" • systém, který myslí rozumně od dob Aristotela (350 př.n.l.) o náplň studia logiky • problém - umět najít řešení teoreticky x prakticky (složitost a vyčíslitelnost) problém - neúplnost a nejistota vstupních dat • systém, který se chová rozumně (inteligentně) inteligentní agent - systém, který • jedná za nějakým účelem • jedná samostatně • jedná na základě vstupů ze svého prostředí • pracuje delší dobu • adaptuje se na změny Úvod do umělé inteligence 1/12 7/21 v Co je "umělá inteligence" Cím se budeme zabývat? Čím se budeme zabývat? • základní struktury a algoritmy běžně používané při technikách programovaní pro inteligentní agenty • strategie řešení, prohledávání stavového prostoru, heuristiky, . .. • s příklady ve cvičení v jazyce Python Úvod do umělé inteligence 1/12 8/21 Nápl ň předmětu Co je "umělá inteligence" Čím se budeme zabývat? O úvod do UI, řešení problémů © prohledávání stavového prostoru © dekompozice problému, problémy s omezujícími podmínkami O hry a základní herní strategie B logický agent, výroková logika B pravdivost, dokazatelnost, důkazové metody průběžná písemka B logika prvního řádu a intenzionální logika □ rezoluční metoda, úvod do logického programování □ modálni logiky, vícehodnotové logiky ® reprezentace a vyvozování znalostí ® učení, rozhodovací stromy, neuronové sítě © zpracování přirozeného jazyka Úvod do umělé inteligence 1/12 9/21 Obsah Organizace předmětu PB016 KB C V I ' " J- I " v • Cím se budeme zabývat? Q Organizace předmětu PB016 o Základní informace o Cvičení IxtíDtíl L/l UU lc 111 U • Problém osmi dam • Problém osmi dam I • Problém osmi dam II • Problém osmi dam III • Další příklad - posunovačka • Reálné problémy řešitelné prohledáváním Úvod do umělé inteligence 1/12 10 / 21 Organizace předmětu PB016 Organizace předmětu PB016 Hodnocení předmětu: • dotazníky na cvičení (11 x 2 = max 22 bodů) nutná podmínka k závěrečné zkoušce > 8 bodů • průběžná písemka (max 20 bodů) • v y2 semestru - v týdnu po 6. přednášce, pro všechny jediný termín o závěrečná písemka (max 58 bodů) • dva řádné a jeden opravný termín hodnocení - součet bodů (max 100 bodů) o známka A za > 92 bodů známka E za > 64 bodů • rozdíly zk, k, z - různé limity o někteří mohou získat extra body ve cvičení (max l/cvičení) • oprava chyby v materiálech • samostatná aktivita nad rámec zadání • nadprůměrné elegantní řešení Úvod do umělé inteligence 1/12 11 / 21 Organizace předmětu PB016 Základní informace Základní informace • web stránka předmětu -http://nlp.fi.muni.cz/uui/ • slajdy i cvičení - průběžně doplňovány v interaktivních osnovách o kontakt na přednášející - Aleš Horák , Luboš Popelínský (Subject: PB016 ...) • literatura: • Russell, S. a Norvig, P.: Artificial Intelligence: A Modern Approach, 3rd ed., Prentice Hall, 2010. (prezenčně v knihovně) • slajdy a cvičení na webu předmětu Úvod do umělé inteligence 1/12 12 / 21 o materiály viz interaktivní osnova cvičení • probíhat budou formou online událostí na univerzitním Google Meet • každý obdrží emailem pozvánku k události od příslušného cvičícího jakmile potvrdíte účast, měla by událost být viditelná ve vašem Google kalendáři • pro připojení se ke cvičení stačí kliknout na Google Meet odkaz spojený s událostí • platforma pro řešení úkolů je Google Colaboratory na sdíleném Google disku • Jupyter notebooky (Python + Markdown/LaTeX) • cvičení jsou povinná (možné max 3 neomluvené absence) Úvod do umělé inteligence 1/12 13 / 21 Obsah KM C V I ' " J- I " v • Cím se budeme zabývat? • Základní informace • Cvičení Q Řešení problémů o Problém osmi dam • Problém osmi dam I Problém osmi dam II • Problém osmi dam III • Další příklad - posunovačka • Reálné problémy řešitelné prohledáváním Úvod do umělé inteligence 1/12 14 / 21 Problém osmi dam Řešení problémů Problém osmi dam úkol: Rozestavte po šachovnici 8 dam tak, aby se žádné dvě vzájemně neohrožovaly. Úvod do umělé inteligence 1/12 15 / 21 Řešení problémů Problém osmi dam Problém osmi dam úkol: Rozestavte po šachovnici 8 dam tak, aby se žádné dvě vzájemně neohrožovaly. Úvod do umělé inteligence 1/12 15 / 21 Problém osmi dam Řešení problémů Problém osmi dam úkol: Rozestavte po šachovnici 8 dam tak, aby se žádné dvě vzájemně neohrožovaly celkem pro 8 dam existuje 92 různých řešení Úvod do umělé inteligence 1/12 15 / 21 v Řešení problémů Problém osmi dam I Problém osmi dam I datová struktura - osmiprvková množina {(^I,yi),(^2,y2),(^3,y3),(^4,y4),(^5,y5),(^6,y6),(^7,y7),(^8,y8)} Úvod do umělé inteligence 1/12 16 / 21 v Řešení problémů Problém osmi dam I Problém osmi dam I datová struktura - osmiprvková množina {(^I,yi),(^2,y2),(^3,y3),(^4,y4),(^5,y5),(^6,y6),(^7,y7),(^8,y8)} solution ={(1,4), (2,2), (3,7), (4,3), (5,6), (6,8), (7,5), (8,1)} J Úvod do umělé inteligence 1/12 16 / 21 v Řešení problémů Problém osmi dam I Problém osmi dam I datová struktura - osmiprvková množina {(^I,yi),(^2,y2),(^3,y3),(^4,y4),(^5,y5),(^6,y6),(^7,y7),(^8,y8)} solution ={(1,4), (2,2), (3,7), (4,3), (5,6), (6,8), (7,5), (8,1)} J function N-Queens(a7 <— 8, queens <— {}) if length (queens) = n then print queens # řešení else for qx <— 1 to n do for <7y «— 1 to n do if NoAttack(<7x, qy, queens) then N-Queens(n, queens + {(qx, <7y)}) Úvod do umělé inteligence 1/12 16 / 21 v Řešení problémů Problém osmi dam I Problém osmi dam I datová struktura - osmiprvková množina {(^I,yi),(^2,y2),(^3,y3),(^4,y4),(^5,y5),(^6,y6),(^7,y7),(^8,y8)} solution ={(1,4), (2,2), (3,7), (4,3), (5,6), (6,8), (7,5), (8,1)} J function N-Queens(a7 <— 8, queens <— {}) if length (queens) = n then print queens # řešení else for qx <— 1 to n do for <7y «— 1 to n do if NoAttack(<7x, qy, queens) then N-Queens(n, queens + {(qx, <7y)}) function NoAttack(<7x, qy, queens) for q G queens do if <7x = q[l] or qy = q[2] or abs(q[l]-qx) = abs(<7[2]-<7y) then return False return True Úvod do umělé inteligence 1/12 16 / 21 v Řešení problémů Problém osmi dam I datová struktura - osmiprvková množina {(^I5yi),(^2,y2),(x3,y3),(x4,y4),(x5,y5),(x6,y6),(x7,y7),(x8,y8)} solution ={(1,4), (2,2), (3,7), (4,3), (5,6), (6,8), (7,5), (8,1)} j function N-Queens(h <— 8, queens «— {}) if length (queens) = n then print queens # řešení else for qx <— 1 to n do for <7y <— 1 to n do if NoAttack(qx, qy, queens) then N-Queens(/7, queens + {(<7X, <7y)}) function NoAttack((7x, <7y, queens) for (7 G queens do if <7x = <7[1] or <7y = <7[2] or abs(q[l]-qx) = abs(q[2]-<7y) then return False return True N-Queens(8) {(8,4), (7,2), (6,7), (5,3), (4,6), (3,8), (2,5), (1,1)} {(7,2), (8,4), (6,7), (5,3), (4,6), (3,8), (2,5), (1,1)} Úvod do umělé inteligence 1/12 16 / 21 v Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 = 281 474 976 710 656 při neopakování pozic 64 • 63 • 62... • 57 = 178 462 987 637 760 Úvod do umělé inteligence 1/12 17 / 21 v Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 « 2.8 x 1014 při neopakování pozic 64 • 63 • 62... • 57 « 1.8 x 1014 Úvod do umělé inteligence 1/12 17 / 21 v Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 « 2.8 x 1014 při neopakování pozic 64 • 63 • 62... • 57 « 1.8 x 1014 omezení stavového prostoru - každá dáma má svůj sloupec {(I,y1),(2,y2),(3,y3),(4,y4),(5,y5),(6,y6),(7,y7),(8,y8)} Úvod do umělé inteligence 1/12 17 / 21 v Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 « 2.8 x 1014 při neopakování pozic 64 • 63 • 62... • 57 « 1.8 x 1014 omezení stavového prostoru - každá dáma má svůj sloupec [yi,y2,y3,y4,y5,y6,y7,ys] Úvod do umělé inteligence 1/12 17 / 21 v Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 « 2.8 x 1014 při neopakování pozic 64 • 63 • 62... • 57 « 1.8 x 1014 omezení stavového prostoru - každá dáma má svůj sloupec [yi,y2,y3,y4,y5,y6,y7,ys] počet možností u řešení II = 88 = 16 777 216 Úvod do umělé inteligence 1/12 17 / 21 v Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 « 2.8 x 1014 při neopakování pozic 64 • 63 • 62... • 57 « 1.8 x 1014 omezení stavového prostoru - každá dáma má svůj sloupec [yi,y2,y3,y4,y5,y6,y7,ys] počet možností u řešení II =8-7-6...-1 = 40320 Úvod do umělé inteligence 1/12 17 / 21 v Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 « 2.8 x 1014 při neopakování pozic 64 • 63 • 62... • 57 « 1.8 x 1014 omezení stavového prostoru - každá dáma má svůj sloupec [yi,y2,y3,y4,y5,y6,y7,ys] počet možností u řešení II =8-7-6...-1 = 40320 function N-Queens(a7 «— 8, queensy «— []) if length (queensy) = n then print queensy # řešení else for <7y ^— 1 to n do if NoAttack(<7y, queensy) then N-Queens(/i, queensy + [<7y]) function NoATTACK(qy, queensy) qx = length (queensy) + 1 for / ^— 1 to length(queensy) do if <7y = <7L/eeA7Sy[/] or abs(/-qrx) = abs(qfi/eensy[/]-qfy) then return False return True Úvod do umělé inteligence 1/12 17 / 21 v Řešení problémů Problém osmi dam III Problém osmi dam III k souřadnicím x a y —> přidáme i souřadnice diagonály u a v u = x-y Dx = [1..8] —► Du = [-7..7] v = x + y Dy = [1..8] Dv = [2..16] Úvod do umělé inteligence 1/12 18 / 21 v Řešení problémů Problém osmi dam III Problém osmi dam II k souřadnicím x a y —> přidáme i souřadnice diagonály u a v u = x-y Dx = [1..8] —> DU = [-7.J] v = x + y Dy = 1..8] Dv = [2..16] Úvod do umělé inteligence 1/12 18 / 21 v Řešení problémů Problém osmi dam III Problém osmi dam II k souřadnicím x a y —> přidáme i souřadnice diagonály u a v u = x-y Dx = [1..8] —> Du = [-7..7] v = x + y Dy = [1..8] Dv = [2..16] u v % Úvod do umělé inteligence 1/12 18 / 21 v Řešení problémů Problém osmi dam III Problém osmi dam III po každém umístění dámy aktualizujeme seznamy volných pozic Úvod do umělé inteligence 1/12 19 / 21 v Řešení problémů Problém osmi dam III Problém osmi dam III po každém umístění dámy aktualizujeme seznamy volných pozic počet možností u řešení III = 2 057 Úvod do umělé inteligence 1/12 19 / 21 po každém umístění dámy aktualizujeme seznamy volných pozic počet možností u řešení III = 2 057 function N-Queens(a7 <- 8, queensy <- [], dy <- [], du <- {}, dv ^— {}) if length (queensy) = 0 and length(c/y) = 0 then return N-Queens(a7, [], [l..n], {-(n-l).. {2.. (2*n)}) else for c/y G c/y do qx ^— length(queensy) + 1 qu ^ qx - qy qv <- qx + qy if G c/u and G c/v then N-Queens(/7, queensy + [<7y], c/y without(c/y), c/u — {c/u}, c/v — {<7v}) if length (queensy) = a7 then print queensy # řešení Úvod do umělé inteligence 1/12 19 / 21 po každém umístění dámy aktualizujeme seznamy volných pozic počet možností u řešení III = 2 057 function N-Queens(a7 «— 8, queensy «— [], dy «— [], du «— {}, dv «— {}) if length (queensy) = 0 and length(c/y) = 0 then return N-Queens(a7, [], [l..n], {-(n-1).. (n-1)}, {2.. (2*n)}) else for c/y G dy do <7x ^— length(queensy) + 1 qu ^ qx - qy qv <- qx + qy if G c/u and G c/v then N-Queens(/i, queensy + [c/y], c/y without(c/y), c/u - {c/u}, c/v - {c/^}) if length (queensy) = /i then print queensy # řešení Problém n dam pro n = 100: Úvod do umělé inteligence 1/12 19 / 21 po každém umístění dámy aktualizujeme seznamy volných pozic počet možností u řešení III = 2 057 function N-Queens(a7 «— 8, queensy «— [], dy «— [], du «— {}, dv «— {}) if length (queensy) = 0 and length(c/y) = 0 then return N-Queens(a7, [], [l..n], {-(n-1).. (n-1)}, {2.. (2*n)}) else for c/y G dy do <7x ^— length(queensy) + 1 qu ^ qx - qy qv <- qx + qy if G c/u and G c/v then N-Queens(/i, queensy + [c/y], c/y without(c/y), c/u - {c/u}, c/v - {c/^}) if length (queensy) = /i then print queensy # řešení Problém n dam pro n = 100: řešení I ... 10400 Úvod do umělé inteligence 1/12 19 / 21 Řešení problémů Problém osmi dam III Problém osmi dam po každém umístění dámy aktualizujeme seznamy volných pozic počet možností u řešení III = 2 057 ^^c/y = [1..8],du = {-7..7},dv = {2..16} function N-Queens(/i «— 8, queensy «— [], dy «— [], du «— {}, dv «— {}) if length (queensy) = 0 and length(c/y) = 0 then return N-Queens(a7, [], [l..n], {-(n-1).. (n-1)}, {2.. (2*n)}) if length (queensy) = /i then print queensy # řešení else for qry G c/y do <7x ^— length(queensy) + 1 qu ^ qx - qy qv <- qx + qy if G c/u and G c/v then N-Queens(/i, queensy + [qy], c/y.without(qy), c/u - {gu}, c/v - {qv}) Problém n dam pro n = 100: řešení I ... 10400 řešení II ... 10158 Úvod do umělé inteligence 1/12 19 / 21 v Řešení problémů Problém osmi dam III Problém osmi dam III po každém umístění dámy aktualizujeme seznamy volných pozic počet možností u řešení III = 2 057 function N-Queens(a7 «— 8, queensy «— [], dy «— [], du «— {}, dv «— {}) if length (queensy) = 0 and length(c/y) = 0 then return N-Queens(a7, [], [l..n], {-(n-1).. (n-1)}, {2.. (2*n)}) if length (queensy) = /i then /- print queens' # few ^{dy = [1..8],du = {-7..7},dv = {2..16} else for qry G dy do <7x «— length(queensy) + 1 qu ^ qx - qy qv <- qx + qy if G c/u and G c/v then N-Queens(/i, queensy + [qy], c/y without(gy), c/u - {gu}, c/v - {qv}) Problém n dam pro n = 100: řešení I ... 10400 řešení II 10158 řešení III ... 1052 Úvod do umělé inteligence 1/12 v Řešení problémů Další příklad - posunovačka Další příklad - posunovačka počáteční stav (např.) cílový stav í 1 ] 2 v_) 3 v._ _/ M f \ 5 \ ) 7 l_ _) ŕ ~\ 8 v ) hra na čtvercové šachovnici mxmsn — m2 — 1 očíslovanými kameny • příklad pro šachovnici 3x3, posunování osmi kamenů (8-posunovačka) 9 stavy - pozice všech kamenů • akce - "pohyb" prázdného místa Úvod do umělé inteligence 1/12 20 / 21 v Řešení problémů Další příklad - posunovačka Další příklad - posunovačka počáteční stav (např.) cílový stav í 1 ] 2 v_) 3 v._ _/ M f \ 5 \ ) M 7 ŕ ~\ 8 1—> l_ _) v ) hra na čtvercové šachovnici mxmsn — m2 — 1 očíslovanými kameny • příklad pro šachovnici 3x3, posunování osmi kamenů (8-posunovačka) 9 stavy - pozice všech kamenů • akce - "pohyb" prázdného místa Optimální řešení obecné n-posunovačky je NP-úplné ... 9!/2 Počet stavů u 8-posunovačky u 15-posunovačky u 24-posunovačky 181440 1013 1025 Úvod do umělé inteligence 1/12 20 / 21 v Řešení problémů Reálné problémy řešitelné prohledáváním Reálné problémy řešitelné prohledáváním hledání cesty z města A do města B • hledání itineráře, problém obchodního cestujícího • návrh VLSI čipu • navigace auta, robota, ... • postup práce automatické výrobní linky a návrh proteinů - 3D-sekvence aminokyselin • Internetové vyhledávání informací Úvod do umělé inteligence 1/12 21 / 21