ARTIFICIAL INTELLIGENCE

2
 Problem Solving
Russell and Norvig: Chapter 3
 Outline
• Problem-solving agents
• Components of Well-Defined Problem
• Problem formulation
• Example problems
• Basic search algorithms
 Problem-solving agents
• In this chapter we consider a type of Goal-Based
Agent, known as Problem Solving Agent that uses
atomic representation.
• Atomic Representation: Consist of indivisible states,
i.e., that has no internal structure.
Example (Atomic Representation)
Finding the route from one part of the country to the other through
some sequence of cities. For simplicity, only city names can represent
the states of the world i.e., single atom or black box.

• Obviously, we can have goal-based agents with

more advanced state representations.
Problem-Solving Agent
sensors

?
environment
agent

actuators
• Formulate Goal
• Formulate Problem
•States
•Actions
• Find Solution
 Problem solving
Goal Formulation : is the first step in problem solving and it
is based on the current situation and the
agent’s performance measure.
It helps to simplify the decision problem.
Goal is normally considered to be set of
states in which the Goal is satisfied.
Problem Formulation : is the process of deciding what
actions and states to consider, given a
goal.
• It is not necessary that in the initial stage the agent action
on the current state (transition) results in achieving the
goal.
• Then generally an agent with several immediate options of
unknown value can decide what to do by first examining
future actions that eventually lead to states of known
 Problem solving
Search-Solution-Execute
Search is the process of looking for a sequence of actions that
reaches the goal.
A search algorithm takes a problem as input and returns a
solution in the form of an action sequence.
Once a solution is found, the actions it recommends can be
carried out. This is called the execution.
Simple Problem-Solving Agent
 Components of Well-Defined Problem

• Initial State
• Actions
• Transition Model
• Goal Test
• Path Cost
 Components of a problem

Definition (Initial State)

As name suggest, the initial state agent starts in. For example,
in tourist example, the initial state of our agent is in Arad, i.e.,
IN(Arad).

Definition (Actions)
Description of possible actions given a particular state s, i.e.,
ACTIONS(s) will return all possible actions executable in s
and these set of actions will be called applicable in s. For
example, {Go(Sibiu), Go(Timisoara), Go(Zerind)} are
applicable in state Arad.
 Components of a problem
Definition (Transition Model)
Describes each action a with respect to state s. i.e.,
RESULT(s,a) will return the state that result by doing action a
in state s. For example, RESULT(IN(Arad),Go(Zerind)) =
IN(Zerind)

Definition (State Space)

The initial state, set of actions and the transition model forms
a state space. It is the set of all possible states reachable from
initial state by any sequence of action. State space forms a
graph or directed network, where nodes are states and links
represent the action. A Path in the state space describes the
sequence of states connected by sequence of actions.
 Components of a problem

Definition (Goal Test)

That determines the given state is goal or not. It is not always
as simple as in our example, i.e., to be in Bucharest, for
example, in a chess game, the goal state is “Checkmate”.

Definition (Path Cost)

A function that assigns cost to each path. The cost function in
problem solving agents is their performance measure. For
example, in our tourist example, the cost is the distance
between states that reflects time. The path cost, in simple
case, can be described by the sum of costs of actions along the
path. We denote it by C(s,a,s’), where s is the current state, a is
the action and s’ is the resulting state.
 Solution and Optimal Solution

Solution is set of actions that leads from initial state to goal

state, there may be many solution for a problem solving
agent.
The quality of this solution is measured by the path cost and
the solution with minimum path cost is called Optimal
Solution.
 Problem Formulation
• All five components, initial state, actions, transition model,
goal test and path cost defined above forms a problem
formulation.
• This formulation is abstract, i.e., details are hidden.
• Abstraction is useful since they simplify the problem by
hiding many details but still covering the most important
information about states and actions (retaining the state
space in simple form), therefore abstraction needs to be
valid.
• Abstraction is called valid when the abstract solution can
be expanded to more detailed world.
• Abstraction is useful if the actions in the solution are easier
than the original problem, i.e, no further planning and
searching.
• Construction of useful and valid abstraction is challenging.
Example: Route finding
 Romania

 Seorang agent sedang berlibur dan

sekarang berada di kota Arad, Romania.
 Besok dia harus naik pesawat dari
Bucharest
 Goal dari agent sekarang adalah pergi ke
Bucharest
 Action yang tidak berhubungan dengan
goal akan dibuang  decision agent lebih
sederhana
 Romania

 Agent  Mencapai tujuan (Bucharest)

dengan naik mobil
 Kemana akan pergi setelah dari Arad ?
 Ada tiga jalan : ke Sibiu, Timisoara, Zerind
 Agent masih belum mengetahui jalan di
sana (mana yang tercepat), tetapi hanya
memiliki peta.
 Dari informasi peta, maka dilakukan
hipotesa terhadap ketiga jalur tsb. untuk
sampai ke Bucharest.
 Romania : Agent and Environment

 Static
Tidak perlu memperhatikan perubahan
yang terjadi pada environment
 Observable
Ada peta, initial state diketahui (di Arad)
 Discrete
Enumeration action
 Deterministic
Tidak bisa menangani terhadap hal-hal
yang tidak diperkirakan
 Romania : Well-defined problem agent

 Initial State  di Arad

 Actions : Successor function 
{<Go(Sibiu),In(Sibiu)>,
<Go(Timisoara),In(Timisoara)>,
<Go(Zerind),In(Zerind)>}
 Goal Test  In(Bucharest)
 Path Cost  di slide berikutnya …
Path cost solusi agent

States
Actions

Start Solution

Goal
 Romania : Formulate goal, formulate
problem, and solution

• Formulate Goal:
Be in Bucharest
• Formulate Problem:
States: various cities
Actions: drive between cities
• Find solution:
Sequence of cities: Arad, Sibiu, Fagaras, Bucharest
 Types of Problems

• Toy Problems : Intended to illustrate or exercise

various problem-solving methods. It can
be given a concise, exact
description and hence is usable by
different researchers to compare the
performance of algorithms.

• Real World Problems : has importance and whose

solutions people actually care about.
Such problems tend not to have a
single agreed-upon description, but we
can give the general flavor of their
formulations.
 Toy Problem : 8-puzzle
 Consist of 3  3 board with eight numbered tiles and a
blank space.
 A tile adjacent to the blank space can slide into the space.
 The objective is to reach a specified goal state, such as the
one shown in the figure.

8 2 1 2 3

3 4 7 4 5 6

5 1 6 7 8

Initial state Goal state

 8-puzzle : Problem formulation
 States: A state description specifies the location of each of
the eight tiles and the blank in one of the nine squares.
 Initial state: Any state can be designated as the initial state.
Note that any given goal can be reached from exactly
half of the possible initial states.
 Actions: The simplest formulation defines the actions as
movements of the blank space Left, Right, Up, or
Down.
 Transition model: Given a state and action, this returns the
resulting state; for example, if we apply Left to the
start state in Figure above, the resulting state has the 5
and the blank switched.
 Goal test: The goal configuration shown in Figure above
(Other goal configurations are possible.)
 Path cost: Each step costs 1, so the path cost is the number of
steps in the path.
 Description: 8-puzzle
 Belongs to the family sliding-block puzzles.
 Often used as a test problem for new AI algorithms.
 Has 181440 reachable states.
 Best search algorithm may take few milliseconds to solve
from any random initial state.

Size of the state space = 9!/2 = 181,440

15-puzzle  .65 x 1012

(4  4 board)
0.18 sec
24-puzzle  .5 x 1025 6 days
(5  5 board)
12 billion years

10 million states/sec
Toy problem: 8-queens

Place 8 queens in a chessboard so that no two queens

are in the same row, column, or diagonal.

A solution Not a solution

8-queens: Problem formulation

Formulation #1:
• States: any arrangement of 0 to 8
queens on the board
• Initial state: 0 queens on the
board
• Successor function: add a queen in
any square
• Goal test: 8 queens on the board,
none attacked

 648 states with 8 queens

 8-queens: Problem formulation
Formulation #2:
• States: any arrangement of k = 0
to 8 queens in the k leftmost
columns with none attacked
• Initial state: 0 queens on the
board
• Successor function: add a queen
to any square in the
leftmost empty column such
that it is not attacked by any other
queen
• Goal test: 8 queens on the
 2,067 states board.
 Real World Problems
 Airline Travel Problem
 Touring Problem
 Traveling Salesman Problem
 VLSI (Very Large Scale Integration)
Layout
 Robot Navigation
 Automatic Assembly Sequencing
 Internet Searching
Real World Problems
Automatic Assembly Sequencing
(How a car is made - VW Germany (Dec 2015))