Constraint Satisfaction Problems

-
identification problem - a problem in which the agent must identify whether it is a goal state or not, with no regards of how it arrives at that goal
  • In identification problems, the goal itself it important, not the path of reaching the goal
  • All paths have the same depth, which is the number of variables in the problem

constraint satisfaction problem (CSP) - an identification search problem in which each state must satisfy a number of constraints (limitations) in order to be a valid goal state
  • In CSPs, states are partial assignments of variables (i.e. some variables have been assigned values while others have not)
constraint graph - a graph whose nodes represent a CSP's variables and edges represent the constraints between the variables/nodes

Components of a CSP

  1. variables - a set of $N$ variables ($X_1,...,X_N$) that can each take on a single value from the domain
  2. domain - a set ${x_1,...,x_d}$ representing all possible values that a CSP variable can take on ($d$ is the size of the domain)
  3. constraints - restrictions on values of variables, potentially with regard to other variables
    • Constraints reduce the domain for certain variables in the problem
    • The goal test of a CSP is defined by the constraints
      • The goal test is a set of constraints specifying allowable combinations of values for subsets of variables
      • The goal found if all constraints are satisfied 
    • Types of constraints
      • unary constraint - a constraint that involves only a single variable in the CSP
        • Unary constraints are not represented in constraint graphs, but instead are simply used to prune the domain of the variable they constrain when necessary
      • binary constraint - a constraint that involves just 2 variables
        • Binary constraints are represented as traditional graph edges in the constraint graph
      • higher-order constraint - a constraint involving more than 2 variables
        • Higher-order constraints can be represented as multiple graph edges on a constraint graph

    Solving CSPs

    • Note: using standard search (e.g. DFS, BFS, etc.) on a CSP takes too long to find a solution

    • Backtracking search

      • backtracking search - a search algorithm that increases the speed of the search on a CSP by "undoing" a bad assignment of variables
        • A bad assignemnt of variables is a state in which not all variables cannot be assigned a value
        • Backtracking search is essentially an optimized version of DFS: backtracking search = DFS + variable ordering optimization + "fail on violation" optimization
        • Variable ordering
          • Variable ordering fixes an ordering for variables and selects values for variables in this order
          • Only assignments to a single variable needs to be considered at each step (as opposed to needing to consider the different number of ways the variable can take on certain values and the different number of ways certain variables can come after it)
        • "Fail on violation"
          • "Fail on violation" simply means checking constraints as we go
          • When selecting values for a variable, only select values that do not conflict with any previously assigned values. If no such value exists, backtrack and return to the previous variable, changing its value.
            • tldr: only consider values which do not conflict with assignments to previous variables

        • Optimizations for backtracking search

          • forward checking - a naive filtering technique for evaluating the effect of a specific assignment to a variable
            • filtering - checks ahead of time whether the domains of unassigned variable can be pruned by removing values that we know will result in backtracking (prevents unnecessary backtracking)
            • Given the current partial solution and a candidate assignment to evaluate, forward checking checks whether another variable can take a consistent value
            • Whenever a new variable is assigned, forward checking prunes the domains of next (unassigned) variables adjacent to the newly assigned variable in the constraint graph
          • arc consistency - a filtering technique that ensures consistent "arcs" between variables 
            • arc - a directed edge between 2 variables in a CSP
            • consistent arc - an arc $X \rightarrow Y$ is consistent if and only if for every value $x$ in the tail variable's domain, there is some value in the head variable's domain which could be assigned without violating a constraint (i.e. an arc is consistent if the tail variable only contains valid value options)

        • Ordering of variables and values

          • Variable ordering/selection
            • minimum remaining variables (MRV) policy - choose whichever unassigned variable has the fewest remaining valid values (i.e. the most constrained variable)
            • It is best to assign a value to the most constrained variables sooner because they are likely to run out of possible options and result in backtracking if left unassigned (we will know sooner if an assignment fails)
          • Value ordering/selection
            • least constraining value (LCV) policy - when selecting which value to assign next to a variable, select the value that prunes the fewest values from the domains of the remaining unassigned variables

    Backtracking search implementation

    {} is used for variable ordering.

    order-domain-values fixes the ordering of the variables and at each step, the variable is selected based on that ordering.

    "if value is consistent with assignment" is the "fail on violation" optimization



    Forward checking procedure

    1. Based on the ordering of variables and values that the forward checking technique follows, pick a variable $X_i$ and assign an initial value to it 
    2. Check its neighboring variables $X_j$ (those that share a constraint with $X_i$) and eliminate values from the domains of $X_j$ that break a constraint 
    3. Repeat for the next variable in the variable ordering (and assign the value to that variable based on the value ordering)
      • Repeat until we have a solution or until we need to backtrack
      • Forward checking backtracks when all domain values have been eliminated from its list of options (if this happens before we have reached the goal state)
      • Forward checking finds a solution we have reached a state that satisfies all constraints

    Arc consistency procedure

    1. Check unary constraints to form the initial domains
      • The initial domains of all variables are formed after checking the unary constraints (the initial domains are made consistent with the unary constraints) 
    2. Examine all arcs between all pairs of variables and remove the values from the tail node's domain which are not consistent with the constraints between the head and tail variables/nodes 
      • The algorithm keeps a fringe of arcs that must yet be checked for consistency 
        • At the start of the algorithm, all possible arcs are on the fringe 
      • A value from the tail's domain is removed if a binary constraint is not met 
    3. When a value is removed from the tail variable's domain, all arcs where the tail variable is the head is put onto the fringe 
      • The arcs where the tail variable is the head must be rechecked for consistency









    Comments

    Post a Comment

    Popular posts from this blog

    AI Search Problems Overview

    -
    Image
    What is an agent? agent - an entity that perceives and acts planning agent - an agent that make decisions based on (hypothesized) consequences of actions Planning agents simulate situations and performs/executes the best action according to its simulations done in the "planning" stage Planning agents consider how the world would be Planning agents must have a model of how the world evolves in response to actions Planning agents must formulate a goal (test) Planning agents are complete (i.e. they never get stuck and always find a solution, since the plan ahead) The agent does not actually perform all the plans out in the real world The planning is all done "in simulation" search agent - a planning agents that solves search problems Search problems search problem - a type of planning problem with the four components (listed below); the environment in which a rational planning agent exists in Search operates over models of the real world
    Read more

    Tips on Pointers and Arrays in C

    -
    Image
    *p++ vs. (*p)++   *p++ means *(p++) ++ binds to p , not to *p ++ will increment "p," not "*p," which is the thing that "p" points to The value of the expression *p++ is the value that p pointed to before being incremented ( *p ) Two useful charts Pointer arithmetic notes (~pointer~) += (~number~);  means  (~pointer~) += ~number~) * sizeof((~type~)); Pointer arithmetic addition adds multiples of the type size to the memory address Ex. If p is a pointer to an integer, then p += 1 means p += 1 * sizeof(int)   (~pointer name~) + 1 points to the next object in memory (returns a pointer to the next element)  (~pointer name~) + i points to the i -th object beyond (~pointer name~) in memory  (~pointer name~) += i increments (~pointer name~) to point to i elements beyond itself  Types of valid pointer arithmetic Adding an integer to a pointer Subtracting 2 pointers (in the same array) Comparing poi
    Read more

    Standard/Planning Search Problems

    -
    Image
    Standard search problems Solution to a standard search problem: a plan Use a search algorithm  to find the plan and solve the search problem Search algorithms are performed on the search tree (of the problem) to find the solution to the search problem All search algorithms follow the same algorithm, but just use a different data structures for the fringe   Types of standard searches ➤  UNINFORMED SEARCH uninformed search  - a search that does not know information about the goal's location Types of uninformed searches Depth first search (DFS) - a search strategy that expands the deepest node first Implementation : uses a last-in-first-out (LIFO)  stack as the fringe Time complexity : $O(b^m)$, for a finite tree where $m$ is the maximum depth and $b$ is the branching factor Space complexity : $O(bm)$ DFS expands only the nodes on a single path from the deepest level to the root Breadth first search (BFS) - a search strategy in which the root is ex
    Read more