Artificial Intelligence
Module 3
Artificial Intelligence Module 3
BCS545B
Syllabus
• Solving Problems by Searching
• Logical Agents
– Artificial Intelligence: Start Russell, Peter Norvig
Chapter 3 (3.5, 3.6) and
Chapter 7 (7.1, 7.2, 7.3, 7.4)
Artificial Intelligence Module 3
BCS545B
Solving Problems by
Searching
Chapter 1
Artificial Intelligence Module 3
BCS545B
Topics Covered in this Chapter
• Informed Search Strategies
• Heuristic Functions
Artificial Intelligence Module 3
BCS545B
Informed Search
This search strategy utilizes problem-specific knowledge to improve efficiency compared
to uninformed search methods.
•
Best-first search: A general approach that expands nodes based on an evaluation
function, f(n).
•
Evaluation function: This function estimates the cost of reaching a goal from a given
node.
•
Heuristic function: A component of the evaluation function that estimates the cost of the
cheapest path from a node to a goal.
•
• Informed search strategies:
– Greedy best-first search: f(n) = h(n)
– A* search: f(n) = g(n) + h(n)
Importance of heuristics: Heuristics provide valuable problem-specific knowledge that
can significantly improve search efficiency.
•
Conclusion: While informed search can be more efficient than uninformed search, the
quality of the heuristic function can greatly impact performance. A well-designed
•
heuristic can dramatically reduce the search space, while a poorly designed heuristic
may not provide much benefit or even lead to suboptimal solutions.
Artificial Intelligence Module 3
BCS545B
Greedy Best first Search
• Greedy best-first search: This algorithm expands nodes based on their
estimated distance to the goal, aiming to reach the goal as quickly as possible.
• Heuristic function: The algorithm uses a heuristic function, h(n), to estimate the
cost of reaching the goal from a given node.
• Example: Romania problem: The straight-line distance heuristic, hSLD, is used
to estimate the distance to Bucharest.
• Advantages: Greedy best-first search can be more efficient than uninformed
search methods, especially with well-designed heuristics.
• Limitations:
– Not always optimal: Greedy best-first search may not find the optimal solution, as it
focuses solely on the immediate goal and can overlook better paths.
– Incomplete: The algorithm can be incomplete, especially in infinite search spaces, as
it may get stuck in local minima or infinite loops.
Heuristic Function: f(n) = h(n)
Artificial Intelligence Module 3
BCS545B
Greedy Best first Search Algorithm
• Initialize:
– Place the starting node on the open list.
– Set the cost of the starting node to 0.
• Select Best Node:
– Find the node on the open list with the lowest heuristic value.
– Remove that node from the open list and place it on the closed list.
• Expand Node:
– Generate all successor nodes of the selected node.
– For each successor node:
• If the successor node is already on the closed list, ignore it.
• Calculate the heuristic value of the successor node.
• Add the successor node to the open list with its calculated heuristic value.
• Goal Test:
– If the selected node is the goal node, return the solution path.
• Repeat:
– Go back to step 2 and repeat until the goal is reached or the open list becomes empty.
Artificial Intelligence Module 3
BCS545B
Best First Search : Example Problem
Artificial Intelligence Module 3
BCS545B
A* Search
• A popular informed search algorithm that combines the cost to reach a node
(g(n)) with the estimated cost to reach the goal (h(n)).
• Admissibility: A heuristic function is admissible if it never overestimates the
cost to reach the goal.
• Consistency: A heuristic function is consistent if it satisfies the triangle
inequality, ensuring that the estimated cost to reach the goal from a node is no
greater than the step cost to a successor node plus the estimated cost from that
successor to the goal.
• Optimality: A* search is optimal if the heuristic function is admissible. This
means it will always find the cheapest solution path.
• Efficiency: A* search is often more efficient than uninformed search methods
due to the use of heuristic information. However, the efficiency depends on the
quality of the heuristic function.
• Conclusion: A* search is a powerful and widely used informed search algorithm
that can effectively solve a variety of problems, especially when combined with
good heuristic functions.
Artificial Intelligence Module 3
BCS545B
A* Algorithm Example
10 A J 6
A 3
6
F
1 7
B 2 5 G
D
7
3 H
8 1
3 1 2 3
8
5
I
C 3
5 5 E 5 J
3
Artificial Intelligence Module 3 0
BCS545B
A* Algorithm Example Solution
10
6
A 3
6
F
1 7
B 2 5 G
D
7
3 H
8 1
3 1 2 3
8
5
I
C 3
5 5 E 5 J
3
Artificial Intelligence Module 3 0
BCS545B
Memory-bounded Heuristic Search
• Memory-bounded heuristic search is a type of search algorithm that uses
heuristics to guide the search while also restricting memory usage to a fixed
limit. This approach is useful in solving large problems where traditional
heuristic searches, like A*, would otherwise consume excessive memory.
Memory-bounded algorithms attempt to balance between efficient memory
usage and finding an optimal or near-optimal solution.
• Types of memory-bounded heuristic search algorithms include:
– Iterative Deepening A* (IDA*):
• Combines depth-limited search with A*, using an iterative approach where the depth limit is
set by an f-cost (the sum of the path cost g and heuristic cost h).
• At each iteration, the search is limited by the smallest f-cost that exceeded the cutoff in the
previous iteration.
• IDA* doesn’t store a full queue of nodes, making it memory-efficient, but it has to re-expand nodes
between iterations, which can increase runtime.
Artificial Intelligence Module 3
BCS545B
Memory-bounded Heuristic Search
– Recursive Best-First Search (RBFS):
• Operates similarly to A* but keeps memory usage low by recursively searching paths with a
backtracking mechanism.
• Only the path from the root to the current node and one alternative path are stored, using an f-
limit to keep track of the best alternative path.
• RBFS can change paths (backtrack) if a previously explored path looks more promising, but it may
suffer from redundant node expansions.
– Simplified Memory-Bounded A* (SMA*):
• Extends A* with a memory constraint, keeping the best nodes until memory is full.
• When memory is exceeded, SMA* drops the least promising nodes (nodes with the highest f-value)
and backs up their f-value to their parent nodes.
• SMA* remembers the quality of dropped paths, allowing it to avoid repeatedly exploring less
promising areas. It’s optimal if the best solution path can be stored within the memory limit but
may suffer from thrashing (frequent switching between paths) if memory is very limited.
Artificial Intelligence Module 3
BCS545B
Heuristic Functions
• A heuristic function is a method or technique
used to estimate the solution to a problem
• Heuristic functions are commonly employed in
search algorithms, optimization problems, and
decision-making processes to guide the search for
a solution in a more efficient manner.
Artificial Intelligence Module 3
BCS545B
Heuristic Functions: 8-Puzzle
• In Case of 8-puzzle, we use two heuristic
functions to estimate the cost of reaching the goal
from a given state. In case of 8 puzzle problem we have a tree of depth 22 to search
which is about 1.8L states. But the same for 15-puzzle problem
– Misplaced Tiles Heuristic
is roughly around 10^13 which is very very huge. That is the
reason we use heuristic function to solve them easily.
• We count the number of tiles not in correct place as the
heuristic value
– Manhattan Distance Heiristic
• We count the no. of tile
positions to move(distance) to
reach the goal state
Artificial Intelligence Module 3
BCS545B
Solve the 8 Puzzle using both the Heuristic
functions
2 8 3 1 2 3
1 6 4 8 4
7 5 7 6 5
Artificial Intelligence Module 3
BCS545B
The effect of heuristic on performance: Test
IDS - Interactive Deepening Search
Artificial Intelligence Module 3
h1 - Misplaced Tile Heuristics
BCS545B h2 - Manhattan Distance Heuristic
Generating admissible heuristics from relaxed
problems
• A relaxed problem is a version of the original
problem with fewer restrictions on the actions.
The state-space graph of the relaxed problem is a
supergraph of the original state space because
the removal of restrictions creates added edges in
the graph.
• The removal of restrictions creates added edges
in the graph, potentially leading to shortcuts in
finding optimal solutions.
Artificial Intelligence Module 3
BCS545B
Generating admissible heuristics from
subproblems: Pattern database
A subproblem involving getting tiles 1, 2, 3, 4 into
their correct positions in the 8-puzzle
Artificial Intelligence Module 3
BCS545B
Generating admissible heuristics from
subproblems: Pattern database
• Admissible heuristics can be derived from the
solution cost of a subproblem of the original
problem. The cost of the optimal solution to the
subproblem is a lower bound on the cost of the
complete problem.
• The idea behind pattern databases is to store
exact solution costs for every possible subproblem
instance. This involves recording the cost of each
new pattern encountered during a search back
from the goal.
Artificial Intelligence Module 3
BCS545B
Learning Heuristics from experience
• One approach is to create relaxed problems for which an
optimal solution can be easily found. These relaxed problems
serve as a basis for estimating the cost of a solution from a
given state.
• Another approach is to learn from experience, where experience
involves solving numerous instances of the problem. Each
optimal solution to a problem provides examples from which
h(n) can be learned. Learning algorithms can be used to
construct a function h(n) that predicts solution costs for states
encountered during search.
• Learning methods, including neural networks, decision trees,
and other techniques
Artificial Intelligence Module 3
BCS545B