Introduction to State Space Search
Artificial Intelligence
CHAPTER 5
Introduction to
Artificial Intelligence
COURSE OBJECTIVES
Understand the state space representation and gain
familiarity with some common problems formulated as
state space search problems.
The students should be able to formulate it in terms of a
state space search problems.
The students should understand how implicit state spaces
can be unfolded during search.
Understand how states can be represented by features
Introduction to
Artificial Intelligence
REVIEW OF INTELLIGENT AGENT
Introduction to
Artificial Intelligence
A GOAL DIRECT AGENT
A goal direct agent needs to achieve
certain goals.
Many problems can be represented as a
set of states and a set of rules of how one
state is transformed to another.
The agent must choose a sequence of
actions to achieve the desired goal.
Introduction to
Artificial Intelligence
A GOAL DIRECT AGENT
Each state is an abstract representation
of the agents environment. It is an
abstract that denotes a configuration of
the agent.
Introduction to
Artificial Intelligence
Initial state: the description of the starting
configuration of the agent.
An action / operator takes the agent from
one state to another state. A state can
have a number of successor states.
A plan is a sequence of actions.
Introduction to
Artificial Intelligence
A goal is a description of a set of
desirable states of the world. Goal states
are often specified by a goal test which
any goal state must satisfy.
Path cost: path positive number
Usually path cost = sum of step
costs
Introduction to
Artificial Intelligence
Problem formulation means choosing a
relevant set of states to consider, and a
feasible set of operators for moving from
one state to another.
Introduction to
Artificial Intelligence
Search is the process of imagining
sequences of operators applied to the
initial state and checking which sequence
reaches a goal state.
Introduction to
Artificial Intelligence
S: the full set of states.
So: the initial state
A:S S set of operators
G: the set of final states.
Search problem: find a
sequence of actions
which transforms the
agent from the initial
state to a goal state
Introduction to
Artificial Intelligence
SEARCH PROBLEM
The search problem consists of finding a
solution plan, which is a path from the
current state to the goal state.
Introduction to
Artificial Intelligence
SEARCH PROBLEM
Representing search problems.
A search problem is represented using a
directed graph.
• The states are represented as nodes.
• The allowed actions are represented as arcs
Introduction to
Artificial Intelligence
SEARCHING PROCESS
Check the current state
Execute allowable actions to move to the
next state.
Check if the new state is a solution state.
If it is not, the new state becomes the current
state and the process is repeated until a
solution is found or the state space is
exhausted.
Introduction to
Artificial Intelligence
STATE SPACE
Introduction to
Artificial Intelligence
STATE SPACE
Introduction to
Artificial Intelligence
STATE SPACE
Introduction to
Artificial Intelligence
STATE SPACE
Introduction to
Artificial Intelligence
STATE SPACE
Introduction to
Artificial Intelligence
STATE SPACE
Introduction to
Artificial Intelligence
PEGS AND DISKS
Consider the following
problem. We have 3 pegs
and 3 disks.
Operators: one may
move the topmost disks
on any needle to the
topmost position to any
other needle.
Introduction to
Artificial Intelligence
STATE SPACE
Introduction to
Artificial Intelligence
STATE SPACE
Introduction to
Artificial Intelligence
STATE SPACE
Introduction to
Artificial Intelligence
STATE SPACE
Introduction to
Artificial Intelligence
STATE SPACE
Introduction to
Artificial Intelligence
STATE SPACE
Introduction to
Artificial Intelligence
STATE SPACE
Introduction to
Artificial Intelligence
STATE SPACE
FINISH
Introduction to
Artificial Intelligence
Class Work: the 8-Puzzle
Map by configuring the start state of the
8 puzzle into the given goal configuration
29
Introduction to Solution
Artificial Intelligence
30
Introduction to
Artificial Intelligence
8 Puzzle - Magic squares
Put the numbers 1,2,3, 4, 5, 6, 7, 8, 9 into a
3 x 3 square to make a magic square. In this
3x3 magic square, the numbers in each
vertical row must add up to 15.
The numbers in each horizontal row must
add up to 15. The diagonals also add up to
15.15 is called the magic number.
31
Introduction to
Artificial Intelligence
8 Puzzle - Magic squares
Solution
32
Introduction to
Artificial Intelligence
Missionaries and cannibals
Three missionaries and three cannibals are on the left
bank of a river.
There is one canoe which can hold one or two people.
Find a way to get everyone to the right bank, without
ever leaving a group of missionaries in one place
outnumbered by cannibals in that place.
07/20/21 33
Introduction to
Artificial Intelligence
Missionaries and Cannibals
R
I
V
E
R
07/20/21 34
Introduction to
Artificial Intelligence
Missionaries and Cannibals
A missionary and cannibal cross
R
I
V
E
R
07/20/21 35
Introduction to
Artificial Intelligence
Missionaries and Cannibals
R
I
V
E
R
07/20/21 36
Introduction to
Artificial Intelligence
Missionaries and Cannibals
One missionary returns
R
I
V
E
R
07/20/21 37
Introduction to
Artificial Intelligence
Missionaries and Cannibals
R
I
V
E
R
07/20/21 38
Introduction to
Artificial Intelligence
Missionaries and Cannibals
Two cannibals cross
R
I
V
E
R
07/20/21 39
Introduction to
Artificial Intelligence
Missionaries and Cannibals
R
I
V
E
R
07/20/21 40
Introduction to
Artificial Intelligence
Missionaries and Cannibals
A cannibal returns
R
I
V
E
R
07/20/21 41
Introduction to
Artificial Intelligence
Missionaries and Cannibals
R
I
V
E
R
07/20/21 42
Introduction to
Artificial Intelligence
Missionaries and Cannibals
Two missionaries cross
R
I
V
E
R
07/20/21 43
Introduction to
Artificial Intelligence
Missionaries and Cannibals
R
I
V
E
R
07/20/21 44
Introduction to
Artificial Intelligence
Missionaries and Cannibals
A missionary and cannibal return
R
I
V
E
R
07/20/21 45
Introduction to
Artificial Intelligence
Missionaries and Cannibals
R
I
V
E
R
07/20/21 46
Introduction to
Artificial Intelligence
Missionaries and Cannibals
Two Missionaries cross
R
I
V
E
R
07/20/21 47
Introduction to
Artificial Intelligence
Missionaries and Cannibals
R
I
V
E
R
07/20/21 48
Introduction to
Artificial Intelligence
Missionaries and Cannibals
A cannibal returns
R
I
V
E
R
07/20/21 49
Introduction to
Artificial Intelligence
Missionaries and Cannibals
R
I
V
E
R
07/20/21 50
Introduction to
Artificial Intelligence
Missionaries and Cannibals
Two cannibals cross
R
I
V
E
R
07/20/21 51
Introduction to
Artificial Intelligence
Missionaries and Cannibals
R
I
V
E
R
07/20/21 52
Introduction to
Artificial Intelligence
Missionaries and Cannibals
A cannibal returns
R
I
V
E
R
07/20/21 53
Introduction to
Artificial Intelligence
Missionaries and Cannibals
R
I
V
E
R
07/20/21 54
Introduction to
Artificial Intelligence
Missionaries and Cannibals
The last two cannibals cross
R
I
V
E
R
07/20/21 55
Introduction to
Artificial Intelligence
Missionaries and Cannibals
R
I
V
E
R
07/20/21 56
Class Work:
Introduction to
Artificial Intelligence
4 Missionaries and 4 Cannibals
R
I
V
E
R
07/20/21 57
Introduction to
Artificial Intelligence
Class Work
A man is headed to a mountain along with a lion, a goat, and a basket of
vegetables. On the way, he needs to cross a river and the boat can only carry
two things at a time. If he takes the vegetables, the lion will eat the goat. If he
takes the lion, the goat will eat the vegetables. How does he cross the river?
58
Introduction to
Artificial Intelligence