(This page contains course notes for Artificial Intelligence taught in the Autumn of 2015. If you have come here from a search engine or the like, you may wish to visit the course home page for more material, or visit my home page for possibly more up to date versions.)

Heuristics

Reading: 4.2, 4.1.

Brute force searches take no notice of the kinds of problems they are solving

The obvious example is during a path finding problem, when a brute force algorithm searches off in the wrong direction entirely.

What we really want is an algorithm that selects the next node to expand, not based on some generic rules like depth, but rather based on some idea of how likely that node is to be on the correct path.

The result is a class of algorithms called "Best-First Search". These algorithms are just like other search algorithms, but they use problem knowledge to select the next node to expand:
Best-First Generate and Test algorithm:

BestFirst(StartState s)
  while (isNotGoal(s))
    generate successors to s
    point successors back to s
    add successors to open
    add s to closed
    s ←  best from open

The mechanism for getting an idea of how likely a node is to be on the correct path is called a heuristic.
Note that I've changed when nodes are added to the closed list. There will be a homework about that.

We define a heuristic as a function h(n) which takes as an argument a node in the search space and returns an estimate of the number (or cost) of the remaining steps

Then we can select the next node to expand based, at least in part, on the H(n) value.
For the path planning algorithm, a common heuristic is the straight-line distance to the goal.
Run through example.

Greedy search- in AI greedy search means, select the node with the smallest h(n) as next node for expansion.

Complete? Depends on the heuristic.

If the heuristic is exact, then yes.
If the heuristic is random, or inversely proportional to the correct values, then no.

Optimal? Again, depends on the heuristic.
Time? given a heuristic that is complete, O(b^d).
Space? Given that a heuristic is complete, O(b^d).

Finding heuristics

What is a good heuristic for the 8 puzzle? Mahattan Distance.
In general, to find a heuristic, you often want to relax one of the rules of the problem.

In path finding, we relaxed the rule that you needed to follow the edges of the graph.
In the 8 puzzle, we relaxed the rule that 2 tiles could not share the same place at the same time.
In the missionaries and cannibals, we...

often, finding the solution to a relaxed version of the problem is a good heuristic for the harder problem.
Be aware that if the heuristic is too costly to calculate, then it may not be worth it.

A*

What is wrong with greedy search?

Worst case, it sufferes the same fate as DFS;
Not optimal, not complete and can suffer O(b^m) time and space complextity.

Here's our situation:

Greedy search selects nodes for expansion based on h(n), and is neither complete nor optimal.
Uniform Cost selects nodes for expansion based on g(n), and is complete and optima, but not efficient.
What should we do? Can we combine the properties of both?

how about: f(n) = h(n) + g(n)?

Since g(n) is the cost so far, and h(n) is the estimated cost remaining, f(n) is the estimated cost of the path through node n.
Does this make some intuitive sense?
What can we prove about it?

Let's make an assumption: that whatever h(n) we're using, it never overestimates the cost to the goal from that node. No matter what value we get for h(n), we know h(n)<=h*(n).

If this is true, we say that h(n) is admissible.
If h(n) is admissible, what can we say about f(n)? It never overestimates the actual cost of the best solution through n.
Make another assumption: That for any pair of nodes n and n' where n is an ancestor of n', the f(n) <= f(n'). This is called monotonicity. In general, a function is monotonic if it doesn't change direction i.e. if it is increasing at some point, it will be increasing at some later point (or at least not decreasing).
Let's prove optimality:

Assume 2 goal states G₁ and G₂. G₁ is the optimal goal state, and G₂ is some goal state on a non-optimal path. (see picture).

Now, f(G₁) = C*, by assumption g(G₁) is the lowest cost path, and h(G₁) = 0, because h(n) is admissible.
Imagine that A* has selected G₂ to expand rather than G₁. (proof by contradiction!)
Thus there is some node n which is the ancestor of G₁ and is also a leaf node in the A* search. Why must there be one?
C* ≥ f(n), by admissibility.
f(G₁) ≥ f(n), by substitution.
f(n) ≥ f(G₂), Since G₂ was selected for expansion rather than n.
f(G₁ ) ≥ f(G₂), by substitution
f(G₂ ) = g(G₂ )+ h(G₂), by assumption.
h(G₂) = 0 it's a goal node and our heuristic is admissible
f(G₂) = g(G₂ ).
f(G₁ ) ≥ g(G₂ ), by substitution
f(G₁ ) = g(G₁ )+ h(G₁), by assumption.
h(G₁) = 0 it's a goal node and our heuristic is admissible
f(G₁) = g(G₁ ).
g(G₁ ) ≥ g(G₂ ), by substitution
The reads, the cost to G₁ is greater than the cost to G₂, but that can't be since G₁ is the optimal goal! Proof by contradiction
q.e.d.

Let's prove completeness:

A* expands nodes in increasing order of f(), it must eventually expand a goal node, unless there are an infinite number of nodes with an f < f(g).
This can only be true if there is some node in the tree with an infinite amount of children...

Now go back and look at monoticity.

We know that as we go down a path, g(n) is increasing, unless we have negative costs (which would pretty much toss all of this out the window).
So if h(n) is also decreasing by less than g(n) is increasing, then f(n) is increasing. But all we know about h(n) is that it never overestimates. We can easily construct an admissible h(n) that is not monotonic. So now what?
pathmax: we know that the cost of the path through n is at least f(n). Now if f(n') is less than f(n), we still know that the cost of the path through f(n) and f(n') is at least f(n). So all we have to do is keep track of the maximal f(n) along a path, and if any f(n) turns out to be less than the max, we just set that f(n) = the max.
Since it is always increasing, the max hould always be the f(parent).
It turns out that most heuristics one could pick are naturally monotonic.
In fact, using the concept of relaxing a constraint of the problem typically results in an admissible monotonic heuristic.

Time & Space Complexity:

Still O(bⁿ), just a more efficient bⁿ
Guess what is more of a problem?

IDA* - Just like iterative deepening can turn breadth-first search into a linear memory algorithm, we can perform the same trick

First we need a f-cost-limited depth first search. It performs a DFS, but instead of going to a particular depth in terms of the number of nodes, we look at the depth in terms of the f-cost of the nodes:
```
FLimitDFS(StartState s, Limit l)
  done  ← false
  min ← ∞
  while (!done)
    if (f(s) ≤ l)
      if(isGoal(s)) 
        return path to s
      generate successors to s
      point successors back to s
      push successors on open stack
    else
      if (f(s) < min) min ← f(s)
    s ←  pop next state from open
    if pop failed, done  ← true
  return min
```
Note that if we don't find the path in this iteration, we return the smallest f-cost on the open list. This enables us to increase the cutoff the right amount. Otherwise we might not increase the f-cost cutoff enough and not search any new nodes next iteration.
The Now that we have our limited DFS, all we need to do is:
```
IDA*(StartState s)
  l ← f(s)
  r ← ⌀
  while (isNotPath(r))
    r ← FLimitDFS(s,l)
    if (isNumber(r)) l ← r
  return r
```
So how well does this work? It is complete and optimal, it is linear in space, and given the right conditions, it is O(B^d) in time.
In order to see that it is linear in space, it is only necessary to see that at any one pass through FLimitDFS, it is running a DFS, and so only ever stores a linear amount of memory.
In order to see that it is complete and optimal, it is only necessary to see that FLimitDFS expands new nodes (nodes not expanded in previous runs through FLimitDFS) in the same order as does A*: in increasing f-cost. If A* finds the optimal path, then so does IDA*.
As for time, in many situations it will run in O(B^d), for the same sort of reasons iterative deepening works in general: the last iteration so dominates the runtime that previous iterations don't matter. BUT, since we're increasing f-cost, we can't really guarantee that:
1. If every f-cost is unique, then each run through the FLimitDFS only adds one node. This makes it much worse. ooooh, good homework problem
2. Even if there are many new nodes at each f-cost, some strange trees can still make this Ω(B^dlg(B^d))
3. If the space is a graph, not a true tree, there is no way to check for loops. A* would detect these loops and not search them, but IDA* would search them again and again. In worst case, this can be Ω(2^{B^d}). There's really no way to beat that and still have linear memory, of course.

IDA* uses too little memory, causing the above problems. One approach is use memory to the fullest. There are a variety of algorithms for doing this, we'll talk about SMA* because the book calls it the "best". Be aware that the book's first author invented SMA*, so take that with a grain of salt.

Operate as with A* until you run out of memory. At this point, there's no room for new children.
So, forget some node already in memory, so we have room for new ones.
Which node? The one we're least likely to expand; the one with the highest f-cost.
But we'd rather not forget about it entirely, since some work was done there, and even worse, we might just try to regenerate that node if the parent's f-cost is small enough.
So what we do is store in the parent the best f-value of a deleted descendant. Note descendant, not child. If we delete a node that already had a child deleted, we back up to its parent the smaller of the two f-costs.
That way, if we ever get to a point where the nodes we have in memory have an f-cost greater than this "backed-up" value, we know somewhere in that subtree is a decent path, and we start searching down that.
While simple to describe, this is nastly to get right, which is why the formal algorithm was deleted in the 2nd edition of the book.