Introduction to

Artificial Intelligence
Lecture: Problem Solving Using Searching
Outline

● Problem-Solving Agents
● Example Problems
● Searching for Solutions

2
Holiday in Romania

3
Goal-based Agents

● Intelligent agents maximize their performance measure.

● Goals help organize behavior by limiting the objectives that the
agent is trying to achieve and the actions it considers.

4
Problem Formulation

● Consider a goal to be a set of world states in which the

objective is satisfied.
● Problem formulation is the process of deciding what actions
and states to consider, given a goal.

5
Properties of the Romania environment

● Observable
○ Each city has a sign indicating its presence for arriving
drivers.
○ The agent always knows the current state.
● Discrete
○ Each city is connected to a small number of other cities.
○ There are only finitely many actions to choose from any
given state.
● Known
○ The agent knows which states are reached by each action.
● Deterministic
○ Each action has exactly one outcome.

6
Solving problem by searching

● Search: 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.
● Execution phase: once a solution is found, the recommended
actions are carried out.

7
Solving problem by searching

function PROBLEM-SOLVING-AGENT(percept) returns an action

persistent: seq, an action sequence, initially empty
state, some description of the current world state
goal, a goal, initially null
problem, a problem formulation
state ← UPDATE-STATE(state, percept)
if seq is empty then
goal ← FORMULATE-GOAL(state)
problem ← FORMULATE-PROBLEM(state, goal)
seq ← SEARCH(problem)
if seq = failure then return a null action
action ← FIRST(seq)
seq ← REST(seq)
return action 8
Well-defined problems and solutions

● A problem can be defined formally by five components.

○ Initial state: in which the agent starts
■ E.g., the agent in Romania has its initial state described
as 𝐼𝑛(𝐴𝑟𝑎𝑑)
○ Actions: the possible actions available to the agent
■ E.g., 𝐴𝐶𝑇𝐼𝑂𝑁(𝐴𝑟𝑎𝑑) = {
𝐺𝑜(𝑆𝑖𝑏𝑖𝑢), 𝐺𝑜(𝑇𝑖𝑚𝑖𝑠𝑜𝑎𝑟𝑎), 𝐺𝑜(𝑍𝑒𝑟𝑖𝑛𝑑)}
○ Transition model: what each action does
■ E.g., 𝑅𝑒𝑠𝑢𝑙𝑡(𝐼𝑛(𝐴𝑟𝑎𝑑), 𝐺𝑜(𝑍𝑒𝑟𝑖𝑛𝑑)) = 𝐼𝑛(𝑍𝑒𝑟𝑖𝑛𝑑)
○ Successor: a state reachable from a given state by a single
action

9
Well-defined problems and solutions

○ Goal test: determine whether a given state is a goal state

■ The goal is specified by either an explicit set of possible
goal states or an abstract property.
■ E.g., 𝐼𝑛(𝐵𝑢𝑐h𝑎𝑟𝑒𝑠𝑡), checkmate
○ Path cost: a function that sets a numeric cost to each path
■ Non-negative, reflecting the agent’s performance
measure
■ E.g., 𝑐(𝐼𝑛(𝐴𝑟𝑎𝑑),𝐺𝑜(𝑍𝑒𝑟𝑖𝑛𝑑),𝐼𝑛(𝑍𝑒𝑟𝑖𝑛𝑑)) = 75
● An optimal solution has the lowest path cost.

10
Formulating problems by abstraction

● Abstraction creates an approximate and simplified model of the

real world, which is too detailed for computer.
● This is critical for automated problem solving.
● The choice of a good abstraction involves
○ Remove as much detail as possible while
○ Retain validity and ensure that the abstract actions are easy
to be carried out.

11
The Vacuum-cleaner world

● States: determined by both the agent location and the dirt

locations
○ 2 x 22 = 8 possible world states (𝑛 × 2𝑛 in general)
● Initial state: Any state can be designated as the initial state.
● Actions: Left, Right, and Suck
● Transition model: The actions have their expected effects.
● Goal test: whether all the squares are clean
● Path cost: each step costs 1

12
The Vacuum-cleaner world

13
The 8-puzzle

● States: the location of each of the eight tiles and the blank
● Initial state: any state can be designated as the initial state
● Actions: movements of the blank space
○ Left, Right, Up, or Down.
○ Different subsets of these are possible depending on where
the blank is
● Transition model: return a resulting state given a state and an
action
● Goal test: whether the state matches the goal configuration
● Path cost: each step costs 1

14
The 8-puzzle

15
The 8-queens

● Incremental formulation: add a queen step-by-step to the empty

initial state
● Complete-state formulation: start with all 8 queens on the board
and move them around
● The path cost is trivial because only the final state counts

16
The 8-queens

● States: any arrangement of 0 to 8 queens on the board

● Initial state: no queens on the board
● Actions: add a queen to any empty square
● Transition model: returns the board with a queen added to the
specified square
● Goal test: 8 queens are on the board, none attacked
● 64 ∙ 63 ⋯ 57 ≈ 1.8 × 1014 possible sequences to investigate

17
Search Tree

● Search algorithms consider many possible action sequences to

find the solution sequence.
● Search tree: the possible action sequences starting at the initial
state (root)
○ Branches are actions and nodes are states in the problem’s
state space
● Frontier: the set of all leaf nodes available for expansion at any
given point
● Search algorithms all share the basic structure while vary
according to how they choose which state to expand next --
called search strategy.

18
Search Tree

19
Search Tree

function TREE-SEARCH(problem) returns a solution, or failure

initialize the frontier using the initial state of problem
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
if the node contains a goal state then return the
corresponding solution
expand the chosen node, adding the resulting nodes to the
frontier

20
Redundant paths

● Redundant paths are unavoidable.

● Following redundant paths may cause a tractable problem to
become intractable.
● This is true even for algorithms that know how to avoid infinite
loops.

21
Graph Search

function GRAPH-SEARCH(problem) returns a solution, or failure

initialize the frontier using the initial state of problem
initialize the explored set to be empty
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
if the node contains a goal state then return the
corresponding solution
add the node to the explored set
expand the chosen node, adding the resulting nodes to the
frontier only if not in the frontier nor explored set 22
Graph Search

23
Infrastructure for search algorithms

● Each node 𝑛 is structuralized by four components.

○ 𝒏. 𝐒𝐓𝐀𝐓𝐄: the state in the state space to which the node
corresponds
○ 𝒏. 𝐏𝐀𝐑𝐄𝐍𝐓: the node in the search tree that generated the
node 𝑛
○ 𝒏. 𝐀𝐂𝐓𝐈𝐎𝐍: the action applied to the parent to generate 𝑛
○ 𝒏. 𝐏𝐀𝐓𝐇 − 𝐂𝐎𝐒𝐓 : the cost, denoted by 𝒈(𝒏), of the path
from the initial state to the node, as indicated by the parent
pointer
● Frontier can be implemented with a (priority) queue or stack.
● Explored set can be a hash table that allows for efficient
checking of repeated states.

24
Infrastructure for search algorithms

25
Problem-solving performance

● Completeness: does it always find a solution if one exists?

● Time complexity: how long does it take to find a solution?
● Space complexity: how much memory is needed to perform
the search?
● Optimality: does it always find a least-cost solution?

26
Homework

● Task 1:
○ Given the start state and the goal one of the 8-puzzle in
page 15.
○ Students draw a search tree by the expanding nodes.
○ The expansion stops when the goal state is expanded.
● Task 2:
○ Program Task 1 in Python using Google Colab
○ Use graph search instead of tree search

27
Homework

1 8 2 8 2 8 2
D L
4 3 1 4 3 1 4 3

7 6 5 7 6 5 7 6 5
U
1 8 2 1 8 2
L 1 2
7 4 3 7 4 3
L 6 5 6 5
4 8 3

7 6 5
1 8 2 D
4 3 1 8 2
U
7 6 5 4 6 3
1 8 2
L 7 5
4 3

7 6 5 28
Homework

from graphviz import Digraph

dot = Digraph()
[Link]('0', '182\n_43\n765')
[Link]('1', '182\n4_3\n765')
[Link]('2', '_82\n143\n765')
[Link]('3', '182\n743\n_65')
[Link]('0', '1', 'L')
[Link]('0', '2', 'D')
[Link]('0', '3', 'U')

dot

29
Homework

● Conduct homework in the given notebook

30
References

● Stuart Russell and Peter Norvig. 2009. Artificial Intelligence: A

Modern Approach (3rd ed.). Prentice Hall Press, Upper Saddle
River, NJ, USA.
● Lê Hoài Bắc, Tô Hoài Việt. 2014. Giáo trình Cơ sở Trí tuệ nhân
tạo. Khoa Công nghệ Thông tin. Trường ĐH Khoa học Tự
nhiên, ĐHQG-HCM.
● Nguyễn Ngọc Thảo, Nguyễn Hải Minh. 2020. Bài giảng Cơ sở
Trí tuệ Nhân tạo. Khoa Công nghệ Thông tin. Trường ĐH Khoa
học Tự nhiên, ĐHQG-HCM.

31