Page 186 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes 9.5.3 Implementing the AND/OR-Tree Search Function

Another important feature of problem reduction rules is that their use allows the order of problem
solving to differ from the order of problem execution. In the state space above, these two are
obviously the same (although one could also search backward from the goal, but in the case of
either forward or backward search the solution involves the same linear order of states.) In the
present case, the problem solver could choose any of the subproblems to work on first.
In the Tower of Hanoi problem, there is no obvious advantage to solving the problem in an
order that differs from the order of problem execution. However, in some problems one may
find that some subproblems are easier than others and their solution may serve to simplify the
solution of the remaining subproblems. A Cryptarithmetic Problem has been developed which
illustrates this point. In this case, the subproblems correspond to the different equations that are
formed in the algebraic representation of the problem. Note, that in this case the state space has
10! states and solving it via state space search is out of the question for any sane human mind. It
thus uses depth first search and exits as soon as the first solution is found. The function will
systematically explore the whole space if no solution can be found (if there are no loops) before
returning <false>. We have used recursion to deal with the other goals. It would have been just
as easy to have used a loop instead which looped through each of the goals input to the search
function and merely called itself recursively in dealing with each of their sub-goals.

9.5.4 Implementing Planning as AND/OR-Tree Search

To implement a simple form of planning behaviour using our generic, AND/OR-tree search
function, we first need to set up the appropriate AND/OR search space (i.e. rule-base). Below is
a set rule which define an implicit AND/OR tree for a “book” problem. This is a variant on the
“cake” problem of Burton and Shad bolt, 1987.

We have placed facts earlier in the rule-base than rules. This is to ensure that in searching, the
system checks facts first before continuing the search via the rules. All the entries are lists of
elements; in each case the first element corresponds to a goal and the remaining elements form
the corresponding sub-goals or “preconditions”. Calling the new search function on the Input
corresponding to a goal of the planning task considered produces behaviour.

9.5.5 Implementing Reasoning as AND/OR-Tree Search

The AND/OR-tree search function is not only applicable in the case where we wish to solve a
simplified planning problem. It can also be applied in many other cases. Any problem whose
solution we can think of in terms of goal-reduction can be solved by the application of AND/
OR-tree search. To obtain a specific implementation we only need to set up the appropriate rule
base.

Example: AND/OR-tree search can be used to solve simple reasoning problems. In this
application goals correspond roughly to “conclusions” and sub-goals correspond roughly to
bits of “evidence”. Search rules state that certain collections of evidence (sub-goals) allow the
drawing (achievement) of a given conclusion (goal).

Self Assessment

State whether the following statements are true or false:

17. The process of decomposing a goal into its sub goals is referred to as goal-reduction.

180 LOVELY PROFESSIONAL UNIVERSITY