Informed Search Strategies and A* Search Flashcards

Event Announcements and Previous Lecture Recap

Administrative Note: As of August 4 at 6 PM, club-organized events are underway. Many clubs have reached capacity limits for sign-ups, though some joint events between multiple clubs still allow for registration.
Greedy Best-First Search Recap:
- Informed search strategies utilize external information provided by a domain expert or additional knowledge about the state space graph to guide the search toward the goal state. This external information is known as a heuristic.
- Greedy Best-First Search sorts the path in the frontier based solely on the heuristic value. It operates similarly to Uniform Cost Search (UCS) but prioritizes nodes estimated to be closest to the goal.
- Observations from greedy search visualization:
  - The algorithm may initially move toward obstacles (walls) because it cannot identify a node as a leaf or dead-end until it has been explored.
  - In previous demonstrations, the search explored a state 'e' first because of its proximity to the goal, resulting in the non-optimal solution path: A, B, F, D, H, G. A more direct path would have been A, D, H, G.
- Worst-Case Scenarios:
  - The search can be misled by a high number of leaf nodes located near the goal, causing significant detours.
  - Admissibility is not guaranteed; finding a solution does not mean it is the optimal one.
  - Completeness is guaranteed only if implemented with a closed list.
  - Time and space complexity are $O(b^d)$ , similar to UCS.
- Heuristic Quality: A random heuristic (e.g., a function returning values between 0 and 100) is equivalent to randomly choosing nodes from the frontier. A high-quality heuristic provides a close approximation of the distance to the goal, leading to faster and potentially more optimal performance.

Comparison of UCS and Greedy Search

Uniform Cost Search (UCS): Minimizes the real path cost $g(n)$ from the start state to node $n$ . It is optimal but can be slow as it treats all directions equally.
Greedy Best-First Search: Minimizes the estimated path cost $h(n)$ from node n$ to the goal. It is often fast but not optimal.\n* A* Search Strategy: This algorithm combines the strengths of both, mixing and matching properties to refine design for specific problems. It is designed to be both fast and optimal.\n\n# A* Search Mechanics\n\n* Core Idea: A* Search uses a priority queue that ranks paths based on the sum of the real path cost and the heuristic value.\n* Evaluation Function:\n f(n) = g(n) + h(n)\n * g(n) $: The cost of the path from the start node to node$ n.\n * h(n) $: The heuristic value or estimated cost from node$ n to the goal state.\n * f(n) $: The total estimated path cost through node$ n.\n* Example Trace with Start Node A (h(a)=5):\n * Initial State: Node a $is added to the queue with a value of$ 5 $($ g=0 + h=5).\n * Generating Neighbors: Node a $expands to nodes$ b $,$ c $, and$ d. \n * Node b $Evaluation:$ f(b) = 6.\n * Exploring b $: Leads to neighbors$ e $and$ f.\n * Path to e $: Path cost is$ 4 $, heuristic is$ 1 $, total$ f(e) = 5.\n * Path to f $: Path cost is$ 5 $, heuristic is$ 2 $, total$ f(f) = 7.\n * Optimal Solution: In the provided graph, the algorithm identifies the shortest path as A, D, H, G with a total cost of 11.\n\n# Properties and Optimality of A*\n\n* Completeness: A* is complete; if a solution exists, it will be found.\n* Complexity:\n * Time Complexity: O(b^d).\n * Space Complexity: O(b^d), as all nodes must be stored in memory in the worst case.\n* Optimality: A* search is optimal if the heuristic used is admissible.\n* Admissible Heuristics:\n * An admissible heuristic never overestimates the true cost to reach the goal state.\n * Formal Definition: h(n) \leq h^(n) $, where$ h^(n) $is the actual optimal cost from$ n to the goal.\n * Requirement: The heuristic for the goal state must be zero (h(G) = 0).\n * Example: Straight-line distance (Euclidean distance) is always admissible because the path traveled (incorporating stairs, obstacles, etc.) will always be equal to or greater than the direct linear distance.\n\n# Proof of A* Optimality with Admissible Heuristics\n\n* Goal: Prove that if node n $is on the optimal path to goal$ g $, and$ g2 $is a suboptimal goal, A* will expand$ n $before$ g2.\n* Assumptions:\n * g2 $is a suboptimal goal, meaning$ g(g) < g(g2).\n * h(g2) = 0 $because it is a goal state, therefore$ f(g2) = g(g2).\n * Node n $is an unexplored node on the optimal path to$ g.\n* Derivation:\n 1. f(g2) = g(g2).\n 2. By suboptimality, f(g) < f(g2) $, which implies the real cost of$ g $is less than the real cost of$ g2.\n 3. The cost of the optimal path to g $is defined as$ g(g) = g(n) + c(n, g) $, where$ c(n, g) $is the real cost from$ n $to$ g.\n 4. By admissibility, h(n) \leq c(n, g).\n 5. Therefore, f(n) = g(n) + h(n) \leq g(n) + c(n, g) = f(g).\n 6. Since f(n) \leq f(g) $and$ f(g) < f(g2) $, it follows that$ f(n) < f(g2).\n* Consequence: Because f(n) < f(g2) $, the priority queue will always prioritize the expansion of node$ n $over the terminal expansion of the suboptimal goal$ g2.\n\n# Heuristic Design for Relaxed Problems\n\n* Concept of Relaxed Problems: A heuristic is often the exact cost to a simplified version of the problem where rules or constraints are removed.\n* Case Study: Eight-Puzzle Game:\n * Original Rules: Tiles can only slide into adjacent empty spaces (up, down, left, right).\n * Relaxed Option 1: Pick up tiles and place them directly in the goal positions (ignoring sliding rules). \n * Heuristic (h_1): Number of misplaced tiles.\n * Admissibility: Admissible because every misplaced tile requires at least one move (usually more) in the real game.\n * Relaxed Option 2: Tiles move to goal positions using grid coordinates but ignore other tiles on the board.\n * Heuristic (h_2): Total Manhattan Distance (Sum of x-coordinate differences and y-coordinate differences for all tiles).\n * Example calculation: For tile 7, if its goal is three spaces away, its contribution to the heuristic is 3. \n * Admissibility: Admissible because the Manhattan distance is the absolute minimum moves required to reach the target location without accounting for path blocking.\n\n# Heuristic Dominance\n\n* Definition of Dominance: For two admissible heuristics h_1 $and$ h_2 $, if$ h_1(n) \geq h_2(n) $for all nodes$ n $, then$ h_1 $dominates$ h_2.\n* Application: A dominant heuristic is superior because its values are closer to the true cost (h^(n)), resulting in fewer node expansions and lower memory usage.\n* Comparison in Eight-Puzzle: Manhattan distance (h_2 $) is generally higher than the count of misplaced tiles ($ h_1 $) and provides a better approximation, meaning it dominates$ h_1.\n* Maximizing Heuristics: If multiple admissible heuristics are available, taking the maximum value is also admissible: h(n) = \max(h_a(n), h_b(n)). This ensures the heuristic is as close as possible to the real value.\n\n# Closed Lists and Consistency\n\n* Closed List (Explored List/Visited List): A data structure used to store expanded nodes to prevent revisiting the same state and avoid infinite loops or exponential growth in loopy state spaces.\n* Challenge with A*: Standard A* implementation with a closed list may lose optimality if the heuristic is not consistent (monotonic).\n * Example: If a node c $is reached via a suboptimal path and added to the closed list, a later, more optimal path to$ c might be ignored.\n* Consistency Definition: A heuristic is consistent if, for every node n $and every successor$ n' $generated by action$ a, the estimated cost is less than or equal to the step cost plus the estimated cost of the successor:\n h(n) \leq c(n, a, n') + h(n')\n* Properties of Consistency:\n * This is known as the triangular property.\n * It ensures that the evaluation function f(n) never decreases along any path.\n * If a heuristic is consistent, the first time A* expands a node, it has found the optimal path to that node.\n * All consistent heuristics are admissible, but not all admissible heuristics are consistent.\n\n# Questions & Discussion\n\n* Difficult Topics: The mathematical proof of A* optimality is cited as the most difficult section. Students should review theoretical foundations if they are unfamiliar with formal proofs.\n* Google Maps Example: Francis noted that Google Maps utilizes actual road distances as the path cost (g(n) $) and potentially straight-line distance as a heuristic ($ h(n)). Straight-line distance is inherently admissible as it is the absolute shortest path possible.\n* Randomized Heuristics: A student asked about using a random heuristic trial (e.g., 90% correct, 10% incorrect). Choosing a heuristic randomly or inconsistently is likely to mislead the search, potentially making it perform worse than Uniform Cost Search by causing unnecessary detours.\n* Determining Admissibility: There is no functional way to "calculate" admissibility without knowing the actual cost (h^). Instead, admissibility is derived analytically by ensuring the heuristic function is the solution to a "relaxed" version of the original problem.\n* Worst-Case vs. Practical Performance: While consistent heuristics technically share the same worst-case time complexity (O(b^d)$$) as uninformed search, in practice, they significantly reduce the number of nodes explored.