Learn about informed search in artificial intelligence including heuristics, Greedy Best First Search, A* algorithm, and admissible heuristics with examples and applications.

Artificial Intelligence relies heavily on search algorithms to solve complex problems efficiently. Among these, informed search algorithms play a crucial role because they use additional knowledge to guide the search process. Unlike uninformed search methods such as Breadth-First Search or Depth-First Search, informed search strategies use heuristics to estimate the most promising path toward a goal.

This article explores Informed Search in AI, covering heuristics, Greedy Best First Search, the A Algorithm, and admissible heuristics* in depth. Understanding these concepts is essential for AI applications such as robot navigation, pathfinding, game playing, and optimization problems.

What is Informed Search in Artificial Intelligence?

Informed search, also known as heuristic search, is a search strategy that uses problem-specific knowledge to find solutions more efficiently than uninformed methods.

Instead of exploring all possible paths blindly, informed search algorithms use heuristic functions to estimate how close a state is to the goal.

Key Characteristics of Informed Search

• Uses domain knowledge to guide search.
• Reduces the number of explored nodes.
• Improves efficiency and performance.
• Often used in pathfinding and optimization problems.

Example

Consider a GPS navigation system. Instead of exploring every possible road, it estimates the distance to the destination and chooses the most promising routes first. This estimation is the heuristic function.

Heuristics in Artificial Intelligence

Definition of Heuristics

A heuristic is a function that estimates the cost or distance from the current state to the goal state.

It is usually represented as:$$h(n)$$Where:

• h(n) = estimated cost from node n to the goal.

Heuristics help search algorithms decide which node to explore next.

Characteristics of Good Heuristics

A good heuristic function should:

1. Be easy to compute.
2. Provide accurate estimates.
3. Never overestimate the actual cost (for optimal algorithms).
4. Reduce unnecessary exploration.

Example of Heuristic

Imagine finding the shortest route between two cities.

Possible heuristic:

• Straight-line distance (Euclidean distance) between the cities.

Even though roads may not be straight, this estimate helps guide the search.

Types of Heuristic Functions

1. Manhattan Distance

Used in grid-based problems like puzzles.

Formula:$$h(n) = |x_1 – x_2| + |y_1 – y_2|$$Common in:

• 8-puzzle problem
• Grid navigation

2. Euclidean Distance

Used when movement is continuous.

Formula:$$h(n) = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$$Common in:

• Robotics
• Path planning

Greedy Best First Search

What is Greedy Best First Search?

Greedy Best First Search (GBFS) is an informed search algorithm that always expands the node that appears closest to the goal according to the heuristic function.

It selects nodes based purely on:$$f(n) = h(n)$$Where:

• h(n) = estimated cost to reach the goal.

The algorithm always chooses the node with the smallest heuristic value.

How Greedy Best First Search Works

Steps:

1. Start with the initial node.
2. Evaluate its heuristic value.
3. Insert nodes into a priority queue.
4. Expand the node with the lowest heuristic value.
5. Continue until the goal is found.

Example

Suppose we want to find the shortest path between cities.

The heuristic is straight-line distance to the destination.

Greedy search always chooses the city closest to the goal according to the heuristic.

A Algorithm Explanation – Wikipedia

Advantages of Greedy Best First Search

• Faster than uninformed search
• Requires fewer node expansions
• Easy to implement

Disadvantages

• Not guaranteed to find the optimal solution
• Can get stuck in local minima
• Performance depends heavily on heuristic quality

A* Algorithm in Artificial Intelligence

What is the A* Algorithm?

The A (A-Star) algorithm* is one of the most popular and powerful informed search algorithms. It combines the advantages of Uniform Cost Search and Greedy Best First Search.

The evaluation function is:$$f(n) = g(n) + h(n)$$Where:

• g(n) = cost from start node to current node
• h(n) = estimated cost from current node to goal
• f(n) = total estimated cost of the solution path

How A* Search Works

Steps:

1. Start from the initial node.
2. Calculate g(n) and h(n).
3. Compute f(n) = g(n) + h(n).
4. Select the node with the lowest f(n) value.
5. Expand it and update neighbors.
6. Continue until the goal is reached.

Example of A* Algorithm

In a map navigation system:

• g(n) = distance traveled so far
• h(n) = straight-line distance to destination

The algorithm chooses the path with the lowest total estimated distance.

Lecture 4: Uninformed Search

Why A* is Better

A* balances:

• Actual path cost
• Estimated remaining cost

This makes it both efficient and optimal.

Applications of A* Algorithm

A* is widely used in:

• GPS navigation systems
• Video game pathfinding
• Robotics
• Network routing
• Logistics and planning

Admissible Heuristic

Definition

A heuristic is admissible if it never overestimates the true cost to reach the goal.

Formally:$$h(n) \leq h^*(n)$$Where:

• h(n) = heuristic estimate
• h*(n) = true minimal cost

Why Admissible Heuristics Matter

Admissible heuristics guarantee that A* will always find the optimal solution.

If the heuristic overestimates the cost, the algorithm might choose a non-optimal path.

Example of Admissible Heuristic

Straight-line distance in maps is admissible because:

• The actual road distance can never be shorter than the straight-line distance.

Consistent vs Admissible Heuristics

A consistent heuristic satisfies:$$h(n) \leq c(n,n’) + h(n’)$$Where:

• c(n,n’) = cost between nodes

Consistency ensures that the heuristic value decreases smoothly along paths.

All consistent heuristics are admissible, but not all admissible heuristics are consistent.

Comparison of Informed Search Algorithms

Algorithm	Evaluation Function	Optimal	Speed
Greedy Best First Search	f(n) = h(n)	No	Fast
A* Algorithm	f(n) = g(n) + h(n)	Yes (with admissible heuristic)	Efficient
Uniform Cost Search	f(n) = g(n)	Yes	Slower

Real World Applications of Informed Search

Informed search algorithms are widely used in modern technology.

1. Navigation Systems

Google Maps and GPS use A search* to find shortest routes.

2. Video Games

Game characters use pathfinding algorithms to move intelligently.

3. Robotics

Robots use heuristics to plan movement paths.

4. AI Planning

Used in scheduling, logistics, and decision-making systems.

Conclusion

Informed search algorithms significantly improve the efficiency of problem solving in Artificial Intelligence. By incorporating heuristic knowledge, these algorithms reduce unnecessary exploration and guide the search toward the goal more effectively.

Key concepts include:

• Heuristics, which estimate the distance to the goal
• Greedy Best First Search, which focuses on heuristic values
• A Algorithm*, which balances actual and estimated costs
• Admissible heuristics, which guarantee optimal solutions

These techniques are fundamental to modern AI applications such as navigation systems, robotics, gaming, and intelligent planning systems.

Understanding informed search algorithms provides a strong foundation for advanced topics in Artificial Intelligence and Machine Learning.

Multiple Choice Questions (MCQs)

1. What is the main idea behind informed search algorithms?
A) Explore all nodes equally
B) Use additional knowledge to guide the search
C) Avoid using heuristics
D) Only use depth-first exploration

Answer: B) Use additional knowledge to guide the search

2. In informed search, the heuristic function is represented as:
A) g(n)
B) f(n)
C) h(n)
D) c(n)

Answer: C) h(n)

3. A heuristic function estimates:
A) Distance from start to node
B) Cost of entire graph
C) Distance from node to goal
D) Number of nodes

Answer: C) Distance from node to goal

4. Which search algorithm uses only heuristic values to select nodes?
A) A* Search
B) Uniform Cost Search
C) Greedy Best First Search
D) Breadth First Search

Answer: C) Greedy Best First Search

5. The evaluation function of Greedy Best First Search is:
A) f(n) = g(n) + h(n)
B) f(n) = g(n)
C) f(n) = h(n)
D) f(n) = n²

Answer: C) f(n) = h(n)

6. The A algorithm combines which two types of search?*
A) DFS and BFS
B) Greedy Search and Uniform Cost Search
C) BFS and UCS
D) DFS and Greedy Search

Answer: B) Greedy Search and Uniform Cost Search

7. The evaluation function used in A search is:*
A) f(n) = g(n)
B) f(n) = h(n)
C) f(n) = g(n) + h(n)
D) f(n) = n + 1

Answer: C) f(n) = g(n) + h(n)

8. In the A algorithm, g(n) represents:*
A) Estimated cost to goal
B) Cost from start to current node
C) Total nodes visited
D) Goal state value

Answer: B) Cost from start to current node

9. In the A algorithm, h(n) represents:*
A) Path cost
B) Total cost
C) Heuristic estimate to goal
D) Node weight

Answer: C) Heuristic estimate to goal

10. A heuristic is admissible if it:
A) Overestimates cost
B) Underestimates or equals the true cost
C) Is always zero
D) Is always maximum

Answer: B) Underestimates or equals the true cost

11. Which algorithm guarantees optimal solution with admissible heuristic?
A) DFS
B) BFS
C) Greedy Best First Search
D) A* Search

Answer: D) A* Search

12. Which heuristic is commonly used in grid problems?
A) Manhattan Distance
B) Binary Distance
C) Random Distance
D) Linear Distance

Answer: A) Manhattan Distance

13. Which of the following is NOT a property of good heuristics?
A) Easy to compute
B) Accurate estimate
C) Always overestimates
D) Guides search efficiently

Answer: C) Always overestimates

14. A algorithm is widely used in:*
A) Database management
B) Pathfinding and navigation
C) Text editing
D) File compression

Answer: B) Pathfinding and navigation

15. Which of the following is an example of heuristic search?
A) Depth First Search
B) Breadth First Search
C) Greedy Best First Search
D) Linear Search

Answer: C) Greedy Best First Search

Short Question Answers

1. What is informed search?

Answer:
Informed search is a search strategy that uses problem-specific knowledge (heuristics) to guide the search toward the goal more efficiently.

2. What is a heuristic function?

Answer:
A heuristic function h(n) estimates the cost or distance from the current node to the goal state.

3. What is Greedy Best First Search?

Answer:
Greedy Best First Search is an informed search algorithm that selects the node with the lowest heuristic value h(n), assuming it is closest to the goal.

4. What is the evaluation function of A* search?

Answer:$$f(n) = g(n) + h(n)$$Where
g(n) = cost from start to node
h(n) = estimated cost to goal

5. What is an admissible heuristic?

Answer:
An admissible heuristic never overestimates the actual cost to reach the goal, ensuring optimal solutions.

6. What is the difference between Greedy Search and A*?

Answer:
Greedy Search uses only h(n), while A* uses g(n) + h(n), making A* more reliable and optimal.

7. Give an example of heuristic function.

Answer:
Straight-line distance between two cities in navigation systems.

8. What is Manhattan Distance?

Answer:
Manhattan Distance is a heuristic used in grid problems:$$|x_1-x_2| + |y_1-y_2|$$

9. Why are heuristics important in AI?

Answer:
Heuristics reduce the number of explored nodes and improve search efficiency.

10. Name two applications of informed search.

Answer:

1. GPS navigation systems
2. Video game pathfinding

Long Questions Answers

Question 1

Explain informed search in Artificial Intelligence. Discuss heuristics and Greedy Best First Search.

Answer

Informed search is a search strategy in Artificial Intelligence that uses heuristic information to guide the search process toward the goal efficiently. Unlike uninformed search algorithms that explore blindly, informed search algorithms use additional knowledge about the problem domain.

Heuristics

A heuristic is a function that estimates the distance or cost from the current state to the goal state.

Mathematically:$$h(n)$$Where n is the current node.

Heuristics help algorithms determine which node should be expanded next.

Examples include:

• Straight-line distance
• Manhattan distance
• Euclidean distance

Greedy Best First Search

Greedy Best First Search is an informed search algorithm that selects the node with the lowest heuristic value.

Evaluation function:$$f(n) = h(n)$$The algorithm always expands the node that appears closest to the goal.

Advantages

• Fast search
• Reduces explored nodes

Disadvantages

• Not guaranteed to find optimal solution
• May get stuck in local minima

Greedy search is commonly used in pathfinding and navigation problems.

Question 2

Explain the A Algorithm and Admissible Heuristics with examples.*

Answer

The A algorithm* is one of the most efficient informed search algorithms used in Artificial Intelligence. It combines the advantages of Uniform Cost Search and Greedy Best First Search.

Evaluation Function

$$f(n) = g(n) + h(n)$$Where:

• g(n) = actual cost from start node to current node
• h(n) = heuristic estimate to the goal
• f(n) = estimated total cost of the solution path

The algorithm always expands the node with the lowest f(n) value.

Working of A*

1. Start with initial node
2. Calculate g(n), h(n), and f(n)
3. Insert nodes into priority queue
4. Expand node with lowest f(n)
5. Continue until goal is reached

Admissible Heuristic

A heuristic is admissible if it never overestimates the actual cost to reach the goal.

Condition:$$h(n) \leq h^*(n)$$Where h*(n) is the true cost.

Example

In navigation systems, straight-line distance is an admissible heuristic because the actual road distance cannot be shorter than the straight-line distance.

Importance

Admissible heuristics guarantee that A search always finds the optimal path*.