Informed Search Methods

Informed Search Methods

• Informed search strategies use problem-specific knowledge to find solutions more efficiently than uninformed strategies.
• Also known as heuristic search.

Best-First Search

• Best-first search exemplifies a general tree or graph search where node expansion hinges on an evaluation function, f(n).
• The evaluation function estimates cost; the node with the lowest evaluation expands first.

Informed Search Strategies

• Informed search strategies utilize additional information, such as a heuristic function h(n), to estimate the cost from a node to the goal.
• Heuristics differentiate informed from uninformed search algorithms, which lack domain-specific knowledge.

Key Characteristics of Informed Search

• Heuristic Function: It estimates the minimal cost from a node to the goal, prioritizing nodes for exploration based on their potential for optimal solutions.
  • h(n) = estimated cost of the cheapest path from node n's state to the goal state.
• Efficiency: Informed searches often find solutions faster in complex spaces by focusing on promising paths.
• Optimality and Completeness: Informed searches can be optimal and complete, depending on the heuristic used; completeness guarantees a solution if one exists, while optimality ensures the best solution is found.

Informed Search Algorithms

• Greedy Best-First Search: It prioritizes node exploration based on estimated cost to the goal as determined by a heuristic function; f(n) = h(n).
• Nodes are expanded based on their closeness to the goal, potentially leading to quicker solutions.

Straight-Line Distance Heuristic

• Straight-line distance heuristic (hSLD) can be used to tackle route-finding issues.
• It needs the straight-line distances to the goal (e.g., Bucharest).
• The values of hSLD can’t be derived from the problem description and benefit from experience to correlate with road distances, making it valuable.
  • hSLD (In(Arad)) = 366 as an example.

Greedy Best-First Search Application

• The initial expansion from Arad targets Sibiu due to its proximity to Bucharest compared to Zerind or Timisoara.
• Subsequently, Fagaras is expanded for being closest.

Incompleteness of Greedy Best-First Tree Search

• Can be incomplete even in finite state spaces, similar to depth-first search
• An example is the inability to find a route from Iasi to Fagaras, which leads to an infinite loop due to repeatedly expanding Neamt and Iasi without reaching the goal.
• Graph search version is complete in finite spaces, but remains incomplete in infinite ones.

A* Search: Minimizing Solution Cost

• A* search evaluates nodes using f(n) = g(n) + h(n), where g(n) is the cost to reach the node, and h(n) is the estimated cost to the goal.
• It aims to find the cheapest solution by prioritizing nodes with the lowest f(n) value, balancing actual path cost and estimated future cost with the help of the heuristic function h(n).

Conditions for Optimality: Admissibility

• Admissibility: h(n) must never overestimate the cost to reach the goal; it ensures f(n) never overestimates the true cost through n.
• Admissible heuristics are optimistic, considering problem-solving costs lower than actual costs.
• Straight-line distance (hSLD) is an admissible heuristic, as the shortest path between points is a straight line.
• An example in the context of searching for Bucharest shows that expansion of Pitesti (f-cost 417) occurs before Bucharest (f-cost 450).

Conditions for Optimality: Consistency

• Consistency: A heuristic h(n) is consistent (or monotonic) if h(n) ≤ c(n, a, n’) + h(n’) for every node n and successor n’.
• It follows the triangle inequality, ensuring the estimated cost from n to the goal isn't more than the cost to a successor n' plus the estimated cost from n' to the goal.
• Such inequality makes sense with admissible heuristic.

Memory-Bounded Heuristic Search or IDA* (Iterative Deepening A*)

• IDA* reduces memory use in A* search by adapting iterative deepening to the heuristic search context.
• IDA* differs by using f-cost (g + h) as the cutoff instead of depth, with the cutoff value being the smallest f-cost exceeding the previous cutoff at each iteration.

Developing and Applying Heuristic Functions

• Methods in designing heuristic functions can guide search algorithms.

Approaches for Heuristic Design

• Domain Knowledge: Use expert knowledge for heuristics construction.
• Relaxation: Simplify the problem to derive heuristics then transfer them back.
• Pattern Databases: Store precomputed values for specific subgoals to efficiently lookup during search.

Admissibility vs Informativeness

• Balancing admissibility and informativeness is vital for heuristic design.
• Admissibility ensures that heuristics never overestimate the true cost to reach the goal state, providing a lower bound and supporting exploration of all potentially optimal paths.
• Informativeness refers to heuristics that estimate the true cost more accurately, guiding the search more effectively.

Heuristic Function Examples

• Puzzle Solving (8-Puzzle): Heuristics can count misplaced tiles or calculate Manhattan distance.
• Route Planning (A Algorithm): Base heuristics on estimated travel distances from map data.
• Game-Playing:
  • Chess heuristics consider material balance, king safety, mobility, and center control.
  • Video games evaluate paths based on terrain, enemies, and mission objectives.

Trade-off

• Admissible Heuristics: These heuristics guarantee an optimal solution but can be less informative
• Informed (or Informative) Heuristics: Offers a more accurate estimation of true cost to guide the search more effectivel but doesn't guarantee optimal solutions