Informed Search

Informed search, also known as heuristic search, addresses the limitations of "blind" uninformed search by using domain-specific knowledge to guide the agent toward the goal. Unlike uninformed strategies, which have no sense of direction, informed search uses an evaluation function to estimate the "goodness" of a successor node

1. Heuristic Functions (h(n))

A heuristic function, denoted as h(n), estimates the cost to reach a goal state from a given node n

• Source of Knowledge: These functions are typically designed based on human intuition rather than formal mathematical derivations

• Purpose: They provide the agent with a sense of direction, allowing it to prioritize successors that appear closer to the goal

2. Best First Search

This algorithm implements the OPEN list as a heap or priority queue

• Mechanics: It calculates h(n) for each unexplored node and chooses the one with the best (usually minimum) value

• Difference from Uniform Cost Search: While Uniform Cost Search only considers the cost to process a successor, Best First Search uses the heuristic to estimate the future cost to reach the goal

• Limitation: It is not necessarily optimal because it ignores the cost already incurred (g(n)) from the starting state to the current node

A* Search

A* search is a more sophisticated strategy that avoids successors that are already expensive to reach

. It defines a node's utility using the function: f(n)=g(n)+h(n)

• g(n): The total cost from the start state to node n (History)

• h(n): The estimated cost from node n to the goal (Future estimate)

• f(n): The estimated total cost of the path from start to goal going through node n

4. Heuristic Properties

For A* to be effective, its heuristics should meet specific criteria:

• Admissibility: A heuristic is admissible if it is optimistic, meaning it never overestimates the true cost to reach the goal (h(n)≤h∗(n))

• Consistency (Monotonicity): A stricter condition where for every node n and its successor n′, the estimate follows the triangle inequality: h(n)≤h(n′)+c(n,a,n′)

• Optimality: A search is guaranteed to be optimal* if the heuristic used is consistent

5. Variants of A*

• (Iterative Deepening A): Similar to Iterative Deepening DFS, it uses a limit on the utility f(n) to manage space complexity**

• :* This version uses a weight parameter w to trade off between past costs and future estimates: f(n)=g(n)+w⋅h(n)

. In practice, a weight of w=5 often works well

6. Generating Heuristics (The n2−1 Puzzle Case)

Using the 8-puzzle as an example, the sources identify several ways to create admissible heuristics:

• Misplaced Tiles (h1​): Simply counting tiles that are not in their goal position

• Manhattan Distance (h2​): Calculating the total number of blocks each tile must traverse to reach its goal position

• Dominance: If h2​(n)≥h1​(n) for all nodes, h2​ is said to dominate h1​ and will generally generate fewer nodes during the search

• Relaxed Problems: Heuristics can be generated by removing constraints from a problem (e.g., allowing a tile to move anywhere)

• Pattern Databases: These involve decomposing the problem into sub-problems, storing their exact costs in a database, and using the maximum of these sub-costs as the heuristic estimate