COE206 – Principles of Artificial

Intelligence
Mustafa MISIR

Istinye University, Department of Computer Engineering

[Link]@[Link]

[Link]
[Link]
L3: Problem Solving
Search Strategies

1 / 68
Outline

I Problem Solving Agents

I Example Problems
I Searching for Solutions

2 / 68
Outline

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

3 / 68
Problem Solving Agents

The focus is a specific goal-based agent called a

problem-solving agent.
I using atomic representations

4 / 68
Problem Solving Agents – Goal

Goal formulation, based on the current situation and the agent’s

performance measure, is the first step in problem solving.
I A goal is a set of world states—exactly those states in which
the goal is satisfied.
I The agent’s task is to find out how to act, now and in the
future, so that it reaches a goal state.

5 / 68
Problem Solving Agents – Problem

Problem formulation is the process of deciding what actions and

states to consider, given a goal.
I e.g. the agent will consider actions at the level of driving from
one major town to another. Each state therefore corresponds
to being in a particular town.

6 / 68
Problem Solving Agents – e.g. Trip to Bucharest

Our agent has now the goal of driving to Bucharest and is

considering where to go from Arad.
I Three roads lead out of Arad, one toward Sibiu, one to
Timisoara, and one to Zerind.

Yet,
I the agent will not know which of its possible actions is best,
because it does not yet know enough about the state that
results from taking each action.
I If the agent has no additional information—i.e., if the
environment is unknown, then it is has no choice but to try
one of the actions at random.

7 / 68
Problem Solving Agents

I The process of looking for a sequence of actions that reaches

the goal is called search.
I A search algorithm takes a problem as input and returns a
solution in the form of an action sequence.
I Once a solution is found, the actions it recommends can be
carried out. This is called the execution phase.

8 / 68
Problem Solving Agents

1. Formulate a goal and a problem

2. Search for a sequence of actions that would solve the problem
3. Execute the actions one at a time
4. When this is complete, formulate another goal and start over
...

9 / 68
Problem Solving Agents

10 / 68
Problem

A problem can be defined formally by five components:

1. an initial state that the agent starts in
2. a description of the possible actions available to the agent
3. a description of what each action does – transition models
The initial state, actions, and transition model implicitly define the
state space of the problem—the set of all states reachable from
the initial state by any sequence of actions.

4. The goal test, which determines whether a given state is a

goal state.
5. A path cost function that assigns a numeric cost to each path.

11 / 68
Problem – e.g. Trip to Bucharest

1. initial state: start from the city of Arad, In(Arad)

2. actions: from the state In(Arad), the applicable actions are {
Go(Sibiu), Go(T imisoara), Go(Zerind) }.
3. transition model: specified by a function RESULT(s, a) that
returns the state that results from doing action a in state s,
e.g. RESULT(In(Arad), Go(Zerind)) = In(Zerind).
4. goal test: { In(Bucharest) }
5. path cost: distance traveled in km

A solution to a problem is an action sequence that leads from the

initial state to a goal state.
I Solution quality is measured by the path cost function, and an
optimal solution has the lowest path cost among all solutions.

12 / 68
Problem Solving Agent
The path cost is the sum of the individual actions’ costs, i.e. the
step cost, taking action a in state s to reach state s0 , c(s, a, s0 )

13 / 68
Outline

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

14 / 68
Toy Problems: e.g. Vacuum World
TASK : Determine the following aspects for a Vacuum Cleaner
scenario:
I All the states, initial state, actions, transition model, goal
test and path cost.

Submit photo of your answer to Piazza as a private message.

Also, deliver its hard copy.

15 / 68
Toy Problems: e.g. Vacuum World
Here is the state space for the vacuum world. Links denote
actions: L = Left, R = Right, S = Suck.

16 / 68
Toy Problems: e.g. Vacuum World

I States: The state is determined by both the agent and the

dirt locations. There are 2 × 22 = 8 possible world states.
I Initial state: Any state can be designated as the initial state.
I Actions: Each state has 3 actions: Left, Right, and Suck.
Larger environments might also include Up and Down.
I Transition model: The actions have their expected effects,
except moving Left and Right in the leftmost and rightmost
squares respectively, and Sucking in a clean square.
I Goal test: This checks whether all the squares are clean.
I Path cost: Each step costs 1, so the path cost is the number
of steps in the path.

17 / 68
Toy Problems: e.g. 8-Puzzle 1

A 3 × 3 board with 8 numbered tiles and a blank space, belonging

to the family of sliding-block puzzles.
I A tile adjacent to the blank space can slide into the space.

1
[Link]
18 / 68
Toy Problems: 8-Puzzle

I States: A state description specifies the location of each of

the eight tiles and the blank in one of the nine squares.
I Initial state: Any state can be designated as the initial state.
I Actions: The simplest formulation defines the actions as
movements of the blank space Left, Right, Up, or Down.
I Transition model: Given a state and action, this returns the
resulting state.
I Goal test: This checks whether the state matches the goal
configuration.
I Path cost: Each step costs 1, so the path cost is the number
of steps in the path.

19 / 68
Toy Problems: 8-Queens

Place 8 queens on a chessboard

such that no queen attacks any
other. (A queen attacks any piece 2

in the same row, column or diag-

onal)

2
In chess, the queen can be moved any number of unoccupied squares in a straight line vertically, horizontally, or diagonally:
[Link]
20 / 68
Toy Problems: 8-Queens

I States: Any arrangement of 0 to 8 queens on the board is a

state.
I Initial state: No queens on the board.
I Actions: Add a queen to any empty square.
I Transition model: Returns the board with a queen added to
the specified square.
I Goal test: 8 queens are on the board, none attacked.
I Path cost: Irrelevant

This formulations has a state space of size

64 × 63 × . . . × 57 = 1.8 × 1014 possible sequences.

21 / 68
Toy Problems: 8-Queens

A better formulation would prohibit placing a queen in any square

that is already attacked:
I States: All possible arrangements of n queens (0 6 n 6 8),
one per column in the leftmost n columns, with no queen
attacking another.
I Actions: Add a queen to any square in the leftmost empty
column such that it is not attacked by any other queen.

This formulation reduces the state space.

22 / 68
Toy Problems: Knuth’s Conjecture - Infinite State Spaces
Starting from number 4, any desired integer number can be
reached via a sequence of factorial, square root, and floor
operations.
vs 
u r 
u q p 
(4!)! = 5
t 


I States: Positive numbers.

I Initial state: 4.
I Actions: Apply factorial, square root, or floor operation
(factorial for integers only).
I Transition model: As given by the mathematical definitions
of the operations.
I Goal test: State is the desired positive integer.
23 / 68
Toy Problems: Tic-Tac-Toe 3

TASK : Determine the following aspects for a Tic Tac Toe game:
I All the states, initial state, actions, transition model, goal
test and path cost.

Submit photo of your answer to Piazza as a private message.

Also, deliver its hard copy.
3
[Link] – Google Search: Tic Tac Toe
24 / 68
Toy Problems: Tic-Tac-Toe 4

TASK : Draw / list the state space for the following game setting:

Submit photo of your answer to Piazza as a private message.

Also, deliver its hard copy.

4
[Link] – Google Search: Tic Tac Toe
25 / 68
Real-world Problems: e.g. Route-Finding

Consider the airline travel problem that must be solved by a

travel-planning Web site:
I States: Each state includes a location and the current time.
I Initial state: This is specified by the user’s query.
I Actions: Take any flight from the current location, in any
seat class, leaving after the current time, leaving enough time
for within-airport transfer if needed.
I Transition model: The state resulting from taking a flight
will have the flight’s destination as the current location and
the flight’s arrival time as the current time.
I Goal test: Are we at the final destination?
I Path cost: This depends on monetary cost, waiting time,
flight time, seat quality etc.

26 / 68
Real-world Problems: e.g. Touring

Closely related to route-finding problems, but with an important

difference.
I Each state must include not just the current location but also
the set of cities the agent has visited.
I So the initial state would be In(Bucharest),
Visited({Bucharest})
I A typical intermediate state would be In(Vaslui),
Visited({Bucharest, Urziceni, Vaslui})
I The goal test would check whether the agent is in Bucharest
and all 20 cities have been visited.

27 / 68
Real-world Problems: e.g. TSP
Traveling Salesperson Problem (TSP) 5

I Visit each city exactly once and return back to the starting
city.

5
image source: [Link] – example TSP solution while solving:
[Link]
28 / 68
Real-world Problems: e.g. VLSI Layout
VLSI layout requires positioning millions of components and
6

connections on a chip to minimize area, minimize circuit delays,

minimize stray capacitances, and maximize manufacturing yield.

6
[Link] Very large-scale integration is the process of creating an integrated circuit
[Link]
by combining millions of MOS transistors onto a single chip – image source:

29 / 68
Real-world Problems: e.g. Robot Navigation

Robot navigation 7

I Rather than following a discrete set of routes, a robot can

move in a continuous space with (in principle) an infinite set
of possible actions and states.

7
image source: [Link] 8220/19/13/2993/htm
30 / 68
Real-world Problems: e.g. Automatic Assembly Sequencing
Specifying an order in which to assemble the parts of some object.
I If the wrong order is chosen, there will be no way to add some
part later in the sequence without undoing some of the work
already done.

31 / 68
Real-world Problems: e.g. Protein Design 8

The goal is to find a sequence of amino acids that will fold into a
3D protein with the right properties to cure some disease.

8
image source: [Link]
32 / 68
Outline

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

33 / 68
Searching for Solutions

A solution is an action sequence, so search algorithms work by

considering various possible action sequences.
I The possible action sequences starting at the initial state
form a search tree with the initial state at the root.
I The branches are actions and the nodes correspond to states
in the state space of the problem.
I The root node refers to the initial state.

The set of all leaf nodes available for expansion at any given point
is called the frontier (open list) while already expanded nodes can
be kept in the explored set (closed list).

34 / 68
Graphs 9

A graph G is a collection of (V, E) pairs where

I V : a set of vertices or nodes
I E: a set of edges connecting the vertices

9
adapted from the slides of CS 5002: Discrete Math – Northeastern University: [Link]
35 / 68
Graphs

I Vertices:
V = {A, B, C, D, E, F }
I Edges: E = { (A, B),
(A, D), (B, C), (C, D),
(C, E), (D, E) }

36 / 68
Graphs – Types

I Directed vs. Undirected

I Labeled vs. Unlabeled
I Weighted vs. Unweighted
I Simple vs. Non-simple
I Sparse vs. Dense
I Cyclic vs. Acyclic

37 / 68
Graphs – Directed vs. Undirected

Undirected if edge (x, y) implies

edge (y, x), otherwise Directed
I Roads between cities usually
undirected (both ways)
I Streets in cities tend to be
directed (one-way)

38 / 68
Graphs – Labeled vs. Unlabeled 11

Each vertex is assigned a unique

name or identifier in a Labeled
graph, otherwise Unlabeled
I e.g. city names in a
transportation network
I While labeled graphs mean
vertex-labeled graphs, there
are also edge-labeled
graphs .
10

10
[Link]
11
[Link]
39 / 68
Graphs – Weighted vs. Unweighted
Weighted (a special type of la-
beled graphs – vertex-labeled) if
each edge or vertex is assigned to
a numerical value (weight), other-
wise Unweighted
I A road network might be
weighted with length,
drive-time and speed-limit
I Streets in cities tend to be
directed (one-way)

Traditionally, weighted graphs

mean edge-weighted graphs. Yet,
vertex-weighted graphs are also
present.

40 / 68
Graphs – Simple vs. Non-Simple 12

A simple (strict) graph is an

unweighted, undirected without
loops or multiple (parallel) edges

I A (self-)loop is an edge
(x, x) on a vertex
I Multiple edges connect the
same vertices (x, y)

12
[Link]
41 / 68
Graphs – Sparse vs. Dense

Graphs are Dense when a large

fraction of vertex pairs have edges
(close to the maximal number of
edges), otherwise Sparse
I No formal distinction
between two types, yet there
is ratio of graph density to 13

quantify the level of density.

13
the number of edges divided by the maximum number of edges: α|E|/(|V |(|V | − 1)) where α = 1 for directed, α = 2 for undirected, the
maximum number of edges for an undirected graph is |V |(|V | − 1)/2 – [Link]

42 / 68
Graphs – Cyclic vs. Acyclic 14

Graphs containing at least one cy-

cle are Cylic, otherwise Acyclic

14
[Link]
43 / 68
Graphs vs. Trees 17

Trees are connected, acyclic and undirected graphs

15

I Although they are undirected, it is possible to see their

directed variants 16

I Directions can also be placed just to emphasize the

parent-child relationships.

15
image source: [Link] on- binary-tree- array/
16
[Link]
17
[Link]
44 / 68
Graph Representations – Adjacency Matrix 18 19

where maintain a V-by-V boolean / binary array, with the entry in

row v and column w defined to be true if there is an edge in the
graph that connects vertex v and vertex w, and to be false
otherwise.

e.g. directed graph

18
Algorithms (4th Ed.) by Robert Sedgewick and Kevin Wayne, 2011 Addison-Wesley – [Link]
19
example source: [Link]
45 / 68
Graph Representations – Adjacency Matrix 20

where maintain a V-by-V boolean / binary array, with the entry in

row v and column w defined to be true if there is an edge in the
graph that connects vertex v and vertex w, and to be false
otherwise.

e.g. undirected graph

20
example source: [Link]
46 / 68
Graph Representations – Adjacency List 21

Maintain a vertex-indexed array of lists of the vertices adjacent to

each vertex.

e.g. directed graph (only outgoing connections)

21
example source: [Link]
47 / 68
Graph Representations – Adjacency List 22

Maintain a vertex-indexed array of lists of the vertices adjacent to

each vertex.

e.g. undirected graph

22
example source: [Link] [Link]/index_files/Bioinformatics/Content/23- [Link]
48 / 68
Graph Representations – Others 23

Edge Array: an adjacency array keeps the neighbors of all vertices,

one after another; and separately, keeps an array of indices that tell
us where in the adjarray to look for the neighbors of each vertex.

Edge List: A list of pairs (i, j) ∈ E.

23
[Link] s12/www/lectures/[Link]
49 / 68
Graph Representation
TASK :
1. List the advantages and disadvantages between Adjacency
Matrix and List for both Directed and Undirected graphs.
2. Show the Adjacency Matrix and List for the following graph.

Submit photo of your answer to Piazza as a private message.

Also, deliver its hard copy.
50 / 68
Graph Representation

TASK : Implement two graph representations including Adjacency

Matrix and Adjacency List.
I With the functionalities of add and remove node

Submit your code to Piazza as a private message.

51 / 68
Searching
Partial search trees for finding a route from Arad to Bucharest.

52 / 68
Searching – Tree Search

53 / 68
Searching – Graph Search

54 / 68
Searching – Graph Search

A sequence of search trees generated by a graph search on the

Romania problem.
I At each stage, we have extended each path by one step.

55 / 68
Searching – Graph Search
The frontier (white nodes) always separates the explored region of
the state space (black nodes) from the unexplored region (gray
nodes).
(a) just the root has been expanded
(b) one leaf node has been expanded
(c) the remaining successors of the root have been expanded in
clockwise order

56 / 68
Search Algorithms – Infrastructure
For each node n of the tree, we have a structure that contains 4
components:
I [Link]: the state in the state space the node corresponds;
I [Link]: the node in the tree generated this node;
I [Link]: the action applied to the parent to generate the node;
I [Link]-COST: the cost, g(n), of the path from the initial state to the
node.

Use the SOLUTION function to return the sequence of actions obtained by

following parent pointers back to the root.
57 / 68
Search Algorithms – Infrastructure

The function CHILD-NODE takes a parent node and an action

and returns the resulting child node:

58 / 68
Search Algorithms – Infrastructure

Now that we have nodes, we need somewhere to put them. The

frontier needs to be stored in such a way that the search algorithm
can easily choose the next node to expand according to its
preferred strategy.

The appropriate data structure for this is a queue, here are its
operations:
I EMPTY?(queue) returns true only if there are no more
elements in the queue.
I POP(queue) removes the first element of the queue and
returns it.
I INSERT(element, queue) inserts an element and returns the
resulting queue.

59 / 68
Search Algorithms – Infrastructure

Queues are characterized by the order in which they store the

inserted nodes. 3 common variants are:
I the first-in, first-out (FIFO) queue: pops the oldest element
of the queue
I the last-in, first-out (LIFO) queue (a.k.a. stack): pops the
newest element of the queue;
I the priority queue: pops the element of the queue with the
highest priority according to some ordering function.

60 / 68
Search Algorithms – Performance Measure

We can evaluate an algorithm’s performance in 4 ways:

I Completeness: Is the algorithm guaranteed to find a solution
when there is one?
I Optimality: Does the strategy find the optimal solution?
I Time complexity: How long does it take to find a solution?
I Space complexity: How much memory is needed to perform
the search?

61 / 68
Graphs – Glossary 24

I A self-loop is an edge that connects a vertex to itself.

I Two edges are parallel if they connect the same pair of vertices.
I When an edge connects two vertices, we say that the vertices are adjacent to one another and that the
edge is incident on both vertices.
I The degree of a vertex is the number of edges incident on it.
I A subgraph is a subset of a graph’s edges (and associated vertices) that constitutes a graph.
I A path in a graph is a sequence of vertices connected by edges, with no repeated edges.
I A simple path is a path with no repeated vertices.
I A cycle is a path (with at least one edge) whose first and last vertices are the same.
I A simple cycle is a cycle with no repeated vertices (other than the requisite repetition of the first and last
vertices).
I The length of a path or a cycle is its number of edges.
I We say that one vertex is connected to another if there exists a path that contains both of them.
I A graph is connected if there is a path from every vertex to every other vertex.
I A graph that is not connected consists of a set of connected components, which are maximal connected
subgraphs.
I An acyclic graph is a graph with no cycles.
I A tree is an acyclic connected graph.
I A forest is a disjoint set of trees.
I A spanning tree of a connected graph is a subgraph that contains all of that graph’s vertices and is a single
tree. A spanning forest of a graph is the union of the spanning trees of its connected components.
I A bipartite graph is a graph whose vertices we can divide into two sets such that all edges connect a vertex
in one set with a vertex in the other set.

24
[Link]
63 / 68