Unformatted text preview:

Introduction to PrologNegation as FailureNegation-by-failure can be non-logicalQuestionNot a Good Idea!How to fix it?Clauses and DatabasesSlide 8Negation and RepresentationConstraint Satisfaction ProblemExample: Map-coloringMapColoring in PrologSatisfiability as CSPBinary ConstraintsDifferent constraint systemsBinary Constraint GraphMatrix Representation for Binary ConstraintsThe programming paradigmRandom Generation of Test ProblemsN-queens Example (4 in our case)Example: SchedulingExample: Job shop schedulingExample: Manpower planningDigital Circuits- full adder CLP(B)Digital Circuits- full adder CLP(B)Black-box vs Glass-box solversBackTracking Algorithm: Recursive formulationControlling BacktrackingControl BacktrackingBacktracking in 4-queensForward CheckingForward Checking in 4-queensArc-ConsistencyCost of Arc-Consistency CheckingAC-3 algorithm: MackworthAC3 ExampleAC3 in Backtrack AlgorithmIntelligent BacktrackingLocal Search for CSPSome Hot Topics in Constraint TechnologyMore Hot Topics1Introduction to Prolog•Useful references:–Clocksin, W.F. and Mellish, C.S., Programming in Prolog: Using the ISO Standard (5th edition), 2003. –Bratko, I., Prolog Programming for Artificial Intelligence (3rd edition), 2001. –Sterling, L. and Shapiro, E., The Art of Prolog (Second edition), 1994. –GNU Prolog Manual, http://pauillac.inria.fr/~diaz/gnu-prolog/manual/2Negation as FailureUsing not will not help you. Do not try to remedy this by defining:guilty(X) :- not(innocent(X)).This is useless, and makes matters even worse:?- guilty(st_francis).yesIt is one thing to show that st_francis cannot be demonstrated to be innocent. But it is quite another thing to incorrectly show that he is guilty.3Negation-by-failure can be non-logicalSome disturbing behaviour even more subtle than the innocent/guilty problem, and can lead to some extremely obscure programming errors. Here is a restaurant database:good_standard(goedels).good_standard(hilberts).expensive(goedels).reasonable(R) :- not(expensive(R)).Consider the following dialogue:?- good_standard(X), reasonable(X).X = hilbertsBut if we ask the logically equivalent question:?- reasonable(X), good_standard(X).no.4QuestionWhy do we get different answers for what seem to be logically equivalent queries?The difference between the questions is as follows.In the first question, the variable X is always instantiated when reasonable(X) is executed.In the second question, X is not instantiated when reasonable(X) is executed.The semantics of reasonable(X) differ depending on whether its argument is instantiated.5Not a Good Idea!It is bad practice to write programs that destroy the correspondence between the logical and procedural meaning of a program without any good reason for doing so.Negation-by-failure does not correspond to logical negation, and so requires special care.6How to fix it?One way is to specify that negation is undefined whenever an attempt is made to negate a non-ground formula.A formula is ‘ground’ if is has no unbound variables.Some Prolog systems issue a run-time exception if you try to negate a non-ground goal.7Clauses and DatabasesIn a relational database, relations are regarded as tables, in which each element of an n-ary relation is stored as a row of the table having n columns.supplierjones chair red 10smith desk black 50Using clauses, a table can be represented by a set of unit clauses. An n-ary relation is named by an n-ary predicate symbol.supplier(jones, chair, red, 10).supplier(smith, desk, black, 50).8Clauses and DatabasesAdvantages of using clauses:1. Rules as well as facts can coexist in the description of a relation.2. Recursive definitions are allowed.3. Multiple answers to the same query are allowed.4. There is no role distinction between input and output.5. Inference takes place automatically.9Negation and RepresentationLike databases, clauses cannot represent negative information. Only true instances are represented.The battle of Waterloo occurred in 1815.How can we show that the battle of Waterloo did not take place in 1923? The database cannot tell us when something is not the case, unless we do one of the following:1. ‘Complete’ the database by adding clauses to specify the battle didn’t occur in 1814, 1813, 1812, ..., 1816, 1817, 1818,...2. Add another clause saying the battle did not take place in another year (the battle occurred in and only in 1815).3. Make the ‘closed world assumption’, implemented by ‘negation by failure’.10Constraint Satisfaction Problem•Finite set of variables: X1,…Xn•Variable Xi has values in domain Di.•Constraints C1…Cm. A constraint specifies legal combinations of the values.•Assignment: selection of values for all variables.•Consistent: assignment satisfies all constraints.11Example: Map-coloring Domain: colors = {red, blue, green} Variables: X1, X2, X3, X4; domain colors Xi is color of country Ci. Constraints:C1 touches C2 … X1 =/= X2C1 touches C3 … X1 =/= X3C2 touches C3 … X2 =/= X3C2 touches C4 … X2 =/= X4C3 touches C4 … X3 =/= X412MapColoring in Prolog•color(r). •color(g). •color(b).•colormap(C1,C2,C3,C4):-color(C1),color(C2),color(C3), C1=\=C2,C1=\=C3, C2=\=C3,C2=\=C4,C3=\=C4.•?- colormap(X,Y,Z,U).–X = r, Y = g, Z = b, U = r.•Is that it. Yes! Turn on trace.13Satisfiability as CSP•Domain: { true, false }•Variables: Propositional variables•Constraints: clauses•sat(true). % base case•sat(not(false)). % base case•sat(or(X,Y)):- sat(X).•sat(or(X,Y)):-sat(Y).•sat(and(X,Y)):-sat(X),sat(Y).•test1(X,Y):- sat(and(not(X),X)).•test2(X,Y):- sat(and(X,not(Y))).14Binary Constraints•Unary constraints: involve only one variable–Means that we can simply re-write the domains•In the problem specification to remove the constraint•Binary constraints: involve two variables–Binary CSPs: all constraints are binary–Much researched•All CSPs can be written as binary CSPs (no details here)•Nice graphical and Matrix representations–Representative of CSPs in general15Different constraint systems•Real/rational constraints: CLP(R), CLP(Q)CLP(R), Sicstus Prolog, CHIP•Finite domains constraints: CLP(FD)Sicstus Prolog, CHIP•Boolean constraints: CLP(B)Sicstus Prolog, CHIP•Interval constraints: CLP(I)CLP(BNR), Numerica, Prolog IV16Binary Constraint GraphX1X3X4X5X2{(1,3),(2,4),(7,6)}{(5,7),(2,2)}{(3,7)}Nodes are VariablesEdges are constraints17Matrix Representationfor Binary ConstraintsC 1 2


View Full Document
Download Lecture Note
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Note and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Note 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?