Transcript Search

CS B551: ELEMENTS OF
ARTIFICIAL INTELLIGENCE
1
Instructor: Kris Hauser
http://cs.indiana.edu/~hauserk
RECAP
http://www.cs.indiana.edu/classes/b551
 Brief history and philosophy of AI
 What is intelligence? Can a machine act/think
intelligently?


Turing machine, Chinese room
2
AGENDA
Problem Solving using Search
 Search Algorithms

3
EXAMPLE: 8-PUZZLE
8
2
3
4
5
1
1
2
3
7
4
5
6
6
7
8
Initial state
Goal state
State: Any arrangement of 8 numbered tiles and an empty tile on a 3x3 board
4
SUCCESSOR FUNCTION: 8-PUZZLE
2
3
4
5
1
6
8
2
7
8
6
3
8
2
3
4
7
3
4
5
1
6
5
1
7
SUCC(state)  subset of states
8
The successor function is knowledge
about the 8-puzzle game, but it does
not tell us which outcome to use, nor to
which state of the board to apply it.
5
2
7
4
1
6
5
Across history, puzzles and games
requiring the exploration of alternatives
have been considered a challenge for
human intelligence:
 Chess originated in Persia and India
about 4000 years ago
 Checkers appear in 3600-year-old
Egyptian paintings
 Go originated in China over 3000 years
ago
So, it’s not surprising that AI uses games 6
to design and test algorithms
EXPLORING ALTERNATIVES
Problems that seem to require intelligence
usually require exploring multiple alternatives
 Search: a systematic way of exploring
alternatives

7
8-QUEENS PROBLEM

State repr. 1


Any non-conflicting
placement of 0-8
queens
State repr. 2

Any placement of 8
queens
8
DEFINING A SEARCH PROBLEM
S
 State space S
 Successor function:
x  S  SUCC(x)  2S
 Initial state s0
 Goal test:
xS  GOAL?(x) =T or F
 Arc cost
9
STATE GRAPH



Each state is
represented by a
distinct node
An arc (or edge)
connects a node s
to a node s’ if
s’  SUCC(s)
The state graph may
contain more than one
connected component
10
SOLUTION TO THE SEARCH PROBLEM




A solution is a path
connecting the initial
node to a goal node
(any one)
The cost of a path is
the sum of the arc
costs along this path
An optimal solution is
a solution path of
minimum cost
There might be
no solution !
G
I
11
PATHLESS PROBLEMS




Sometimes the path
doesn’t matter
A solution is any goal
node
Arcs represent
potential state
transformations
E.g. 8-queens,
Simplex for LPs, Map
coloring
G
I
12
REPRESENTATION 1
State: any placement of 0-8
queens
 Initial state: 0 queens
 Successor function:



Goal test:


Place queen in empty square
Non-conflicting placement of
8 queens
# of states ~ 64x63x…x57 ~
3x1014
13
REPRESENTATION 2
State: any placement of nonconflicting 0-8 queens in
columns starting from left
 Initial state: 0 queens
 Successor function:



Goal test:


A queen placed in leftmost
empty column such that it
causes no conflicts
Any state with 8 queens
# of states = 2057
14
PATH PLANNING
What is the state space?
15
FORMULATION #1
Cost of one horizontal/vertical step = 1
Cost of one diagonal step = 2
16
OPTIMAL SOLUTION
This path is the shortest in the discretized state
space, but not in the original continuous space
17
FORMULATION #2
Cost of one step: length of segment
18
FORMULATION #2
Visibility graph
Cost of one step: length of segment
19
SOLUTION PATH
The shortest path in this state space is also the
shortest in the original continuous space
20
WHAT IS A STATE?

A state does:
Represent all information meaningful to the problem
at a given “instant in time” – past, present, or future
 Exist in an abstract, mathematical sense


A state DOES NOT:
Necessarily exist in the computer’s memory
 Tell the computer how it arrived at the state
 Tell the computer how to choose the next state
 Need to be a unique representation

21
WHAT IS A STATE SPACE?

An abstract mathematical object


Membership should be trivially testable



E.g., the set of all permutations of (1,…,8,empty)
E.g., S = { s | s is reachable from the start state
through transformations of the successor function } is
not easily testable
Arcs should be easily generated
Again: the state space does NOT contain
information about which arc to take (or not to
take) in a given state
22
5-MINUTE QUIZ

Formulate 2x2 Tic-Tac-Toe, where you play both
X and O’s actions, as a search problem. The goal
state is any state with two in a line. Assume O
goes first.
Draw entire state graph. For compactness’s sake,
eliminate symmetrical states
 Indicate initial and goal states on this graph


Suppose one side is allowed to pass. How does the
state graph change? Do you need to change
anything to the problem definition?
23
EXAMPLE: 8-PUZZLE
8
2
3
4
5
1
1
2
3
7
4
5
6
6
7
8
Initial state
Goal state
State: Any arrangement of 8 numbered tiles and an empty tile on a 3x3 board
24
15-PUZZLE

Introduced (?) in 1878 by Sam Loyd, who
dubbed himself “America’s greatest puzzleexpert”
25
15-PUZZLE

Sam Loyd offered $1,000 of his own money to the
first person who would solve the following
problem:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
?
1
2
3
4
5
6
7
8
9
10
11
12
13
15
14
26

But no one ever won the prize !!
27
HOW BIG IS THE STATE SPACE OF THE (N21)-PUZZLE?

8-puzzle  ?? states
28
HOW BIG IS THE STATE SPACE OF THE (N21)-PUZZLE?
8-puzzle  9! = 362,880 states
 15-puzzle  16! ~ 2.09 x 1013 states
 24-puzzle  25! ~ 1025 states


But only half of these states are reachable from
any given state
(but you may not know that in advance)
29
PERMUTATION INVERSIONS




Wlg, let the goal be:
1
5
9
13
2
6
10
14
3 4
7 8
11 12
15
A tile j appears after a tile i if either j appears on the same row as
i to the right of i, or on another row below the row of i.
For every i = 1, 2, ..., 15, let ni be the number of tiles j < i that
appear after tile i (permutation inversions)
N = n2 + n3 +  + n15 + row number of empty tile
1
3
4
5 10 7
8
9
2
6
11 12
13 14 15
n2 = 0
n5 = 0
n8 = 1
n11 = 0
n14 = 0
n3 = 0
n6 = 0
n9 = 1
n12 = 0
n15 = 0
n4 = 0
n7 = 1
n10 = 4
n13 = 0
N=7+4
30
Proposition: (N mod 2) is invariant under any
legal move of the empty tile
 Proof:

Any horizontal move of the empty tile leaves N
unchanged
 A vertical move of the empty tile changes N by an
even increment ( 1  1  1  1)

s=
1
2
5
6
3
4
1
2
7
5
6 11 7
9 10 11 8
13 14 15 12
s’ =
9 10
3
4
8
13 14 15 12
N(s’) = N(s) + 3 + 1
31




Proposition: (N mod 2) is invariant under any
legal move of the empty tile
 For a goal state g to be reachable from a state
s, a necessary condition is that N(g) and N(s)
have the same parity
It can be shown that this is also a sufficient
condition
 The state graph consists of two connected
components of equal size
32
SEARCHING THE STATE SPACE

It is often not feasible (or too expensive) to build
a complete representation of the state graph
33
8-, 15-, 24-PUZZLES
8-puzzle  362,880 states
0.036 sec
15-puzzle  2.09 x 1013 states
~ 55 hours
24-puzzle  1025 states
> 109 years
100 millions states/sec 34
INTRACTABILITY
Constructing the full state graph is intractable
for most interesting problems
 n-puzzle: (n+1)! states
 k-queens:
kk states

Tractability of search hinges on the
ability to explore only a tiny portion of
the state graph!
35
SEARCHING
36
SEARCHING THE STATE SPACE
Search tree
37
SEARCHING THE STATE SPACE
Search tree
38
SEARCHING THE STATE SPACE
Search tree
39
SEARCHING THE STATE SPACE
Search tree
40
SEARCHING THE STATE SPACE
Search tree
41
SEARCHING THE STATE SPACE
Search tree
42
SEARCH NODES AND STATES
8
2
3
4
7
5
1
6
8
2
7
3
4
5
1
If states are allowed to be revisited,
the search tree may be infinite even
when the state space is finite
6
8
2
8
2
8
3
4
7
3
4
7
3
5
1
6
5
1
6
5
4
1
2
8
2
7
3
4
6
5
1 43 6
7
DATA STRUCTURE OF A NODE
8
2
3
4
7
5
1
6
STATE
PARENT-NODE
BOOKKEEPING
CHILDREN
...
Action
Right
Depth
5
Path-Cost 5
Expanded
yes
Depth of a node N
= length of path from root to N
(depth of the root = 0)
44
8
NODE EXPANSION

The expansion of a node N of
the search tree consists of:
node generation  node
expansion
8 2
3
4
7
5
1
6
N
Evaluating the successor
function on STATE(N)
 Generating a child of N for
each state returned by the
function


2
8 4
2
7
3
4
7
3
5
1
6
5
1
6
8 2
3 4 7
5 1 45 6
FRINGE OF SEARCH TREE

The fringe is the set of all search nodes that
haven’t been expanded yet
8 2
3 4 7
5 1 6
8 2 7
3 4
5 1 6
8
2
3 4 7
5 1 6
8 2
3 4 7
5 1 6
8 2 7
3
4
5 1 6
8 2
3 4 7
5 1 6
Is it identical
to the set of
leaves?
47
SEARCH STRATEGY
The fringe is the set of all search nodes that
haven’t been expanded yet
 The fringe is implemented as a priority queue
FRINGE

INSERT(node,FRINGE)
 REMOVE(FRINGE)


The ordering of the nodes in FRINGE defines the
search strategy
48
SEARCH ALGORITHM #1
SEARCH#1
1. If GOAL?(initial-state) then return initial-state
2. INSERT(initial-node,FRINGE)
3. Repeat:
4. If empty(FRINGE) then return failure
5. N  REMOVE(FRINGE)
Expansion of N
6. s  STATE(N)
7. For every state s’ in SUCCESSORS(s)
8.
Create a new node N’ as a child of N
9.
If GOAL?(s’) then return path or goal state
10.
INSERT(N’,FRINGE)
49
PERFORMANCE MEASURES
Completeness
A search algorithm is complete if it finds a
solution whenever one exists
[What about the case when no solution exists?]
 Optimality
A search algorithm is optimal if it returns a
minimum-cost path whenever a solution exists
 Complexity
It measures the time and amount of memory
required by the algorithm

50
TOPICS OF NEXT 3-4 CLASSES

Blind (uninformed) Search


Heuristic (informed) Search


Little or no knowledge about how to search
How to use extra knowledge about the problem
Local Search

With knowledge about goal distribution
51
RECAP

General problem solving framework
State space
 Successor function
 Goal test
 => State graph


Search is a methodical way of exploring
alternatives
52
HOMEWORK
Register!
 Readings: R&N Ch. 3.4-3.5
 HW1

On OnCourse
 Writing and programming
 Due date: 9/6

53