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.

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 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, a common heuristic is the Manhattan distance to the goal: $M_{dist} = |x_2 - x_1| + |y_2 - y_1|$ By calculating $h(n)$ for each adjacent square, the robot can prefer moves that decrease the Manhattan distance to the target.

---

Best-First Search

Best-first search is an approach where we use an evaluation function $f(n)$ for each node to estimate its "desirability." The algorithm always expands the most desirable unexpanded node first.

It is implemented by ordering the nodes in the frontier queue in decreasing order of desirability.

There are two main special cases of best-first search:

1. Greedy best-first search
2. A search*

---

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 just the heuristic function: $f(n) = h(n)$

Example: Route Finding in Romania

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

• $h_{SLD}(\text{Arad}) = 366$
• $h_{SLD}(\text{Sibiu}) = 253$
• $h_{SLD}(\text{Timisoara}) = 329$
• $h_{SLD}(\text{Zerind}) = 374$

When we expand Arad, our options are Sibiu, Timisoara, and Zerind. Because $h_{SLD}(\text{Sibiu})$ is the smallest, Greedy Best-First Search will expand Sibiu next.

By greedily following the lowest $h(n)$ value, the search plunges straight toward the goal.

Properties of Greedy Best-First Search

• Complete? Yes, if we eliminate endless loops (by keeping track of visited states). Otherwise, no.
• Optimal? No. It might find a path quickly, but not necessarily the shortest one. (For example, moving to a geographically closer city that happens to have a terrible, winding road connection).
• Time Complexity: $O(b^m)$, but a good heuristic can give dramatic improvement over uninformed search.
• Space Complexity: $O(b^m)$, as it keeps all generated nodes in memory.