Artificial Intelligence and Expert Systems
Lecture Three Informed Search Algorithm
October 6, 2024
Introduction: Uninformed vs Informed Search
• Uninformed Search methods (e.g., Breadth-First Search, Depth-First Search)
explore the search space without any additional information about the goal’s
location.
• Informed Search methods (e.g., Greedy Best-First Search, A*) use
problem-specific knowledge to guide the search towards the goal.
• Informed search is called ”informed” because it leverages a heuristic function
that estimates how close a state is to the goal.
• Heuristics provide a way to rank which paths appear to be more promising and
should be explored first.
2/34
Heuristics and Why Informed Search is Better
• A heuristic is a function h(s) that estimates the cost of reaching the goal from
state s.
• Informed algorithms like A* and Greedy Best-First Search often solve problems
more efficiently than uninformed methods because they use heuristics to avoid
exploring irrelevant parts of the search space.
• Why are heuristics useful?
• They focus the search, reducing the number of states expanded.
• Provide a more directed approach compared to uninformed methods.
• Example: If finding a path on a map, using straight-line distance (Euclidean
distance) is a common heuristic that estimates how far a location is from the
destination.
3/34
Algorithms Overview
In this presentation, we will explore the following algorithms:
• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Uniform-Cost Search (UCS)
• Greedy Best-First Search (GBFS)
• A* Search
4/34
Breadth-First Search (BFS)
• Type: Uninformed
• Strategy: Explores all nodes level by level.
• Advantages:
• Complete and will always find a solution if one exists.
• Guarantees the shortest path if all actions have the same cost.
• Disadvantages:
• Explores all possibilities, which can be inefficient in large spaces.
• High memory consumption.
5/34
Depth-First Search (DFS)
• Type: Uninformed
• Strategy: Explores as far down one branch as possible before backtracking.
• Advantages:
• Low memory consumption.
• Can be useful for problems where solutions are deep in the search space.
• Disadvantages:
• Not guaranteed to find the shortest path.
• Can get stuck in deep, irrelevant paths.
6/34
Uniform-Cost Search (UCS)
• Type: Uninformed
• Strategy: Expands the node with the lowest path cost, ensuring the cheapest
path to the goal.
• Advantages:
• Guaranteed to find the optimal solution.
• Complete.
• Disadvantages:
• Can be slow if all actions have similar costs.
• Can explore in irrelevant directions.
7/34
Why Use Heuristics?
Origin of ”Heuristic”: Derived from the Ancient Greek ϵυρισκϵιν (”I find”); modern
usage in problem-solving popularized by George Polya in ”How to Solve It”.
Application in AI: In AI and particularly in search algorithms, heuristics guide the
search towards goal states more efficiently than uninformed search methods by
predicting how close the end goal is from a current state.
Trade-Offs: Heuristics balance between speed (low computational overhead) and
accuracy (closeness to the actual minimum cost). Perfect accuracy (h = h∗ ) would
require solving the problem itself, thus nullifying the benefit.
8/34
Heuristic Functions: Definitions
Definition (Heuristic Function): A heuristic function h for a state space
Θ = (S, A, c, T, I, SG) is a function h : S → R+ ∪ {∞}. The value h(s) for a state s is
referred to as the state’s heuristic value, or h value.
Definition (Remaining Cost, h∗ ): The remaining cost of s ∈ S is the cost of an
optimal plan for s, or ∞ if no plan exists. The perfect heuristic h∗ assigns every s ∈ S
its remaining cost as the heuristic value.
Purpose: Heuristic functions estimate the remaining cost h∗ . They aim to provide a
quick, often optimistic estimation of the cost from a given state to a goal state,
influencing the search algorithm’s strategy.
9/34
Heuristic Functions: Balancing Precision and
Efficiency
Understanding ”Estimate Remaining Cost”
• The concept of estimating the remaining cost involves applying a heuristic function, typically denoted as h.
This function’s goal is twofold:
• Precision: It should closely approximate the true remaining cost to the goal, noted
as h∗ .
• Computational Efficiency: It should require minimal resources to compute,
enhancing overall search speed.
• These objectives are often at odds:
• A heuristic of h = 0 incurs no computational cost but provides no useful
information for the search.
• Conversely, h = h∗ provides perfect guidance but is as complex as solving the
actual problem.
• Optimization Challenge: The key is to find a balance where the heuristic is both informative enough to guide
the search effectively and efficient enough to compute in a reasonable time frame.
10/34
Examples of Heuristic Functions
Illustrative Cases of Heuristic Functions
• Zero Heuristic (h(n) = 0 for all n):
• Offers no guidance on which direction to pursue towards the goal.
• Equivalent to uninformed search strategies like Breadth-First Search.
• Euclidean Distance:
• Computes the straight-line distance to the goal, ignoring obstacles.
• Useful in open environments but less so in cluttered spaces.
• Manhattan Distance:
• Measures the sum of the absolute differences of the Cartesian coordinates.
• Ideal for grid-based maps with right-angled turns, like city street grids.
• Relaxed Problem Heuristics:
• Simplifies the problem to make the heuristic solvable, e.g., ignoring walls in a maze.
• Strikes a balance between informativeness and computational ease.
11/34
Heuristic Example: Maze Solving with Manhattan
Distance
Problem (Π): Solve a maze from start (S) to goal (G).
Heuristic Function h: Use Manhattan distance, calculated as h(n) = |xn − xg | + |yn − yg |, where (xn , yn ) are the
coordinates of node n and (xg , yg ) are the coordinates of the goal.
Visualization:
18
S 17 16 15 14 13 12 11 10 9 8 7 6 5 4
17 16 15 14 13 12 11 10 9 8 7 6 5 4 3
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
14 13 12 11 10 9 8 7 6 5 4 3 2 1 G
Explanation: The Manhattan distance provides a quick and easy-to-compute estimate of the distance to the goal,
ignoring any obstacles that might be in the way. It’s especially effective in grid-based puzzles or mazes.
12/34
Properties of Heuristic Functions
Admissibility: A heuristic is admissible if it never overestimates the true cost to
reach the goal, i.e., h(s) ≤ h∗ (s) for all s ∈ S.
Consistency (Monotonicity): A heuristic is consistent if, for every node n and every
successor n′ , h(n) ≤ c(n, n′ ) + h(n′ ) holds, where c(n, n′ ) is the step cost from n to n′ .
Goal-Awareness: A heuristic is goal-aware if h(s) = 0 for all goal states s ∈ SG.
Implications: Consistency implies admissibility, but not all admissible heuristics are
consistent. Consistent heuristics guarantee that the cost estimate from each node
does not decrease faster than the actual lowest possible cost.
13/34
Good vs. Bad Heuristics
• A good heuristic is admissible, meaning it never overestimates the true cost to
reach the goal. It should also be consistent, ensuring the search is efficient and
optimal.
• Bad heuristics can misguide the search. If a heuristic overestimates, it may
prevent the algorithm from finding the optimal solution.
• Example of a good heuristic: In the 8-puzzle, the Manhattan distance heuristic
measures the sum of the vertical and horizontal distances of each tile from its
goal position.
• Example of a bad heuristic: If the heuristic in the 8-puzzle simply returns a
random number for each state, the search would no longer be directed towards
the goal.
14/34
Heuristic Function Examples
Admissibility and Consistency
• Admissible:
• Example: Straight-line distance.
• It never overestimates the actual minimum distance.
• Non-Admissible:
• Example: Flight costs using peak season prices.
• Overestimates costs during off-peak seasons.
• Consistent:
• Example: Manhattan distance in a grid.
• Step costs align with heuristic predictions.
• Admissible but Inconsistent:
• Example: Hamming distance in puzzles.
• Does not overestimate steps but fails to maintain step-to-heuristic
proportionality.
Note: Consistency implies admissibility. Consistent heuristics ensure more reliable path predictions in search
algorithms like A*.
15/34
Greedy Best-First Search (GBFS)
• Type: Informed
• Strategy: Expands the node that appears closest to the goal according to the
heuristic.
• Advantages:
• Often faster than uninformed search.
• Focuses the search toward the goal.
• Disadvantages:
• Not guaranteed to find the optimal path.
• Can get stuck in local minima or wrong paths.
16/34
Greedy Search
Definition:
• A possible way to judge the “worth” of a node is to estimate its path-costs to
the goal.
• Heuristic h(n) = estimated path-costs from n to the goal.
• The only real restriction is that h(n) = 0 if n is a goal.
• A best-first search using h(n) as the evaluation function, i.e., f(n) = h(n), is
called a greedy search.
Example:
• Route-finding problem:
• h(n) = straight-line distance from n to the goal.
17/34
Greedy Best-First Search
• Goal: Always expand the node with the smallest estimated cost to the goal
(heuristic h(n)).
• Heuristic Function: f(n) = h(n)
• Properties:
• Fast, but not guaranteed to find the shortest path.
• May get stuck in loops or dead-ends.
• Incomplete and Non-Optimal.
• Example: Straight-line distance in route planning.
18/34
General Search Algorithms
Algorithm 1 Tree-Search Algorithm Russell and Norvig (2010)
1: Initialize the frontier using the initial state of problem
2: loop
3: if the frontier is empty then
4: return failure
5: end if
6: Choose a leaf node and remove it from the frontier
7: if the node contains a goal state then
8: return the corresponding solution
9: end if
10: Expand the chosen node, adding the resulting nodes to the frontier
11: end loop
19/34
Greedy Search Example
Figure: Romania Map with actual costs in the arrows connecting the cities and the heuristic costs in
the table on the right Russell and Norvig (2010)
20/34
Greedy Search from Arab to Bucharest
Figure: Arab to Bucharest Greedy SearchRussell and Norvig (2010)
21/34
Greedy Search - Properties
• A good heuristic might reduce search time drastically.
• Non-optimal: Does not necessarily find the best solution.
• Incomplete: May fail to find any solution in some cases.
• The graph-search version is complete only in finite spaces.
Question: Can we do better?
22/34
A* Search
• Type: Informed
• Strategy: Combines the benefits of UCS and GBFS by using both path cost g(n)
and heuristic h(n).
• Advantages:
• Guaranteed to find the optimal solution when the heuristic is admissible.
• Efficiently balances exploration and exploitation.
• Disadvantages:
• Can be memory-intensive.
• Performance depends on the quality of the heuristic.
23/34
Mechanics of A* Search
• A* calculates f(n) = g(n) + h(n) for each node, where g(n) is the known cost to
reach n from the start node, and h(n) is the estimated cost from n to the goal.
• The algorithm always expands the node with the lowest f(n), balancing between
path cost and heuristic estimate.
• The expansion process involves evaluating successor nodes, adding them to
the priority queue, and potentially updating paths to already-visited nodes if a
cheaper path is found.
• This strategic expansion makes A* highly efficient in practice, particularly when
the heuristic closely approximates the true cost.
24/34
A* Search: Minimization of the Estimated Path Costs
Overview:
• A* combines the greedy search with the uniform-search strategy.
• Always expand the node with the lowest f(n) first.
• g(n) = actual cost from the initial state to n.
• h(n) = estimated cost from n to the next goal.
• f(n) = g(n) + h(n), the estimated cost of the cheapest solution through n.
Heuristic Admissibility:
• Let h∗ (n) be the actual cost of the optimal path from n to the next goal.
• h is admissible if for all n, h(n) ≤ h∗ (n) (e.g., straight-line distance is admissible).
• This implies that h is an optimistic estimate of the costs that actually occur.
25/34
Romania Search Example
Figure: Romania Map with actual costs in the arrows connecting the cities and the heuristic costs in
the table on the right Russell and Norvig (2010)
26/34
A* Search: Minimization of the Estimated Path Costs
Overview:
• A* combines the greedy search with the uniform-search strategy.
• Always expand the node with the lowest f(n) first.
• g(n) = actual cost from the initial state to n.
• h(n) = estimated cost from n to the next goal.
• f(n) = g(n) + h(n), the estimated cost of the cheapest solution through n.
Heuristic Admissibility:
• Let h∗ (n) be the actual cost of the optimal path from n to the next goal.
• h is admissible if for all n, h(n) ≤ h∗ (n) (e.g., straight-line distance is admissible).
• This implies that h is an optimistic estimate of the costs that actually occur.
27/34
A* Solution
Figure: A* solution from Arad to Rimnicu Vilcea
28/34
A* Solution
Figure: A* solution from Rimnicu Vilcea to Bucharest
29/34
Optimality of A*
• A* search is optimal if the heuristic h(n) is admissible, meaning it never
overestimates the cost to reach the goal.
• Admissible heuristics ensure that f(n) never overestimates the true cost of a
solution along the current path through n.
• An example of an admissible heuristic is the straight-line distance (hSLD) used in
route finding, as it is the shortest possible path between any two points.
• The optimality of A* is crucial for applications where finding the least costly
path is mandatory, such as in navigation systems or strategic planning in AI.
30/34
Completeness and Complexity of A*
• Completeness: A* search is complete, meaning it will always find a solution if
one exists, provided every step cost exceeds some small positive constant δ .
• This condition ensures that the search does not stall at a node with a cost
significantly lower than the actual minimum, preventing infinite loops.
• Complexity: The time complexity of A* is generally exponential in terms of the
length of the solution path due to the number of nodes generated. This is
especially true when the heuristic is not close enough to the true cost.
• In practice, the space complexity can also become a limiting factor, as all
generated nodes must be stored.
31/34
Admissible and Consistent Heuristics
• Admissible heuristics are optimistic, assuming the cost of reaching the goal is
less than the actual cost.
• Consistency, or monotonicity, a stronger condition, ensures that h(n) is not only
optimistic but also satisfies the triangle inequality with respect to the cost
function.
• For a heuristic to be consistent, for every node n and every successor n′ , it must
hold that: h(n) ≤ c(n, n′ ) + h(n′ ).
• While all consistent heuristics are admissible, not all admissible heuristics are
consistent. Consistency is particularly important for graph-search versions of
A* to avoid revisiting nodes.
32/34
Reference
Some slides and ideas are adapted from the following sources:
• Artificial Intelligence: A Modern Approach Russell and Norvig (2010)
33/34
Thank you for your attention
October 6, 2024
Russell, S. and Norvig, P. (2010). Artificial Intelligence: A Modern Approach. Prentice
Hall, 3 edition.
34/34
