Introduction to AI: Search and Planning - Blind and Heuristic Search Algorithms

Course Introduction and Overview

• Module 1: Search and Planning: This is the first of five modules for the course.

• Schedule: The topic of Search and Planning will be covered over two weeks. These lecture slides available on Canvas cover both this week and next week. Today's lecture covers the first half (approximately 50 slides), and the remaining half will be finished next week.

• Practical Application: Students are expected to apply these concepts in their lab worksheets (for regular labs) or workshop sessions (for City Campus students) later in the week.

Learning Objectives for Search and Planning

• Problem Definition: Defining search problems in terms of states and actions, which is the foundational framework for AI agents.

• Blind Search Algorithms: Applying Depth-First Search (DFS) and Breadth-First Search (BFS) to solve problems, while contrasting their specific strengths and weaknesses.

• Heuristic Search: Understanding how heuristic information differs from blind search.

  • Best-First Search: Using heuristic information to guide search.

  • A* Search: Finding optimal solutions using heuristics.

• Adversarial Search (Next Week): Solving game-based problems using the Minimax algorithm and Monte Carlo Tree Search (MCTS) for games without heuristic knowledge.

• Planning in Stochastic Environments (Next Week): Modeling real-world problems with randomness and uncertainty as Markov Decision Processes (MDPs) and applying the Value Iteration algorithm.

Foundations of Search and Planning

• Purpose: Search and Planning are concerned with finding strategies or plans to achieve specific goals. This is the primary function of most real-world AI agents.

• Formalization: Problems are formalized for computers using two primary components:

  • Initial Starting State: The current configuration of the agent or environment (e.g., sitting on a stool).

  • Actions: Moves or transitions the agent can take (e.g., standing up, moving the left leg, moving the right leg) to reach an end state or goal state.

• Toy Versions vs. Real World: While the course uses puzzles and games for fundamental introductions, these concepts extrapolate to complex robotics and real-world systems.

• Examples of Search Problems:

  • Tic Tac Toe: A simple game explored later.

  • Tower of Hanoi: A classic logic puzzle.

  • Mazes: Finding a path from a green starting square to a red goal square.

  • Sliding Block Puzzles (8-Puzzle): Sliding numbered tiles into an adjacent empty position to reach a specific goal configuration (e.g., moving tile $3$ down to reach the next state).

Blind Search Algorithms

• Definition: Blind search algorithms investigation all possible solutions in a systematic, "brute force" manner. They have no knowledge of whether they are getting closer to the goal until they reach it.

• Characteristics:

  • They explore sequences of actions and states one at a time.

  • They ensure no solution is overlooked.

  • They are slow and unoptimized.

  • Feasibility: They are often impractical for large problems. For example, in Chess, it is estimated that there are more possible move sequences than atoms in the observable universe.

• State Space as a Tree:

  • Root Node: The initial state (located at the top in computer science).

  • Branches: The actions that lead to new nodes.

  • Leaf Nodes: The end states or goal states at the bottom.

  • Nodes/States: Every configuration of pieces or coordinates (e.g., in a board of $4$ spaces with $2$ pieces, any configuration is a state).

Depth-First Search (DFS)

• Logic: DFS explores as deep as possible down one branch of the search tree before backtracking.

• General Procedure (Natural Language):

  1. Start at the root.

  2. Always take the leftmost action available.

  3. Continue taking the leftmost action until a dead end (leaf node with no children) is reached.

  4. Backtrack to the nearest node that has another untried action.

  5. Take the next leftmost action and repeat.

• Pseudo-code Implementation:

  1. Input: A list $L$ containing the initial state and an empty list $Lseen$ for previously seen states.

  2. Let $S$ be the first state in $L$.

  3. If $S$ is the final state, stop with success.

  4. Apply all legal search operators to $S$ to get children. Ignore children already in $Lseen$.

  5. Put remaining children, ordered left to right, at the beginning of $L$.

  6. Remove $S$ from $L$ and add it to $Lseen$.

  7. If $L$ is empty, stop (failure). Otherwise, return to step 1.

• Key Behavior: The algorithm prioritizes children of the current node, effectively pushing the search deep into the tree quickly.

Breadth-First Search (BFS)

• Logic: BFS explores every state at the current depth level before moving to the next level of depth.

• Pseudo-code Implementation:

  • The steps are identical to DFS with one critical difference in step 5:

  • Step 5 Difference: Put the remaining children at the end of $L$ rather than the beginning.

• Queue Mechanics: Since children are placed at the back of the list, they are treated as a queue. The algorithm must process all "sibling" nodes before it can begin processing the "children" of those siblings.

• Visual Representation: If DFS is like a probe going deep, BFS is like a radiating wave expanding outward from the starting point layer by layer.

Comparing DFS and BFS Meta-Characteristics

• Branching Factor ($b$): The average number of actions/children from any given state. Low branching (e.g., $2$ actions) vs. high branching (e.g., Chess).

• Search Depth ($d$): The number of actions required to reach the goal.

• Memory Efficiency:

  • DFS: Memory grows linearly with the depth of the tree ($O(d)$). It only needs to store the current branch it is investigating.

  • BFS: Memory grows exponentially with depth ($O(b^d)$) because it must store all nodes at the current level.

• Optimality:

  • DFS: Does not guarantee the shortest or most optimal path. It simply finds the first solution it can.

  • BFS: Guarantees the optimal solution (the path with the minimum number of actions).

• The Neighborhood Analogy (Pete and Bill): If Pete is looking for his friend Bill in a street of houses, DFS would check every room of the first house on the left, then the next house to the left, all the way to the end of the street before checking the neighbor on the right. BFS would check the immediate neighbors first—this is more logical when the goal is likely close to the start.

Heuristic Search Algorithms

• Definition: Heuristic search uses an evaluation function to rank child states, estimating how much "closer" a state is to the goal.

• Heuristic ($H(s)$): A "rule of thumb" or estimate. It can be a reward/score to maximize or a cost to minimize.

• Examples:

  • Maze: Straight-line distance ("as the crow flies") to the goal. This is like a "warmer/colder" indicator.

  • 8-Puzzle: Counting how many tiles are currently in their correct final position (e.g., if $5$ tiles are correct, the state score is $5$).

• Manhattan Distance: The sum of vertical and horizontal moves required for each tile to reach its goal position, ignoring obstacles/blocking tiles.

Hill Climbing Algorithm

• Logic: A variant of DFS that orders children based on the heuristic evaluation rather than purely left-to-right.

• Procedure: When generating children, run the evaluation function. Place the most promising child (highest score or lowest cost) at the beginning of list $L$.

• Strengths: Often finds solutions significantly faster than blind DFS by following the "steeper" path toward the goal.

• Weaknesses: Even a good heuristic can be misleading. Falsely promising paths may exist if the evaluation function isn't perfectly reliable.

Best-First Search (Greedy Search)

• Logic: Unlike Hill Climbing which is depth-oriented, Best-First Search always picks the state from the entire list $L$ that has the best heuristic value.

• Global Priority: It does not force the search to go deep if a better option exists elsewhere in the tree.

• Greedy Nature: It is called "greedy" because it always makes the choice that looks best in the immediate moment without considering the path cost to get there.

• Issue: It does not guarantee an optimal solution. It may overlook a shorter road if it has to pass through a state that "looks" bad (has a poor heuristic) initially.

Look-Ahead Strategies and Temporal Worsening

• Temporal Worsening: The concept that sometimes, to find the goal, an agent must temporarily move into a state that looks worse according to the heuristic (e.g., moving a tile away from its goal to clear a path for another tile).

• Look-Ahead: To avoid being fooled by immediate heuristic values, an agent can look several steps into the future (grandchildren or great-grandchildren nodes).

• Example: In a tree, Node B might look best ($2.5$), but Node D leads to a grandchild Node K ($3.2$). A look-ahead allows the agent to choose D over B.

The A* Search Algorithm

• Formula: $f(s) = g(s) + h(s)$.

  • $g(s)$: The accumulated cost (number of steps or distance) already taken to reach state $S$ from the start.

  • $h(s)$: The heuristic estimate of the remaining distance/cost to reach the goal from state $S$.

  • $f(s)$: The total estimated cost of the path through state $S$.

• Mechanism: A* always expands the node in $L$ with the lowest $f(s)$. This balances the "distance traveled" with "distance to go."

• Selection Process Example (Cities Network):

  • Starting at $S$, options $A, B, C$.

  • $A$: $Cost(4) + Heuristic(8) = 12$.

  • $B$: $Cost(10) + Heuristic(6) = 16$.

  • $C$: $Cost(5) + Heuristic(11) = 16$.

  • A* picks $A$ because $12$ is the lowest total estimate.

Dijkstra's Algorithm and the Importance of Admissibility

• Dijkstra's Algorithm: A special case of A* where the heuristic function $h(s)$ is always zero for every state. It relies purely on the accumulated cost $g(s)$.

• Admissibility (Optimism): For A* to guarantee the optimal path, the heuristic must be admissible, meaning it never overestimates the true cost to the goal.

  • Condition: $h(s) \le h^*(s)$, where $h^*(s)$ is the true cost.

  • Example: Straight-line distance in a maze is admissible because you can never reach a goal faster than a straight line; the actual path will be equal or longer.

Practical Comparisons and Visual Analysis

• Maze Performance (Example Metrics):

  • Best-First Search: Checked $48$ states, path length $43$ (Fast but not optimal).

  • A*: Checked $59$ states, path length $31$ (Slower but optimal).

  • BFS: Checked $89$ states, path length $31$ (Very slow but optimal).

• Key Takeaway: A* provides the best balance of speed and optimality, provided an admissible heuristic is used.