Heuristic search（启发式搜索）

• The idea is to develop a domain specific heuristic function h(n), guessing the cost of getting to the goal from node n
• We require that h(n) = 0 for every node n whose state satisfies the goal
• There are different ways of guessing this cost in different domains. i.e., heuristics are domain specfic.

Motivation

• In uninformed search, we don’t try to evaluate which of the nodes on the frontier are most promising.
  • e.g., in uniform cost search we always expand the cheapest path. We don’t consider the cost of getting to the goal from the end of the current path.
• However, often we have some other knowledge about the merit of nodes.
  • e.g., how costly it is to get to the goal from that node.

Greedy best-first search (Greedy BFS)

• We use $h(n)$ to order the nodes on the frontier.
• We are greedily trying to achieve a low cost solution.
• However, this method ignores the cost of getting to $n$, so it can be lead astray exploring nodes that cost a lot to get to but seem to be close to the goal
• Thus Greedy BFS is not optimal

A∗ search

• Define an evaluation function $f(n) = g(n) + h(n)$
  • $g(n)$ is the cost of the path to node n
  • $h(n)$ is the heuristic estimate of the cost of getting to a goal node from n
• So $f(n)$ is an estimate of the cost of getting to the goal via node n.
• We use $f(n)$ to order the nodes on the frontier

Conditions on h(n): Admissible

• We always assume that $c(n1 \to n2) ≥ \epsilon > 0$.The cost of any transition is greater than zero and can’t be arbitrarily small.
• Let $h∗(n)$ be the cost of an optimal path from n to a goal node ($\infty$ if there is no path).
• h(n) is admissible if for all nodes n, $h(n) \le h∗(n)$
• So an admissible heuristic underestimates the true cost to reach the goal from the current node
• Hence $h(g) = 0$ for any goal node $g$

Consistency (aka monotonicity)

• $h(n)$ is consistent/monotone if for any nodes $n_1$ and $n_2$, $h(n_1) \le c(n_1 \to n_2) + h(n_2)$
• Note that consistency implies admissibility (proof)
  1. no path from $n$ to the goal
  2. Let $n = n_1 \to n_2 \to \ldots \to n_k$ be an optimal path from $n$ to a goal node. We prove by induction on i that for all i, $h(n_i) \le h∗(n_i)$.
• Most admissible heuristics are also monotone.

Time and space complexities

• When $h(n) = 0$, for all $n$, $h$ is monotone. A∗ becomes uniform-cost
• Hence the same bounds as uniform-cost apply. (These are worst case bounds). Still exponential unless we have a very good $h$!

Admissibility implies optimality

• Suppose that an optimal solution has cost C∗
• Any optimal solution will be expanded before any path with cost > C∗ (to be proved later)
• Note that in general, paths are not expanded in the order of their costs (see the example on Pg. 14)
• So the paths expanded before an optimal solution must have cost $\le$ C∗
• There are finitely many paths with cost $\le$ C∗
• Eventually we must examine an optimal solution, and a sub-optimal solution will not be examined before an optimal solution

Any optimal path will be expanded before any path of cost > C∗

Proof:

• Let p∗ be an optimal solution
• Assume that p is a path s.t. c(p) > c(p∗) and p is expanded before p∗
• Then there must be a node n on p∗ which is still in the frontier
• So $c(p) \le f(p) \le f(n) = g(n) + h(n) \le g(n) + h∗(n) = c(p∗)$, contradicting $c(p) > c(p∗)$

What about cycle checking

• We will show that monotonicity guarantees we have found an optimal path to a node the first time we visit it
• Thus with monotonicity, cycle checking preserves optimality
• However, with only admissibility, cycle checking might not preserve optimality.
• To fix this: for previously visited nodes, must remember cost of previous path. If new path is cheaper must explore again