Chapter 2
Problem solving
Basanta Joshi, PhD
basanta@[Link]
Lecture notes can be downloaded from
[Link]
Goal Based Agents
Goal Based Agents
• Assumes the problem environment is:
• Static
• The plan remains the same
• Observable
• Agent knows the initial state
• Discrete
• Agent can enumerate the choices
• Deterministic
• Agent can plan a sequence of actions such that each will lead to an
intermediate state
• The agent carries out its plans with its eyes closed
• Certain of what’s going on
• Open loop system
Well Defined Problems and Solutions
A problem
• Initial state
• Actions and Successor Function
• Goal test
• Path cost
Problem Solving
Problem Solving
Problem Solving
Problem Solving
Problem Solving
Problem Space
Problem Space
Problem Solving
Problem Solving
State
State
State space
Structure of State space
Problem solution
Problem solution
Problem Solving
Example: Measuring Problem
Example: Measuring Problem
Problem-Solving Agent
sensors
?
environment
agent
actuators
Problem-Solving Agent
sensors
?
environment
agent
actuators
• Formulate Goal
• Formulate Problem
•States
•Actions
• Find Solution
Assumptions
• World States
• Actions as transitions between states
• Goal Formulation: A set of states
• Problem Formulation:
The sequence of required actions to move from
current state to a goal state
Problem-Solving Agent
Example: Measuring Problem
Example: Measuring Problem
Environment types
Problem types
Problem types
Problem types
Problem types
Problem types
Components of well-defined problems
Components of well-defined problems
Example: Romania
On holiday in Romania; currently in Arad.
Flight leaves tomorrow from Bucharest
Formulate goal:
be in Bucharest
Formulate problem:
states: various cities
actions: drive between cities
Find solution:
sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest
Example: vacuum world
Problem Formulation
Example: Travelling from Arad to Bucharest
Single-state problem formulation
• A problem is defined by four items:
• initial state e.g., "at Arad”
• actions or successor function S(x) = set of action–state pairs
e.g., S(Arad) = {<Arad -->Zerind, Zerind>, <Arad -->Timisoara, Timisoara>, … }
• goal test, can be
explicit, e.g., x = "at Bucharest"
implicit, e.g., Checkmate(x)
• path cost (additive)
e.g., sum of distances, number of actions executed, etc.
c(x,a,y) is the step cost, assumed to be ≥ 0
A solution is a sequence of actions leading from the initial state to a goal state
Selecting a state space
Example Problems
Example: vacuum world
Multiple State Problem
Sensorless
Start in {1,2,3,4,5,6,7,8}
Solution?
[Right, Clean, Left, Clean]
Example: vacuum world
Contingency
Nondeterminism: Cleaning may
dirty a clean carpet.
Partially observable: Location, dirt at current
location.
Percept: [L, Clean], i.e., start in #5 or #7
Solution?
[Right, if dirt then Clean]
Vacuum world state space graph
States? Dirt and robot location
Actions? Left, Right, Clean
Goal test? No dirt at all locations
Path cost? 1 per action
Example: The 8-puzzle
States? Locations of tiles
Actions? Move blank left, right, up, down
Goal test? Given
Path cost? 1 per move
Example: Eight Puzzle
Eight puzzle is from a family of “sliding –block
puzzles”
NP Complete
8 puzzle has 9!/2 = 181440 states
15 puzzle has approx. 1.3*1012 states
24 puzzle has approx. 1*1025 states
Example: Eight Queens
Place eight queens on a chess
board such that no queen can Q
attack another queen
Q
Q
No path cost because only the Q
final state counts!
Q
Q
Incremental formulations Q
Q
Complete state formulations
Example: Eight Queens
States:Any arrangement of 0 to 8
queens on the board Q
Initial state:No queens on the board Q
Successor function:Add a queen Q
to an empty square
Q
Goal Test:8 queens on the board Q
and none are attacked
Q
64*63*…*57 = 1.8*1014
possible sequences Q
Ouch! Q
Example: Eight Queens
States:
Q
Arrangements of n queens, one
per column in the leftmost n Q
columns, with no queen attacking
another are states Q
Successor function: Q
Q
Add a queen to any square in the
leftmost empty column such that it Q
is not attacked by any other queen.
Q
2057 sequences to investigate
Q
Example: Cryptarithmatic
States? A cryptharithmetic puzzle w/ some letters replaced with digits.
Actions? Replacing a letter with an unused digit.
Goal test? Puzzle contains only digits.
Path cost? ZERO. All solutions equally valid.
Example: Missionaries and cannibals
problem formulation
State : 3 missionaries and 3 cannibals in the either side of
the river
Operators: either 1 missionary, 1 cannibal, 2
missionaries, 2 cannibals, or one of each across in the
boat.
Goal test: 3 missionaries and 3 cannibals in the other
side of the river
Path cost: the number of crossing
Example: robotic assembly
States? real-valued coordinates of robot joint angles parts of the object to be
assembled
Actions? continuous motions of robot joints
Goal test? complete assembly
Path cost? time to execute
Search Trees
Tree search algorithms
States Vs. Nodes
Tree search algorithms
Basic idea:
offline, simulated exploration of state space by
generating successors of already-explored states
(a.k.a.~expanding states)
Finding a solution
Finding a solution
Example: Travelling from Arad to Bucharest
Tree search example
Tree search example
Tree search example
State Graphs vs. search Trees
Encapsulating state information in nodes
Implementing general search
Implementing general search
Evaluation of search strategies