Dekompozice problému, AND/OR grafy, problémy s omezujícími podmínkami Aleš Horák E-mail: hales@fi.muni.cz http://nlp.fi.muni.cz/uui/ Obsah: ▶ Dekompozice a AND/OR grafy ▶ Prohledávání AND/OR grafů ▶ Problémy s omezujícími podmínkami ▶ CLP – Constraint Logic Programming Úvod do umělé inteligence 3/12 1 / 33 Dekompozice a AND/OR grafy Příklad – Hanojské věže Příklad – Hanojské věž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í bit.ly/uuihanoi1 (Tower3 je zde cíl) 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 Úvod do umělé inteligence 3/12 2 / 33 Dekompozice a AND/OR grafy Příklad – Hanojské věže Příklad – Hanojské věže – pokrač. schéma celého řešení pro n = 3: n = 3(A,B,C) ⃝ n − 1 = 2(A,C,B) ⃝ n − 2 = 1(A,B,C) 1(A,C,B) n − 2 = 1(B,C,A) 1(A,B,C) n − 1 = 2(C,B,A) ⃝ n − 2 = 1(C,A,B) 1(C,B,A) n − 2 = 1(A,B,C) Úvod do umělé inteligence 3/12 3 / 33 Dekompozice a AND/OR grafy Příklad – Hanojské věže Příklad – Hanojské věže – pokrač. function HanoiTower(n, source, dest, spare) if n = 1 then return (source, dest) # pro 1 disk – přesuň ho ze source na dest else output = .............HanoiTower(n - 1, source, spare, dest) # přesuň n − 1 disků na spare output.append((source, dest)) # přesuň zbývající největší disk na dest # přesuň odložených n − 1 disků na dest output.append(..............HanoiTower(n - 1, spare, dest, source)) return output HanoiTower(3,’a’,’b’,’c’): [(’a’, ’b’), (’a’, ’c’), (’b’, ’c’), (’a’, ’b’), (’c’, ’a’), (’c’, ’b’), (’a’, ’b’)] 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 / 33 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 l a k . . . 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 . c l v a e u z b k y d x T . Úvod do umělé inteligence 3/12 5 / 33 Dekompozice a AND/OR grafy Cesta mezi městy pomocí dekompozice Cesta mezi městy pomocí dekompozice – pokrač. schéma řešení pomocí rozkladu na podproblémy = AND/OR graf a→z via k ⃝ a→k . . . . . . k→z . . . . . . via l ⃝ a→l . . . . . . l→z . . . . . . OR uzel AND uzly 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 / 33 Dekompozice a AND/OR grafy Další příklady Příklad – agent vysavač v nestálém prostředí problém agenta Vysavače v nestálém prostředí: ▶ dvě místnosti, jeden vysavač ▶ v každé místnosti je/není špína ▶ počet stavů je 2 × 22 = 8 ▶ akce ={doLeva,doPrava,Vys´avej} ▶ 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ů: ▶ 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 7 / 33 Dekompozice a AND/OR grafy Další příklady Příklad – agent vysavač v nestálém prostředí pokrač. ⃝ ⃝ ⃝ Vysávej Vysávej doPrava Vysávej doLeva doPrava doLeva Vysávej Úvod do umělé inteligence 3/12 8 / 33 Dekompozice a AND/OR grafy Další příklady Příklad – výherní strategie Hra 2 hráčů s perfektními znalostmi, 2 výstupy výhra prohra 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ů Q1, Q2, ... typu soupeř-je-na-tahu ▶ následně soupeřovy tahy vedou do stavů R11, R12, ... já-jsem-na-tahu ▶ 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í ⇔ některý z Qi je výherní, OR ▶ stav Qi soupeř-je-na-tahu je výherní ⇔ všechny Rij jsou výherní, AND ▶ výherní strategie = řešení AND/OR grafu P Q1 ⃝ R11 R12 . . . Q2 ⃝ R21 R22 . . . Q3 ⃝ R31 R32 . . . Úvod do umělé inteligence 3/12 9 / 33 Dekompozice a AND/OR grafy Další příklady Příklad – výherní strategie o o x x x o o o x x x x o o o x o x x x o o o x o x x x x o o o x x x o x o o o x x x x o x o o o x x x x o o o x x o x x o o o x x o x x x o o o x x x o x o o o x x x x o x o o o x x x x o o o x o x x x o o o x o x x x x o o o x o x x x o o o x x o x x x o Úvod do umělé inteligence 3/12 10 / 33 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 a b ⃝ d e h c ⃝ f ⃝ i g Úvod do umělé inteligence 3/12 11 / 33 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 ⇒ 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 a b ⃝ d e h c ⃝ f ⃝ i g −→ a b ⃝ d e h Úvod do umělé inteligence 3/12 12 / 33 Prohledávání AND/OR grafů Prohledávání AND/OR grafu do hloubky Prohledávání AND/OR grafu do hloubky function AndOrDepthFirstSearch(problem, path ← []) # vrací řešení nebo "failure" if length(path) = 0 then return AndOrDepthFirstSearch(problem, [problem.init_state]) current_node ← path.last() # 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 ∈ path then next result = AndOrDepthFirstSearch(problem, path + [child]) if result ̸= "failure" then return [child ] + result return "failure" else if problem.is_and_state(current_node) then results = [] foreach child in problem.moves(current_node) do if child ∈ path then return "failure" result = AndOrDepthFirstSearch(problem, path + [child]) if result = "failure" then return "failure" results .append(result) return [ child ] + [ results ] AndOrDepthFirstSearch(problem): [’a’,’b’,[ [’d’], [’e’,’h’]] ] OR-uzel AND-uzel a b ⃝ d e h Úvod do umělé inteligence 3/12 13 / 33 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* ▶ cena přechodové hrany = míra složitosti podproblému: uzel = and or , [(NaslUzel1,Cena1), (NaslUzel2,Cena2), ... , (NaslUzelN,CenaN)] ▶ 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 N1, . . . , Nb a jeho předchůdce M definujeme: F(N) = cena(M, N)+    h(N), pro ještě neexpandovaný uzel N 0, pro cílový uzel (elementární problém) mini (F(Ni )), pro OR-uzel N i F(Ni ), pro AND-uzel 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 14 / 33 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ý1, Nevyřešený2, . . . , Vyřešený1, . . . ] FNevyřešený1 ≤ FNevyřešený2 ≤ . . . a b ⃝ d e h c ⃝ f ⃝ i g 1 1 1 6 3 2 3 1 2 předp. ∀N : h(N) = 0 a b ⃝ d e h c ⃝ f ⃝ i g 1 1 1 6 3 2 3 1 9 2 9 1 7 6/2 11 7 3 1 Úvod do umělé inteligence 3/12 15 / 33 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 Mesto1 a Mesto2 – ohodnocené hrany problem.moves(Mesto1) → [(Mesto2,Vzdal2), ...] ▶ klíčové postavení města Mesto3 na cestě z Mesto1 do Mesto2 – funkce problem.key(Mesto1, Mesto2) → [Mesto3, ...]. S . c l v a e u z b k y d x T . 3 2 2 1 2 3 2 4 23 1 3 3 5 31 2 Úvod do umělé inteligence 3/12 16 / 33 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. ∃ Y1, Y2,. . . klíčové body mezi městy A a Z. Hledej jednu z cest: • cestu z A do Z přes Y1 • cestu z A do Z přes Y2 • . . . 2. Není-li mezi městy A a Z klíčové město ⇒ hledej souseda Y města A takového, že existuje cesta z Y do Z. Úvod do umělé inteligence 3/12 17 / 33 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 l’, 0)]) ... for X ∈ problem.cities do for Z ∈ problem.cities do nodes = []; for Y ∈ problem.key(X, Z) do nodes.append((’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 ∈ problem.cities do for Z ∈ problem.cities do nodes = []; for Y, V ∈ 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 l’ → (’and’, [(’a-l’, 0), (’l-z’, 0)]) ... for X ∈ problem.cities do for Z ∈ problem.cities do for Y ∈ problem.key(X, Z) do problem.add(’X-Z via Y ’ → (’and’, [(’X-Y ’,0), (’Y -Z’,0)])) # cíle – elementární problémy goal(’a-a’); goal(’b-b’); ... for X ∈ problem.cities do problem.add(goal(’X-X’)) Úvod do umělé inteligence 3/12 18 / 33 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 . c l v a e u z b k y d x T . 3 2 2 1 2 3 2 4 23 1 3 3 5 31 2 AO∗Search(’a-z’): [(’a-z’,11), (’a-z via l’,11), [[(’l-z’,6), (’u-z’,6), (’y-z’,5), (’z-z’,3)], [(’a-l’,5), (’c-l’,5), (’l-l’,2)]]] AND-uzel Úvod do umělé inteligence 3/12 19 / 33 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 “černá skříňka” – pouze cílová podmínka a přechodová funkce ▶ problém s omezujícími podmínkami, Constraint Satisfaction Problem, CSP: • n-tice proměnných X1, X2, . . . , Xn s hodnotami z domén D1, D2, . . . , Dn, Di ̸= ∅ • množina omezení C1, C2, . . . , Cm nad proměnnými Xi • stav = přiřazení hodnot proměnným {Xi = vi , Xj = vj , . . .} – konzistentní přiřazení neporušuje žádné z omezení Ci – úplné přiřazení zmiňuje každou proměnnou Xi • řešení = úplné konzistentní přiřazení hodnot proměnným někdy je ještě potřeba maximalizovat cílovou funkci ▶ výhody: • jednoduchý formální jazyk pro specifikaci problému • může využívat obecné heuristiky (ne jen specifické pro daný problém) Úvod do umělé inteligence 3/12 20 / 33 Problémy s omezujícími podmínkami Příklad – obarvení mapy Příklad – obarvení mapy Western Australia Northern Territory South Australia Queensland New South Wales Victoria Tasmania ▶ Proměnné WA, NT, Q, NSW , V , SA, T ▶ Domény Di = {červená, zelená, modrá} ▶ Omezení – sousedící oblasti musí mít různou barvu tj. pro každé dvě sousedící: WA ̸= NT nebo (WA, NT) ∈ {(červená, zelená), (červená, modrá), (zelená, modrá), . . .} Úvod do umělé inteligence 3/12 21 / 33 Problémy s omezujícími podmínkami Příklad – obarvení mapy Příklad – obarvení mapy – pokrač. Western Australia Northern Territory South Australia Queensland New South Wales Victoria Tasmania ▶ Řešení – konzistentní přiřazení všem proměnným: {WA = červená, NT = zelená, Q = červená, NSW = zelená, V = červená, SA = modrá, T = zelená} Úvod do umělé inteligence 3/12 22 / 33 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ř. StartJob1 + 5 ≤ StartJob3 – číselné lineární problémy jsou řešitelné, nelineární obecné řešení nemají ▶ spojité hodnoty proměnných • časté u reálných problémů • např. počáteční/koncový čas měření na Webbově 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 23 / 33 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 24 / 33 Problémy s omezujícími podmínkami Graf omezení Graf omezení Pro binární omezení: uzly = proměnné, hrany = reprezentují jednotlivá omezení Pro n-ární omezení: hypergraf: uzly = proměnné, uzly = omezení, hrany = použití proměnné v omezení Western Australia Northern Territory South Australia Queensland New South Wales Victoria Tasmania Victoria WA NT SA Q NSW V T Algoritmy pro řešení CSP využívají této grafové reprezentace omezení Úvod do umělé inteligence 3/12 25 / 33 CLP – Constraint Logic Programming CLP – Constraint Logic Programming X in 1..5 , Y in 2..8 , X+Y #= T: X in 1..5 Y in 2..8 T in 3..13 X in 1..5 , Y in 2..8 , X+Y #= T, labeling([X,Y,T]): T = 3 X = 1 Y = 2 ?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é aritmetická omezení . . . – rel. operátory #=, #\=, #<, #=<, #>, #>= – sum(Variables,RelOp,Suma) výroková omezení . . . #\ negace, #/\ konjunkce, #\/ disjunkce, #<==> ekvivalence kombinatorická omezení . . . all_distinct(List), global_cardinality(List, KeyCounts) hledá hodnoty podle omezení Úvod do umělé inteligence 3/12 26 / 33 CLP – Constraint Logic Programming Příklad – algebrogram Příklad – algebrogram S E N D + M O R E ---------- M O N E Y Proměnné {S, E, N, D, M, O, R, Y } Domény Di = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Omezení – S > 0, M > 0 – S ̸= E ̸= N ̸= D ̸= M ̸= O ̸= R ̸= Y – 1000 ∗ S + 100 ∗ E + 10 ∗ N + D + 1000 ∗ M + 100 ∗ O + 10 ∗ R + E = 10000 ∗ M + 1000 ∗ O + 100 ∗ N + 10 ∗ E + Y function MoreMoney([S,E,N,D,M,O,R,Y]) [S,E,N,D,M,O,R,Y] ins 0..9 S #> 0; M #> 0 all_distinct ([S,E,N,D,M,O,R,Y]) 1000∗S + 100∗E + 10∗N + D + 1000∗M + 100∗O + 10∗R + E #= 10000∗M + 1000∗O + 100∗N + 10∗E + Y labeling([S,E,N,D,M,O,R,Y]) MoreMoney([S,E,N,D,M,O,R,Y]): S = 9, E = 5, N = 6, D = 7, M = 1, O = 0, R = 8, Y = 2 Úvod do umělé inteligence 3/12 27 / 33 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ávácí strom dosahuje hloubky n (počet proměnných) a řešení se nachází v této hloubce (d = n) ⇒ je vhodné použít prohledávání do hloubky Úvod do umělé inteligence 3/12 28 / 33 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. |Di |n, větvení jde ovlivnit obecnými strategiemi ▶ 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 29 / 33 CLP – Constraint Logic Programming Příklad – problém N dam Příklad – problém N dam function Queens(N) L = [qy1, qy2, ..., qyN ] # seznam N proměnných L ins 1.. N for i ← 1 to N-1 do for j ← i+1 to N do NoThreat(L[i], L[j ] , j - i) labeling(L) function NoThreat(Y1, Y2, J) return Y1 #\= Y2 and Y1+J #\= Y2 and Y1-J #\= Y2 Queens(4): [2,4,1,3] [3,1,4,2] 1. definice proměnných a domén 2. definice omezení 3. hledání řešení Úvod do umělé inteligence 3/12 30 / 33 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 ▶ dopředná kontrola → udržovat seznam možných hodnot pro zbývající proměnné ▶ propagace omezení → navíc kontrolovat možné nekonzistence mezi zbývajícími proměnnými Úvod do umělé inteligence 3/12 31 / 33 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 ([ ff , 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 ▶ uspořádání řešení – bez uspořádání nebo min(X), max(X), . . . Úvod do umělé inteligence 3/12 32 / 33 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 Úvod do umělé inteligence 3/12 33 / 33