What is Informed Search in Artificial Intelligence?

A key idea in artificial intelligence (AI) and search algorithms is informed search, which improves problem-solving effectiveness by using more information about the issue at hand. In this blog, we’ll explore informed search in the world of AI, various types, and some notable case studies. Understanding ‘Informed Search’ is like having a trusty map and compass for AI’s journey.

Enhance your artificial intelligence knowledge with this exclusive training video featuring real-world expertise.

What is Informed Search?

Informed search is a type of search algorithm in artificial intelligence that uses additional information or heuristics to make more accurate decisions about which paths to explore first. These heuristics provide estimates of how close a given state is to the goal, guiding the search toward more promising solutions. Informed search is particularly useful in solving complex problems efficiently, as it can significantly reduce the search space and improve the speed of finding solutions.

Informed search algorithms can quickly reject irrelevant or less promising alternatives, allowing the search to concentrate on the most reliable options, by employing domain-specific knowledge to drive the search. Heuristics are used by these kinds of AI search algorithms to increase the search’s effectiveness and speed.

What is the Need for Informed Search?

The need for informed search in artificial intelligence arises from several key factors that make it a valuable approach for solving problems efficiently and effectively. Here are some of the primary reasons why an informed search is essential:

• Domain Knowledge: Heuristics are a type of domain-specific knowledge that may be used in informed search algorithms. With this information, the search process can be directed in ways that are not possible with blind search techniques. For example, a heuristic based on real-time traffic information can help avoid busy routes while planning a trip.
• Pattern Recognition: In order to find patterns or characteristics in data more effectively, informed search can be utilized in pattern recognition tasks. Heuristic-guided search, for example, can enhance model training and feature selection in machine learning.
• Efficiency: In general, informed search algorithms beat blind (uninformed) search algorithms in terms of efficiency. They may reduce the search space and frequently find solutions more rapidly by making well-informed selections about which paths to look at first using heuristic knowledge. This effectiveness is crucial in general, complicated problem fields.
• Complex Decision Making: Applications that require complicated decision-making processes, such as playing games (like chess or go), are helped by informed search. Machine learning robots can analyze future moves and strategies more effectively with the use of heuristic knowledge.
• Problem Complexity: Many issues in the real world have large search areas and are very difficult. Thanks to informed search, AI systems can more successfully navigate these complex topographies by concentrating on the most promising areas. Blind search algorithms might have trouble finding answers in an appropriate amount of time without heuristics.

Types of Informed Search in Artificial Intelligence

There are various types of informed search algorithms in artificial intelligence (AI), each with a unique method for applying heuristics and other data to guide the search for solutions. Here are some regular classifications of informed search algorithms:

Heuristic Function

A heuristic function is a strategy for solving problems by determining the cost or distance to a goal state in a search problem by making a “best guess” or using a rule of thumb. A search algorithm can be directed in the right direction by using the heuristic function, which calculates how far the objective state is from the present state.

These features are used by intelligent search engines as an extra source of data to decide which course to take. Heuristic functions are crucial in informed search algorithms for this reason.

Example:

A player can begin the game of tic tac toe from a variety of positions, and each position has a different chance of winning. The first player, however, has the best chance of succeeding if they begin from the middle of the board. As a result, winning chances can be used as a heuristic.

Pure Heuristic Function: The most basic type of heuristic search algorithm is pure heuristic search. Nodes are expanded according to their heuristic value, h(n). It keeps an OPEN list and a CLOSED list. It lists the nodes that have already expanded in the CLOSED list and the nodes that haven’t expanded yet in the OPEN list.

Each node n with the lowest heuristic value is expanded, producing all of its children, and then n is added to the closed list. The algorithm keeps running until a goal state is found.

The admissibility of the Heuristic function is given as

h(n) <= h*(n)

Here h(n) is the Heuristic cost, and h*(n) is the estimated cost. Hence, the heuristic cost should be less than or equal to the estimated cost.

Best First Search

The path that appears to be the best at the time is always chosen by the greedy best-first search algorithm. It combines techniques like depth-first search and breadth-first search. It uses search and the heuristic function. We can benefit from both algorithms’ advantages by using best-first search. We can select the most promising node at each stage using a best-first search. The node that is nearest to the goal node is expanded using the best first search technique, and the closest cost is calculated using a heuristic function.

We expand the node that is closest to the goal node, and the closest cost is estimated by a Heuristic function, i.e. f(n)= h(n). 

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

Steps to perform in this algorithm:

• Step 1: The initial node should first be added to the OPEN list.
• Step 2: Stop and return failure if the OPEN list is empty.
• Step 3: Move the node n that has the lowest h(n) value out of the OPEN list and into the CLOSED list.
• Step 4: Generate the successors of node n and expand node n.
• Step 5: Determine whether or not each successor of node n is a goal node. Return success and end the search if any successor node is the goal node; otherwise, move on to Step 6.
• Step 6: The method examines each successor node for the evaluation function f(n) before determining whether it has ever been in the OPEN or CLOSED list. Add the node to the OPEN list if it hasn’t already been there.
• Step 7: Return to Step 2.

Example:

Certainly, let’s use the Best-First Search algorithm with the given heuristic values for nodes S, A, B, C, D, H, F, G, and E. We’ll explore how the algorithm works based on these heuristics.

Here’s a table representing the nodes and their heuristic values:

Initialization:

Start with the initial state, which is node S.

Add S to the open list with a heuristic value of 10.

Node Expansion:

The algorithm selects the node from the open list with the lowest heuristic value. In this case, it’s node B with a heuristic value of 7.

Expand node B and generate its successors (nodes H and A).

Add H and A to the open list with heuristic values of 6 and 9, respectively.

Continued Expansion:

The algorithm selects node H from the open list with a heuristic value of 6.

Expand node H and generate its successor G.

Add G to the open list with a heuristic value of 3.

Further Expansion:

The algorithm selects node G from the open list with a heuristic value of 3.

Expand node G and generate its successor E.

Add E to the open list with a heuristic value of 0.

Goal Reached:

The algorithm terminates upon reaching the goal state, which is node E with a heuristic value of 0.

Result: The correct path found by the Best-First Search algorithm based on the given heuristic values is indeed S -> B -> H -> G -> E.

A* Search

A* search is the most commonly known form of best-first search. The heuristic function h(n), along with the distance from the initial state g(n) to the node n, is used. Due to the combination of UCS and greedy best-first search features, the issue is effectively solved. Using the heuristic function, the A* search method locates the shortest route through the search space. This search algorithm produces the best results more quickly and extends the search tree a little less. In contrast to UCS, the A* algorithm utilizes g(n)+h(n) instead of g(n).

We use both the search heuristic and the node-reach cost in the A* search method. Therefore, we can add both costs as follows; this total is known as the fitness number.

f(n)=g(n)+h(n)

Steps to perform in this algorithm:

• Step 1: Place the beginning node in the OPEN list as the first step.
• Step 2: Verify whether or not the OPEN list is empty; if it is, return failure and stop.
• Step 3: Choose the node from the OPEN list that has the evaluation function (g+h) with the least value. Return success and stop if node n is the destination node; otherwise, continue. 
• Step 4: Generate all of the successors for node n, expand it, and add it to the closed list. Check to see if each successor, n’, is already in the OPEN or CLOSED list before computing its evaluation function and adding it to the Open list.
• Step 5: If node n’ is not already in OPEN or CLOSED, it should be attached to the back pointer, which represents the value with the lowest g(n’) value.
• Step 6: Return to Step 2 in Step 6.

Example: Given the heuristic values and distances between nodes, let’s use the A* algorithm to find the optimal path from node S to node G.

Here’s the table representing the nodes, their heuristic values, and the distances between nodes:

Initialization:

Start with the initial state, which is node S.

Create an open list and add S to it with a cost of 0 (initial cost) and a heuristic value of 5 (estimated cost to reach G).

Node Expansion:

The algorithm selects the node from the open list with the lowest cost + heuristic value. In this case, it’s node S with a cost of 0 + 5 = 5.

Expand node S and generate its successor nodes A and G.

Calculate the cost to reach A and G and add them to the open list.

Continued Expansion:

The algorithm selects node A from the open list with a cost of 1 (cost to reach A) + 3 (heuristic value of A) = 4.

Expand node A and generate its successor node C.

Calculate the cost to reach C and add it to the open list.

Goal Reached:

The algorithm terminates upon reaching the goal state, which is node G with a cost of 10 (cost to reach G) + 0 (heuristic value of G).

Result:

The A* algorithm finds the optimal path from node S to node G: S -> A -> C -> G.

This path has the lowest cost among all possible paths, considering both the actual distance and the heuristic values.

In this example, the A* algorithm efficiently finds the optimal solution, and the optimal path is indeed S -> A -> C -> G with a cost of 10.

Hill Climbing

• To ascertain the summit of a mountain or to identify the optimal solution to a given problem, one may employ the hill climbing algorithm. This algorithm, categorized as a local search technique, perpetually advances in the direction of elevated terrain or increased value. When it reaches a peak value where none of its neighbors have a greater value, it ends.
• The hill climbing algorithm is a method for solving mathematical problems with optimization. Traveling-salesman is one of the most frequently mentioned cases of a hill climbing algorithm problem where we need to reduce the salesman’s journey distance.
• It is also known as greedy local search since it only conducts searches in its favorable immediate neighbor state and not beyond.
• State and value are the two components of a hill climbing algorithm node.
• When a reliable heuristic is available, hill climbing is typically used.
• Since this algorithm merely retains a single current state, we don’t need to manage or maintain the search tree or graph.

Features of Hill Climbing Algorithm:

• Greedy Strategy: The search for a hill-climbing algorithm advances in the direction where the cost is optimized
• No Backtracking: Since it cannot recall past states, it does not go back into the search space.
• Generate and Test Variant: The Generate and Test method has a version called Hill Climbing. Feedback from the Generate and Test approach aids in choosing which way to move through the search space.

Difference Between Informed and Uninformed Search

The most notable difference between informed search and uniformed search is given below:

Use Cases of Informed Search in AI

Many different domains have used informed search algorithms, which employ heuristic data to direct their search for solutions. Following are some common situations for an informed search:

• Navigating by Pathfinding: For GPS systems and mapping applications, route planning frequently makes use of informed search algorithms. They assist in determining the shortest or swiftest route between two points while taking into account current traffic patterns and the state of the roads.
• Playing a Game: Playing agents in board games like chess, checkers, and Go can make wise decisions with the aid of informed search algorithms like minimax with alpha-beta pruning and heuristic-based evaluation functions.
• Vehicle Autonomy and Robotics: Informed search is used in autonomous robots and vehicles for activities including path following, obstacle avoidance, and motion planning. It helps robots efficiently navigate difficult conditions.
• Timetabling and Scheduling: Informed search can enhance resource allocation and reduce conflicts in scheduling applications like staff scheduling, airline scheduling, and class scheduling.
• Routing on a Network: In computer networks, informed search algorithms are used to choose the best paths for data packets while accounting for network latency and congestion. 

Conclusion

Informed search algorithms are vital in AI, enhancing the efficiency of goal-oriented searches through heuristic-driven guidance. The future holds potential for refining heuristics and expanding applications across diverse AI domains. By employing heuristic functions to assess moving costs and directing the search process, these algorithms pave the way for quicker problem-solving and improved computational resource utilization.