Module:2 Problem Solving
based on Searching
[Link]
Assistant Professor/SCOPE
VIT,Chennai
[Link], AsstProf/SCOPE, VIT-Chennai.
Algorithmic view of AI
• AI performed→
• Formal Cognitive Tasks(Playing Games, Solving Maths)
• Expert Tasks(Medical, Financial, Engineering)
• Perceptual tasks(Vision, Speech Robot)
• A large number of problems are NP hard
• AI develops a set of tools or heuristics to
• Solve problems in practice
• Naturally occurring instances
[Link], AsstProf/SCOPE, VIT-Chennai.
Algorithms evolution in AI
[Link], AsstProf/SCOPE, VIT-Chennai.
Problem Solving based on Searching
• Purpose of search- Get optimal solution for all types of problems.
• State→
[Link], AsstProf/SCOPE, VIT-Chennai.
Agent’s Knowledge Representation
[Link], AsstProf/SCOPE, VIT-Chennai.
Vacuum World
• Atomic-
• S1,S2,….S8
• If we add a second Romba, then
state space doubles
• Proportional-
• 3 variables- Dirt-in-leftroom (T/F), Dirt-in-rightroom(T/F), Romba-in(T/F)
• 23 states
• If we add a second Romba, then representation increases by one.
• Relational-
• World made of objects->Robot, rooms etc
• In{Robot, room}, dirt{status}
• If we add a second Romba, then AsstProf/SCOPE,
[Link], object increases
VIT-Chennai. by one.
Atomic Agent
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Search Tree
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
State Vs Node
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Search Strategies
[Link], AsstProf/SCOPE, VIT-Chennai.
Repeated States
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Depth First Search
[Link], AsstProf/SCOPE, VIT-Chennai.
DFS- Evaluation
• Complete- No
• Time Complexity-
• Space Complexity-
• Optimal- No
[Link], AsstProf/SCOPE, VIT-Chennai.
Breadth First Search
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
BFS- Evaluation
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Uniform Cost Search: Cheapest first
• Maintains queue to visit nodes.
• Complete- Yes (b is finite)
• Time Complexity-
• Space Complexity-
• Optimal- Yes
[Link], AsstProf/SCOPE, VIT-Chennai.
Example- Water Jug Problem
[Link], AsstProf/SCOPE, VIT-Chennai.
Search Tree
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Depth-Limited Search Algorithm
• A depth-limited search algorithm is similar to depth-first search with a
predetermined limit. Depth-limited search can solve the drawback of
the infinite path in the Depth-first search.
• In this algorithm, the node at the depth limit will treat as it has no
successor nodes further.
• Depth-limited search can be terminated with two Conditions of
failure:
• Standard failure value: It indicates that problem does not have any solution.
• Cutoff failure value: It defines no solution for the problem within a given
depth limit.
[Link], AsstProf/SCOPE, VIT-Chennai.
• Memory Efficient
→O(bl)
• Completeness: No
• Optimality: No
•Time complexity:
O(bl), l→level
[Link], AsstProf/SCOPE, VIT-Chennai.
Iterative deepening depth-first Search
• The iterative deepening algorithm is a combination of DFS and BFS
algorithms.
• This search algorithm finds out the best depth limit and does it by gradually
increasing the limit until a goal is found.
• This algorithm performs depth-first search up to a certain "depth limit",
and it keeps increasing the depth limit after each iteration until the goal
node is found.
• This Search algorithm combines the benefits of Breadth-first search's fast
search and depth-first search's memory efficiency.
• The iterative search algorithm is useful uninformed search when search
space is large, and depth of goal node is unknown.
[Link], AsstProf/SCOPE, VIT-Chennai.
1'st Iteration-----> A
2'nd Iteration----> A, B, C
3'rd Iteration------>A, B, D, E, C, F, G
4'th Iteration------>A, B, D, H, I, E, C, F, K, G
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
The monkey and the banana
• Description
A monkey enters a room via the door. In the room, near
the window, is a box. In the middle of the room hangs a
banana from the ceiling. The monkey wants to grasp
the banana, and can do so after climbing on the box in
the middle of the room.
States
For each state, we need to record:
- the position of the monkey (door, window, middle, ...)
- the position of the box
- if the monkey is on the box
- if the monkey has the banana
The initial state is (door, window, no, no).
The set of goal states is (*, *, *, yes).
[Link], AsstProf/SCOPE, VIT-Chennai.
Moves
walk(P): from (M, B, no, H) to (P, B, no, H).
push(P): from (M, M, no, H) to (P, P, no, H).
climb: from (M, M, no, H) to (M, M, yes, H).
grasp: from (middle, B, yes, no) to (middle, B, yes, yes).
[Link], AsstProf/SCOPE, VIT-Chennai.
Consider the following graph
• BFS: ?
• DFS: ?
• IDDFS: ?
[Link], AsstProf/SCOPE, VIT-Chennai.
Consider the following graph
[Link], AsstProf/SCOPE, VIT-Chennai.
Consider the following graph
• BFS: ?
• DFS: ?
• IDDFS: ?
[Link], AsstProf/SCOPE, VIT-Chennai.
Consider the following graph
[Link], AsstProf/SCOPE, VIT-Chennai.
Handling Repeated Nodes
[Link], AsstProf/SCOPE, VIT-Chennai.
Partial Reduction
• Is possible:
• By checking if any children of a node ‘n’ has the same state as the
parent of ‘n’.
• By checking if any children of a node ‘n’ has the same state as any
ancestor of ‘n’.
[Link], AsstProf/SCOPE, VIT-Chennai.
Problem with all discussed approaches
• They are blind.
• Solution→ adding guidance(heuristic estimate)
→ Informed search
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Informed Search Algorithms
• Being smart about what paths to try and what paths to avoid.
• Intuitions need not be always right.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Best First Search
• Use an evaluation function f(n) for node ‘n’.
• Always selects node from the fringe that has the lowest ‘f’
value.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Example
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
A* Search
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Example
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Goodness of Heuristics
• Admissible
• Consistent
[Link], AsstProf/SCOPE, VIT-Chennai.
Admissible Heuristics
[Link], AsstProf/SCOPE, VIT-Chennai.
Consistent Heuristics
[Link], AsstProf/SCOPE, VIT-Chennai.
• h is admissible
• But not optimal for graph
based search strategy
[Link], AsstProf/SCOPE, VIT-Chennai.
Properties of A* Search Algorithm
[Link], AsstProf/SCOPE, VIT-Chennai.
Estimate the optimal path for a robot in ‘S’ to reach ‘G’ using A* search
algorithm
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Example- BFS & DFS
[Link], AsstProf/SCOPE, VIT-Chennai.
Example- BFS & DFS
[Link], AsstProf/SCOPE, VIT-Chennai.
Example- Iterative deepening search
[Link], AsstProf/SCOPE, VIT-Chennai.
Example- Iterative deepening search
[Link], AsstProf/SCOPE, VIT-Chennai.
PEAS
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
