Artificial Intelligence
lecture 2
Problem solving by searching
Dr. Manel Mrabet
Dr. Manel Mrabet 2
Dr. Manel Mrabet 3
Dr. Manel Mrabet 4
Dr. Manel Mrabet 5
Agent program types
Simple reflex agents respond directly to percepts,
model-based reflex agents maintain internal state to
track aspects of the world that are not evident in the
current percept.
Goal-based agents act to achieve their goals,
utility-based agents try to maximize their own expected
“happiness.”
Learning agent improve their performance over time
Dr. Manel Mrabet 6
Solving Problem by Search
This chapter describes one kind of goal-based agent
called a problem-solving agent.
It’s an important aspect of intelligence
The solution of many problems can be described by finding
a sequence of actions that lead to a desirable goal.
Each action changes the state and the aim is to find
the sequence of actions and states that lead from the
initial (start) state to a final (goal) state.
Dr. Manel Mrabet 7
Solving Problem by Search
Problem-solving agents use atomic representations
Dr. Manel Mrabet 8
Formulating problems
A problem can be defined formally by 4 components:
1. An initial state, q(0)
2. A list of possible actions, a, for the agent
3.A goal test (there can be many goal states)
4. A path cost
One way to solve this is to search for a path
q(0) q(1) q(2) ... q(N)
such that q(N) is a goal state.
Dr. Manel Mrabet 9
Formulating problems
Example Problems: Vacuum world state space graph
Dr. Manel Mrabet 10
Vacuum world Formulating problems
[Link] state:
[Link] vacuum can be in any state of the 8 states
shown in the picture.
2. State description:
Successor function generates legal states resulting
from applying the three actions {Left, Right, and
Suck}.
The states space is shown in the picture, there are
8 world states.
3. Goal test:
[Link] whether all squares are clean.
4. Path cost:
[Link] step costs 1, so the path cost is the sum of
steps in the path.
Dr. Manel Mrabet 11
Formulating problems
Example Problems : 8-puzzle
• State: Specification of each of the
eight tiles in the nine squares (the
blank is in the remaining square).
• Initial state: Any state.
• Successor function (actions): Blank
moves Left, Right, Up, or Down.
• Goal test: Check whether the goal
state has been reached.
2 8 3 1 2 3
• Path cost: Each move costs 1. The
1 6 4 8 4
path cost = the number of moves.
7 5 7 6 5
Start State Goal State
Dr. Manel Mrabet 12
Formulating problems
Example Problems : 8-puzzle
• State: Specification of each of the
eight tiles in the nine squares (the
blank is in the remaining square).
• Initial state: Any state.
• Successor function (actions): Blank
moves Left, Right, Up, or Down.
Examples:
• Goal test: Check whether the goal
q state
= {7, 2,
has4,been
5, 0, 6, 8, 3, 1}
reached.
2 8 3 1 2 3
q• Path
= {2, cost: Each
8, 3, 1, 6, 4,move
7, 0, costs
5} 1. The
1 6 4 8 4
path cost = the number of moves.
7 5 7 6 5
Start State Goal State
Dr. Manel Mrabet 13
Formulating problems
Example Problems : 8-puzzle
• State: Specification of each of the
eight tiles in the nine squares (the
blank is in the remaining square).
• Initial state: Any state.
• Successor function (actions): Blank
moves Left, Right, Up, or Down.
• Goal test: Check whether the goal
state has been reached.
2 8 3 1 2 3
• Path cost: Each move costs 1. The
1 6 4 8 4
path cost = the number of moves.
7 5 7 6 5
Start State Goal State
Dr. Manel Mrabet 14
Formulating problems
Example Problems : expanding 8-puzzle
2 8 3
q = {2, 8, 3, 1, 6, 4, 7, 0, 5}
1 6 4
7 5
Blank moves left Blank moves right
Blank moves up
2 8 3 2 8 3 2 8 3
1 6 4 1 4 1 6 4
7 5 7 6 5 7 5
q = {2, 8, 3, 1, 6, 4, 0, 7, 5} q = {2, 8, 3, 1, 6, 4, 7, 5, 0}
q = {2, 8, 3,Dr. 1, 0, 4, 7, 6, 5}
Manel Mrabet 15
Example Problems : 8-puzzle solution
1 2 3 1 2 3
4 8 4 5 6
7 6 5 7 8
Initial state Goal state
Operators: slide blank up, slide blank down, slide blank left, slide blank right
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
4 8 4 8 5 4 8 5 4 5 4 5 4 5 6
7 6 5 7 6 7 6 7 8 6 7 8 6 7 8
Solution: sb-down, sb-left, sb-up,sb-right, sb-down
Path cost: 5 steps to reach the goal
Dr. Manel Mrabet 16
Example Problems : Missionaries and cannibals
The missionaries and cannibals:
Three missionaries and three cannibals are on one side of a river, along
with a boat that can hold one or two people (one for rowing). Find
a way to get everyone to the other side, without ever leaving a
group of missionaries in one place outnumbered by the cannibals
in that place (the cannibals eat the missionaries the
Dr. Manel Mrabet 17
Image from [Link]
Formulating problems
Example Problems : Missionaries and cannibals
State: q = (M,C,B) signifying the number of missionaries, cannibals, and boats
on the left bank.
The start state : (3,3,1)
Actions (successor function): (10 possible but only 5 available each
move due to boat)
One cannibal/missionary crossing L R: subtract (0,1,1) or
(1,0,1)
Two cannibals/missionaries crossing L R: subtract (0,2,1) or
(2,0,1)
One cannibal/missionary crossing R L: add (1,0,1) or
(0,1,1)
Two cannibals/missionaries crossing R L: add (2,0,1) or
(0,2,1)
One cannibal and one missionary crossing: add/subtract
(1,1,1)
goal state is (0,0,0).
Path Cost: Number of crossings. Dr. Manel Mrabet 18
Example Problems : Missionaries and cannibals state space
graph
Dr. Manel Mrabet 19
3,3,1 Example Problems :
Missionaries and cannibals
2,3,0 3,2,0
1,3,0
3,1,0 2,2,0 state space graph
3,2,1 3,2,1 2,3,1
1,2,0 3,0,0 2,1,0
3,1,1
2,1,0 1,1,0 2,0,0
2,1,1 1,2,1 1,3,1 2,2,1
(M,C,B) 0,2,0 2,0,0
1,2,0 2,1,0
Yellow state: repeated states
1,2,1 0,3,1 1,3,1
Red state: missionaries get eaten
0,1,0
1,1,1
0,2,1 2,1,1 1,2,1
Dr. Manel Mrabet 20
1,0,0 0,0,0 0,0,0
The River Problem
A farmer wishes to carry a wolf, a duck and corn across a river,
from the south to the north shore. The farmer is the proud
owner of a small rowing boat called Bounty which he feels is
easily up to the job. Unfortunately the boat is only large enough
to carry at most the farmer and one other item. Worse again, if
left unattended the wolf will eat the duck and the duck will eat
the corn.
River
boat
Farmer, Wolf,
Duck and Corn
How can the farmer safely transport the wolf, the duck and the corn to
the opposite shore?
Dr. Manel Mrabet 21
The River Problem
F=Farmer W=Wolf D=Duck C=Corn /=River
-/FWCD
FWCD/-
How can the farmer safely transport the wolf, the duck and the
corn to the opposite shore?
Dr. Manel Mrabet 22
Formulating problems
The River Problem
• State representation: location of farmer and items in both sides of
river
[items in South shore / items in North shore] : (FWDC/-, FD/WC, C/FWD …)
• Initial State: farmer, wolf, duck and corn in the south shore FWDC/-
• Goal State: farmer, duck and corn in the north shore -/FWDC
• Operators: the farmer takes in the boat at most one item from one
side to the other side
(F-Takes-W, F-Takes-D, F-Takes-C, F-Takes-Self [himself only])
• Path cost: the number of crossings
Dr. Manel Mrabet 23
Example Problems : The River Problem state space graph
FWDC/
WD/FC
WDC/F
WC/FD
DC/FW
FWC/D W/FDC
C/FWD FW/DC FWD/C
FC/WD FDC/W
WD/FC D/FWC
D/FWC
DC/FW
FWD/C
Yellow state: repeated states FD/WC
Red state: corn or duck get eaten
/FWDC
Problem solution: (path Cost = 7)
Dr. Manel Mrabet 24
River Crossing
Three couples go picnic together. They must move across
a river with only one boat carrying a maximum of 2
peoples. Help them move across the river, provided that
husbands would not allow their wives to go with another
man without their presence there.
How can the three couples cross the river?
Dr. Manel Mrabet 25
Formulating problems
Example Problems : River crossing
State: q = (M,W,B) signifying the number of men, women, and boats on the
right bank.
The start state : (3,3,1)
Actions (successor function):
One couple crossing R L
Two men/women crossing R L
One man/women crossing R L
One man/women crossing L R
Two men/women crossing L R
One couple crossing L R
goal state is (0,0,0).
Path Cost: Number of crossings. Dr. Manel Mrabet 26
GOAL STATE
Dr. Manel Mrabet 27
Summary
Search: process of constructing sequences of actions that
achieve a goal given a problem.
It is assumed that the environment is observable,
deterministic, static and completely known.
Goal formulation is the first step in solving problems by
searching. It facilitates problem formulation.
Formulating a problem requires specifying five components:
State representation, Initial state, Goal state, Operators
(actions), and Path cost function.
Dr. Manel Mrabet 28
