Transcript Artificial Intelligence

Artificial Intelligence
Practical 2: Forward
Checking
Ian Gent
[email protected]
Artificial Intelligence
Practical 2: Forward
Checking
Part
Part
Part
Part
I:
II:
III:
IV:
Overview
Three ways to implement FC
Other parts of the practical
What I’m looking for
Practical 2: Forward Checking
 Write a program to implement the two
algorithms BT (Backtracking) and FC
(Forward Checking.) Perform an empirical
comparison of the two algorithms.
 Some practical stuff:
 This is practical 2 of 2.
 Each will carry equal weight, I.e. 10% of total credit
 You may use any implementation language you wish
 Deadline(s) are negotiable (can be decided after vacation)
3
Aims and Objectives
 Aims:
 to give experience in implementing important AI search
algorithms
 to give experience in comparing AI techniques empirically
 Objectives:
 after completing the practical, you should have:
 implemented the algorithms BT and FC
 gained an appreciation of some of the basic techniques necessary
 performed and reported on an empirical comparison of different
algorithms
4
What you need to do
 Implement BT and FC for binary CSP’s
 if you can do FC you can do BT
 FC is the hard bit
 implement at least two (static) heuristics for each
 Implement a reader to read in benchmark CSP’s
 format of problems will be provided
 use benchmarks for testing
 Perform empirical comparison of algorithms
 run on benchmark problems
 report on comparative success of algorithm/heuristic
combinations
5
What you can get away with
 Implement BT binary CSP’s
 implement at least one heuristics
 Implement a reader to read in benchmark CSP’s
 format of problems will be provided
 use benchmarks for testing
 Perform empirical comparison of algorithms
 run on benchmark problems
 report on success or otherwise
 Don’t expect too many marks for doing the above
 but don’t expect zero either
6
Three Ways to Implement FC
 You only need one implementation!
 Choose the style that suits you and the language
you like using
 Three ways are:
 using the general search algorithm
 recursive
 from pseudocode using specific data structures
7
Implementing FC (1)
 You can implement FC using the generic search
algorithm presented earlier
 Search states = some representation of current
assignment of values to variables, and current
domains for each variable
 Forward checking done when new states created
 Do search by depth-first
 Main problem is memory management
 not letting space expand endlessly/overwriting existing
states
 easier if you’ve got GC built in
8
FC via general search algorithm
 1. Form a one element list with null state
• null state = state with no decisions = original CSP
 2. Loop Until (either list empty or we have a solution)
 Remove the first state S from the list
 Choose the next decision to make
• which variable x to assign next
 Create a new state for each possible choice of decision
• decisions are all remaining values v in Dx
• to create each new state, assign x=v and forward check
 MERGE the set of new states into the list
 3. If (solution in list) succeed and report solution
 else list must be empty, so fail
9
Implementing FC (2)
 Functional languages are good for search
 e.g. Lisp, Haskell
 Write propagator for forward checking which makes
non destructive changes.
 I.e. original state still exists, but we get a new one for free
 GC done for you
 Write search function recursively
 handles the manipulation of the list for you via the function
calling stack
10
Implementing FC (2)
 Search (CSP):
 choose var
 while (value remains in CDvar)
 Call Search( fc-propagate(CSP[var = value]))
 If call succeeds with solution, return solution
 If all calls failed, return failure
11
Implementing FC(3)
 Follow implementation outlined by Prosser
 Avoids most memory management problems
 Explicit data structures initially set up
 when we remove values from vi to vj we modify them
 reductions[j] contains sequence of sequence
 each one a sequence of values disallowed by past var
 past-fc[j] is a set of variables
 set of variables i which caused value removals from vj
 future-fc[i] is another set
 set of variables in which the current value of vi causes
value removals
12
General pseudocode for bcssp
 Procedure bccsp (n, status)
 consistent := true, status := unknown, ii := 1
 while (status = unknown)
 if (consistent)
• ii := label(ii,consistent)
– need special purpose function fc-label here
• else ii := unlabel(ii,consistent)
– and fc-unlabel here
 if (ii > n)
• status := solution
• else if (ii = 0)
– status := impossible
13
Implementing FC(3.2)
 Use data structure suggested by Bacchus/van Run
 Have a 2D array Domain[ii,k]
 first dimension is variables, second dimension values
 Domain[ii,k] = 0 if value k still possible for variable ii
 I.e. if k still belongs to CD[ii]
 If value k impossible, removed from CD[ii]
 Domain[ii,k] = j, where j is variable that caused removal
 On backtracking, to undo effect of assigning j
 if Domain[ii,k] = j, reset it so that Domain[ii,k] = 0
 either store all changes made by j, or just iterate over 2D
array looking for those equal to j
14
Other parts of the practical
 Input format:
 the APES group has a standard format for sharing binary
CSP’s.
 Allows sharing of benchmarks
 Valuable for testing (all programs should give same
results)
 Write a reader for this format
 translate input to your internal format for CSP
 your representation of variables, domains, constraints
 create small test problems for yourself
 and if you want, share them for others
15
Heuristics
 I am only looking for static variable ordering
heuristics
 implement dynamic ones if you wish
 heuristics are harder in Prosser’s version
 see paper by Bacchus & van Run for pointers
 Heuristics you might consider





lexicographic, v1, v2, v3…
random, v17, v16, v2, v19 …
min degree: var involved in least constraints first
max degree: var involved in most constraints first
other heuristics you find/can think of
16
Empirical Report
 Run your program(s) against benchmark instances I
will provide, and others you might want to try
 From empirical evidence, how do the techniques
perform?
 Is FC better than BT? Worse? varies across problems?
 Are there some problems that you can’t solve in
reasonable cpu time?
 Is min degree better than max degree?
 Are some problems harder than others?
17
Empirical Report
 Write a report on your experiments
 Describe the purpose of each experiment, the
results, and conclusions you draw
 Try to make it a good piece of empirical AI!
 Include results as e.g. tables or graphs
 as appendix if too many results
 Probably a few pages
18
What I am looking for
 A correct functioning program
 speed is not important (within reason)
 should implement at least 4 combinations of
algorithm/heuristic
 A report summarising program and empirical work
 no set word limit, probably needs a few pages to present
good empirical work well
 evidence that your code is correct
 e.g. sample output, correct result on benchmarks
 conclusions on your empirical result
 code (electronically if it’s HUGE)
19
Additional Issues
 Some ways to get more credit …
 create/find problems for which usually worse
algorithm/heuristic does better
 think of different heuristics
 think of interesting hypotheses and test them
 implement FC so that propagation causes a chain
reaction.
 I.e. if you get domain size = 1, redo FC from there
 Since I’ve asked for static heuristics, we may search on
variable x, domain size 4, when variable y has d.s. = 1
 implement dynamic variable ordering heuristics
20
Some pointers
 A tutorial on constraint programming
 Barbara Smith
 Leeds University, 1995
 Hybrid Algorithms for the Constraint Satisfaction
Problem
 Patrick Prosser
 Computational Intelligence, 1993
 Dynamic Variable Ordering in CSPs
 Bacchus & van Run
 CP95, 1995
21