Problem Redundancy AO Search

Problem Redundancy AO Search

Problem Redundancy AO Search

Welcome back to LiveiPlmatch.Com. we are going to discuss Problem Redundancy AO Search, It is the type of problem reduction.

Problem reduction search requires And/Or Graph/Tree.

Problem Reduction :

To find the best way to solve the problem if the problem decomposed into subprblem such that there exist multiple ways of decompositions.

Any problem in problem reduction search can be represented using AND/OR Graph.

In such graph each node ‘n’ represents a sub-problem which is to be forther decomposed.

An ‘OR’ node in the graph represents a choice between alternate decomposeitions.

‘AND’ node represents a possible decompositions into sub-problem where each must be solved.

Each node ‘n’ can have an Heuristic value i.e. h(n). Where h(n) is an estimation of the cost to solve ‘n’.


Given = {G , S , T}

G : It is an AND / OR graph.

S : initial state i.e. it represents a problem which should be solved

T : Set of terminal value

h(n) : Heuristic Value

We need to find G* which is a marked subtree that gives the best decompositions.


Step 1 : G* = { s } , f(x) = h(s)

if S E T mark s as solved

Step 2 : if S is labelled as solved then return G*

Step 3 : Select a non-terminal leaf from marked subtree & let it be n.

Step 4 : Generate successor of n

for each successor m of n

f(m) = h(m)

Step 5 : cost_revise(n)

Step 6 : go to step 2.


Step 1 : x = {n}

Step 2 : if x={} then return

Step 3 : remove a state m from x which do not have any children in x

Step 4 : if m is AND node having successor r1,r2,r3…………..rk

for each Ri

f(m) = Ef(ri) + cost(MiRi)

marked each edege m to ri

Step 5 : If m is OR node having successor


for each ri

f(m) = min { f(ri) + cost(MiRi) }

mark best successor m —>Ri

Step 6 : if f(m) has changed then insert parent (m) in x

Step 7 : Go to Step 2.


leave a comment

Create Account

Log In Your Account