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/34 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í Můžeme rozložit na fáze: A B i : i i I2 l : i _____L _ 3 : i bit . ly/uuihanoi (Tower3 je zde cíl) 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 B B I I Úvod do umělé inteligence 3/12 2/34 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-l = 2(A,C,B) 1(A,B,C) n-l = 2(C,B,A) n -2 = 1(A,B,C) 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/34 Dekompozice a AND/OR grafy Příklad - Hanojské věže Příklad - Hanojské věž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/34 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/34 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— OR uzel via k AND uzly via I a— k^z a^l l^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/34 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 Úvod do umělé inteligence 3/12 7/34 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 =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 ► každý list stromu řešení T je cílovým uzlem v G 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č ► ► ► ► o v každé místnosti je/není špína počet stavů je 2 x 22 = 8 a kce ={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ů: ► 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/34 Příklad Dekompozice a AND/OR grafy Příklady - agent vysavač v nestálém prostředí pokrač. 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, (?2, ••• typu soupeř-je-na-tahu ► následně soupeřovy tahy vedou do stavů /?n, /?i2,... 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í 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 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 0 0 x 0 x x x 0 0 0 0 x x 0 0 0 x x x 0 x 0 0 0 x v v v A A A 0 x 0 0 x x x x 0 x x x x x 0 0 x x x 0 x 0 0 0 x v v v A A A 0 x 0 0 0 x 0 x x x 0 0 0 0 x x 0 0 x x x x 0 x x x x x Úvod do umělé inteligence 3/12 12 / 34 Prohledávání AND/OR grafů Prohledávání AND/OR grafu do hloubky Prohledávání AND/OR grafu do hloubky QR-uzel ) function AndOrDepthFirstSearch(problem, path 4— []) # 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 foreach child in problem.moves(current-node) do if child G path then return "failure" result = AndOrDepthFirstSearch(pro£>/em, path + [c/7/7c/|) if result = "failure" then return "failure" results . append (result) return [ child] + [ results ] AndOrDepthFirstSearch (problem): b O \ h Úvod do umělé inteligence 3/12 13 / 34 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 , [(NaslUzell.Cenal), (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 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) F(/V) = cena(M, N)+{ min/(F(A//)), pro OR-uzel N J2íf(ní), 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 / 34 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 15 / 34 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 16 / 34 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 17 / 34 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-Z3 —»> ('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 V ('and3, [('X-V',0), (3Y-Z\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 18 / 34 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 ľ ,11), [[('l-z',6), 7- [[('l-z',6), ('u-z',6), ('y-z',5), ('z-z',3)], [('a-1',5), ('c-1',5), ('1-1',2)]]] AND-uzel Úvod do umělé inteligence 3/12 19 / 34 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í Q, C2,..., Cm nad proměnnými X, • stav = přiřazení hodnot proměnným {X/ = v-nXj = 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 ► 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 20 / 34 Príklad Problémy s omezujícími podmínkami Příklad - obarvení mapy - obarvení mapy ► 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 (1/1/4, NT) G {(červená, zelená), (červená, modrá), (zelená, modrá) Úvod do umělé inteligence 3/12 21 / 34 Problémy s omezujícími podmínkami Příklad - obarvení mapy Příklad - obarvení mapy - pokrač. Australia Northern Territory New South Wales Tasmania v ► Řešení - konzistentní přiřazení všem proměnným: { WA = červená, NT = ená, Q = červená, NSW = zelená, V = červená SA = modrá, T = zelená} Úvod do umělé inteligence 3/12 22 / 34 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 < StartJobi - čí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 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 23 / 34 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 / 34 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: 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í 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]): T= 3 X = 1 Y= 2 hledá hodnoty podle omezení j Úvod do umělé inteligence 3/12 26 / 34 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 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 * O + 100 *A/ + 10 * E + Y function MoreMoney([S,E,A/,D,M,0,R,Y\) [S,E,N,D,M,0,R,Y\ ins 0..9 S#> 0; M#> 0 aILdistinct ([S, E, A/, D, M, O,/?, V]) 1000*S + 100*E + 10* N + D + 1000*M + 100*O + 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, 0,R,Y\)\ S = 9, E = 5, A/ = 6, D = 7, M = 1, O = 0, /? = 8, Y =2 Úvod do umělé inteligence 3/12 28 / 34 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 29 / 34 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 ► 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 30 / 34 CLP - Constraint Logic Programming Příklad - problém N dam Příklad - problém N dam function Queens (A/) ^- = [*7yl' Qy2» ■ ■ ■» Qyl\l] # seznam N proměnných L ins 1.. A/ f 1. definice proměnných a domén for / <- 1 to A/1 do 1- for j ^— /+1 to A/ do ^^2. definice omezení NoThreat(í_[/], /.[/], j-/) labeling(/_) .....> --1 3. hledaní reseni J function NoThreat(Vi, Y2, J) return Vi #\= Y2 and Yi+J #\= Y2 and YW #\= Y2 Queens(4): [2,4,1,3] [3,1,4,2] Úvod do umělé inteligence 3/12 31 / 34 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 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 ► uspořádání řešení - bez uspořádání nebo min(X), max(X), . .. Úvod do umělé inteligence 3/12 33 / 34 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 34 / 34