Artificial Intelligence

Problem-solving
Solving problems by searching
Informed Search and Exploration
Constraint Satisfaction Problems
Adversarial Search
 Artificial Intelligence

A simple problem solving agent

formulates a goal and a problem,
searches for a sequence of actions that
would solve the problem, and then
executes the actions one at a time. When
this is complete, it formulates another
goal and starts over. Note that when it is
executing the sequence it ignores its
percepts : it assumes that the solution it
has found will always work. 2
 Artificial Intelligence

WELL DEFINED PROBLEMS AND SOLUTIONS

A problem can be defined formally by four
components
 The initial State that the agent starts in.
 A description of possible actions available to
the agents
 A Goal test, which determines whether a given
state is a goal state.
 A path cost function that assigns numeric cost
to each path.

3
 Artificial Intelligence

EXAMPLE PROBLEMS

Toy Problems
Vacuum world Problem.
States : The agent is in one of two locations,
each of which might or might not
contain dirt. Thus there are 2 x 22 = 8
possible world states.
Initial State : Any state can be designated as the initial
state
Successor function : This generates the legal states that
result from trying the three actions (left,right,suck)
Goal test : This checks whether all the squares are clean.
Path Cost : Each step costs 1, so the path cost is the
number of steps in the path.
4
 Artificial Intelligence

Other Toy problems

8-Puzzle Problem
8-Queens Problem

Real-world Problems
Route-finding problem
Knapsack Problem

5
 Artificial Intelligence

SEARCHING FOR SOLUTIONS

 Search Tree
 Generate & Test

Measuring problem-solving performance

 Completeness
 Optimality
 Time Complexity
 Space Complexity

6
 Artificial Intelligence

Uninformed Search Strategies

 Breadth-first Search
Optimal when all step costs are equal,because it always
expands the shallowest unexpanded node.
 Uniform Cost Search
It expands the node n with the lowest path cost. It doesn’t
care about the number of steps a path has, but only
about their total cost.
 Depth First Search
 Depth-Limited Search

DLS means DFS with a predetermined depth limit

l

7
 Artificial Intelligence

Depth-first Search
 Search Strategy Properties
 Criteria
– Completeness: if there is a solution
will the algorithm find it?
– Time complexity: how much time
does the algorithm take to arrive at a
solution, if one exists?
– Space complexity: how much space
does the algorithm require?
– Optimality: is the solution
optimal? 8
 Artificial Intelligence

In-Completeness of DFS
 DFS is not complete
– fails in infinite-depth spaces, spaces
with loops
 Variants
– limit depth of search
– avoid re-visiting nodes.
– avoid repeated states along path
=> complete in finite spaces

9
 Artificial Intelligence

DFS with depth limit Performance

 Properties
– Complete: No
» Guaranteed to stop
» Complete only if exists solution at level l<d
(where d is the maximum depth)
– Time complexity: O(b^d)
» Best case l
» Worst case (b^(d+1)-1)/(b-1)
Where b is the branching factor
» improved performance when there are many
solutions
– Space complexity: O(bd)
» i.e., linear space
– Optimal: No
10
 Artificial Intelligence

DFS Summary
 Advantages
– Low space complexity
– Good chance of success when there are
many solutions.
– Complete if there is a solution shorter than
the depth limit.
 Disadvantages
– Without the depth limit search may
continue down an infinite branch.
– Solutions longer than the depth limit will not
be found.
– The solution found may not be the shortest
solution.
11
 Artificial Intelligence

Breadth-first Search
 Expand node with minimal depth.
 avoid revisiting nodes. Since every
node is in memory, the additional
cost is negligible.

12
 Artificial Intelligence

BFS Performance
 Properties
– Complete: Yes (if b is finite)
– Time complexity: 1+b+b^2+…+b^l
= O(b^l)
– Space complexity: O(b^l) (keeps
every node in memory)
– Optimal: Yes (if cost=1 per step); not
optimal in general
» where b is branching factor and
» l is the depth of the shortest solution
13
 Artificial Intelligence

Uniform cost Search

 Expand least-cost unexpanded node
– the breadth-first search is just uniform cost
search with f(n)=DEPTH(n)

1 10
5 B 5
S G
– Node discovery
15 5
C

– Stop at first expanded goal node

14
 Artificial Intelligence

Uniform cost Search

 Properties of Uniform-Cost Search
– Complete: Yes, if step cost >= e (epsilon)
– Time complexity: # of nodes with f <= C*
» C* = cost of optimal solution
» Worst case O(b^(C*/e))
» O(b^l) if step costs are equal
– Space complexity: # of nodes with f <= C*,
O(b^l)
– Optimal: Yes, if step cost >= e (epsilon)

15
 Artificial Intelligence

 Iterative Deepening Depth First Search

1. General strategy often used in combination with depth-first
search, that finds the best depth limit. It does this by
gradually increasing the limit-first 0, then 1, then 2 and so
on---until a goal is found.
2. Combines the benefits of BFS & DFS.
3. It may seem wasteful, because states are generated
multiple times. But it turns out this is not very costly.
4. For ex. The nodes on the bottom level(depth d) are
generated once, those on the next to bottom level are
generated twice, and so on.
So the total no. of nodes generated is
N(IDS) = (d)b + (d-1)b2 + … +(1)bd, which gives a time
complexity of O(bd). Now For BFS N(BFS) = b+ b2+…+bd+1
-b). Note that BFS generates some nodes at depth d+1,
whereas IDS does not. 16
 Artificial Intelligence

Iterative Deepening Search

 Combine the best of both worlds
– Depth first search has linear memory
requirements
– Breadth first search gives an optimal
solution.
 Iterative Deepening Search executes
depth first search with depth limit 1,
then 2, 3, etc. until a solution is found.
 The algorithm has no memory between
searches.
17
 Artificial Intelligence

Iterative Deepening Search

 Limit=0
 Limit=1

 Limit=2

 Limit=3
…

18
 Searching Strategies
Artificial Intelligence

Iterative Deepening Search

 Properties
– Complete: Yes
– Time complexity:
(l+1)*b^0+l*b+(l-1)*b^2+…
+1*b^l = O(b^l)
– Space complexity: O(bl)
– Optimal: Yes, if step cost = 1
» Can be modified to explore
uniform-cost tree
19
 Searching Strategies
Artificial Intelligence

Iterative Deepening Search - Discussion

 Numerical demonstration:
Let b=10, l=5.
– BFS resource use (memory and # nodes
expanded)
1+10+100+1000+10000+100000 = 111,111
– Iterative Deepening resource use
» Memory requirement: 10*5 = 50
» # expanded nodes
6+50+400+3000+20000+100000 = 123,456
=> re-searching cost is small compared
with the cost of expanding the leaves
20
 Artificial Intelligence

Bidirectional Search
 Simultaneously search both forward
from the initial state and backward from
the goal, and stop when the two
searches meet in the middle.

Start Goal

21
 Artificial Intelligence

Bidirectional Search Discussion

 Numerical Example (b=10, l = 6)
– Bi-directional search finds solution at d=3 for
both forward and backward search. Assuming
BFS in each half 22,200 nodes are generated.
– Compare with 11,111,100 for a standard BFS.
 Implementation issues:
– Operators are reversible.
– There may be many possible goal states.
– Check if a node appears in the “other” search tree.
– What’s the best search strategy in each half.

22
 Searching Strategies
Artificial Intelligence

Bidirectional Search Performance

 Properties
– Complete: Yes (using a complete
search procedure for each half)
– Time complexity: O(b^(l/2))
– Space complexity: O(b^(l/2))
– Optimal: Yes, if step cost = 1
» Can be modified to explore uniform-cost
tree

23
 Searching Strategies
Artificial Intelligence

Comparison Search Strategies

Bi-
Iterative direction
Breadth-Uniform- Depth- Depth-
Criterion Deepeni al (if
First Cost First Limited
ng applicabl
e)
Time b^l b^l b^m b^d b^l b^(l/2)
Space b^l b^l bm bd bl b^(l/2)
Optimal
Yes Yes No No Yes Yes
?
Complet Yes, if
Yes Yes No Yes Yes
e? d>=l

– b is the branching factor;

– l is the depth of solution;
– m is the maximum depth of the search tree;
24
– d is the depth limit.
 Artificial Intelligence

AVOIDING REPEATED STATES

• Possibility of wasting time by expanding states that
have already been encountered and expanded before.
• For some problems such as route finding, sliding-blocks
puzzles, search trees for these problems are infinite, but
if we prune some of the repeated states, we can cut the
search tree down to finite size.
SEARCHING WITH PARTIAL INFORMATION
1. Sensorless problems (Conformant problems) :
If the agent has no sensors at all, then it could be in one
of several possible initial states, and each action might
therefore lead to one of several possible successor states 25
 Artificial Intelligence

Contingency problems
If the environment is partially observable or if actions are uncertain, then
agent’s percepts provide new information after each action.
Each possible percept defines a contingency that must be planned for.
A problem is called adversarial if the uncertainty is caused by the actions of
another agent.

Exploration Problems
When the states and action of the environment are unknown, the agent must
act to discover them.

26
 Artificial Intelligence

Search Strategies
 Uninformed search (= blind search)
– have no information about the number of steps or
the path cost from the current state to the goal
 Informed search (= heuristic search)
– have some domain-specific information
– we can use this information to speed-up search
– e.g. Bucharest is southeast of Arad.
– e.g. the number of tiles that are out of place in an 8-
puzzle position
– e.g. for missionaries and cannibals problem, select
moves that move people across the river quickly

27
 Artificial Intelligence

Best-First-Search Performance
 Completeness
– Complete if either finite depth, or minimum drop in h value for each operator
 Time complexity
– Depends on how good the heuristic function is
– A “perfect” heuristic function will lead search directly to the goal
– We rarely have “perfect” heuristic function
 Space Complexity
– Maintains fringe of search in memory
– High storage requirement
 Optimality
– Non-optimal solutions

3 2 x

Suppose the heuristic drops to 1

one everywhere except along the 1 1 1 x28
path along which the solution lies
 Artificial Intelligence

Iterative Improvement Algorithms

 Start with the complete configuration
and make modifications to improve the
quality
 Consider the states laid out on the
surface of a landscape
 Keep track of only the current state
=> Simplification of Best-First-Search
 Do not look ahead beyond the
immediate neighbors of that state
– Ex: amnesiac climb to summit in a thick fog

29
 Artificial Intelligence

Iterative Improvement Basic Principle

“Like climbing Everest in thick fog with

amnesia” 30
 Artificial Intelligence

Hill-Climbing
 Simple loop that continually moves in the direction of
decreasing value
 does not maintain a search tree, so the node data
structure need only record the state and its evaluation.
 Always try to make changes that improve the current
state
 Steepest-descent: pick the steepest next state

Hill-Climbing(initial-state)
state  initial-state
do forever
next  minimum valued successor of state
if (h(next) >= h(state)) return current
state  next
31
 Artificial Intelligence

8-queens
State contains 8 queens on the board
Successor function returns all states generated by moving
a single queen to another square in the same column
(8*7 = 56 next states)
h(s) = number of queens that attack each other in state s.

H(s) = 17, best next is 12 H(s) = 1, local minimum 32

 Artificial Intelligence

Drawbacks
 Local maxima/minima : halt with local
maximum/minimum
 Plateaux : random walk
 Ridges : oscillate from side to side, limit progress

• Random-Restart Hill-Climbing
Conducts a series of hill-climbing searches from
randomly generated initial states. 33
 Artificial Intelligence

Hill-Climbing Performance
 Completeness
– Not complete, does not use systematic
search method
 Time complexity
– Depends on heuristic function
 Space Complexity
– Very low storage requirement
 Optimality
– Non-optimal solutions
– Often results in locally optimal solution

34
 Artificial Intelligence

Search Performance
Heuristic 1: Heuristic 2:
8-Square
Tiles out of place Manhattan distance*
Search Algorithm expanded solution length expanded solution length
Iterative Deepening 1105 9
hill-climbing 2 no solution found 10 9
best-first 495 24 9 9

*Manhattan distance =.total number of horizontal and vertical moves required to

move all tiles to their position in the goal state from their current position.

3 2 5 h1 = 7 1 2
7 1 3 4 5
h2 = 2+1+1+2+1+1+1+0=9
4 6 8 6 7 8
=> Choice of heuristic is critical to heuristic search algorithm performance.
35