Constraint Satisfaction Problems & Constraint Programming Representing Knowledge with Constraints x1 x2 x6 x3 x5 KNOWLEDGE REPRESENTATION & REASONING x4 1 KR&R for Combinatorial Problems Many, many practical applications Resource allocation, scheduling, routing, frequency Sports scheduling example assignment, timetabling, vehicle routing, etc. In sports league scheduling we try to build the schedule of matches between teams (e.g. football teams). There are Properties various constraints: Computationally difficult Each team must play each other exactly twice (once home once away) Technical and modeling and expertise needed Experimental in nature No team can play more than two consecutive home or away matches Important ($$$) in practice The number of times that a team plays two consecutive Many solution techniques home or away matches must be minimum Teams that use the same stadium cannot play home games (Mixed) integer programming at the same date Specialized methods Games between top teams must occur at certain dates (due Local search/metaheuristics to TV coverage) Constraint programming Etc. KNOWLEDGE REPRESENTATION & REASONING 2 Quotations “Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it.” Eugene C. Freuder, Constraints, April 1997 “Were you to ask me which programming paradigm is likely to gain most in commercial significance over the next 5 years I’d have to pick Constraint Programming, even though it’s perhaps currently one of the least known and understood.” Dick Pountain, BYTE, February 1995 KNOWLEDGE REPRESENTATION & REASONING 3 Constraint Programming Constraint programming is the continuous dream of programming x1 State the constraints The solver will find a solution Knowledge representation with constraints is the preferred model in many domains Scheduling Vehicle routing Resource allocation Temporal Reasoning … KNOWLEDGE REPRESENTATION & REASONING x2 x6 x3 x5 x4 4 What is Constraint Programming? Broad Answer: Programming where the use of constraints plays a central role alternative to logic programming, functional programming, object- oriented programming there are constraint programming languages that support this What is a constraint? Let X1,X2, . . . ,Xn be a finite sequence of variables, each associated with a domain, D1,D2, . . . ,Dn. A constraint on X1,X2, . . . ,Xn is a relation D1 × D2 × · · · × Dn can be defined explicitly/extensionally or implicitly/intentionally KNOWLEDGE REPRESENTATION & REASONING 5 What is Constraint Programming? Narrow Answer: A more specific answer is obtained by programming with constraints in a particular manner. Constraint programming involves solving a problem by: Modelling: Formulate the problem as a finite set of constraints (a Constraint Satisfaction Problem). Solving: Solve the CSP, perhaps by using a constraint programming language Mapping: Map the solution to the CSP to a solution to the original problem KNOWLEDGE REPRESENTATION & REASONING 6 What is a Constraint? What is a constraint? Let X1,X2, . . . ,Xn be a finite sequence of variables, each associated with a domain, D1,D2, . . . ,Dn. A constraint on X1,X2, . . . ,Xn is a relation D1 × D2 × · · · × Dn can be defined explicitly/extensionally or implicitly/intentionally There are constraints everywhere! explicit (0,1,0) (1,0,0) (1,1,0) (1,1,1) implicit x+y>z KNOWLEDGE REPRESENTATION & REASONING Room Myrto is occupied from 12:00 until 15:00 Traffic in the web < 100 Gbytes/sec Salary < 15k Euro Train 1 must leave 20 minutes before train 2 arrives Exams for 1st semester must be at least 2 days apart 7 Constraint Programming (CP) Began in late 1970s – early 1980s from AI world III (Marseilles, France) CLP(R) CHIP (ECRC, Germany) These days… Prolog Software Engineering AI Application areas CP Scheduling, sequencing, resource and personnel allocation, etc. etc. Active research area Specialized conferences (CP, CP/AI-OR, …) Journal (Constraints) Companies (ILOG, COSYTEC,..) KNOWLEDGE REPRESENTATION & REASONING Logic Programming OR Discrete Mathematics Let’s look at this 8 Constraint Programming Two main contributions A new solving approach to combinatorial problems AI search methods and heuristics Orthogonal and complementary to standard OR methods A new language for representing combinatorial problems Rich language for constraints Much closer to the real problem than OR Language for search procedures Easily extensible KNOWLEDGE REPRESENTATION & REASONING 9 The Origins Artificial Intelligence Scene Operations Research Interactive Graphics Sketchpad (Sutherland) ThingLab (Borning) Labelling (Waltz) NP-hard combinatorial problems Logic Programming unification --> constraint solving Let’s look at this KNOWLEDGE REPRESENTATION & REASONING 10 Integer Programming (IP) Consider the manufacture of television sets. A linear programming model might give a production plan of 205.7 sets per week. No trouble stating that production should be 205 sets per week (or even ``roughly 200 sets per week''). Suppose we were buying warehouses to store finished goods. A model that suggests we buy 0.7 warehouse at some location and 0.6 somewhere else would be of little value. Warehouses come in integer quantities, and we would like our model to reflect that fact. This integrality restriction has far reaching effects. Modeling with integer variables has turned out to be useful far beyond restrictions to integral production quantities. With integer variables, one can model logical requirements, fixed costs, sequencing and scheduling requirements, and many other problem aspects. KNOWLEDGE REPRESENTATION & REASONING 11 Integer Programming (IP) The trouble with all this modeling power, however, is that problems with as few as 40 variables can be beyond the abilities of even the most sophisticated computers. Most real problems with more than 100 or so variables are not possible to solve unless they show specific exploitable structure. Despite the possibility (or even likelihood) of enormous computing times, there are methods that can be applied to solving integer programs. An IP problem in which all variables are required to be integer is called a pure integer programming problem. If some variables are restricted to be integer and some are not then the problem is a mixed integer programming problem (MIP). The case where the integer variables are restricted to be 0 or 1 is called pure (mixed) 0-1 programming problems or pure (mixed) binary integer programming problems. KNOWLEDGE REPRESENTATION & REASONING 12 Relationship to Linear Programming Given an integer program There is an associated linear program called the linear relaxation formed by dropping the integrality restrictions: Since (LR) is less constrained than (IP), the following are immediate: If (IP) is a minimization, the optimal objective value for (LR) is less than or equal to the optimal objective for (IP). If (IP) is a maximization, the optimal objective value for (LR) is greater than or equal to that of (IP). If (LR) is infeasible, then so is (IP). Solving (LR) does give some information: it gives a bound on the optimal value, and, if we are lucky, may give the optimal solution to IP. But for some problems it is very difficult to even get a feasible solution! KNOWLEDGE REPRESENTATION & REASONING 13 Branch and Bound We will explain branch and bound by using this model: Maximize 8X1+ 11X2 + 6X3 + 4X4 Subject to 5X1+ 7X2 + 4X3 + 3X4 ≤ 14 Xj {0,1} j = 1,…4. The linear relaxation solution is X1=1, X2 = 1,X3 = 0.5, X4 =0 with a value of 22. We know that no integer solution will have value more than 22. Unfortunately, since X3 is not integer, we do not have an integer solution yet. We want to force X3 to be integer. To do so, we branch on X3, creating two new problems. In one, we will add the constraint X3=0. In the other, we add the constraint X3= 1. Note that any optimal solution to the overall problem must be feasible to one of the subproblems. If we solve the linear relaxations of the subproblems, we get the following solutions: X3 = 0: objective 21.65, X1 = 1, X2 = 1, X3 = 0 ,X4=0.677; X3 = 1: objective 21.85, X1 = 1, X2 = 0.714, X3 = 1, X4 = 0. At this point we know that the optimal integer solution is no more than 21.85, but we still do not have any feasible integer solution. So, we will take a subproblem and branch on one of its variables. In general, we will choose the subproblem as follows: We will choose an active subproblem, which so far only means one we have not chosen before, and we will choose the subproblem with the highest solution value (for maximization) (lowest for minimization). In this case, we will choose the subproblem with X3 = 1, and branch on X2. After solving the resulting subproblems, we have the branch and bound tree in Figure 2. Figure 1 Figure 2 KNOWLEDGE REPRESENTATION & REASONING 14 Branch and Bound The solutions are: X3 = 1,X2 = 0: objective 18, X1 = 1, X2=0, X3=1,X4=1; X3 = 1, X2=1: objective 21.8, X1 = 0.6, X2=1, X3=1, X4=0. We now have a feasible integer solution with value 18. Furthermore, since the X3=1, X2=0 problem gave an integer solution, no further branching on that problem is necessary. It is not active due to integrality of solution. There are still active subproblems that might give values more than 18. Using our rules, we will branch on problem X3=1, X2=1 by branching on X1to get Figure 3. The solutions are: X3=1, X2=1, X1=0: objective 21, X1=0, X2=1, X3= 1, X4=1 X3 =1 , X2=1, X1=1: infeasible. Our best integer solution now has value 21. The subproblem that generates that is not active due to integrality of solution. The other subproblem generated is not active due to infeasibility. There is still a subproblem that is active. It is the subproblem with solution value 21.65. There is no better integer solution for this subproblem than 21. But we already have a solution with value 21. It is not useful to search for another such solution. Therefore, we can mark this subproblem it not active. There are no longer any active subproblems, so the optimal solution value is 21. KNOWLEDGE REPRESENTATION & REASONING Figure 3 15 Constraint Satisfaction Problems At the core of Constraint Programming KNOWLEDGE REPRESENTATION & REASONING 16 What is a Constraint Satisfaction Problem? A constraint satisfaction problem (CSP) is defined by: A set of variables X1,…,Xn Each variable Χi has a domain Di with its possible values A set of constraints C1,…,Cm Each constraint involves a subset of the variables it specifies the allowed combinations of values for this subset 1 A k-ary constraint C on a set of variables X1,…,Xk is a subset of the Cartesian product D1 x…x Dk {0,…,5} The set of variables in a constraint is called the constraint scope x x2 {0,…,3} Binary and non-binary (or n-ary) constraint satisfaction problems KNOWLEDGE REPRESENTATION & REASONING 17 Constraint Satisfaction Problems Solution of a CSP Assignment of a value to each variable so that all constraints are satisfied Goals: Find one solution (feasibility problem) Find all solutions Find a solution that maximizes (or minimizes) some quantity constraint optimization problem Find an approximate “solution” All these tasks are NP-hard! (except perhaps one of them) KNOWLEDGE REPRESENTATION & REASONING 18 Constraint Graphs & Hypergraphs x1 x2 x1 x2 x6 x3 x6 x4 x5 x5 x4 variables – nodes binary constraints – edges the label of an edge specifies the constraint KNOWLEDGE REPRESENTATION & REASONING x3 variables – nodes n-ary constraints – hyperedges 19 Example – Map Coloring We want to color each area in the map with a different color We have three colors red, green, blue KNOWLEDGE REPRESENTATION & REASONING 20 Example – Map Coloring Formal Definition: Variables Domains (the same for all variables) WA, NT, SA, Q, NSW, V, T {red, green, blue} Constraints C(WA,NT) = {(red, green), (red, blue), (green, red), (green, blue), (blue,red), (blue, green)} C(WA,SA) = … KNOWLEDGE REPRESENTATION & REASONING 21 Constraint Graph NT Q WA SA All constraints are binary NSW Two unconnected components V T KNOWLEDGE REPRESENTATION & REASONING 22 Example – 8 Queens problem We want to place 8 queens on the chessboard so they can’t attack each other KNOWLEDGE REPRESENTATION & REASONING 23 Example– 8 Queens problem Formal Definition: Variables Each variable Xi (i=1,…,8) represents the column where there is the i-th queen (i.e. the queen in the i-th row) Domains If the columns are represented by numbers from 1 to 8 then the domain of each variable Xi is Di = {1,2,…,8} KNOWLEDGE REPRESENTATION & REASONING 24 Παράδειγμα – 8 Queens problem Constraints There is a binary constraint C(Xi, Xj) for each pair of variables. These constraints can be defined as follows: For all variables Xi and Xj , Xi Xj For all variables Xi and Xj , if Xi = a and Xj = b then i – j a – b and i – j b – a KNOWLEDGE REPRESENTATION & REASONING 25 Example – Cryptoarithmetics T WO +T WO FO U R F T X3 KNOWLEDGE REPRESENTATION & REASONING U X2 W R O X1 26 Example – Cryptoarithmetics Formal Definition: Variables and Domains F, T, U, W, R, O {0,1,2,3,4,5,6,7,8,9} X1, X2, X3 {0,1} Constraints alldifferent(F, T, U, W, R, O) O + O = R + 10 X1 X1 + W + W = U + 10 X2 X2 + T + T = O + 10 X3 X3 = F KNOWLEDGE REPRESENTATION & REASONING T WO +T WO FO U R 27 Example: Crossword puzzle 1 2 3 4 5 KNOWLEDGE REPRESENTATION & REASONING 28 Crossword puzzle as a CSP Variables and their domains X1 is 1 across X2 is 2 down X3 is 3 down X4 is 4 across X5 is 5 across D1 consists of all 5-letter words in the dictionary D2 consists of all 4-letter words in the dictionary D3 consists of all 3-letter words in the dictionary D4 consists of all 4-letter words in the dictionary D5 consists of all 2-letter words in the dictionary Constraints (implicit/intensional) C12 is “the 3rd letter of X1 must equal the 1st letter of X2” C13 is “the 5th letter of X1 must equal the 1st letter of X3” C24 is … C25 is … C34 is ... KNOWLEDGE REPRESENTATION & REASONING 29 Crossword puzzle as a CSP 1 2 3 4 Variables: X1 X2 X3 X4 X5 5 Domains: D1 = {astar, happy, hello, hoses} D2 = {live, load, peal, peel, save, talk} D3 = {ant, oak, old} D4 = {live, load, peal, peel, save, talk} KNOWLEDGE REPRESENTATION & REASONING X1 X2 X3 X4 Constraints (explicit/extensional): C12 = {(astar, talk), (happy, peal), (happy, peel), (hello, live) …} C13 = ... 30 Real Constraint Satisfaction Problems puzzles (not really practical applications, but they are fun) N-queens, Zebra (five house puzzle), crossword puzzle, cryptoarithmetics (SEND+MORE=MONEY), mastermind graph coloring analysis and synthesis of analog circuits option trading analysis cutting stock DNA sequencing crew scheduling chemical hypothetical reasoning warehouse location patient treatment scheduling airport counter allocation (Cathay Pacific Airways Ltd) crew rostering problem (Italian Railway Company) well activity scheduling (Saga Petroleum a.s.) KNOWLEDGE REPRESENTATION & REASONING 31 Early Commercial Applications (90s) Lufthansa: Short-term staff planning. Hongkong Container Harbor: Resource planning. Renault: Short-term production planning. Nokia: Software configuration for mobile phones. Airbus: Cabin layout. Siemens: Circuit verification. Caisse d’epargne: Portfolio management. KNOWLEDGE REPRESENTATION & REASONING 32 Applications in Research Artificial Intelligence Machine Vision Natural Language Understanding Temporal and Spatial Reasoning Theorem Proving Qualitative Reasoning Robotics Agents Planning Timetabling Scheduling Vehicle Routing Resource allocation Frequency Assignment KNOWLEDGE REPRESENTATION & REASONING 33 Applications in Research Computer Science: Molecular Biology, Biochemestry, Bioinformatics: Parsing Medicine: Scheduling, Stock Investment Planning Linguistics: Protein Folding, Genomic Sequencing Economics: Program Analysis, Robotics, Agents Decision Support Physics: System Modeling KNOWLEDGE REPRESENTATION & REASONING 34 CSP Technology : Practical & Successful Constraint satisfaction technology is one of the most successful examples of practical AI There are many successful companies which build and trade CSP technology ILOG Cosytec Parc Technologies i2 Technologies IQ Software … KNOWLEDGE REPRESENTATION & REASONING 35 CSP Technology : Practical & Successful! AKL FSQP/CFSQP ALE Goedel Amulet and Garnet GNU-Prolog ICE InC++ library B-Prolog IF/Prolog Bertrand Brandeis Interval Arithmetic Constraint ILOG Numerica, ILOG Schedule, ILOG Solver Interval Solver for Microsoft Excel Solver JSolver RISC-CLP(Real) CHIP LIFE SEL CIAL MAC ICStus CLAIRE Newton Screamer CLP Nicolog StarFLIP++ CONFLEX' Omega Steeles constraint system' Oz CPLEX TOY ProFIT Toupie Cassowary Prolog III, Prolog IV Trilogy Contax Pulsar Unicalc Cooldraw, Deltablue, Skyblue, QUAD-CLP(R) cu-Prolog ThinglabII Quantum Leap opbdp ECLiPSe KNOWLEDGE REPRESENTATION & REASONING 36 A real CSP – Job-shop scheduling Examples of job shop scheduling problems include factory scheduling problems, in which some operations have to be performed within one or several shifts spacecraft mission scheduling problems, in which time windows are determined by astronomical events over which we have no control patient treatment scheduling problems, in which a number of patients need to receive treatment that requires certain equipment within certain time windows, etc. When solving a job shop CSP, the objective is to find as quickly as possible a feasible schedule, namely a schedule where each operation is performed within one of its legal time windows and no resource is oversubscribed. KNOWLEDGE REPRESENTATION & REASONING 37 Job-shop scheduling problem (JSSP) A JSSP requires scheduling a set of jobs J={ j1, ... , jn} on a set of physical resources RES={R1, ... ,Rm} Each job j consists of a set of operations O ={O1, ... ,On} to be scheduled according to a process routing that specifies a partial ordering among these operations (e.g. Oi BEFORE Oj ). O1 O4 O6 O2 O5 O7 O3 O8 O1 O2 O3 Job 2 Job 1 KNOWLEDGE REPRESENTATION & REASONING 38 Job-shop scheduling problem (JSSP) Each job j has a release date rdj and a due date (or deadline) ddj between which all its operations have to be performed. Each operation Oi has a fixed duration dui and a start time sti whose value has to be selected. The domain of possible start times of each operation is initially constrained by the release and due dates of the job to which the operation belongs. there can be additional unary constraints that further restrict the set of admissible start times of each operation, thereby defining one or several time windows within which an operation has to be carried out e.g. a specific shift in factory scheduling In order to be successfully executed, each operation Oi requires pi different resources (e.g. a machine) Rij (1 j pi ) KNOWLEDGE REPRESENTATION & REASONING 39 The JSSP as a CSP Variables A set of variables is associated with each operation, Oi, which consists of the operation start time, sti its resource requirements, Rij Constraints Precedence constraints defined by the process routings translate into linear inequalities of the type: sti +dui stj (i.e. Oi BEFORE Oj ) Capacity constraints that restrict the use of each resource to only one operation at a time translate into disjunctive constraints of the form: ("p where Oi ,Oj require Rp) sti +dui stj stj +duj sti. These constraints simply express that, unless they use different resources, two operations Oi and Oj cannot overlap. KNOWLEDGE REPRESENTATION & REASONING 40 The JSSP as a CSP A job shop problem with 4 jobs Each node is labeled by the operation that it represents and the resource required by this operation. Each operation has a single resource requirement with a single possible value. Operation start times are the only variables. KNOWLEDGE REPRESENTATION & REASONING 41 A real CSP – The car sequencing problem In a car production scenario, cars are placed on conveyor belts which move through different work areas. A production line is normally required to produce cars of different models. The number of cars required for each model is called the production requirement. Each work area is constrained by its resource constraint or Capacity constraint. variable – one for every position in the conveyor belt (i.e. if there are n cars to be scheduled, the problem consists of n variables). domain - the set of car models, for example from model A to D. The task - to assign a value (a car model) to each variable (a position in the conveyor belt), satisfying both the production requirements and capacity constraints. KNOWLEDGE REPRESENTATION & REASONING 42 The car sequencing problem KNOWLEDGE REPRESENTATION & REASONING 43 Constraints and Databases There are close links between CSPs and relational database theory Constraint terminology Database terminology CSP Variable Domain Constraint Constraint scope Constraint tuples Set of solutions KNOWLEDGE REPRESENTATION & REASONING Database Attribute Attribute domain Table Table schema Table instance Join of all tables 44 Constraints and Databases – Example Consider the following CSP A set of variables X = {x0,…,x9} All variables have the domain D = {0,1,2} There are constraints with the following scopes and allowed tuples: c1 = {x0,x1,x3} – {(0,0,0), (0,1,0), (1,0,1), (1,1,1), (0,1,2)} c2 = {x1,x2,x3} – {(0,0,0), (0,0,1), (1,1,0), (1,0,1), (0,1,2)} c3 = {x1,x4} – {(0,0), (1,1)} c4 = {x3,x6} – {(0,0), (1,1), (1,0), (2,0)} c5 = {x4,x5,x6} – {(0,0,0), (0,0,1), (1,1,1), (1,0,2)} c6 = {x4,x7} – {(0,1), (1,0)} c7 = {x5,x8} – {(0,1), (1,0), (1,1)} c8 = {x6,x9} – {(0,0), (1,1)} KNOWLEDGE REPRESENTATION & REASONING 45 Constraints and Databases – Example The constraints as a relational database c1 c2 c3 c4 c5 c6 c7 c8 x0 x1 x3 x1 x2 x3 x1 x4 x3 x6 x4 x5 x 6 x4 x7 x5 x8 x6 x 9 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 2 0 e t c. 0 1 2 0 1 2 KNOWLEDGE REPRESENTATION & REASONING 46 Solving CSPs Assuming we have expressed knowledge about a problem as a CSP how can we reason with it? how can we find a solution (if one exists)? how can we find all solutions? how can we infer new knowledge? Generate and test Backtracking search algorithms Approximation algorithms Constraint propagation algorithms KNOWLEDGE REPRESENTATION & REASONING 47 Solving CSPs There are two general approaches to solving CSPs that are used in practice Systematic Search Explore systematically the space of all assignments systematic = every valuation will be explored sometime extends partial assignments Local Search explore the search space by small steps start with an initial complete assignment repairs complete assignments KNOWLEDGE REPRESENTATION & REASONING 48 First of all: Generate & Test Probably the most general problem solving method Algorithm: generate labelling test satisfaction Drawbacks: blind generator late discovery of inconsistencies KNOWLEDGE REPRESENTATION & REASONING Improvements: smart generator --> local search testing within generator --> backtracking 49 Generate and test: Crossword Puzzle Try each possible combination until you find one that works: – live – ant – live astar – live – ant – load astar – live – ant – peal … astar 1 2 3 4 5 Doesn’t check constraints until all variables have been instantiated Very inefficient way to explore the space of possibilities (4*6*3*6 = 432 for this trivial problem, most inconsistent) KNOWLEDGE REPRESENTATION & REASONING 50 Search Algorithms for CSPs A general search algorithm for CSPs Initial State Actions Assign a value from Di to an unassigned variable Xi Goal Test No value has been assigned to any variable All variables have been assigned and all constraints are satisfied The order in which the actions are executed does not matter We can take advantage of this! KNOWLEDGE REPRESENTATION & REASONING 51 The Search Space of CSPs The search space is finite The depth of the search tree is specified Equal to the number of variables Solutions are always at the leaves of the search tree Leaves KNOWLEDGE REPRESENTATION & REASONING 52 Search Algorithms for CSPs Which generic AI search algorithm looks suitable for CSPs? Breadth-First Search ? Depth-First Search ? No! BFS will be inefficient because solutions are always at the leaves Better than BFS. But it will frequently waste time searching while constraints are already violated Hill Climbing ? Minimize conflicts KNOWLEDGE REPRESENTATION & REASONING 53 Search Algorithms for CSPs We will study variations of DFS especially for CSPs. These algorithms are based on backtracking search Simple (or Chronological) Backtracking (BT) Backjumping (BJ) Forward Checking (FC) FC with Conflict-based Backjumping (FC-CBJ) Maintaining Arc Consistency (MAC) Also two variations of hill climbing Min-conflicts Min-conflicts with Random Walk KNOWLEDGE REPRESENTATION & REASONING 54 Chronological Backtracking (ΒΤ) The basic idea in all systematic backtracking-based algorithms is to start with a partial solution (i.e. assignments of a subset of the variables) and continue assigning variables until we reach a complete solution BT follows this technique Consider the variables in some order Pick an unassigned variable and give it a provisional value such that it is consistent with all of the constraints If no such assignment can be made, we’ve reached a dead end and need to backtrack to the previous variable and try its next value Continue this process until a solution is found or we backtrack to the initial variable and have exhausted all possible valaues KNOWLEDGE REPRESENTATION & REASONING 55 Chronological Backtracking (ΒΤ) Previous variables variable 0 { variable 1 b a a b a variable 2 b (current variable) { b a b a a variable 3 b a b a current assignment b a variable 4 solution b Future variables KNOWLEDGE REPRESENTATION & REASONING 56 Chronological Backtracking (ΒΤ) procedure CHRONOLOGICAL_BACKTRACKING (vars,doms,cons) solution BT (vars,Ø,doms,cons) function BT (unlabelled,compound_label,doms,cons) returns a solution or NIL if unlabelled = Ø then return compound_label else pick a variable x from unlabelled repeat pick a value v from Dx; delete v from Dx if compound_label + {(x,v)} violates no constraints then result BT(unlabelled - {x}, compound_label + {(x,v)}, doms,cons) if result NIL then return result end until Dx = Ø return NIL end KNOWLEDGE REPRESENTATION & REASONING 57 Chronological Backtracking (in action) WA = red WA = red NT = red WA = red NT = green Q = red WA = red NT = green WA = red NT = green Q = green WA = green WA = blue WA = red NT = blue WA = red NT = green Q = blue KNOWLEDGE REPRESENTATION & REASONING 58 Backtracking: Crossword Puzzle 1 a s 4 2 t a a l 5 k 3 r u n X1=astar X1=happy X2=live X2=load X3=ant KNOWLEDGE REPRESENTATION & REASONING … X2=live … X2=talk X3=oak X3=old 59 Chronological Backtracking (ΒΤ) Evaluation Complete and Sound ? Time complexity: Ο(dne) where d is the maximum domain size, n the number of variables, and e the number of constraints Χώρος: Ο(nd) Yes and Yes the space required to store the domains of all variables The complexities hold under the assumption that all constraint checks are performed in constant time and constraints are stored in constant space KNOWLEDGE REPRESENTATION & REASONING 60 GT & BT – Example 1 Problem: X::{1,2}, Y::{1,2}, Z::{1,2} X = Y, X Z, Y > Z generate & test X 1 1 1 1 2 2 2 Y 1 1 2 2 1 1 2 Z 1 2 1 2 1 2 1 backtracking test fail fail fail fail fail fail passed KNOWLEDGE REPRESENTATION & REASONING X 1 Y 1 2 2 1 2 Z 1 2 1 test fail fail fail fail passed 61 GT & BT 4-queen problem Q1 1 2 3 4 Q2 Q3 Q4 Place 4 queens so that no two queens are in attack. Qi: line number of queen in column i, for 1i4 Q1, Q2, Q3, Q4 Q1Q2, Q1Q3, Q1Q4, Q2Q3, Q2Q4, Q3Q4, Q1Q2-1, Q1Q2+1, Q1Q3-2, Q1Q3+2, Q1Q4-3, Q1Q4+3, Q2Q3-1, Q2Q3+1, Q2Q4-2, Q2Q4+2, Q3Q4-1, Q3Q4+1 KNOWLEDGE REPRESENTATION & REASONING 62 4-queen problem first solution Q1 Q2 Q3 Q4 1 2 3 4 There is a total of 256 valuations GT algorithm will generate 64 valuations with Q1=1; + + = 48 valuations with Q1=2, 1Q23; 3 valuations with Q1=2, Q2=4, Q3=1; 115 valuations to find first solution KNOWLEDGE REPRESENTATION & REASONING 63 4-queen problem, BT algorithm Q1 1 2 3 4 Q2 Q3 Q4 Q1 Q2 Q3 Q4 Q1 Q2 Q3 Q4 Q1 Q2 Q3 Q4 1 2 3 4 1 2 3 4 1 2 3 4 KNOWLEDGE REPRESENTATION & REASONING Q1 Q2 Q3 Q4 1 2 3 4 64 Advantages declarative nature with procedural capabilities (when needed) co-operative problem solving unified framework for integration of variety of special-purpose algorithms semantic foundation focus on describing the problem to be solved, and choosing the algorithm to solve it amazingly clean and elegant languages roots in logic programming applications proven success KNOWLEDGE REPRESENTATION & REASONING 65 Limitations NP-hard problems & tractability unpredictable behaviour ad-hoc modelling too much expertise required new constraints, solvers, heuristics, modelling non-incremental (rescheduling) awkward handling of optimization solvers tuned to finding first solution weak solver collaboration with OR engines for example KNOWLEDGE REPRESENTATION & REASONING 66 Useful Links On-line guide to Constraint Programming http://kti.ms.mff.cuni.cz/%7Ebartak/constraints/ Constraints Archive http://www.cs.unh.edu/ccc/archive/ CSPLib : a problem library for constraints http://4c.ucc.ie/~tw/csplib/ Course on Theory and Practice of Constraint Satisfaction http://www.cse.unl.edu/~choueiry/CSCE990-05/schedule.htm KNOWLEDGE REPRESENTATION & REASONING 67

Descargar
# Dynamic and Distributed Scheduling in Communication