Constraint Logic Programming CLP 1 Prolog and generate and test paradigma Example: Magic Square Example 1: Find a mapping of numerals 0 to 9 on the variables A, B, ...I such that the totals in all rows and columns are the same (the corresponding sum has to be 15). square1([A,B,C,D,E,F,G,H,I]):generate1([A,B,C,D,E,F,G,H,I]), test1([A,B,C,D,E,F,G,H,I]). 2 / 23 A B C 2 7 6 D E F 9 5 1 G H I 4 3 8 Umělá inteligence I. Naive solution 1 square1([A,B,C,D,E,F,G,H,I]):- generate1([A,B,C,D,E,F,G,H,I]), test1([A,B,C,D,E,F,G,H,I]). generate1(X):- n_list1(X). A B C n_list1([]). D E F G H I n_list1([H|T]):- numeral(H), n_list1(T). numeral(1). numeral(6). numeral(2). numeral(7). numeral(3). numeral(8). numeral(4). numeral(9). numeral(5). test1([A,B,C,D,E,F,G,H,I]):- all_different([A,B,C,D,E,F,G,H,I]), A+B+C =:= 15, D+E+F =:= 15, G+H+I =:= 15,A+D+G =:= 15, B+E+H =:= 15, C+F+I =:= 15,C+E+G =:= 15, A+E+I =:= 15. all_different([]). all_different([H|T]):- not_in(H,T), all_different(T). not_in(_,[]). not_in(H,[HH|T]):- H=\=HH, not_in(H,T). 3 / 23 Umělá inteligence I. Criticism + solution 2 Problems: generate1 creates numerous lists of candidate solutions, which do not meet even the basic condition (no repetition of numerals). Number of calls to the predicate numeral is 99 = 387 420 489. The first solution has been found after 85.66 s (P4, 2.8GHz). How to improve the solution? More efficient predicate generate2 limits the repetition of numerals already during the process of generating the candidate solution. square2([A,B,C,D,E,F,G,H,I]):generate2([A,B,C,D,E,F,G,H,I]), test2([A,B,C,D,E,F,G,H,I]). generate2(X):- n_list2(X). n_list2([]). n_list2([H|T]):- n_list2(T), numeral(H), not_in(H,T). test2([A,B,C,D,E,F,G,H,I]):A+B+C =:= 15,D+E+F =:= 15,G+H+I =:= 15, B+E+H =:= 15,C+F+I =:= 15,C+E+G =:= 15, 4 / 23 A+D+G =:= 15, A+E+I =:= 15. Umělá inteligence I. Solution 3 square2 program is much quicker predicate numeral is called 5 611 770 times only the first solution has been found after 0.53 s Further improvement can be achieved by interleaving the tests which can be checked with the process of generation of the candidate solution. Heuristics: start setting the values to the variables which appear most often in the considered totals. square3([A,B,C,D,E,F,G,H,I]):gentest3(E,[]), gentest3(A,[E]), gentest3(I,[E,A]), A+E+I gentest3(C,[E,A,I]), gentest3(G,[E,A,I,C]), G+E+C gentest3(B,[E,A,I,C,G]), A+B+C gentest3(H,[E,A,I,C,G,B]), B+E+H gentest3(D,[E,A,I,C,G,B,H]), A+D+G gentest3(F,[E,A,I,C,G,B,H,D]),D+E+F gentest3(D,L) :- numeral(D), not_in(D,L). =:= 15, =:= =:= =:= =:= =:= A B C D E F G H I 15, 15, 15, G+H+I =:= 15, 15, 15, C+F+I =:= 15. Now, predicate numeral is called 6498 times only and the first solution has been immediately, ie. in 0.00 s (bellow resolving power). Next solutions in 0.02 s 5 / 23 Umělá inteligence I. Solution 4 Diversity of used numerals can be ensured if there is available the list of those numerals which have not been used, yet : square4([A,B,C,D,E,F,G,H,I]):- A B C choose(A,R1,R2), D E F choose(I,R2,R3), A+E+I =:= 15, G H I choose(E,[1,2,3,4,5,6,7,8,9],R1), choose(C,R3,R4), choose(G,R4,R5), G+E+C =:= 15, choose(B,R5,R6), A+B+C =:= 15, choose(H,R6,R7), B+E+H =:= 15, G+H+I =:= 15, choose(D,R7,R8), A+D+G =:= 15, choose(F,R8,R9), D+E+F =:= 15, C+F+I =:= 15. % choose(Member,Source_list,What_remains_from_Source_list). choose(P,[P|T],T). choose(P,[H|T],[H|TT]):- choose(P,T,TT). Number of calls of the predicate numeral is reduced to 3361. The first solution is found in 0.00 s, the same for the further solutions. 6 / 23 Umělá inteligence I. Alternatives to „generate and test paradigma“ Solution based on “test and generate paradigma” The gradual increase of the solution efficiency is due to increased involvement of problem constraints in the process of generation of candidate solutions. Can it be ensured by changing the sequence of predicates in the original solution? search(Solution):- test(Solution), generate(Solution). No! But we can get close using the schema: provide constraints and generate The idea is to ensure automatic interruption of the generation as soon as any constrain is violated This cannot be achieved in standard Prolog, because the predicates for testing (e.g. arithm. operations) require that all their arguments are grounded grounding is ensured in the predicate generate Additional functionality is needed!! Some implementations of Prolog offer suspension of goals by a built-in predicate constrain(Variable, Goal) if Variable is grounded, the system is asked to solve the Goal if Variable is free (not grounded), Goal is suspended (frozen, delayed) until the Variable is grounded 7 / 23 Umělá inteligence I. Solution based on suspension square_c(L) :- test_c(L),n_list1(L). test_c([A,B,C,D,E,F,G,H,I]):- all_different ([A,B,C,D,E,F,G,H,I]), total(A,B,C),total(D,E,F),total(G,H,I),total(A,D,G), total(B,E,H),total(C,F,I),total(A,E,I),total(C,E,G). total(X,Y,Z):- constrain(X,constrain(Y,constrain(Z,X+Y+Z=:=15))). n_list1([]). n_list1([H|T]):- numeral(H), n_list1(T). all_different_c([]). all_different_c([H|T]):- not_in_c(H,T), all_different(T). not_in_c(_,[]). not_in_c(H,[HH|T]):- constrain(H,constrain(HH, H=\=HH)), not_in_c(H,T). Number of calls of the predicate numeral is reduced to 2377. 8 / 23 Umělá inteligence I. Prolog and unification as its basic operation Advantages of unification -uniform manipulation with all objects of a language - programs are understandable and predicates are invertible - it can be applied to syntacticaly related objekts Problem appears as soon as we need to compare objekts which have the same meaning (semantics) but their syntax differs - e.g. the query ?- 2+3 = 5. fails in standard Prolog, because the two expressions cannot be unified. Partial solution of standard Prolog: introduction of extralogical operator is -is fails whenever it is applied to exprssions with free variables, e.g. ?- 5 is 3 + X. fails in standard Prolog. Constraint Logic Programming (CLP) tries to resolve both upper mentioned problems: “test and generate programming paradigma” and unification. In CLP, unification is replaced by a decision procedure, which takes into account both syntax and semantics of considered objects. 9 / 23 Umělá inteligence I. CLP CLP is not a pure enhancement of standard Prolog, but its generalization. Constraints are expressed using a fixed set of operators, e.g. from the domain of arithmetics (comparison of linear arithmetic expressions), set theory (finite domains). Each CLP system specifies a set of predicates, which are suspended automaticaly, whenever their arguments contain free (non-grounded) variables. The resulting CLP program ensures a direct solution based on “constrain and generate paradigma” without any additional auxiliary predicates. Constraint solving - two approaches incremental linear methods = the system treats the set C of all constraints requested up to now as a whole; whenever a new constraint is added to C the resulting set is tested for consistency (and backtracking is started as soon as inconsistency appears). domain technologies = the used variables can be given restrictions concerning their finite domain using the operator :: (e.g. X :: 1..9). Additional functionality of the system is on-line propagation of domain constraints between all mutually related variables. Backtracking is started whenever a domain of any considered variable is empty. 10 / 23 Umělá inteligence I. CLP system i e ECL PS ECLiPSe provides automated suspension of the following predicates of arithmetics Real numbers: <, > >=,=<, =:=, =\= Racional numbers: $=, $<, … Integers: #=, ## (různý), #<, … [-10 000 000, 10 000 000] Efficient deterministic methods (simplex m., Gaus elimination, etc.) are used to solve the set of considered constraints 11 / 23 Umělá inteligence I. Beatles and spiders Suppose, you get a closed box with beatles and spiders. You know that all of them together have 34 legs. How many beatles you have? insects(Beatles, Spiders,Legs):- Beatles #>0,Spiders#>0, 8*Spiders + 6* Beatles #= Legs. ?- insects(B, S,34). The system adds the domain info B:: 0..10000000,S:: 0..10 000 000 0 + 6*B <= 8*S + 6*B (=34) <= 8*107 + 6*B, thus 6*B <= 34 and 0<= B <6 8*S + 0 <= 8*S + 6*B (=34) <= 8*S +6*107, thus 8*S <= 34 and 0<= S <5 … solution Beatles=3, Spiders=2 ?- insects(Beatles, Spiders,46). Spiders= Spiders{[2..5]}, Beatles={[1..5]} Delayed goals: -46 + 8* Spiders{[2..5]}+6* Beatles={[1..5]}#=0 12 / 23 Umělá inteligence I. Magic square in ECLiPSe test5(L):- L=[A,B,C,D,E,F,G,H,I], L::1..9, alldifferent(L), A+B+C #= 15, D+E+F #= 15, G+H+I #= 15, A+D+G #= 15, B+E+H #= 15, C+F+I #= 15, C+E+G #= 15, A+E+I #= 15. generate5([]). generate5([H|T]):- indomain(H), generate5(T). 13 / 23 Umělá inteligence I. optimize(+Objective,-Cost) This build-in predicate (in eplex library) calls the external solver's optimizer and succeeds if it finds an optimum for the Objective function. In this case the problem variables get instantiated to the solution values, and Cost gets bound to the cost of this solution. Note that this will find at most one solution, ie. you won't get alternative optima on backtracking. [eclipse1]: [eclipse2]: Y = 2.0 X=2 C = 2.0 yes. 14 / 23 eplex:(X+Y >= 3), eplex:(X-Y =:= 0), optimize(min(X), C). Y = 1.5 X = 1.5 C = 1.5 yes. integers([X]), eplex:(X+Y >= 3), eplex:(X-Y =:= 0), optimize(min(X), C). Umělá inteligence I. Transportation problem Costs of transport Customer 2 Customer 3 Daily Producer1 5 1 1 4 Producer2 2 6 9 6 3 5 2 10 Customer’s requirements Customer 1 production optim([X11,X12,X13,X21,X22,X23], Costs) :- integers ([X11,X12,X13,X21,X22,X23,Costs]), eplex:( X11 >=0,X12 >=0,X13 >=0, X21 >=0,X22 >=0,X23 >=0), eplex:( X11+X21 >=3, X12+X22 >=5, X13+X23 >=2), eplex:( X11 + X12 +X13 <=4, X21 + X22 + X23 <=6), Costs = 5*X11 +X12 + X13 + 2*X21 + 6*X22, +9*X23, optimize(min(Costs),C). X = [0,2,2,3,3,0], C =28. 15 / 23 Umělá inteligence I. On-line Guide to Constraint Programming, Roman Barták, 2001. http://kti.ms.mff.cuni.cz/~bartak/constraints/ The ECLiPSe Constraint Logic Programming System, Imperial College London, 2001. http://www.icparc.ic.ac.uk/eclipse 16 / 23 Umělá inteligence I.

1/--страниц