25-09-2013, 03:02 PM
Artificial Intelligence Problem solving by searching
Artificial Intelligence Problem.ppt (Size: 1.19 MB / Downloads: 26)
Constraint Satisfaction Problems (CSPs)
Standard search problem:
state is a "black box“ – any data structure that supports successor function, heuristic function, and goal test
CSP:
state is defined by variables Xi with values from domain Di
goal test is a set of constraints specifying allowable combinations of values for subsets of variables
Varieties of CSPs
Discrete variables
finite domains:
n variables, domain size d O(dn) complete assignments
e.g., Boolean CSPs, incl. Boolean satisfiability (NP-complete)
infinite domains:
integers, strings, etc.
e.g., job scheduling, variables are start/end days for each job
need a constraint language, e.g., StartJob1 + 5 ≤ StartJob3
Continuous variables
e.g., start/end times for Hubble Space Telescope observations
linear constraints solvable in polynomial time by linear programming
Backtracking search
Every solution appears at depth n with n variables
use depth-first search
Depth-first search for CSPs with single-variable assignments is called backtracking search
Backtracking search is the basic uninformed algorithm for CSPs
Can solve n-queens for n ≈ 25
Improving backtracking efficiency
General-purpose heuristics can give huge gains in speed:
Which variable should be assigned next?
In what order should its values be tried?
Can we detect inevitable failure early?
Most constraining variable
MCV
Tie-breaker among most constrained
variables
Most constraining variable:
choose the variable with the most constraints on remaining variables (select variable that is involved in the largest number of constraints - edges in graph on other unassigned variables)
Forward Checking
Assigns variable X, say
Looks at each unassigned variable, Y say, connected to X and delete from Y’s domain any value inconsistent with X’s assignment
Eliminates branching on certain variables by propagating information
If forward checking detects a dead end, algorithm will backtrack immediately.
Summary
CSPs are a special kind of problem:
states defined by values of a fixed set of variables
goal test defined by constraints on variable values
Backtracking = depth-first search with one variable assigned per node
Variable ordering and value selection heuristics help significantly
Forward checking prevents assignments that guarantee later failure
Constraint propagation (e.g., arc consistency) does additional work to constrain values and detect inconsistencies
Iterative min-conflicts is usually effective in practice