Transcript ppt - IIT Bombay

CS 621 Artificial Intelligence
Lecture 3 – 02/08/05
Prof. Pushpak Bhattacharyya
TWO THEOREMS FOR A* ALGORITHM
02-08-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
1
Algorithm A*
Input: Search graph
Output: Optimal search path to goal
Data Structures: Open list (OL), closed list (CL)
02-08-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
2
Steps in A*
1. Install start node S on OL.
2. If OL is empty, exit with FAIL.
3. Select the first node on OL. Call it n. Transfer it to CL.
4. If n is a goal node, exit with success, after tracing a path from n to S.
5. Expand n into the set M which is non-ancestors of n. Install in OL all
those in M that are not already in OL or CL.
6. For those members of M already in OL, see if the parent pointer
should be redirected to obtain a less costly path. For those in CL, do this
recursively for the nodes and their descendents.
7. Reorder OL in order of increasing f(n) value where f(n) = g(n) + h(n).
In case of tie, favour a deeper node.
8.Goto step 2
02-08-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
3
Theorem - 1
Statement : A* is admissible, i.e.,
●Terminates finding the path from S to a, if it exists.
●The path is optimal.
Lemma : Any time before A* terminates, there exists on the OL, a node
n*, such that
●n* is on the optimal path from S to G
●A* has found the optimal path to n*
●The f value of n* is such that f(n*) <= f*(s)
where f* = g* + h*
g* = actual cost of optimal path from S to n*
h* = actual cost of optimal path from n* to g.
02-08-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
4
Theorem - 1 (Contd)
We observe f*(s) = h*(s)
since g*(s) = 0
Prove the lemma by induction on the number of steps.
Base Case:
Step 1 - S is on the OL
since a) S is on the optimal path
b) A* has found the optimal path to S, trivially
c) f(s) <= f*(s), because
h(n) <= h*(n) for every n by definition of A*
02-08-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
5
Proving Lemma
Hypothesis: Suppose the lemma is true for all the steps upto m.
Induction Step: To prove the lemma for the (m+1) th step. Let n* be the
node at the mth step (previous step).
Case 1: n* is not chosen for expansion.
Case 2: n* is chosen for expansion and brings to OL the nodes m1,m2,...
mp.
One of m1,m2,... mp, say mk* will be on the optimal path to g. Thus (a) is
true, (b) is true (c)
n*
f(s) < = f*(s) ?
02-08-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
6
m1
m2
mp
Proving Lemma (Contd)
To show (c)
f(mk*) = g(mk*) + h(mk*)
g(mk*) = g*(mk*) since mk* is on the optimal path.
h(mk*) <= h*(mk*) by definition of A*.
Also for any node on the optimal path,
f*(n) = f*(s)
For the path s, n1, n2, .... g, for any node ni
f*(ni) = f*(s)
The lemma is proved.
02-08-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
7
Proving Admissibility from the
Lemma
(a) Termination: If A* does not terminate, the g value of expanded
nodes will eventually become unbounded.
Key assumption: each arc cost is positive.
Thereby ‘f’ value will become unbounded.
(b) Optimality: Suppose A* terminates without finding the optimal path,
then just before termination,suppose nk is the node chosen for expansion.
When g is chosen for expansion
f(g) = g(g) + h(g)
{h(g) = 0}
g(g) is non-optimal, i.e., g(g) > g*(g) not possible.
02-08-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
8
Theorem - 2
If A1* and A2* are two versions of A* and if A2* has better heuristics
than A1*, then A1* has to expand atleast all those nodes that A2* expands.
Meaning of “better heuristics”
h2(n) > h1(n) for every n
Proof: By induction on the depth of the search tree of A2*.
Base Case: depth, d = 0
S is expanded by both A2* and A1*, hence true
Hypothesis: Suppose all nodes at depth = k in A2*'s search tree is
expanded by A1*.
02-08-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
9
Theorem 2 (Contd 1)
Induction Step: All nodes at depth = k+1 are also expanded by A1*.
Suppose to the contrary that a node ‘m’ at depth = k+1 is not expanded
by A1* but expanded by A2*.
Since A2* expanded m and terminated.
f2(m) <= f*(s)
------ (1)
Since A1* terminated without expanding m,
f1(m) >= f*(s)
------ (2)
02-08-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
10
Theorem 2 (Contd 2)
The path to ‘m’ is seen by A2* as well as A1*.
g1(m) <= g2(m)
----- (3)
f1(m) >= f2(m)
----- (4)
(from 1 & 2)
or g1(m) + h1(m) >= g2(m) + h2(m)
------ (5)
g1(m) + h1(m) >= g2(m) + h2(m)
and
g1(m) <= g2(m)
Hence h1(m) >= h2(m)
atleast for m, A1* and A2* have equal heuristic - contradiction
02-08-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
11
Monotone Restriction
How to eliminate the recursive search on the closed list (expensive).
Possible by a simple constraint on the heuristic.
Monotone Restriction (MR)
triangular inequalilty - satisfying
S
G
n1
h(n1)
G
h(n2)
02-08-05
C(n1 ,n2)
n2 is a child of n1
MR says
cost of direct arc between n1 and n2 = C(n1, n2)
h(n1) <= h(n2) + C(n1,n2)
consistent heuristic.
n2
Prof. Pushpak Bhattacharyya, IIT
Bombay
12
Theorem Without Proof
If Monotone Restriction is satisfied, then the search for less costly path
for a node in the CL is not necessary.
In other words, if a node is chosen for expansion by A*, it has found an
optimal path to the node.
02-08-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
13
Summary
●
Proved two theorems about A*
Termination optimality
efficiency
● Stated without proof, the condition for no-search in CL – Defined
monotone restriction
Intended Topics
Information theory & AI
● Probabilistic methods in AI
● AI for large problems – enormous data
●
02-08-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
14