Tuesday, November 22, 2011

A* Search

Algorithms form an important part of the problem solving process in Artificial Intelligence. One useful algorithm is A* Search, which is an extension of another useful algorithm called Dijkstra's algorithm. This video is a short introduction to the subject.

So, the key part of this algorithm is the evaluation function $$f(\text{node})=g(\text{node})+h(\text{node})$$ (note that in the video "state" is treated as a "node"), where
- $g(\text{node})$ is the cost from the "Start" node to the current node and
- $h(\text{node})$ is the heuristic (estimated) cost from the current node to the "Goal".
The algorithm works by always expanding the path which has the minimum value of $f(\text{node})$ first (cheapest first). The search terminates when the "Goal" node is chosen for expansion or there are no more nodes to expand.

For the heuristic function to be admissible (or optimistic, which is the same) it is important that for any node $h(\text{node}) \le$ actual cost from the node to the "Goal". If this is true, then "A* Search" will always find the lowest cost path from the "Start" to the "Goal", this video explains this principle with more details.

As you could mention, the last video operates with another term called "search frontier". It is a "characteristic" of the algorithm or the way it progresses to/with expanding the nodes. For example:
- this article shows how the search frontier looks for the Breadth-First Search algorithm and
- this article shows how the search frontier looks for the Depth-First Search algorithm.

An implementation of this algorithm would use a priority queue, where priority is dictated by the function f.

Now, let's consolidate this material with an exercise:

For heuristic function h and cost of action 10 (per step), find the order (1, 2, 3, ...) of the nodes expansion (the node is expanded when it is removed from queue). Start with "1" at the "Start" state at the top. Indicate the nodes that will never be expanded. Is the heuristic function admissible?

First of all the heuristic function is not admissible because h(B5)=20 > 10, where 10 is the actual cost from B5 to the "Goal".

Now, let's start with the expansion. The frontier is at the "Start".

1. f(A1)=10+11=21, f(A2)=18, f(A3)=17, f(A4)=16, f(A5)=20. The frontier moves to A1, A2, A3, A4, A5 (this is the content of the queue).

2. A4 is the node (in the queue) with the minimum f (=16), so it's the second node to be expanded (removed from the queue). f(B4)=10+10+5=25, f(B5)=40. The frontier moves to A1, A2, A3, B4, B5, A5.

3. A3 is the next node with the minimum f (=17), so it's the third node to be expanded. But there is nothing to add to the queue. The frontier now is A1, A2, B4, B5, A5.

4. A2 is the next node with the minimum f (=18), so it's the forth node to be expanded. f(B2)=10+10+3=23, f(B3)=29. The frontier moves to A1, B2, B3, B4, B5, A5.

5. A5 is the next node (again, in the queue) with the minimum f (=20), so it's the fifth node to be expanded. f("Goal")=10+10+0=20. The frontier moves to A1, B2, B3, B4, B5, "Goal".

6. The "Goal" is the next node (from the queue) with the minimum f (=20), so it's the sixth node to be expanded and, because it is the "Goal", it is also the last one to be expanded (i.e. end of the search).

Here is the expansion order: "Start"-1, A4-2, A3-3, A2-4, A5-5, "Goal"-6.

The nodes which were never expanded: A1, B1, B2, B3, B4 and B5.

1 comment:

  1. Thinking out loud:

    Simple arithmetic. I have 74 assets and need to compute the best (low risk, high return) portfolio investment distribution. This means all the combinations of assets from 2 to 74 = (2^74) - 74=18889465931478580854710.

    The highest frequency a CPU can achieve is (http://blogs.amd.com/play/2011/09/09/guinness/) 8.429Ghz or 8429000000 operations per second 18889465931478580854710/8429000000=71062 years (the final figure is higher because portfolio distribution calculations involve linear algebra operations with matrixes, so it's not really a single CPU operation). For a cloud of 40000 computers with dual CPU will roughly take at least 1 year to complete the task.

    Now, let's do some heuristic, 92 pairs of assets are highly correlated, ρ ≥ 0.9, so it is pointless to analyse all the assets. We can effectively exclude 39 assets. 74-39=35 assets to consider or a total of (2^35) – 35=34359738333. 34359738333/8429000000 almost 4 seconds.

    ReplyDelete