人工智能(三) wu-kan

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
  • 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 \dots \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