Lecture 04.1: Informed Search and Heuristics

Uninformed search methods blindly explore the state space. They only know if a state is a goal or not. Informed search (or heuristic search) methods add domain-specific information to select the best path along which to continue searching.

---

Searching to Solve Problems

Before an agent can search for solutions, it operates under environmental assumptions (deterministic, observable, static, and completely known) and formulates a well-defined problem consisting of five parts:

1. Initial State: The starting state of the agent (e.g., $In(Arad)$).
2. Set of Actions: The set of possible actions available to the agent in state $s$, denoted $Actions(s)$.
3. Transition Model: A description of what each action does, denoted $Result(s, a)$.
4. Goal Test Function: A test determining whether a given state is a goal state.
5. Action Cost Function: A function $c(s, a, s')$ calculating the step cost of taking action $a$ to transition from state $s$ to $s'$.

The environment of the problem is represented by a state space. A path through the state space from the initial state to a goal state is a solution. The process of removing unnecessary details from a state representation is called abstraction.

---

The Heuristic Function $h(n)$

To guide the search, we define a heuristic function, $h(n)$, which estimates the "goodness" of a node $n$. Specifically: $h(n) = \text{estimated cost (or distance) from } n \text{ to a goal state}$

The heuristic function is an estimate based on domain-specific information that is computable directly from the current state description.

Example: Manhattan Distance in Robot Navigation

In a grid-based robot navigation problem where movement is restricted to horizontal and vertical steps, the general $n$-dimensional Manhattan distance between two points $x$ and $y$ is: $\text{Manhattan distance} = \sum_{i=1}^n |x_i - y_i|$

For a standard 2-dimensional grid, this simplifies to: $M_{dist} = |x_2 - x_1| + |y_2 - y_1|$

The Obstacle Trap in Greedy Search

When navigating around obstacles (such as U-shaped wall barriers), Greedy Best-First Search relies solely on $h(n)$. As a result, the robot moves to cells with smaller $h(n)$ values, drawing it directly toward the barrier wall. Because it ignores the path cost $g(n)$ accumulated so far, it gets stuck driving into dead ends against obstacle boundaries before being forced to backtrack around the barrier.

---

Best-First Search

Best-first search is a general search framework where we evaluate nodes using an evaluation function $f(n)$ to estimate node "desirability." The algorithm always expands the most desirable unexpanded node first.

It is implemented using a priority queue that orders nodes in increasing order of $f(n)$ (where lower cost means higher desirability).

Two primary special cases of best-first search are:

1. Greedy Best-First Search ($f(n) = h(n)$)
2. A Search* ($f(n) = g(n) + h(n)$)

---

Greedy Best-First Search

Greedy best-first search tries to expand the node that appears to be closest to the goal. It evaluates nodes by using solely the heuristic function: $f(n) = h(n)$

Example: Route Finding in Romania

Imagine finding a route from Arad to Bucharest. We use the Straight-Line Distance (SLD) to Bucharest as our heuristic $h_{SLD}(n)$.

Straight-Line Distances to Bucharest ($h_{SLD}$)

Step-by-Step Search Trace

1. Start at Arad: $h(\text{Arad}) = 366$.
2. Expand Arad: Successors are Sibiu ($253$), Timisoara ($329$), and Zerind ($374$). Lowest $h$ is Sibiu ($253$).
3. Expand Sibiu: Successors are Fagaras ($176$), Rimnicu Vilcea ($193$), Arad ($366$), and Oradea ($380$). Lowest $h$ is Fagaras ($176$).
4. Expand Fagaras: Successors are Bucharest ($0$) and Sibiu ($253$). Lowest $h$ is Bucharest ($0$). Goal reached!

By greedily following the lowest $h(n)$ value, Greedy Best-First Search finds the path: $\text{Arad} \rightarrow \text{Sibiu} \rightarrow \text{Fagaras} \rightarrow \text{Bucharest}$

• Path Cost: $140 + 99 + 211 = 450$
• Optimal Path: $\text{Arad} \rightarrow \text{Sibiu} \rightarrow \text{Rimnicu Vilcea} \rightarrow \text{Pitesti} \rightarrow \text{Bucharest}$ with cost $140 + 80 + 97 + 101 = 418$.

Because Greedy BFS ignores path costs, it selected Fagaras ($h=176$) over Rimnicu Vilcea ($h=193$), missing the shorter total route!

---

Properties of Greedy Best-First Search

• Complete? No in tree search (can get stuck in infinite loops such as $\text{Arad} \leftrightarrow \text{Sibiu}$). Yes in graph search if repeated states are tracked and eliminated.
• Optimal? No. As shown in the Romania example, it can yield a path cost of $450$ when an optimal path of $418$ exists.
• Time Complexity: $O(b^m)$ in worst case, where $m$ is maximum depth, but a good heuristic can dramatically reduce search time.
• Space Complexity: $O(b^m)$, as it retains all generated nodes in memory.