Advance Artificial Intelligence
9999 Rs


Informed Search

  • A search using domain-specific knowledge.
  • Suppose that we have a way to estimate how close a state is to the goal, with an evaluation function.
  • General strategy: expand the best state in the open list first. It's called a best-first search or ordered state-space search.
  • In general the evaluation function is imprecise, which makes the method a heuristic (works well in most cases).
  • The evaluation is often based on empirical observations.

Learning Out Comes 

  • A search problem consists of:
    • A State Space. Set of all possible states where you can be.
    • A Start State. The state from where the search begins.
    • A Goal Test. A function that looks at the current state returns whether or not it is the goal state.
  • The Solution to a search problem is a sequence of actions, called the plan that transforms the start state to the goal state.
  • This plan is achieved through search algorithms.

So far we have talked about the uninformed search algorithms which looked through search space for all possible solutions of the problem without having any additional knowledge about search space. But informed search algorithm contains an array of knowledge such as how far we are from the goal, path cost, how to reach to goal node, etc. This knowledge help agents to explore less to the search space and find more efficiently the goal node.

The informed search algorithm is more useful for large search space. Informed search algorithm uses the idea of heuristic, so it is also called Heuristic search.

Heuristics function: Heuristic is a function which is used in Informed Search, and it finds the most promising path. It takes the current state of the agent as its input and produces the estimation of how close agent is from the goal. The heuristic method, however, might not always give the best solution, but it guaranteed to find a good solution in reasonable time. Heuristic function estimates how close a state is to the goal. It is represented by h(n), and it calculates the cost of an optimal path between the pair of states. The value of the heuristic function is always positive.



learn now