SI: Systèmes Intelligents

L3 – SCI

Pr. Souham Meshoul

[email protected]

Problem Solving by Searching (1)

Chapter 2
1
Problem solving by searching 1

Objectives

 Learn how to formulate a search problem.

 Learn the different algorithms used to solve

problems by searching.

 Learn how to assess the performance of a

search algorithm.
2
Plan
 Introduction

 Uninformed search
 Basic concepts
 Problem formulation
 Performance evaluation

 Basic search strategies

 Repeated states problem
 Searching with partial information
 Summary
3
Introduction
Solving a particular problem = Need to define the elements of
a problem and its solution.

1. Define the problem precisely.

2. Isolate and represent the task knowledge that is necessary

to solve the problem.

3. Choose and apply the best problem solving technique(s)

to the particular problem.

4
Introduction
Task = search Why search ?
 Early works of AI was mainly towards

• proving theorems
• solving puzzles
• playing games

 All AI is search!

 Not totally true (obviously) but more true than you might
think.

 All life is problem solving !!

 Finding a good/best solution to a problem amongst many

possible solutions. 5
Introduction
Problem solving as search

Task = Search
 Search is required to solve a wide range of problems.

 Search is a method that can be used by computers to

examine a huge problem space to find a goal.
e.g Searching for a contact lens on a football field

 Challenge: How to find the goal as quickly as possible or

without using too many resources.
6
Introduction
A problem can be considered to consist of a goal and a set of actions
that can be taken to lead to the goal

Start

End
Task = finding the sequence of actions that lead to the
7
desirable goal.
Introduction: Classic AI Search
Problems
Map searching (navigation) 

8
Introduction: Classic AI Search
Problems
 3*3*3 Rubik’s Cube
 Rubik’s cube: Rubik 1974

There are 901,083,404,981,813,616 different

states. The average depth of a solution is
about 18.
9
Introduction: Classic AI Search
Problems
Classic AI search problems
 8-Puzzle

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

The 8-puzzle belongs to the family of Sliding-block puzzles.

The 8-puzzle has 9!/2=181,440 reacheable states.
The 8-puzzle has around 1.3 trillion states… 10
Introduction: Classic AI Search
Problems
Classic AI search problems
 N-Queens:

11
Introduction: Classic AI Search
Problems

:Queens-5 
1 2 3 4 5
1

5
12
Introduction: Classic AI Search
Problems

:Queens-5 
1 2 3 4 5
1

5
13
Introduction: Classic AI Search
Problems

:Queens-5 
1 2 3 4 5
1

5
14
Introduction: Classic AI Search
Problems

:Queens-5 
1 2 3 4 5
1

5
15
Introduction: Classic AI Search
Problems

:Queens-5 
1 2 3 4 5
1

5
16
Introduction: Classic AI Search
Problems

:Queens-5 
1 2 3 4 5
1

2
Solution !!
No Queen is 3
under Attack
4

5
17
Introduction: Classic AI Search
Problems
Missionaries and Cannibals
 Three missionaries and three cannibals are on the
left bank of a river.

 There is one canoe which can hold one or two

people.

 Find a way to get everyone to the right bank, without

ever leaving a group of missionaries in one place
outnumbered by cannibals in that place.

18
Introduction: Classic AI Search
Problems
Initial Situation

19
Introduction: Classic AI Search
Problems
Missionaries and Cannibals
Goal

20
Introduction: Classic AI Search
Problems
The River Problem
A farmer wishes to carry a wolf, a duck and corn across a river, from
the south to the north shore. The farmer is the proud owner of a
small rowing boat called Bounty which he feels is easily up to the
job. Unfortunately the boat is only large enough to carry at most the
farmer and one other item. Worse again, if left unattended the wolf
.will eat the duck and the duck will eat the corn
Farmer, Wolf,
Duck and Corn
River River boat

boat
Farmer, Wolf,
Duck and Corn

How can the farmer safely transport the wolf, the duck and the corn to
?the opposite shore
21
Introduction
Real world Problems

 Touring problems

 Route Finding

 Travelling salesperson

 VLSI Layout

 Robot navigation

 Internet searching …

22
Introduction

 Search can be performed without any

additional information about how to reach a
solution:
Blind Search (Uniformed search)

 Search can be performed using heuristics :

Informed Search

23
Uninformed search

To successfully operate, blind search should satisfy some

properties:

 It must be complete: It must generate every possible

solution otherwise it might miss a suitable solution.

 It must be able to find the best solution.

24
Uninformed search
 Key questions to be addressed:
1. What goal do we need to achieve?
2. How to know when a goal is reached?
3. What knowledge we need?
4. What actions do we need to do?

 A goal can be described as:

1. A task to be accomplished
2. A situation to be reached
3. A set of properties to be acquired

25
Uninformed search: Basic concepts
Uninformed search: Basic concepts

 State: configuration, situation, point……

 Problem formulation: Process of deciding what actions and states to

consider given a goal.

 Solution: Sequence of actions that help achieving the goal: a path

from an initial state to the goal state .

 Search: Process of looking for a solution. Takes input (problem) and

returns solution.

 Execution: To carry out the actions recommended by the solution

26
Uninformed search: basic concepts

A Problem Space consists of

 The current state of the world (initial state)

 A description of the actions we can take to transform one state

of the world into another (operators).

 A description of the desired state of the world (goal state), this

could be implicit or explicit.

 A solution consists of the goal state, or a path to the goal state.

27
Uninformed search: Basic concepts

Initial State Operators Goal State

2 1 3 Slide blank square left.

1 2 3
4 7 6 Slide blank square right. 4 5 6
….
5 8 7 8

28
Problem solving by searching 1

Uninformed search: Problem formulation

 Problem definition: a problem can be formally

defined by:
1. Initial state.
2. Successor function.
3. Goal test : determines whether a given state is
a goal state.
4. Path cost funtion: assigns a cost to each path.
Should recflect the performance measure usec
to assess the quality of any solution.
29
Problem solving by searching 1
Uninformed search: Problem formulation

Successor function
 Given a particular state x,
fsuccessor(x) = {(<action, new state>) }
where action is one of the legal actions in state x and new
state is the successor state that can be reached from x by
applying action.

 The successor function allows together with the initial

state to define the STATE SPACE: that is the set of all
states reachable from the initial state.

 A path in the state space is a sequence of states connected

by a sequence of actions.

30
Problem solving by searching 1

Uninformed search: Problem formulation

Solution definition:

A potential solution is a path from the initial state to

a goal state.

Solution quality is measured by the path cost

function.

An optimal solution has the lowest path cost among

all solutions. 31
Problem solving by searching 1

Uninformed search: Problem formulation

Arad

Zerind Sibiu Timisoara

Arad Oradea Fagaras Rimnicu Vilcea

Sibiu Bucharest
32
Problem solving by searching 1
Uninformed search: An example

Touring problem: Given a set of n cities, the touring problem consists in visiting cities at
least once starting and ending in the same city.
States:
Specified by the current city and the set of cities already visited.

Initial state:
Any state can be designed as the initial state.

Successor function:
Generates the next city to visit according to the current state.

Goal test:
Ending city reached and all cities have been visited.

Path cost:
Sum of all step costs.

33
Problem solving by searching 1
Uninformed search: Searching for solutions:

 To solve the problem, we need to define a search strategy

that allows to explore efficiently the state space.

 How to represent the state space?

 Tree
 Graph

 Each state is represented by a node.

 Expansion operation: A node is expanded if the successor

function for the corresponding state generates new states.

34
Problem solving by searching 1
Uninformed search: Informal description

Function Tree-Search(problem,strategy) returns a solution or a

failure

Initialize the search tree using the initial state of problem

Loop do
If there are no candidates for expansion then return failure
Choose a leaf node for expansion according to strategy
If the node contains a goal state then return the corresponding
solution
Else expand the node and add the resulting node to the search
tree
End Loop

35
Problem solving by searching 1

Uninformed search: Towards a formal description

Node definition: Parent Node

Data structure with 5 components:
•State: representation of a physical
configuration.
•Parent node: The node in the Node
search tree that generated this node.
•Action: action applied to the
parent node to generate this node.
•Path cost: cost of the path from
the initial state to the node.
•Depth: The number of steps along
the path from the initial state.
36
Problem solving by searching 1

Uninformed search: Towards a formal description

How to deal with non expanded nodes?

Fringe : set of nodes generated but not yet expanded. Each

node is a leaf node.

What is the suitable representation of fringe?

 Set of nodes: Simplest way but could be computationally

expensive.
 Queue: best implementation of the fringe

37
Problem solving by searching 1
Uninformed search: Towards a formal description

What are the operations to be performed on the queue?

 Make-Node(state,parent,action,depth,cost) : creates a node with the
given parameters.
 Empty?(queue) : returns TRUE only if there are no more nodes in the
queue.
 First(queue) : returns the first node of the queue.
 Remove-First(queue) : returns First(queue) and removes it from the
queue.
 Insert(element, queue) : inserts a node into the queue and returns the
resulting queue.
 Insert-All(elements, queue) : inserts a set of nodes into the queue and
returns the resulting queue.

38
Problem solving by searching 1

Uninformed search: Formal description

Function Tree-Search(problem,fringe) returns a solution or a failure

fringe ← Insert (Make-Node(Initial state[problem],NULL,NULL,d,c),fringe)

Loop do
If Empty?(fringe) then return failure

node ← Remove-First(fringe)

If Goal-Test[ problem] applied to State[node] succeeds then return

Solution(node)

fringe ← Insert-all( Expand (node,problem),fringe)

End loop 39
Problem solving by searching 1

Uninformed search: Formal description

Function Expand (node,problem) returns a set of nodes

successors ← empty set

For each <action,result> in fsuccessor(state(node)) do

Path-cost ← path-cost[node] + step-cost(State[node],action,result)

Depth ← Depth[node]+1

S ← Make-node (result, node, action, Path-cost, Depth)

Add s to successors

return successors 40
Problem solving by searching 1
Uninformed search: Performance evaluation

The performance of problem solving algorithms can be evaluated along the

following dimensions:

 Completeness: is it guaranteed to find a solution when there is

one?

 Optimality: Does the strategy find the optimal solution?

 Time complexity: how long does it take to find a solution? How

can it be measured?

 Space complexity: how much memory is needed to perform the

search? How can it be measured?

41
Problem solving by searching 1

Uninformed search: Performance evaluation

 b : The branching factor: maximum number of

successors of any node.

 d : The depth of the shallowest goal node.

 m : The maximum length of any path in the

state space.

42
Basic search strategies
 Breadth First Search (BFS)

 Depth First Search (DFS)

 Depth Limited Search (DLS)

 Uniform Cost Search (UCS)

 Iterative Deepening Search (IDS)

 …

43
Basic search strategies
 Strategies that order nodes without using any
domain specific information (only problem
definition is provided).

 Generate successors and simply differentiate

between a goal state and a non goal state.

 Blind search strategies differ by the order of node

expansion.

44
Basic search strategies: BFS
 Main idea: Nodes at depth i are expanded before nodes at
depth (i+1).
 Implementation: use of a First-In-First-Out queue (FIFO).
Nodes visited first are expanded first.

Shallow nodes are expanded before deeper nodes. 45

Basic search strategies: BFS

 Completeness: yes if the branching factor b is finite.

 Optimality: shallowest goal is not necessarily the optimal

one. It is optimal if all actions have the same cost.

 Time complexity: At the worst case, BFS expands every

node (except goal node) thus taking time as follows:

1 +b + b2 + b3 +….+ bd + (bd+1 – b)=O(bd+1)

 Memory complexity: BFS keeps every node in memory.

Space is a big problem.
46
Basic search strategies: DFS
 DFS expands the deepest node in the current fringe of the
search tree.

 As nodes are expanded, they are dropped from the fringe

so then the search « backs up » to the next shallowest node
that still has unexplored successors.

 DFS strategy is implemented using a Last-In_First-Out

(LIFO) queue or stack.

 Another alternative is to implement DFS with a recursive

function that calls itself on each of its children in turn.
47
Basic search strategies: DFS

48
Basic search strategies

49
Basic search strategies: DFS
DFS evaluation
 Completeness: Incomplete in case of unbounded depth
containing no solution.
 Optimality: does not provide always optimal solutions.

 Time complexity: At the worst case, DFS generates about

O(bm) nodes in the search tree.
 Memory complexity: DFS requires less memory than BFS.
It needs to store only a single path from the root to a leaf
node along with the remaining unexpanded sibling nodes
for each node in the path. The required storage is (bm+1)
where b is the branching factor and m maximium depth.
50
Basic search strategies: DLS

 It is simply DFS with a depth bound.

Searching is not permitted beyond the depth bound.
 Works well if we know what the depth of the solution is.
 Termination is guaranteed.
 If the solution is beneath the depth bound, the search
cannot find the goal (hence this search algorithm is
incomplete).
 Otherwise use Iterative deepening search (IDS).
51
Basic search strategies: IDS

52
Basic search strategies: IDS
 Key idea: Iterative deepening search (IDS) applies DLS repeatedly with
increasing depth. It terminates when a solution is found or no solutions
exists.
 IDS combines the benefits of BFS and DFS: Like DFS the memory
requirements are very modest (O(bd)). Like BFS, it is complete when the
branching factor is finite.
 The total number of generated nodes is :

N(IDS)=(d)b + (d-1) b2 + …+(1)bd

 In general, iterative deepening is the preferred Uninformed search
method when there is a large search space and the depth of the solution
is not known.

53
Basic search strategies: UCS

 In case of equal step costs, Breadth First search

finds the optimal solution.

 For any step-cost function, Uniform Cost search

expands the node n with the lowest path cost.

 UCS takes into account the total cost.

 UCS is guided by path costs rather than depths.

Nodes are ordered according to their path cost.
54
Basic search strategies: UCS

55
Basic search strategies: UCS

56
Basic search strategies

57
Repeated states problem
 Problem: Possibility of wasting time by expanding states that have
already been encountered and expanded before.

 Occurs when actions are reversible.

 A solvable problem can become unsolvable if the algorithm does not

detect them systematically.

 For detection purposes, a comparison operation is needed.

 For DFS, looping paths can be discarded immediately.

 Need to keep more nodes in memory: tradeoff between time and

space.

 Keep a list to store every expanded node.

58
Repeated states problem
Function Graph-Search(problem,fringe) returns a solution or a
failure

closed ← empty;
fringe ← Insert (Make-Node(Initial-state[problem],NULL,NULL,d,c),fringe)

Loop do
If Empty?(fringe) then return failure
node ← Remove-First(fringe)
If Goal-Test[ problem] applied to State[node] succeeds then return
Solution(node)
If state [node] is not in closed then
add State [node] to closed
fringe ← Insert-all( Expand (node,problem),fringe)
End Loop

59
Searching with partial information
Uninformed search: Searching with partial information

 When the world is not fully observable, we must

reason about sets of states rather than single states.

 Search is performed in the belief state space instead

of state space.

 Initial state is a belief state.

60
Searching with partial information
Uninformed search: Searching with partial information

 Vaccum world example: initial belief state : set of possible

states

61
Searching with partial information
 GO Right action on the belief state leads to:

 GO Left action on the belief state leads to:

 Suck action on the belief state leads to:

62
Summary
 Search: process of constructing sequences of actions that achieve a goal given
a problem.

 Goal formulation is the first step in solving problems by searching. It

facilitates problem formulation.

 Formulating a problem requires specifying four components: Initial states,

successor function, goal test and path cost function. Environment is
represented as a state space.

 A solution is a path from the initial state to a goal state.

 Search algorithms are judged on the basis of completeness, optimality, time

complexity and space complexity.

 Several search strategies: BFS, DFS, DLS, IDS,UCS…

63