Anshul Jain
22 Apr 2020
From agents to search algorithms and its strategy uninformed search, in our last few articles, we covered the three important components of problem-solving used by AI machines and systems and the role they play in enabling them to reach the goal or find the accurate solution. The focus, however, will be now on the fourth important component of solving a problem, i.e. Informed Search. Uninformed Search Algorithm, which is one of the categories of Search Algorithm, is used to traverse the search space to search for all possible solutions to the problem, without any additional or domain knowledge. However, it is not as efficient as its counterpart, the informed search.
Therefore, to understand what makes the informed search, the second category of search algorithms, more efficient, we are going to discuss it in detail, along with the various search strategies it uses to achieve the goal state.
Introduction to Informed Search Algorithm:
As stated earlier, Uninformed Search does not require any additional information to search for the most suitable solution for the problem. However, unlike its counterpart, informed search requires both- domain knowledge and the details provided in problem definition to search/traverse the search space and reach the goal node, and is therefore considered more efficient.
Informed Search Algorithm, is short, contains an array of knowledge, like distance to the goal, path cost, steps to reach the goal node, among others, which helps it reach the solution more efficiently, without compromising time and cost of the search. However, to achieve this it uses the heuristic function, which is further based on evaluation applied to states in the search tree. Other characteristics of Informed Search Algorithm are:
- It is also known as Directed Search or Heuristic Search.
- Tries to reduce the amount of search.
- Dependent on the evaluation function to determine the ordering of operations.
- The number of nodes that lead to good heuristic is placed in front.
- Evaluation is often based on empirical observations.
- It is more useful for large search space.
Heuristic Function: The Important Component of Informed Search
Informed Search and the various informed search techniques use the idea of heuristic or the heuristic function for problem-solving, as it enables the agents to reach the goal using the lowest costing path. Heuristic Function is an estimate of the cost of the path from the current or initial state to the goal state, which is used to construct an evaluation function as well as to evaluate the most promising path to reach a state space.
Furthermore, this problem-specific component of informed search can be termed admissible heuristic in cases when the estimated cost is always lower than or equal to the actual cost of reaching the goal state. It is this problem-specific knowledge that is used by informed search strategies to find the optimal solution faster.
The admissibility of the heuristic function is given as: h(n) <= h*(n) Wherein h(n) is heuristic cost and h*(n) the estimated cost.
So, now that we understand the informed search algorithm, let us now discuss the types of informed search strategies.
What is Informed Search Strategy?
Informed Search is classified into three major types, which use different paths and tree state to reach the goal or solution. These have different time and space complexity and the number of nodes involved in the process of problem-solving.
1. Greedy Search:
Also known as Best First Searches, Greedy search expands the node that appears to be the closest to the goal. This strategy is quite similar to an uninformed search’s uniform-cost search strategy, with a minor difference that it orders nodes by their heuristic estimates rather than the cost of paths from the start state.
Though more efficient than breadth-first search and depth-first search, in its worst-case performance, the greedy search can behave like an unguided depth-first search and get stuck in a loop.
Example:
A route-finding problem, that straight-line distances from the node to the goal, can be used to evaluate each node.
2. A* Search:
Considered to be the best search algorithm used in path-finding and graph traversals, A* Search is optimal, complete, and efficient, as it has combined features of Uniform-Cost Search (UCS) and Greedy Search, which allows it to solve very complex problems. This search algorithm maximizes the total estimated cost that includes the cost of reaching a state as well as reaching the goal from the goal.
A*Search provides optimal results fasters, as it finds the shortest path through the search space, using the heuristic function and expands the search tree. However, there is one drawback, it keeps all generated nodes in memory, which makes it not suitable for various large-scale problems.
A* Search can be used in the following two manners:
A) A* Tree Search:
This type of A* Search is optimal when the heuristic used is admissible. A* Tress Search is called tree search as it builds a search tree, rather than a search graph to reach the solution. Failure to detect repeated states can cause exponentially more work.
B) A* Graph Search:
A* Graph Search, the second type of A* Search, places stronger demands on the heuristic, requiring it to be consistent. It can only be optimal in the presence of an admissible heuristic and not a consistent heuristic, by using a cost-sensitive closed set. This, unlike A* Tress Search, eliminates repeated work by maintaining a closed set of expanded nodes and only adding those which are not in the closed set.
Conclusion:
Among the various components that enable agents to effectively reach the goal and deliver solutions, the significance of the Informed Search Algorithm is extremely high. It ensures search space is searched or traversed efficiently by agents, without compromising the time, cost, and speed of search. In short, the Informed Search Algorithm helps agents overcome the drawbacks of Uninformed Search and improves the way they reach an accurate solution.
To understand ‘What is the Difference Between Uninformed Search and Informed Search Strategies?’, click here.
