Dekompozice problému, AND/OR grafy, problémy s omezujícími podmínkami Aleš Horák E-mail: hales@fi.muni.cz http://nip.fi.muni.cz/uui/ Obsah: • Dekompozice a AND/OR grafy • Prohledávání AND/OR grafů • Problémy s omezujícími podmínkami o CLP - Constraint Logic Programming Úvod do umělé inteligence 3/12 1/36 Dekompozice a AND/OR grafy Príklad - Hanojské veže Príklad - Hanojské veže • máme tři tyče: A, B a C. • na tyči A je (podle velikosti) n kotoučů. • úkol: přeskládat z A pomocí C na tyč B (zaps. n(A, B, C)) bez porušení uspořádání A B i : i i h 1 : i _____L _ 3 : i bit . ly/uuihanoi (Tower3 je zde cíl) ;iíDo Úvod do umělé inteligence 3/12 2/36 Dekompozice a AND/OR grafy Príklad - Hanojské veže Príklad - Hanojské veže • máme tři tyče: A, B a C. • na tyči A je (podle velikosti) n kotoučů. • úkol: přeskládat z A pomocí C na tyč B (zaps. n(A, B, C)) bez porušení uspořádání Můžeme rozložit na fáze: 1. přeskládat n - -1 kotoučů z A pomocí B na C A B i : i i h 1 : i _____L _ 3 : i bit . ly/uuihanoi (Tower3 je zde cíl) IiDS 1----- . H-\ Úvod do umělé inteligence 3/12 2/36 Dekompozice a AND/OR grafy Príklad - Hanojské veže Príklad - Hanojské veže • máme tři tyče: A, B a C. • na tyči A je (podle velikosti) n kotoučů. • úkol: přeskládat z A pomocí C na tyč B (zaps. n(A, B, C)) bez porušení uspořádání A B i : i i h 1 : i _____L _ 3 : i bit . ly/uuihanoi (Tower3 je zde cíl) ;iíDo Můžeme rozložit na fáze: 1. přeskládat n—1 kotoučů z A pomocí B na C 2. přeložit 1 kotouč z A na B 1 1 A i f ŕ-1 . H-\ B Úvod do umělé inteligence 3/12 2/36 Dekompozice a AND/OR grafy Príklad - Hanojské veže Príklad - Hanojské veže • máme tři tyče: A, B a C. • na tyči A je (podle velikosti) n kotoučů. • úkol: přeskládat z A pomocí C na tyč B (zaps. n(A, B, C)) bez porušení uspořádání A B i : i i h 1 : i _____L _ 3 : i bit . ly/uuihanoi (Tower3 je zde cíl) ;iíDo Můžeme rozložit na fáze: 1. přeskládat n—1 kotoučů z A pomocí B na C. 2. přeložit 1 kotouč z A na B 3. přeskládat n- 1 kotoučů z C pomocí A na B 1 1 A i f ŕ-1 . H-\ B B Úvod do umělé inteligence 3/12 2/36 Dekompozice a AND/OR grafy Príklad - Hanojské veže Príklad - Hanojské veže - pokrač. schéma celého řešení pro n = 3: n = 3(A,B,C) n-l = 2(A,C,B) 1(A,B,C) n-l = 2(C,B,A) Úvod do umělé inteligence 3/12 3/36 Dekompozice a AND/OR grafy Príklad - Hanojské veže Príklad - Hanojské veže - pokrač. schéma celého řešení pro n = 3: n = 3(A,B,C) n - 1 = 2(A,C,B) O 1(A,B,C) n-2 = 1(A,B,C) n-1 = 2(C,B,A) O n-2 = 1(B,C,A) n-2 = 1(C,A,B) n-2 = 1(A,B,C) 1(A,C,B) 1(C,B,A) Úvod do umělé inteligence 3/12 3/36 Dekompozice a AND/OR grafy Príklad - Hanojské veže Príklad - Hanojské veže - pokrač. schéma celého řešení pro n = 3: n = 3(A,B,C) n - 1 = 2(A,C,B) O 1(A,B,C) n-2 = 1(A,B,C) n-1 = 2(C,B,A) O n-2 = 1(B,C,A) n-2 = 1(C,A,B) n-2 = 1(A,B,C) 1(A,C,B) 1(C,B,A) Úvod do umělé inteligence 3/12 3/36 Dekompozice a AND/OR grafy Příklad - Hanojské věže Příklad - Hanojs ké věže - pc )krač. function HanoiTower(/i, source, dest, spare) if n = 1 then return [source, dest) # pro 1 disk - přesuň ho ze source na dest else output = HanoiTower(/i - 1, source, spare, dest) # přesuň n-1 disků na spare output.append((sol/rce, dest)) # přesuň zbývajícínejvětšídisk na dest # přesuň odložených n — 1 disků na dest output.append(HanoiTower(/i -1, spare, dest, source)) return output 0 optimalizace? Úvod do umělé inteligence 3/12 4/36 Dekompozice a AND/OR grafy Príklad - Hanojské veže Príklad - Hanojské veže - pokrač. function HanoiTower(/i, source, dest, spare) if n = 1 then return [source, dest) # pro 1 disk - přesuň ho ze source na dest else output = HanoiTower(/i - 1, source, spare, dest) # přesuň n-1 disků na spare output.append((sol/rce, dest)) # přesuň zbývajícínejvětšídisk na dest # přesuň odložených n — 1 disků na dest output.append(HanoiTower(/i -1, spare, dest, source)) return output HanoiTower^'aVb Ve'): [('a', 'b'), (>a\ 'c'), (>b\ 'c'), (>a\ 'b'), (>c\ 'a'), (>c\ >b>), (>a\ 'b')] optimalizace? Úvod do umělé inteligence 3/12 4/36 Dekompozice a AND/OR grafy Príklad - Hanojské veže Príklad - Hanojské veže - pokrač. function HanoiTower(/i, source, dest, spare) if n = 1 then return [source, dest) # pro 1 disk - přesuň ho ze source na dest else output = HanoiTower(/i - 1, source, spare, dest) # přesuň n-1 disků na spare output.append((sol/rce, dest)) # přesuň zbývajícínejvětšídisk na dest # přesuň odložených n — 1 disků na dest output.append(HanoiTower(/i -1, spare, dest, source)) return output HanoiTower^'aVb Ve'): [('a\ JbJ), (Ja\ JcJ), (>b\ JcJ), (Ja\ JbJ), (>c\ 'a'), (Jc\ >b>), (Ja\ Jb')] optimalizace - ukládat výsledky prvního rekurzivního volání a uložený výsledek vždy převzít bez nadbytečné další rekurze Úvod do umělé inteligence 3/12 4/36 Dekompozice a AND/OR grafy Cesta mezi městy pomocí dekompozice Cesta mezi městy pomocí dekompozice města: a, ..., e ... ve státě S lak ... hraniční přechody u, ..., z ... ve státě T hledáme cestu z a do z: • cesta z a do hraničního přechodu • cesta z hraničního přechodu do z S Úvod do umělé inteligence 3/12 5/36 Dekompozice a AND/OR grafy Cesta mezi městy pomocí dekompozice Cesta mezi městy pomocí d lekompozice - pokrač. schéma řešení pomocí rozkladu na podproblémy = AND/OR graf a^z OR uze a—k—a—M I—^z Celkové řešení = podgraf AND/OR grafu, který nevynechává žádného následníka AND-uzlu. Úvod do umělé inteligence 3/12 6/36 Dekompozice a AND/OR grafy AND/OR graf a strom řešení AND/OR graf a strom řešení AND/OR graf = graf s 2 typy vnitřních uzlů - AND uzly a OR uzly • AND uzel jako součást řešení vyžaduje průchod všech svých poduzlů • OR uzel se chová jako bežný uzel klasického grafu Úvod do umělé inteligence 3/12 7/36 Dekompozice a AND/OR grafy AND/OR graf a strom řešení AND/OR graf a strom řešení AND/OR graf = graf s 2 typy vnitřních uzlů - AND uzly a OR uzly • AND uzel jako součást řešení vyžaduje průchod všech svých poduzlů • OR uzel se chová jako bežný uzel klasického grafu Úvod do umělé inteligence 3/12 7/36 Dekompozice a AND/OR grafy AND/OR graf a strom řešení AND/OR graf a strom řešení strom řešení T problému P s AND/OR grafem G\ • problém P je kořen stromu T • jestliže P je OR uzel grafu G =>► právě jeden z jeho následníků se svým stromem řešení je v T • jestliže P je AND uzel grafu G =4> všichni jeho následníci se svými stromy řešení jsou v T • každý list stromu řešení T je cílovým uzlem v G Úvod do umělé inteligence 3/12 8/36 Dekompozice a AND/OR grafy AND/OR graf a strom řešení AND/OR graf a strom řešení strom řešení T problému P s AND/OR grafem G\ • problém P je kořen stromu T 9 jestliže P je OR uzel grafu G =4> právě jeden z jeho následníků se svým stromem řešení je v T • jestliže P je AND uzel grafu G =>► všichni jeho následníci se svými stromy řešení jsou v T 9 každý list stromu řešení T je cílovým uzlem v G a a b O O c b O d e f g d e h Úvod do umělé inteligence 3/12 8/36 Dekompozice a AND/OR grafy Příklady Příklad - agent vysavač v nestálém prostředí problém agenta Vysavače (2. přednáška) v nestálém prostředí: • dvě místnosti, jeden vysavač • v každé místnosti je/není špína 9 počet stavů je 2 x 22 = 8 • akce ={doLeva,doPrava,Vysávej} • nedeterminismus - akce Vysávej může: • ve špinavé místnosti - vysát místnost a někdy i tu vedlejší • v čisté místnosti - někdy místnost zašpinit Úvod do umělé inteligence 3/12 9/36 Dekompozice a AND/OR grafy Příklady Příklad - agent vysavač v nestálém prostředí problém agenta Vysavače (2. přednáška) v nestálém prostředí: • dvě místnosti, jeden vysavač • v každé místnosti je/není špína 9 počet stavů je 2 x 22 = 8 • akce ={doLeva,doPrava,Vysávej} • nedeterminismus - akce Vysávej může: • ve špinavé místnosti - vysát místnost a někdy i tu vedlejší • v čisté místnosti - někdy místnost zašpinit Strategie/kontingenční plán (prohledávací strom) obsahuje 2 typy uzlů: o deterministické stavy, kde se prostředí nemůže měnit - agent jen volí další postup, OR • nedeterministické stavy, kde se prostředí náhodně může změnit - agent musí řešit více možností, AND • mohou nastat cykly, řešení je jen když nedeterminismus není vždy negativní Úvod do umělé inteligence 3/12 9/36 Dekompozice a AND/OR grafy Příklady Příklad - agent vysavač v nestálém prostředí pokrač. Úvod do umělé inteligence 3/12 10 / 36 Dekompozice a AND/OR grafy Příklady Příklad - agent vysavač v nestálém prostředí pokrač. Úvod do umělé inteligence 3/12 10 / 36 Dekompozice a AND/OR grafy Příklady Příklad - výherní strategie Hra 2 hráčů s perfektními znalostmi, 2 výstupy Výherní strategii je možné formulovat jako AND/OR graf: • počáteční stav P typu já-jsem-na-tahu • moje tahy vedou do stavů Qi, Q2, ••• typu soupeř-je-na-tahu 9 následně soupeřovy tahy vedou do stavů /?n, /?i2,... já-jsem-na-tahu Úvod do umělé inteligence 3/12 11 / 36 Dekompozice a AND/OR grafy Příklady Příklad - výherní strategie Hra 2 hráčů s perfektními znalostmi, 2 výstupy Výherní strategii je možné formulovat jako AND/OR graf: • počáteční stav P typu já-jsem-na-tahu • moje tahy vedou do stavů Qi, Q2, ••• typu soupeř-je-na-tahu 9 následně soupeřovy tahy vedou do stavů /?n, /?i2,... já-jsem-na-tahu 9 cíl - stav, který je výhra podle pravidel (prohra je neřešitelný problém) • stav P já-jsem-na-tahu je výherní 44> některý z Q, je výherní, OR • stav Qi soupeř-je-na-tahu je výherní 44> všechny R,j jsou výherní, AND • výherní strategie = řešení AND/OR grafu Úvod do umělé inteligence 3/12 11 / 36 Dekompozice a AND/OR grafy Příklady Příklad - výherní strategie Hra 2 hráčů s perfektními znalostmi, 2 výstupy Výherní strategii je možné formulovat jako AND/OR graf: • počáteční stav P typu já-jsem-na-tahu • moje tahy vedou do stavů Qi, Q2, ••• typu soupeř-je-na-tahu 9 následně soupeřovy tahy vedou do stavů /?n, /?i2,... já-jsem-na-tahu 9 cíl - stav, který je výhra podle pravidel (prohra je neřešitelný problém) • stav P já-jsem-na-tahu je výherní 44> některý z Q, je výherní, OR • stav Qi soupeř-je-na-tahu je výherní 44> všechny R,j jsou výherní, AND • výherní strategie = řešení AND/OR grafu Úvod do umělé inteligence 3/12 11 / 36 Dekompozice a AND/OR grafy Příklady 0 0 X X X 0 Úvod do umělé inteligence 3/12 12 / 36 Dekompozice a AND/OR grafy Příklady Příklad - výherní strategie 0 0 X X X 0 0 0 X X X X 0 0 0 X X X X 0 0 0 X X X X 0 Úvod do umělé inteligence 3/12 12 / 36 Dekompozice a AND/OR grafy Příklady Příklad - výherní strategie 0 0 X X X 0 0 0 X X X X 0 0 0 X 0 0 X X X X X 0 X X 0 0 0 X 0 X X X 0 0 0 X X X 0 X 0 0 0 X X 0 X X 0 0 0 X X X 0 X 0 0 0 X 0 X X X 0 0 0 X 0 X X X 0 0 0 X 0 X X X X 0 0 0 X X X X 0 X 0 0 0 X X 0 X X X 0 0 0 X X X X 0 X 0 0 0 X 0 X X X X 0 0 0 X X 0 X X X 0 Úvod do umělé inteligence 3/12 12 / 36 Dekompozice a AND/OR grafy Příklady Příklad - výherní strategie 0 0 X X X 0 0 0 0 X X 0 0 0 X v v v A A A 0 X 0 0 X X X X X 0 0 X v v v A A A 0 X 0 0 0 0 X X 0 0 X X X X X Úvod do umělé inteligence 3/12 12 / 36 Dekompozice a AND/OR grafy Příklady Příklad - výherní strategie 0 0 X X X 0 0 0 0 X X 0 0 0 X v v v A A A 0 X 0 0 X X X X X 0 0 X v v v A A A 0 X 0 0 0 0 X X 0 0 X X X X X Úvod do umělé inteligence 3/12 12 / 36 Prohledávání AND/OR grafů Prohledávání AND/OR grafu do hloubky Obsah Dekompozice a AND/OR grafy • Příklad - Hanojské věže • AND/OR graf a strom řešení • Příklady O Prohledávání AND/OR grafů • Prohledávání AND/OR grafu do hloubky o Heuristické prohledávání AND/OR grafu (AO*) roDiemy s omezujícími 9 Varianty CSP podle hodnot proměnných • Varianty omezení CLP C t t L P • Řešení problémů s omezujícími podmínkami • Prohledávání s navracením « Ovlivnění efektivity prohledávání s navracením Úvod do umělé inteligence 3/12 13 / 36 Prohledávání AND/OR grafů Prohledávání AND/OR grafu do hloubky Prohledávání AND/OR grafu do hloubky OR-uzel function AndOrDepthFirstSearch(problem, path <(— []) # vrací řešení nebo "failure" if length (path) = 0 then return AndOrDepthFirstSearch(proĎ/em, [problem, in it .state ]) current-node <— path.Iast() # poslední prvek cesty if problem. is_goal (current-node) then return # prázdné (elementární) řešení else if problem. is_or_state (current-node) then foreach child in problem.moves(current-node) do if child G path then next result = AndOrDepthFirstSearch(proĎ/em, path + [child]) if result 7^ "failure" then return [child] + result return "failure" else if problem. is_and.state (current-node) then results = I AND-uzel foreach child in problem.moves(current-node) do if child G pat/7 then return "failure" result = AndOrDepthFirstSearch(pro£>/em, path + [c/7/7c/|) if result = "failure" then return "failure" results . append (result) return [ child] + [ results ] Úvod do umělé inteligence 3/12 14 / 36 Prohledávání AND/OR grafů Prohledávání AND/OR grafu do hloubky Prohledávání AND/OR grafu do hloubky OR-uzel function AndOrDepthFirstSearch(problem, path <(— []) # vrací řešení nebo "failure" if length (path) = 0 then return AndOrDepthFirstSearch(proĎ/ern, [problem, in it .state ]) current-node <— path.Iast() # poslední prvek cesty if problem. is_goal (current-node) then return # prázdné (elementární) řešení else if problem. is_or_state (current-node) then foreach child in problem.moves(current-node) do if child G path then next result = AndOrDepthFirstSearch(proĎ/em, path + [child]) if result 7^ "failure" then return [child] + result return "failure" else if problem. is_and.state (current-node) then results = I AND-uzel then return "failure1 foreach child in problem.moves(current-node) do if child G path then return "failure" result = AndOrDepthFirstSearch(prob/ern, pat/7 + [child]) if result = "failure" results . append (result) return [ child] + [ results ] AndOrDepthFirstSearch (problem): [>aVb\[['d>], [JeVh>]]] b O \ h Úvod do umělé inteligence 3/12 14 / 36 Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*) Heuristické prohledávání AND/OR grafu (AO*) • algoritmus AO* má stejné charakteristiky a složitost jako A* 9 cena přechodové hrany = míra složitosti podproblému: UZel = aQnrd, [(NaslUzell.Cenal), (NaslUzel2,Cena2), ... , (NaslUzelN.CenaN)] J • definujeme cenu uzlu jako cenu optimálního řešení jeho podstromu • pro každý uzel N máme daný odhad jeho ceny: h(N) = heuristický odhad ceny optimálního podgrafu s kořenem N • pro každý uzel N, jeho následníky A/i,..., A/^ a jeho předchůdce M definujeme: /?(/V), pro ještě neexpandovaný uzel N 0, pro cílový uzel (elementární problém) min/(F(A//)), pro OR-uzel N E/^A//), pro AND-uzel N F(N) = cena(M, N)+< Pro optimální strom řešení S je tedy F(S) právě cena tohoto řešení Úvod do umělé inteligence 3/12 15 / 36 Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*) Heuristické prohledávání AND/OR grafu - příklad setříděný seznam částečně expandovaných stromů řešení = [Nevyřešeným Nevyřešený2, ..., Vyřešenýi, ...] ^"Nevyřešenýi — ^~Nevyřešený2 — • • • předp. V/V : h(N) = 0 Úvod do umělé inteligence 3/12 16 / 36 Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*) Heuristické prohledávání AND/OR grafu - příklad setříděný seznam částečně expandovaných stromů řešení = [Nevyřešeným Nevyřešený2, ..., Vyřešeným ...] ^"Nevyřešenýi — ^~Nevyřešený2 — • • • předp. V/V : h(N) = 0 Úvod do umělé inteligence 3/12 16 / 36 Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*) Heuristické prohledávání AND/OR grafu - příklad setříděný seznam částečně expandovaných stromů řešení = [Nevyřešeným Nevyřešený2, ..., Vyřešenýi, ...] Nevyřešenýi — rNevyřešený2 — • • • předp. V/V : h(N) = 0 Úvod do umělé inteligence 3/12 16 / 36 Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*) Heuristické prohledávání AND/OR grafu - příklad setříděný seznam částečně expandovaných stromů řešení [Nevyřešeným Nevyřešený2, ..., Vyřešenýi, ...] ^"Nevyřešenýi — ^~Nevyřešený2 — • • • předp. V/V : h(N) = 0 h 6 C 3 Úvod do umělé inteligence 3/12 16 / 36 Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*) Heuristické prohledávání AND/OR grafu - příklad setříděný seznam částečně expandovaných stromů řešení = [Nevyřešeným Nevyřešený2, ..., Vyřešeným ...] Nevyřešenýi — rNevyřešený2 — • • • předp. V/V : h(N) = 0 6 Úvod do umělé inteligence 3/12 16 / 36 Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*) Heuristické prohledávání AND/OR grafu - příklad setříděný seznam částečně expandovaných stromů řešení = 6/2 3 Úvod do umělé inteligence 3/12 16 / 36 Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*) Heuristické prohledávání AND/OR grafu - příklad setříděný seznam částečně expandovaných stromů řešení = [Nevyřešeným Nevyřešený2, ..., Vyřešenýi, ...] Nevyřešenýi — rNevyřešený2 — • • • g l 6/2 3 Úvod do umělé inteligence 3/12 16 / 36 Prohledávání AND/OR grafů Cesta mezi městy heuristickým AND/OR hledáním Cesta mezi městy heuristický m AND/OR hledáním • cesta mezi sousedícími městy Mestol a Mesto2 - ohodnocené hrany problém.moves(Mestol) —>► [(Mesto2,Vzdal2), ...] • klíčové postavení města Mesto3 na cestě z Mestol do Mesto2 - funkce problém.key(Mestol, Mesto2) —>► [Mesto3, ...]. Úvod do umělé inteligence 3/12 17 / 36 Prohledávání AND/OR grafů Cesta mezi městy heuristickým AND/OR hledáním Cesta mezi městy heuristickým AND/OR hledáním vlastní hledání cesty: 1. 3 Yl, Y2,... klíčové body mezi městy A a Z. Hledej jednu z cest: • cestu z A do Z přes Yl • cestu z A do Z přes Y2 • 2. Není-li mezi městy A a Z klíčové město =4> hledej souseda Y města A takového, že existuje cesta z Y do Z. Úvod do umělé inteligence 3/12 18 / 36 Prohledávání AND/OR grafů Cesta mezi městy heuristickým AND/OR hledáním Cesta mezi městy heuristickým AND/OR hledáním Konstrukce příslušného AND/OR grafu: "manuální" výpis všech uzlů: # kterákoliv cesta přes klíčové město 'a-z* ('or\ [('a-z via k\ 0), ('a-z via 1\ 0)]) 'a-v' ('or', [('a-v via k\ 0), ('a-v via 1\ 0)]) # kterákoliv cesta přes sousední města »a-l> (b-l' ->• ('or\ [('e-l\ 3), (M-l\ 2)]) # cesta do klíčového města a z klíčového města 'a-z via ľ ('and', [('a-l', 0), ('l-z\ 0)]) 'a-v via ľ ('and', [('a-l', 0), ('1-v', 0)]) # cíle — elementární problémy goal('a-a'); goal('b-b'); ... Úvod do umělé inteligence 3/12 19 / 36 Prohledávání AND/OR grafů Cesta mezi městy heuristickým AND/OR hledáním Cesta mezi městy heuristickým AND/OR hledáním Konstrukce příslušného AND/OR grafu: "pravidlová" definice grafu: # kterákoliv cesta přes klíčové město 'a-z' —> ('or', [('a-z via k', 0), ('a-z via I', 0)]) ... for X G problem.cities do for Z G problem.cities do nodes = []; for Y G problem.key(X, Z) do nodes.append((3 X-Z via Y\ 0)) if length (nodes) >0 then problem. add(' X-Z' —»> ('or', nodes)) # kterákoliv cesta přes sousední města 'a-l' —> ('or', [('c-l', 3), ('b-l', 2)]) ... for X G problem.cities do for Z G problem.cities do nodes = []; for V, \/ G problem.moves(X) do nodes.append((' Y-Z', V)) if length (nodes) >0 then problem. add(' X-Z' —('or', nodes)) # cesta do a z klíčového města 'a-z via /' —>- ('and', [('a-l', 0), ('l-z', 0)]) ... for X G problem.cities do for Z G problem.cities do for YG problem, key{X, Z) do problem.add(3X-Z via Y' ('and3, [(3X-Y3,0), (3Y-Z3,0)])) # c/7e - elementární problémy goal('a-a'); goal('b-b'); ... for X G problem.cities do proĎ/em.addtgoal^X-X')) Úvod do umělé inteligence 3/12 19 / 36 Prohledávání AND/OR grafů Cesta mezi městy heuristickým AND/OR hledáním Cesta mezi městy heuristickým AND/OR hledáním - pokrač. heuristika h{ X — Z | X — Z via Y ) = vzdušná vzdálenost Když \/n : h(n) < h*(n), kde h* je minimální cena řešení uzlu n najdeme vždy optimální řešení Úvod do umělé inteligence 3/12 20 / 36 Prohledávání AND/OR grafů Cesta mezi městy heuristickým AND/OR hledáním Cesta mezi městy heuristickým AND/OR hledáním - pokrač. heuristika h{ X — Z | X — Z via Y ) = vzdušná vzdálenost Když \/n : h(n) < h*(n), kde h* je minimální cena řešení uzlu n najdeme vždy optimální řešení S AO+Search^a-z'): [('a-z',11), ('a-z via [[('l-z',6), " ('u-z',6), ('y-z',5), ('z-z',3)], [('a-1',5), ('c-1',5), ('1-1',2)]]] Úvod do umělé inteligence 3/12 20 / 36 Problémy s omezujícími podmínkami • Příklad - Hanojské věže • AND/OR graf a strom řešení • Příklady \J Prohledávaní AND/OK gratu • Prohledávání AND/OR grafu do hloubky • Heuristické prohledávání AND/OR grafu (AO*) Q Problémy s omezujícími podmínkami o Varianty CSP podle hodnot proměnných • Varianty omezení • Řešení problémů s omezujícími podmínkami • Prohledávání s navracením • Ovlivnění efektivity prohledávání s navracením Úvod do umělé inteligence 3/12 21 / 36 Problémy s omezujícími podmínkami Problémy s omezujícími podmínkami • standardní problém řešený prohledáváním stavového prostoru —> stav je 11 černá skříňka" - pouze cílová podmínka a přechodová funkce Úvod do umělé inteligence 3/12 22 / 36 Problémy s omezujícími podmínkami Problémy s omezujícími podmínkami standardní problém řešený prohledáváním stavového prostoru —> stav je 11 černá skříňka" - pouze cílová podmínka a přechodová funkce problém s omezujícími podmínkami, Constraint Satisfaction Problem, CSP: • a7-tice proměnných Xi,X2,... ,Xn s hodnotami z domén Di, D2,..., Dn, • množina omezení Ci, C2,..., Cm nad proměnnými X, Úvod do umělé inteligence 3/12 22 / 36 Problémy s omezujícími podmínkami Problémy s omezujícími podmínkami • standardní problém řešený prohledáváním stavového prostoru —> stav je 11 černá skříňka" - pouze cílová podmínka a přechodová funkce • problém s omezujícími podmínkami, Constraint Satisfaction Problem, CSP: • a7-tice proměnných Xi,X2,... ,Xn s hodnotami z domén Di, D2,..., Dn, • množina omezení Ci, C2,..., Cm nad proměnnými X, • stav = přiřazení hodnot proměnným {X/ = 17, X/ = vj,...} - konzistentní přiřazení neporušuje žádné z omezení C, - úplné přiřazení zmiňuje každou proměnnou X, • řešení = úplné konzistentní přiřazení hodnot proměnným někdy je ještě potřeba maximalizovat cílovou funkci Úvod do umělé inteligence 3/12 22 / 36 Problémy s omezujícími podmínkami Problémy s omezujícími pod mínkami • standardní problém řešený prohledáváním stavového prostoru —> stav je 11 černá skříňka" - pouze cílová podmínka a přechodová funkce • problém s omezujícími podmínkami, Constraint Satisfaction Problem, CSP: • a7-tice proměnných Xi,X2,... ,Xn s hodnotami z domén Di, D2,..., Dn, • množina omezení Ci, C2,..., Cm nad proměnnými X, • stav = přiřazení hodnot proměnným {X/ = 17, X/ = vj,...} - konzistentní přiřazení neporušuje žádné z omezení C, - úplné přiřazení zmiňuje každou proměnnou X, • řešení = úplné konzistentní přiřazení hodnot proměnným někdy je ještě potřeba maximalizovat cílovou funkci 9 výhody: • jednoduchý formální jazyk pro specifikaci problému • může využívat obecné heuristiky (nejen specifické pro daný problém) Úvod do umělé inteligence 3/12 22 / 36 Problémy s omezujícími podmínkami Příklad - obarvení mapy Příklad - obarvení mapy Tasmania • Proměnné WA, NT, Q, NSW, V, SA, T • Domény D\ — {červená, zelená, modrá} • Omezení - sousedící oblasti musí mít různou barvu tj. pro každé dvě sousedící: WA ^ NT nebo (I/I//4, NT) G {(červená, zelená), (červená, modrá), (zelená, modrá),...} Úvod do umělé inteligence 3/12 23 / 36 Problémy s omezujícími podmínkami Příklad - obarvení mapy Příklad - obarvení mapy - pokrač. • Řešení - konzistentní přiřazení všem proměnným: {1/1/4 = červená, NT = zelená, Q = červená, NSW = zelená, V = červená, SA - modrá, T = zelená} CSliDo) Úvod do umělé inteligence 3/12 24 / 36 Problémy s omezujícími podmínkami Varianty CSP podle hodnot proměnných Varianty CSP podle hodnot proměnných • diskrétní hodnoty proměnných - spočetně mnoho jednotlivých hodnot • konečné domény např. Booleovské (včetně NP-úplných problémů splnitelnosti) - výčtové • nekonečné domény - čísla, řetězce, .. . např. rozvrh prací - proměnné = počáteční/koncový den každého úkolu - vyžaduje jazyk omezení, např. Start Jobi + 5 < StartJob?, číselné lineární problémy jsou řešitelné, nelineárníobecné řešení nemají Úvod do umělé inteligence 3/12 25 / 36 Problémy s omezujícími podmínkami Varianty CSP podle hodnot proměnných Varianty CSP podle hodnot proměnných • diskrétní hodnoty proměnných - spočetně mnoho jednotlivých hodnot • konečné domény např. Booleovské (včetně NP-úplných problémů splnitelnosti) - výčtové • nekonečné domény - čísla, řetězce, .. . např. rozvrh prací - proměnné = počáteční/koncový den každého úkolu - vyžaduje jazyk omezení, např. Start Jobi + 5 < StartJob?, - číselné lineární problémy jsou řešitelné, nelineárníobecné řešení nemají 9 spojité hodnoty proměnných • časté u reálných problémů • např. počáteční/koncový čas měření na Hubbleově teleskopu (závisí na astronomických, precedenčních a technických omezeních) • lineární omezení řešené pomocí Lineárního programování (omezení = lineární (ne)rovnice tvořící konvexní oblast) —>» jsou řešitelné v polynomiálním čase Úvod do umělé inteligence 3/12 25 / 36 Problémy s omezujícími podmínkami Varianty omezení Varianty omezení • unární omezení zahrnuje jedinou proměnnou např. SA ^ zelená • binární omezení zahrnují dvě proměnné např. SA ^ WA • omezení vyššího řádu zahrnují 3 a více proměnných např. kryptoaritmetické omezení na sloupce u algebrogramu • preferenční omezení (soft constraints), např. 'červená je lepší než zelená' možno reprezentovat pomocí ceny přiřazení u konkrétní hodnoty a konkrétní proměnné —>► hledá se optimalizované řešení vzhledem k ceně Úvod do umělé inteligence 3/12 26 / 36 Problémy s omezujícími podmínkami Graf omezení Graf omezení Pro binární omezení: uzly = proměnné, hrany = reprezentují jednotlivá omezení Pro H-ární omezení: hypergraf: O uzly = proměnné, □ uzly = omezení, hrany = použití proměnné v omezení Algoritmy pro řešení CSP využívají této grafové reprezentace omezení Úvod do umělé inteligence 3/12 27 / 36 CLP - Constraint Logic Programming CLP - Constraint Logic Programming Xin 1..5, Yin 2..8 , X+Y#= T: Xin 1..5 Yin 2..8 Tin 3..13 Úvod do umělé inteligence 3/12 28 / 36 CLP - Constraint Logic Programming CLP - Constraint Logic Programming ?X in +Min..+Max ?X in +Domain .. . A in 1..3 \/8..15 \/5..9 \/100. +VarList ins +Domain fd_dom(?Var,?Domain) zjištění domény proměnné X in 1..5, Yin 2..8 , X+Y#= T: Xin 1..5 Yin 2..8 Tin 3..13 Úvod do umělé inteligence 3/12 28 / 36 CLP - Constraint Logic Programming CLP - Constraint Logic Programming ?X in +Min..+Max ?X in +Domain .. . A in 1..3 \/8..15 \/5..9 \/100. +VarList ins +Domain fd_dom(?Var,?Domain) zjištění domény proměnné n 1..5, Yin 2..8 , X+Y#= T: Xin 1..5 Yin 2..8 Tin 3..13 aritmetická omezení . .. - rel. operátory #=, #\=, #<, #=<, #>, #> = - sum(Variables,RelOp,Suma) výroková omezení . . . #\ negace, #/\ konjunkce, #\/ disjunkce, #<==> ekvivalence kombinatorická omezení .. . alLdistinct(List), global_cardinality(List, KeyCounts) Úvod do umělé inteligence 3/12 28 / 36 CLP - Constraint Logic Programming CLP - Constraint Logic Programming ?X in +Min..+Max ?X in +Domain .. . A in 1..3 \/8..15 \/5..9 \/100. +VarList ins +Domain fd_dom(?Var,?Domain) zjištění domény proměnné Xin 1..5, Yin 2..8 , X+Y#= T: Xin 1..5 Yin 2..8 Tin 3..13 aritmetická omezení . .. - rel. operátory #=, #\=, #<, #=<, #>, #> = - sum(Variables,RelOp,Suma) výroková omezení . . . #\ negace, #/\ konjunkce, #\/ disjunkce, #<==> ekvivalence kombinatorická omezení .. . alLdistinct(List), global_cardinality(List, KeyCounts) Xin 1..5, Vin 2..8 , X+Y#= T, labeling([X,Y,7]): _ ^agag=^=\ hledá hodnoty podle omezení j Y= 2 Úvod do umělé inteligence 3/12 28 / 36 CLP - Constraint Logic Programming CLP - Constraint Logic Programming - pokrac. X #< 4, [X,Y] ins 0..5: X in 0..3 , Y in 0..5. Úvod do umělé inteligence 3/12 29 / 36 CLP - Constraint Logic Programming CLP - Constraint Logic Prog ^ramming - pokrac. X #< 4, [X,Y] ins 0..5: X in 0..3, Y in 0..5. X #< 4, indomain(X): ERROR: Arguments are not sufficiently instantiated Uvod do umele inteligence 3/12 29 / 36 CLP - Constraint Logic Programming CLP - Constraint Logic Programming - pokrac. X #< 4, [X,Y] ins 0..5: X in 0..3 , Y in 0..5. X #< 4, indomain(X): ERROR: Arguments are not sufficiently instantiated X #> 3, X #< 6, indomain(X): X = 4 X = 5 Úvod do umělé inteligence 3/12 29 / 36 CLP - Constraint Logic Programming CLP - Constraint Logic Programming - pokrac X #< 4, [X,Y] ins 0..5: X in 0..3, Y in 0..5. X #< 4, indomain(X): ERROR: Arguments are not sufficiently instantiated X #> 3, X #< 6, indomain(X): X = 4 X = 5 X in 4.. sup, X #\= 17, fd_dom(X,F): F = 4..16\/18..sup, X in 4..16\/18..sup. Úvod do umělé inteligence 3/12 29 / 36 CLP - Constraint Logic Programming Příklad - algebrogram Příklad - algebrogram SEND + MORE MONEY Úvod do umělé inteligence 3/12 30 / 36 CLP - Constraint Logic Programming Příklad - algebrogram Příklad - algebrogram SEND + MORE MONEY Proměnné Domény Omezení Úvod do umělé inteligence 3/12 30 / 36 CLP - Constraint Logic Programming Příklad - algebrogram Příklad - algebrogram Proměnné {S,E,N,D,M,0,R,Y} SEND Domény + MORE Omezení MONEY Úvod do umělé inteligence 3/12 30 / 36 CLP - Constraint Logic Programming Příklad - algebrogram Příklad - algebrogram Proměnné {S,E,N,D,M,0,R,Y} SEND Domény D-, = {0,1, 2, 3,4, 5, 6, 7, 8, 9} + MORE Omezení MONEY Úvod do umělé inteligence 3/12 30 / 36 CLP - Constraint Logic Programming Příklad - algebrogram Příklad - algebrogram Proměnné SEND Domény + MORE Omezení - MONEY {S, E, A/, D, M, O,/?, Y} D/ = {0,1, 2,3,4,5,6,7,8, 9} S > 0, M > 0 S^E^N^D^M^O^R^Y 1000 *S + 100*E + 10*A/+D + 1000 * M + 100 * O + 10 * R + E = 10000 * M + 1000 *0 + 100 *A/ + 10 *E+Y Úvod do umělé inteligence 3/12 30 / 36 CLP - Constraint Logic Programming Příklad - algebrogram Příklad - algebrogram Proměnné SEND Domény + MORE Omezení - MONEY {S, E, A/, D, M, O,/?, Y} D/ = {0,1, 2,3,4,5,6,7,8, 9} S > 0, M > 0 1000 *S + 100*E + 10*A/+D + 1000 * M + 100 * O + 10 * R + E = 10000 * M + 1000 *0 + 100 *A/ + 10 *E+Y function MoreMoney( [S, E,A/,D,M,O,/?, Y|) [S,E,N,D,M,0,R,Y\ ins 0..9 S#> 0; M#> 0 aILdistinct ([S,E,N,D,M,0,R,Y\) 1000*S + 100*E + 10*/V + D + 1000*M + 100*O + 10*/? + E #= 10000*M + 1000*0 + 100*/V + 10*E + Y labeling {[S, E, N, D, M, 0,R,Y\) Úvod do umělé inteligence 3/12 30 / 36 Proměnné {S, E, N, D, M, O, R, Y} SEND Domény D; = {0,1, 2, 3,4, 5, 6, 7, 8, 9} function MoreMoney([S,E,N,D,M,0,R,Y\) [S,E,N,D,M,0,R,Y\ ins 0..9 S#> 0; M#> 0 aILdistinct {[S,E,N,D,M,0,R,Y\) 1000*S + 100*E + 10* N + D + 1000*M + 100*0 + 10*/? + E #= 10000*M + 1000*0 + 100*/V + 10*E + Y labeling ([S, E,/V, D, M, O,/?, V]) MoreMoney( [S, E, A/, D, M, O, R, Y\): S = 9, E = 5, A/ = 6, D = 7, M = 1, O = 0, /? = 8, Y =2 + MORE Omezení S > 0, M > 0 S^E^N^D^M^O^R^Y MONEY 1000 *S + 100*E + 10*A/+D + 1000 * M + 100 * O + 10 * /? + E = 10000 * M + 1000 *0 + 100 *A/ + 10 * E + Y Úvod do umělé inteligence 3/12 30 / 36 v CLP - Constraint Logic Programming Řešení problémů s omezujícími podmínkami Inkrementální formulace CSP CSP je možné převést na standardní prohledávání takto: • stav - přiřazení hodnot proměnným • počáteční stav - prázdné přiřazení {} • přechodová funkce - přiřazení hodnoty libovolné dosud nenastavené proměnné tak, aby výsledné přiřazení bylo konzistentní • cílová podmínka - aktuální přiřazení je úplné • cena cesty - konstantní (např. 1) pro každý krok Úvod do umělé inteligence 3/12 31 / 36 v CLP - Constraint Logic Programming Řešení problémů s omezujícími podmínkami Inkrementální formulace CSP CSP je možné převést na standardní prohledávání takto: • stav - přiřazení hodnot proměnným • počáteční stav - prázdné přiřazení {} • přechodová funkce - přiřazení hodnoty libovolné dosud nenastavené proměnné tak, aby výsledné přiřazení bylo konzistentní • cílová podmínka - aktuální přiřazení je úplné • cena cesty - konstantní (např. 1) pro každý krok 1. platí beze změny pro všechny CSP! 2. prohledávací strom dosahuje hloubky n (počet proměnných) a řešení se nachází v této hloubce (d = n) =4> je vhodné použít prohledávání do hloubky Úvod do umělé inteligence 3/12 31 / 36 CLP - Constraint Logic Programming Prohledávání s navracením Prohledávání s navracením • přiřazení proměnným jsou komutativní tj. [1. WA = červená, 2. NT = zelená] je totéž jako [1. NT = zelená, 2. WA = červená] • stačí uvažovat pouze přiřazení jediné proměnné v každém kroku počet listů max. |D/|n, větvení jde ovlivnit obecnými strategiemi o prohledávání do hloubky pro CSP - tzv. prohledávání s navracením (backtracking search) • prohledávání s navracením je základní neinformovaná strategie pro řešení problémů s omezujícími podmínkami • schopný vyřešit např. problém n-dam pro n « 25 (naivní řešení 1069, vlastní sloupce 1025) Úvod do umělé inteligence 3/12 32 / 36 CLP - Constraint Logic Programming Příklad - problém N dam Příklad - problém N dam function Queens(/V) L = [qyi, qy2, CJyN] # seznam N proměnných L ins 1.. N for / ^ 1 to A/1 do for j > ——1 3. hledaní reseni I function NoThreat(Y\, Y2, J) return Y1 #\= Y2 and Yi+J #\= Y2 and Yi-J #\= Y2 Queens(4): [2,4,1,3] [3,1,4,2] Úvod do umělé inteligence 3/12 33 / 36 CLP - Constraint Logic Programming Ovlivnění efektivity prohledávání s navracením Ovlivnění efektivity prohledávání s navracením Obecné metody ovlivnění efektivity: - Která proměnná dostane hodnotu v tomto kroku? - V jakém pořadí zkoušet přiřazení hodnot konkrétní proměnné? - Můžeme předčasně detekovat nutný neúspěch v dalších krocích? Úvod do umělé inteligence 3/12 34 / 36 CLP - Constraint Logic Programming Ovlivnění efektivity prohledávání s navracením Ovlivnění efektivity prohledávání s navracením Obecné metody ovlivnění efektivity: - Která proměnná dostane hodnotu v tomto kroku? - V jakém pořadí zkoušet přiřazení hodnot konkrétní proměnné? - Můžeme předčasně detekovat nutný neúspěch v dalších krocích? používané strategie: • nejomezenější proměnná —>► vybrat proměnnou s nejméně možnými hodnotami v v v v Úvod do umělé inteligence 3/12 34 / 36 CLP - Constraint Logic Programming Ovlivnění efektivity prohledávání s navracením Ovlivnění efektivity prohledávání s navracením Obecné metody ovlivnění efektivity: - Která proměnná dostane hodnotu v tomto kroku? - V jakém pořadí zkoušet přiřazení hodnot konkrétní proměnné? - Můžeme předčasně detekovat nutný neúspěch v dalších krocích? používané strategie: • nejomezenější proměnná —>► vybrat proměnnou s nejméně možnými hodnotami • nejvíce omezující proměnná —>► vybrat proměnnou s nejvíce omezeními na zbývající proměnné Úvod do umělé inteligence 3/12 34 / 36 CLP - Constraint Logic Programming Ovlivnění efektivity prohledávání s navracením Ovlivnění efektivity prohledávání s navracením Obecné metody ovlivnění efektivity: - Která proměnná dostane hodnotu v tomto kroku? - V jakém pořadí zkoušet přiřazení hodnot konkrétní proměnné? - Můžeme předčasně detekovat nutný neúspěch v dalších krocích? používané strategie: • nejomezenější proměnná —>► vybrat proměnnou s nejméně možnými hodnotami • nejvíce omezující proměnná —>► vybrat proměnnou s nejvíce omezeními na zbývající proměnné • nejméně omezující hodnota —>► pro danou proměnnou - hodnota, která zruší nejmíň hodnot zbývajících proměnných csiiDo) umožňuje 1 hodnotu pro SA umožňuje 0 hodnot pro SA Úvod do umělé inteligence 3/12 34 / 36 CLP - Constraint Logic Programming Ovlivnění efektivity prohledávání s navracením Ovlivnění efektivity prohledávání s navracením Obecné metody ovlivnění efektivity: - Která proměnná dostane hodnotu v tomto kroku? - V jakém pořadí zkoušet přiřazení hodnot konkrétní proměnné? - Můžeme předčasně detekovat nutný neúspěch v dalších krocích? používané strategie: • nejomezenější proměnná —>► vybrat proměnnou s nejméně možnými hodnotami • nejvíce omezující proměnná —>► vybrat proměnnou s nejvíce omezeními na zbývající proměnné o nejméně omezující hodnota —>► pro danou proměnnou - hodnota, která zruší nejmíň hodnot zbývajících proměnných csiiDo) • dopředná kontrola —>► udržovat seznam možných hodnot pro zbývající proměnné o propagace omezení —>► navíc kontrolovat možné nekonzistence mezi zbývajícími proměnnými Úvod do umělé inteligence 3/12 34 / 36 CLP - Constraint Logic Programming Ovlivnění efektivity v CLP Ovlivnění efektivity v CLP V Prologu (CLP) možnosti ovlivnění efektivity - labeling(Typ, ...): ?- constraints (Vars,Cost), labeling ([ f f, bisect , down, min(Cost)], Vars). • výběr proměnné - leftmost, min, max, ff, ... • dělení domény - step, enum, bisect • prohledávání domény - up, down o uspořádání řešení - bez uspořádání nebo min(X), max(X), ... Úvod do umělé inteligence 3/12 35 / 36 CLP - Constraint Logic Programming Systémy pro řešení omezujících podmínek Systémy pro řešení omezujících podmínek • Prolog - SWI, CHIP, ECLiPSe, SICStus Prolog, Prolog IV, GNU Prolog, IF/Prolog • C/C++ - CHIP++, ILOG Solver, Gecode • Java - JCK, JCL, Koalog • LISP - Screamer • Python - logilab-constraint www.logilab.org/852, python-constraint • Mozart - www.mozart-oz.org, jazyk Oz Úvod do umělé inteligence 3/12 36 / 36