Informed Search Strategies - Heuristic Properties, Weighted A*, and IDA*

Overview of Informed Search Strategies and Heuristic Properties

• Informed Search Strategies Defined:

  • Informed search strategies utilize additional problem-specific knowledge beyond the core domain definition. This extra information is known as a heuristic (denoted as $h(n)$).

  • Heuristics guide search algorithms toward goal states more efficiently than uninformed search methods.

• Heuristic Admissibility:

  • Definition: A heuristic $h(n)$ is admissible if it never overestimates the true cost to reach the nearest goal state. Formally, $h(n) \forall n \neq \text{goal}$ satisfies $0 \times h(n) \times h^*(n)$, where $h^*(n)$ is the true optimal path cost from node $n$ to the goal.

  • Impact on $A^*$ Search: Admissibility guarantees that $A^*$ search will return an optimal solution when searching tree structures or graphs without closed list restrictions.

  • Impact on Greedy Search: While Greedy Best-First Search does not guarantee optimality even with an admissible heuristic, using an admissible heuristic significantly improves practical efficiency, helping the search locate solutions faster while minimizing overall path cost.

• Heuristic Dominance:

  • Definition: Given two admissible heuristics $h_1(n)$ and $h_2(n)$, heuristic $h_2(n)$ dominates $h_1(n)$ if $h_2(n) \times h_1(n)$ for all non-goal nodes $n$.

  • Practical Consequence: A dominant heuristic provides estimates closer to the true path cost $h^*(n)$. Searches using a dominant heuristic expand fewer nodes on average, leading to higher efficiency and faster solution discovery.

• Special Case: Zero Heuristic ($h(n) = 0$):

  • When the heuristic is set to $h(n) = 0$ for all nodes $n$, the $A^*$ evaluation function $f(n) = g(n) + h(n)$ simplifies directly to $f(n) = g(n)$.

  • This converts $A^*$ search into Uniform Cost Search (UCS), as the frontier priority queue orders nodes purely based on cumulative path cost $g(n)$.

Consistency (Monotonicity) Property and Formal Proof

• Definition of Consistency (Monotonicity):

  • A heuristic $h(n)$ is consistent (or monotonic) if, for every node $n$ and every successor $n'$ of $n$ generated by any action $a$:         $h(n) \times c(n, a, n') + h(n')$         where $c(n, a, n')$ represents the step cost of transitioning from $n$ to $n'$.

  • Triangle Inequality Analogy: The estimated cost of reaching the goal from $n$ must not exceed the step cost to reach a neighbor $n'$ plus the estimated cost to reach the goal from $n'$.

• Monotonicity of Evaluation Function $f(n)$:

  • Consistency ensures that the evaluation function $f(n)$ is monotonically non-decreasing along any path leading to the goal.

  • If a heuristic is inconsistent, $f(n)$ can fluctuate up and down along a path, causing graph search algorithms with standard closed lists to prioritize suboptimal paths.

• Formal Proof of $f(n') \times f(n)$ for Consistent Heuristics:

  • Objective: Prove that for any node $n$ and successor $n'$, $f(n') \times f(n)$.

  • Step 1: From the definition of consistency:         $h(n) \times c(n, n') + h(n')$

  • Step 2: By definition, the evaluation function at successor $n'$ is:         $f(n') = g(n') + h(n')$

  • Step 3: Express the path cost $g(n')$ in terms of node $n$:         $g(n') = g(n) + c(n, n')$

  • Step 4: Substitute $g(n')$ into the expression for $f(n')$, obtaining:         $f(n') = g(n) + c(n, n') + h(n')$

  • Step 5: Apply the consistency inequality $c(n, n') + h(n') \times h(n)$ to the substituted equation:         $f(n') = g(n) + c(n, n') + h(n') \times g(n) + h(n)$

  • Step 6: Substitute $f(n) = g(n) + h(n)$ into the right side:         $f(n') \times f(n)$

  • Conclusion: The evaluation function $f(n)$ along any path is non-decreasing when $h(n)$ is consistent.

Implementing Closed Lists: Reopening Nodes and Inconsistency Handling

• The Closed List Dilemma:

  • Tracking explored states in a closed list (or explored set) avoids redundant node expansions and infinite loops.

  • If a heuristic is admissible but inconsistent, standard $A^*$ graph search with a strict closed list can return a suboptimal solution because it discards revisited nodes that were expanded earlier via higher-cost paths.

• $A^*$ Graph Search with Node Reopening:

  • To maintain optimality when consistency cannot be proven or does not hold, $A^*$ search must incorporate a reopening mechanism for nodes in the closed list.

  • Reopening Logic:

    • When a state $n$ is generated that already exists in the closed list, evaluate its new path evaluation score $f_{\text{new}}(n)$.

    • If f_{\text{new}}(n) < f_{\text{old}}(n), update the stored path score for state $n$ and re-insert $n$ into the frontier (reopen the node).

    • If $f_{\text{new}}(n) \times f_{\text{old}}(n)$, ignore the duplicate state and continue.

• Illustrative Reopening Example:

  • Consider a graph with start node $S$, goal $G$, and intermediate nodes $A$, $B$, $C$:

    • Path $S \rightarrow B \rightarrow C$ generates node $C$ with score $f(C) = 4$. Node $C$ is expanded and placed in the closed list.

    • Path $S \rightarrow A \rightarrow C$ later generates node $C$ with path evaluation score $f(C) = 3$ ($g=1+2=3$).

    • Standard closed list drops the path $S \rightarrow A \rightarrow C$ because $C$ is in the closed list.

    • Reopening closed list compares scores: 3 < 4. Node $C$ is re-added to the frontier with $f(C) = 3$, preserving access to the optimal path to G$.\n\n* **Algorithmic Insights & Parameter Sensitivity**:\n * Small algorithmic adjustments (e.g., adding node reopening logic) significantly alter theoretical properties such as completeness and optimality.\n * Understanding low-level computational decisions is essential across complex algorithms, including machine learning models with hundreds of parameters.\n\n\n# Interactive Quiz and Graph Analysis\n\n* **Quiz Results & Leaderboard**:\n * **First Place**: Krishna (fastest and most correct performance).\n * **Second Place**: Ji Chen.\n * **Third Place**: Eva (competing as SSS).\n * **Other Participant**: Lou (answered 3 questions, selected 1 incorrect answer choice).\n\n* **Graph Analysis Question 1: Admissibility Verification**:\n * **Problem Statement**: Determine if the heuristic h$for node$B in the given graph is admissible.\n * **Node Breakdown**:\n * Node C$: True shortest path cost to goal$h^(C) = 1$; heuristic value$h(C) = 1 (admissible).\n * Node A$: True shortest path cost to goal$h^(A) = 6$; heuristic value$h(A) = 6 (admissible).\n * Node B$: True shortest path cost to goal$h^*(B) = 3$; heuristic value$h(B) = 5$.

  • Conclusion: Because h(B) = 5 > 3 = h^*(B), the heuristic overestimates the actual cost. Thus, $h$ is not admissible.

• Graph Analysis Question 2: Consistency Verification:

  • Problem Statement: Analyze admissibility and consistency properties across nodes $S$, $A$, $B$, $C$, $G$.

  • Node Properties:

    • Node $C$: $h(C) = 6$, step cost $c(A, C) = 5$.

    • Node $A$: $h(A) = 7$.

    • Consistency Evaluation at Edge $A \rightarrow C$:             $h(A) \times c(A, C) + h(C) \times 7 \times 5 + 6 = 11$             Checking direct value bounds: $7 \times 6$ fails.

  • Admissibility Check:

    • Node $A$: $h^*(A) = 7$, $h(A) = 7$ (admissible).

    • Node $B$: $h^*(B) = 4$, $h(B) = 4$ (admissible).

    • Node $S$: $h^*(S) = 6$, $h(S) = 5$ (admissible underestimate).

  • Conclusion: The heuristic for this graph is admissible but inconsistent.

Weighted A* Search

• Motivation:

  • Weighted $A^*$ Search balances the speed of Greedy Best-First Search with the optimality guarantees of Uniform Cost Search (UCS) / standard $A^*$.

  • Introduces a weight parameter $w$ to adjust the relative influence of path cost $g(n)$ and heuristic $h(n)$.

• Evaluation Function Formula:

  • $f(n) = (2 - w) \times g(n) + w \times h(n)$

  • Note: Alternative formulas exist in literature (e.g., $f(n) = g(n) + w \times h(n)$), but the formulation above allows continuous scaling between standard algorithms across defined boundary values of $w$:

    • Case $w = 0$: $f(n) = 2 \times g(n) + 0 \times h(n) = 2 \times g(n)$. The heuristic is ignored completely. Operates identically to Uniform Cost Search (UCS).

    • Case $w = 1$: $f(n) = 1 \times g(n) + 1 \times h(n) = g(n) + h(n)$. Reverts to classical $A^*$ Search.

    • Case $w = 2$: $f(n) = 0 \times g(n) + 2 \times h(n) = 2 \times h(n)$. Path cost is ignored completely. Operates identically to Greedy Best-First Search.

    • Case $w = 0.5$: $f(n) = 1.5 \times g(n) + 0.5 \times h(n)$. Weighs path cost more heavily; behaves closer to UCS, preserving optimality.

    • Case $w = 1.5$: $f(n) = 0.5 \times g(n) + 1.5 \times h(n)$. Weighs heuristic value more heavily; finds solutions faster by being greedier, but forfeits optimal path guarantees.

• Trace Example for $w = 1.5$:

  • Start state $A$: $g(A) = 0$, $h(A) = 5 \times f(A) = 0.5 \times 0 + 1.5 \times 5 = 7.5$

  • Successor Generation: Node $A$ expands to $B$, $C$, $D$.

  • Frontier Path Options: $AB$, $AD$, $AC$.

  • Execution Path: Proceeds greedily with path $AB$, reaching a solution in fewer node expansion steps than classical A^*$.\n\n* **Algorithm Properties**:\n * **Time Complexity**: Comparable to UCS or Greedy Search, depending on weight setting w.\n * **Space Complexity**: High (requires storing all open states in priority queue memory).\n * **Completeness**: Complete.\n * **Optimality**: Guaranteed if w imes 1$(with admissible heuristic); not guaranteed if$w > 1$.

Iterative Deepening A* Search (IDA*)

• Motivation:

  • Standard $A^*$ and Weighted $A^*$ consume large amounts of memory storing open lists in priority queues.

  • Depth-First Search (DFS) uses linear memory $O(b \times m)$, but lacks completeness and optimality.

  • $IDA^*$ combines the linear space efficiency of DFS with the optimality and time properties of $A^*$.

• Core Mechanism:

  • $IDA^*$ uses the evaluation function $f(n) = g(n) + h(n)$ as a cost threshold $L$ for depth-limited search passes.

  • The frontier is maintained as a LIFO stack (DFS structure).

  • During each iteration, paths are expanded depth-first until a node exceeds the threshold $L$ (f(n) > L).

  • Pruned nodes that exceed $L$ are not added to the stack. Their evaluation scores are recorded.

  • The threshold for the subsequent iteration $L_{\text{next}}$ is set to the minimum $f(n)$ score among all nodes pruned in the current iteration.

• Step-by-Step Execution Example:

  • Initial Setup: Start state $A$ with $g(A) = 0$, $h(A) = 5 \times f(A) = 5$.

  • Iteration 1 ($L = 5$):

    • Root $A$ ($f=5 \times 5$) generates successors $B$, $C$, $D$.

    • Calculated scores: $f(C) = 10$, $f(B) = 6$, f(D) = 10$.\n * All exceed threshold L = 5; all are pruned.\n * Update threshold: L_{ ext{next}} = imes(10, 6, 10) = 6$.

  • Iteration 2 ($L = 6$):

    • Root $A$ expands $B$ ($f(B) = 6 \times 6$), while $C$ ($f=10$) and $D$ ($f=10$) are pruned.

    • Path $AB$ expands to $ABE$ ($f(ABE) = 5 \times 6$).

    • $ABE$ has no further successors (dead end).

    • Pruned values gathered: $10, 10$. Minimum exceeded value is 7$.\n * Update threshold: L_{ ext{next}} = 7$.

  • Iteration 3 ($L = 7$):

    • Stack explores $AB \times ABF$.

    • $ABF$ generates $ABFD$ (f(ABFD) = 13 > 7; pruned).

    • Minimum exceeded value is 10$.\n * Update threshold: L_{ ext{next}} = 10$.

  • Iteration 4 ($L = 10$):

    • Explores $A \times D \times ADH$ (f(ADH) > 10; pruned).

    • Exceeded scores: $11, 13, 13$. Minimum exceeded value is 11$.\n * Update threshold: L_{ ext{next}} = 11$.

  • Iteration 5 ($L = 11$):

    • Threshold reaches the cost of the optimal solution path ($11$), finding the optimal goal state instantly.

• Algorithm Properties:

  • Completeness: Complete.

  • Optimality: Guaranteed if heuristic $h(n)$ is admissible.

  • Space Complexity: Linear $O(b \times m)$, where $b$ is the branching factor and $m$ is maximum depth. Significantly outperforms $A^*$ in memory efficiency.

  • Time Complexity: Exponential $O(b^m)$ in worst-case analysis, but asymptotically comparable to $A^*$ in practice.

Comparative Analysis of Search Algorithms

• Breadth-First Search (BFS):

  • Admissible/Optimal: Yes (when all step costs are equal to $1$).

  • Space Complexity: High (exponential).

• Uniform Cost Search (UCS):

  • Admissible/Optimal: Yes (for general positive step costs).

  • Space Complexity: High (exponential).

• Depth-First Search (DFS):

  • Admissible/Optimal: No.

  • Space Complexity: Low (linear $O(b \times m)$).

• Greedy Best-First Search:

  • Admissible/Optimal: No.

  • Time Efficiency: High (fast in practice).

  • Space Complexity: High.

• Iterative Deepening Search (IDS):

  • Admissible/Optimal: Yes (for uniform step costs).

  • Space Complexity: Low (linear).

• $A^*$ Search:

  • Admissible/Optimal: Yes (with admissible heuristic).

  • Space Complexity: High (stores open priority queue in memory).

• $IDA^*$ Search:

  • Admissible/Optimal: Yes (with admissible heuristic).

  • Space Complexity: Low (linear memory usage).

Questions & Discussion

• Inconsistency vs. Admissibility Property Independence:

  • Question: Are admissibility and consistency completely separate properties? Can a heuristic be admissible while simultaneously being inconsistent?

  • Answer: Yes. Admissibility ($h(n) \times h^*(n)$) and consistency ($h(n) \times c(n, n') + h(n')$) are distinct mathematical properties. A heuristic can never overestimate the true remaining cost (admissible) while still exhibiting local step fluctuations that violate monotonicity (inconsistent).