Transcript Artificial Intelligence

Artificial Intelligence
Search: 2
Ian Gent
[email protected]
Artificial Intelligence
Search 2
Part I :
Part II:
Part II:
The Eights Puzzle
Search Algorithms via lists
Best First Search
The Eights Puzzle
 Sliding blocks puzzle, more usually 15 puzzle
 shows you the state of AI in the sixties
 how many moves between these states?
1 2 3
2 1 6
8
4
4
7 6 5
8
7 5 3
3
Search Reminder
 Search states, Search trees
 Don’t store whole search trees, just the frontier
ABC, ABc, AbC, Abc, aBC, abC, abc
state = ()
Choose A
a
(a)
Choose B
B
(a B)
Impossible
A
(A)
Choose C
b
(a b)
Impossible
C
(AC)
Choose B
B
(ABC)
Impossible
c
Ac
impossible
b
(AbC)
Solution
4
Frontiers as lists
 One way to implement search algorithms is via lists
 Lists fundamental in AI programming
 main data structure in Lisp, Prolog
 makes list processing really easy (no pointers)
 <end of advert for AI languages>
 Lists can easily store frontier of search
 Each element in list is search state
 Different algorithms manipulate list differently
5
A general search algorithm
 1. Form a one element list with null state
 2. Loop Until (either list empty or we have a solution)
 Remove the first state X from the list
 Choose the next decision to make
• e.g. which letter to set in SAT, which city to choose successor in TSP
 Create a new state for each possible choice of decision
• e.g. upper/lower case, Walla Walla/Oberlin/Ithaca
 MERGE the set of new states into the list
• different algorithms will have different MERGE methods
 3. If (solution in list) succeed
 else list must be empty, so fail
6
Depth First Search
 The most important AI search algorithm?
 MERGE = push
 treat list as a stack
 new search states to explore at front of list, get treated first
 What about when many new states created?
 We use a heuristic to decide what order to push new
states
 all new states in front of all old states in the list
 What about when no new states created?
 We must be at a leaf node in the search tree
 we have to backtrack to higher nodes
7
Breadth First Search
 MERGE = add to end
 treat list as a queue
 new search states to explore at end of list,
 What about when many new states created?
 We use a heuristic to decide what order to add new states
 Breadth first considers all states at a given depth in
the search tree before going on to the next depth
 compare with depth-first,
 depth-first considers all children of current node before
any other nodes in the search tree
 list can be exponential size -- all nodes at given depth
8
Depth-First-Depth-Bounded
Search
 As depth-first search
 Disallow nodes beyond a certain depth d in tree
 to implement, add depth in tree to search state
 Compare DFDB with Depth-first
 DFDB: always finds solution at depth <= d
 DF may find very deep solution before shallow ones
 DFDB: never goes down infinite branch
 relevant if search tree contains infinite branches
• e.g. Eights puzzle
 DFDB: we have a resource limit (b^d if b branching rate)
 How do we choose d?
9
Iterative Deepening Search
 No longer a simple instance of general search
 d = min-d
 Loop Until (solution found)
 apply DFDB(d)
 d := d + increment
 Why?




Guarantees to find a solution if one exists (cf DFDB)
Finds shallow solutions first (cf DF)
Always has small frontier (cf Breadth First)
Surprising asymptotic guarantees
 search time typically no more than d/(d-1) as bad as DF
10
Why is Iterative deepening ok?
 Suppose increment = 1, solution at depth d
 how much more work do we expect to do in I.D. vs DF ?
 I.d. repeats work from depths 1 to d

d
i=1
bi = b d+1 / (b - 1)
 Ratio to b d = b d+1 / bd(b - 1) = b/(b-1)
 So we only do b/(b-1) times as much work as we need to
 e.g. even if b=2, only do twice as much work
 Very often worth the overhead for the advantages
11
Comparing Search
Algorithms
Depth
First
Breadth
First
Depth
Iterative
Bounded Deepening
Always finds
solution if one
exists?
First solution
shallowest?
Yes if no Yes
inf. branch
No
Yes
No
Yes
No
Size of list at
depth d?
bd
b^d
bd
Yes if min-d,
increment
correct
bd
No
No
Yes
Revisits nodes No
redundantly?
12
Best First Search
 All the algorithms up to now have been hard wired
 I.e. they search the tree in a fixed order
 use heuristics only to choose among a small number of
choices
 e.g. which letter to set in SAT / whether to be A or a
 Would it be a good idea to explore the frontier
heuristically?
 I.e. use the most promising part of the frontier?
 This is Best First Search
13
Best First Search
 Best First Search is still an instance of general
algorithm
 Need heuristic score for each search state
 MERGE: merge new states in sorted order of score
 I.e. list always contains most promising state first
 can be efficiently done if use (e.g.) heap for list
• no, heaps not done for free in Lisp, Prolog.
 Search can be like depth-first, breadth-first, or inbetween
 list can become exponentially long
14
Search in the Eights Puzzle
 The Eights puzzle is different to (e.g.) SAT
 can have infinitely long branches if we don’t check for
loops
 bad news for depth-first,
 still ok for iterative deepening
 Usually no need to choose variable (e.g. letter in SAT)
 there is only one piece to move (the blank)
 we have a choice of places to move it to
 we might want to minimise length of path
 in SAT just want satisfying assignment
15
Search in the Eights Puzzle
 Are the hard wired methods effective?
 Breadth-first very poor except for very easy problems
 Depth-first useful without loop checking
 not much good with it, either
 Depth-bounded -- how do we choose depth bound?
 Iterative deepening ok
 and we can use increment = 2 (why?)
 still need good heuristics for move choice
 Will Best-First be ok?
16
Search in the Eights Puzzle
 How can we use Best-First for the Eights puzzle?
 We need good heuristic for rating states
 Ideally want to find guaranteed shortest solution
 Therefore need to take account of moves so far
 And some way of guaranteeing no better solution
elsewhere
17
Next week in Search for AI
 Heuristics for the Eights Puzzle
 the A* algorithm
18