DA_202_04_CSP_part1 (1).pdf

DA 202 Basic of Artificial Intelligence Constraint Satisfaction Problems 1 What is Search For? ▪ Assumptions about the world: a single agent, deterministic actions, fully observed...

DA 202 Basic of Artificial Intelligence Constraint Satisfaction Problems 1 What is Search For? ▪ Assumptions about the world: a single agent, deterministic actions, fully observed state, discrete state space ▪ Planning: sequences of actions ▪ The path to the goal is the important thing ▪ Paths have various costs, depths ▪ Heuristics give problem-specific guidance ▪ Identification: assignments to variables ▪ The goal itself is important, not the path ▪ All paths at the same depth (for some formulations) ▪ CSPs are specialized for identification problems 2 1  Constraint Satisfaction Problems ▪ Standard search problems: ▪ State is a “black box”: arbitrary data structure ▪ Goal test can be any function over states ▪ Successor function can also be anything ▪ Constraint satisfaction problems (CSPs): ▪ A special subset of search problems ▪ State is defined by variables Xi with values from a domain D (sometimes D depends on i) ▪ Goal test is a set of constraints specifying allowable combinations of values for subsets of variables ▪ Simple example of a formal representation language ▪ Allows useful general-purpose algorithms with more power than standard search algorithms 3 Example: Map Coloring ▪ Variables: ▪ Domains: ▪ Constraints: adjacent regions must have different colors Implicit: Explicit: ▪ Solutions are assignments satisfying all constraints, e.g.: 4 2  Example: N-Queens ▪ Formulation 1: ▪ Variables: ▪ Domains: ▪ Constraints 5 Example: N-Queens ▪ Formulation 2: ▪ Variables: ▪ Domains: ▪ Constraints: Implicit: Explicit: 6 3  Constraint Graphs 7 Constraint Graphs ▪ Binary CSP: each constraint relates (at most) two variables ▪ Binary constraint graph: nodes are variables, arcs show constraints ▪ General-purpose CSP algorithms use the graph structure to speed up search. E.g., Tasmania is an independent subproblem! 8 4  Example: Cryptarithmetic ▪ Variables: ▪ Domains: ▪ Constraints: 9 Example: Sudoku ▪ Variables: ▪ Each (open) square ▪ Domains: ▪ {1,2,…,9} ▪ Constraints: 9-way alldiff for each column 9-way alldiff for each row 9-way alldiff for each region (or can have a bunch of pairwise inequality constraints) 10 5  Example: The Waltz Algorithm ▪ The Waltz algorithm is for interpreting line drawings of solid polyhedra as 3D objects ▪ An early example of an AI computation posed as a CSP ? ▪ Approach: ▪ Each intersection is a variable ▪ Adjacent intersections impose constraints on each other ▪ Solutions are physically realizable 3D interpretations 12 Varieties of CSPs ▪ Discrete Variables ▪ Finite domains ▪ Size d means O(dn) complete assignments ▪ E.g., Boolean CSPs, including Boolean satisfiability (NP- complete) ▪ Infinite domains (integers, strings, etc.) ▪ E.g., job scheduling, variables are start/end times for each job ▪ Linear constraints solvable, nonlinear undecidable ▪ Continuous variables ▪ E.g., start/end times for Hubble Telescope observations ▪ Linear constraints solvable in polynomial time by LP methods (see cs170 for a bit of this theory) 13 6  Varieties of Constraints ▪ Varieties of Constraints ▪ Unary constraints involve a single variable (equivalent to reducing domains), e.g.: ▪ Binary constraints involve pairs of variables, e.g.: ▪ Higher-order constraints involve 3 or more variables: e.g., cryptarithmetic column constraints ▪ Preferences (soft constraints): ▪ E.g., red is better than green ▪ Often representable by a cost for each variable assignment ▪ Gives constrained optimization problems ▪ (We’ll ignore these until we get to Bayes’ nets) 14 Real-World CSPs ▪ Assignment problems: e.g., who teaches what class ▪ Timetabling problems: e.g., which class is offered when and where? ▪ Hardware configuration ▪ Transportation scheduling ▪ Factory scheduling ▪ Circuit layout ▪ Fault diagnosis ▪ … lots more! ▪ Many real-world problems involve real-valued variables… 15 7  Solving CSPs 16 Standard Search Formulation ▪ Standard search formulation of CSPs ▪ States defined by the values assigned so far (partial assignments) ▪ Initial state: the empty assignment, {} ▪ Successor function: assign a value to an unassigned variable ▪ Goal test: the current assignment is complete and satisfies all constraints ▪ We’ll start with the straightforward, naïve approach, then improve it 17 8  Search Methods ▪ What would BFS do? ▪ What would DFS do? ▪ What problems does naïve search have? 18 Backtracking Search ▪ Backtracking search is the basic uninformed algorithm for solving CSPs ▪ Idea 1: One variable at a time ▪ Variable assignments are commutative, so fix ordering ▪ I.e., [WA = red then NT = green] same as [NT = green then WA = red] ▪ Only need to consider assignments to a single variable at each step ▪ Idea 2: Check constraints as you go ▪ I.e. consider only values which do not conflict previous assignments ▪ Might have to do some computation to check the constraints ▪ “Incremental goal test” ▪ Depth-first search with these two improvements is called backtracking search (not the best name) ▪ Can solve n-queens for n  25 19 9  Backtracking Example 20 Backtracking Search ▪ Backtracking = DFS + variable-ordering + fail-on-violation ▪ What are the choice points? 21 10  Improving Backtracking ▪ General-purpose ideas give huge gains in speed ▪ Ordering: ▪ Which variable should be assigned next? ▪ In what order should its values be tried? ▪ Filtering: Can we detect inevitable failure early? ▪ Structure: Can we exploit the problem structure? 22 Filtering: Forward Checking ▪ Filtering: Keep track of domains for unassigned variables and cross off bad options ▪ Forward checking: Cross off values that violate a constraint when added to the existing assignment NT Q WA SA NSW V 23 11  Filtering: Constraint Propagation ▪ Forward checking propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures: NT Q WA SA NSW V ▪ NT and SA cannot both be blue! ▪ Why didn’t we detect this yet? ▪ Constraint propagation: reason from constraint to constraint 24 Consistency of A Single Arc ▪ An arc X → Y is consistent iff for every x in the tail there is some y in the head which could be assigned without violating a constraint NT Q WA SA NSW V Delete from the tail! ▪ Forward checking: Enforcing consistency of arcs pointing to each new assignment 25 12  Arc Consistency of an Entire CSP ▪ A simple form of propagation makes sure all arcs are consistent: NT Q WA SA NSW V ▪ Important: If X loses a value, neighbors of X need to be rechecked! ▪ Arc consistency detects failure earlier than forward checking Remember: Delete ▪ Can be run as a preprocessor or after each assignment from the tail! ▪ What’s the downside of enforcing arc consistency? 26 Enforcing Arc Consistency in a CSP ▪ Runtime: O(n2d3), can be reduced to O(n2d2) ▪ … but detecting all possible future problems is NP-hard – why? 27 13  Limitations of Arc Consistency ▪ After enforcing arc consistency: ▪ Can have one solution left ▪ Can have multiple solutions left ▪ Can have no solutions left (and not know it) ▪ Arc consistency still runs What went wrong here? inside a backtracking search! 28 Ordering: Minimum Remaining Values ▪ Variable Ordering: Minimum remaining values (MRV): ▪ Choose the variable with the fewest legal left values in its domain ▪ Why min rather than max? ▪ Also called “most constrained variable” ▪ “Fail-fast” ordering 29 14  Ordering: Least Constraining Value ▪ Value Ordering: Least Constraining Value ▪ Given a choice of variable, choose the least constraining value ▪ I.e., the one that rules out the fewest values in the remaining variables ▪ Note that it may take some computation to determine this! (E.g., rerunning filtering) ▪ Why least rather than most? ▪ Combining these ordering ideas makes 1000 queens feasible 30 15