Introduction to

Artificial Intelligence
Problem Solving by Search

2
 Search algorithm

• Defined as
– taking a problem
– and returns a solution
• Once a solution is found
– the agent follows the solution
– and carries out the list of actions – execution phase
• Design of an agent
– “Formulate, search, execute”
 Evaluation Criteria

• formulation of a problem as search task

• basic search strategies
• important properties of search strategies
• selection of search strategies for specific tasks
(The ordering of the nodes defines the search strategy)
 Problem-Solving

• The task to solve a particular problem (steps)

– goal formulation
• what is the goal state
• what are important characteristics of the goal state
• how does the agent know that it has reached the goal
• are there several possible goal states
– are they equal or are some more preferable
– problem formulation
• what are the possible states of the world relevant for solving the
problem
• what information is accessible to the agent
• how can the agent progress from state to state
 Problem-Solving

- Searching for solutions

– Finding out a solution is done by
• searching through the state space
– All problems are transformed
• as a search tree
• generated by the initial state and successor function
 Search tree

• Initial state
– The root of the search tree is a search node
• Expanding
– applying successor function to the current state
– thereby generating a new set of states
• leaf nodes
– the states having no successors
Fringe : Set of search nodes that have not been expanded yet.
• Refer to next figure
Example
 From our Example

1. Formulate Goal

- Be In Amman

2. Formulate Problem

- States : Cities
- actions : Drive Between Cities

3. Find Solution

- Sequence of Cities : ajlun – Jarash - Amman

 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: Romania
 State Space 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>, … }

goal test, (or goal state)

e.g., x = "at Bucharest”, 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
 Example: The 8-puzzle

move( x, loc y, loc z ) Up

Down
Left
Right
 State Space Problem Formulation

• States:
– a state description specifies the location of each of the eight
tiles and blank in one of the nine squares
• Initial State:
– Any state in state space
• Successor function:
– the blank moves Left, Right, Up, or Down
• Goal test:
– current state matches the goal configuration
• Path cost:
– each step costs 1, so the path cost is just the length of the
path
The 8-puzzle Search Tree
Start State

1 2 3
4 6
7 5 8

1 2 3
4 5 6
7 8

1 2 3
4 5 6
7 8
Goal State
 Example: River Crossing

• Items: Man, Wolf, Cabbage, Goat.

• Man wants to cross river with all items.
– Wolf will eat Goat
– Goat will eat Cabbage.
– Boat will take max of two.
 Searching for solutions

• the farmer will first take goat on the other side and return
back alone. We have farmer, wolf, and cabbage at one side
and goat on the other side.
• Now, he will take the wolf along, drop the wolf on the
other side and return with the goat.
• So now on one side, we have farmer, cabbage, and goat
and on the other side, we have a wolf.
• Now, he takes the cabbage along and returns alone.
• So now the scenario is: farmer, goat on one side and wolf,
cabbage on the other side.
• Now, finally, he crosses the river with the goat and hence
succeeds in taking all his belongings with him.
 River Crossing Search tree

• Farmer: f
• Wolf: w
• Goat: g
• Cabbage: c
 Measuring problem-solving performance
• The evaluation of a search strategy
– Completeness:
• is the strategy guaranteed to find a solution when there is one?
– Optimality:
• does the strategy find the highest-quality solution when there are
several different solutions?
– Time complexity:
• how long does it take to find a solution?
– Space complexity:
• how much memory is needed to perform the search?
 Measuring problem-solving performance

• In AI, complexity is expressed in

– b, branching factor, maximum number of successors of any
node
– d, the depth of the shallowest goal node.
(depth of the least-cost solution)
– m, the maximum length of any path in the state space
• Time and Space is measured in
– number of nodes generated during the search
– maximum number of nodes stored in memory
 Why Search can be difficult
• At the start of the search, the search algorithm does not know
– the size of the tree
– the shape of the tree
– the depth of the goal states

• How big can a search tree be?

– say there is a constant branching factor b
– and one goal exists at depth d
– search tree which includes a goal can have
bd different branches in the tree (worst case)

• Examples:
– b = 2, d = 10: bd = 210= 1024
– b = 10, d = 10: bd = 1010= 10,000,000,000
 Measuring problem-solving performance

• For effectiveness of a search algorithm

– we can just consider the total cost
– The total cost = path cost (g) of the solution found +
search cost
• search cost = time necessary to find the solution
• Tradeoff:
– (long time, optimal solution with least g)
– vs. (shorter time, solution with slightly larger path cost g)
 Search Strategies

• Uninformed , or blind search

– no information about the number of steps
– or the path cost from the current state to the goal
– search the state space blindly
• Informed search, or heuristic search
– a cleverer strategy that searches toward the goal,
– based on the information from the current state so far
 Uninformed search strategies

• Breadth-first search
• Depth-first search
 Breadth-first search

• The root node is expanded first (FIFO)

• All the nodes generated by the root node are then
expanded
• And then their successors and so on
 Breadth-first search
S

A D

B D A E

C E E B B F
11

D F B F C E A C G
14 17 15 15 13

G C G F
19 19 17
G 25
 Breadth-First Strategy

New nodes are inserted at the end of FRINGE

2 3 FRINGE = (1)

4 5 6 7
 Breadth-First Strategy

New nodes are inserted at the end of FRINGE

2 3 FRINGE = (2, 3)

4 5 6 7
 Breadth-First Strategy

New nodes are inserted at the end of FRINGE

2 3 FRINGE = (3, 4, 5)

4 5 6 7
 Breadth-First Strategy

New nodes are inserted at the end of FRINGE

2 3 FRINGE = (4, 5, 6, 7)

4 5 6 7
 Breadth-first search (Analysis)

• Breadth-first search
– Complete – find the solution eventually
– Optimal, if step cost is 1
The disadvantage
– if the branching factor of a node is large,
– for even small instances (e.g., chess)
• the space complexity and the time complexity are enormous
 Breadth-first search (Analysis)

• assuming 10000 nodes can be processed per second, each with 1000
bytes of storage
 Depth-first search

• Always expands one of the nodes at the deepest

level of the tree
• Only when the search hits a dead end
– goes back and expands nodes at shallower levels
– Dead end à leaf nodes but not the goal
• Backtracking search
– only one successor is generated on expansion
– rather than all successors
– fewer memory
 Depth-first search

• Expand deepest unexpanded node

•
• Implementation:
– fringe = LIFO , i.e., put successors at front
–
 Depth-first search

• Expand deepest unexpanded node

•
• Implementation:
– fringe = LIFO queue, i.e., put successors at front
–
 Depth-first search

• Expand deepest unexpanded node

•
• Implementation:
– fringe = LIFO queue, i.e., put successors at front
–
 Depth-first search

• Expand deepest unexpanded node

•
• Implementation:
– fringe = LIFO queue, i.e., put successors at front
–
 Depth-first search

• Expand deepest unexpanded node

•
• Implementation:
– fringe = LIFO queue, i.e., put successors at front
–
 Depth-first search

• Expand deepest unexpanded node

•
• Implementation:
– fringe = LIFO queue, i.e., put successors at front
–
 Depth-first search

• Expand deepest unexpanded node

•
• Implementation:
– fringe = LIFO queue, i.e., put successors at front
–
 Depth-first search

• Expand deepest unexpanded node

•
• Implementation:
– fringe = LIFO queue, i.e., put successors at front
–
 Depth-first search

• Expand deepest unexpanded node

•
• Implementation:
– fringe = LIFO queue, i.e., put successors at front
–
 Depth-first search

• Expand deepest unexpanded node

•
• Implementation:
– fringe = LIFO queue, i.e., put successors at front
–
 Depth-first search

• Expand deepest unexpanded node

•
• Implementation:
– fringe = LIFO queue, i.e., put successors at front
–
 Depth-first search

• Expand deepest unexpanded node

•
• Implementation:
– fringe = LIFO queue, i.e., put successors at front
–
 Depth-first search
S

A D

B D A E

C E E B B F
11

D F B F C E A C G
14 17 15 15 13

G C G F
19 19 17
G 25
 Depth-first search (Analysis)

• Not complete
– because a path may be infinite or looping
– then the path will never fail and go back try another
option
• Not optimal
– it doesn't guarantee the best solution
• It overcomes
– the time and space complexities
 Comparison between Depth-first and Breadth-first
Depth-first search n Breadth-first search
n It requires less memory since n All the tree that so far has been
only the nodes on the current generated must be stored.
path are stored.
n All the tree must be examined
n By chance it may find a to level (n) before any node on
solution without examining level (n+1).
much of the search space.
n It will not follow a wrong path
n It may follow a wrong path for a long time.
for a very long time.
n If there are multiple solutions
n It may find a long path then the minimal solution will
solution be found so the longer paths
never explored before shorter
one.
11