Page 184 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes peg. In this case, we will consider the state at the top of the figure the starting state. In this case,
all three disks are on the left-most peg. And, we will consider the state at the bottom right to be
the goal state. In this state, the three disks are now all stacked on the right-most peg.
Recall that in state space search the generators correspond to moves in the state space. Thus, the
two states below the top state in the triangle of states corresponds to the movement of the
smallest disk either to the rightmost peg or to the middle peg. The shortest solution to this
problem corresponds to the path down the right side of the state space. This solution is shown in
the animation below.

In problem reduction search, the problem space consists of an AND/OR graph of (partial) state
pairs. These pairs are referred to as (sub)problems. The first element of the pair is the starting
state of the (sub)problem and the second element of the pair is the goal state (sub)problem.
There are two types of generators: non-terminal rules and terminal rules. Non-terminal rules
decompose a problem pair, <s0, g0> into an ANDed set of problem pairs {<si,gi>, <sj,gj>, ...>.
The assumption is that the set of subproblems are in some sense simpler problems than the
problem itself. The set is referred to as an ANDed set because the assumption is that the solution
of all of the subproblems implies that the problem has been solved. Note all of the subproblems
must be solved in order to solve the parent problem.
Any subproblem may itself be decomposed into subproblems. But, in order for this method to
succeed, all subproblems must eventually terminate in primitive subproblems. A primitive
subproblem is one which can not be decomposed (i.e., there is no non-terminal that is applicable
to the subproblem) and its solution is simple or direct. The terminal rules serve as recognizers
of primitive subproblems.
The symmetry of the state space shown above may have led you to suspect that the Tower of
Hanoi problem can be elegantly solved using the method of problem decomposition. The AND
tree that solves the 3 disk problem is shown below.

9.5.2 Implementing Arbitrary AND/OR-Trees

Let us number the state space solution shown in the state space above 1 through 8 so that we can
refer to the states by number. 1 corresponds to the topmost or starting state and 8 to the right
corner or goal state. These two states are the first and second element in the problem shown as
the root node in the AND tree above. The red arc is used to indicate that the node is an AND
node.
The problem is decomposed into three subproblems. The left subproblem consists of states 1
and 4; the middle subproblem consists of states 4 and 5; and the right corresponds to states 5 and
8. Note that the left and the right subproblems correspond to the top and bottom nodes of the

178 LOVELY PROFESSIONAL UNIVERSITY