Using goal structure to direct search in a problem solver
Abstract
This thesis describes a class of problems in which interactions
occur when plans to achieve members of a set of simultaneous goals are
concatenated in the hope of achieving the whole goal. They will be
termed "interaction problems". Several well known problems fall
into this class. Swapping the values of two computer registers
is a typical example.
A very simple 3 block problem is used to illustrate the
interaction difficulty. It is used to describe how a simple
method can be employed to derive enough information from an
interaction which has occurred to allow problem solving to proceed
effectively.
The method used to detect interactions and derive information
from them, allowing problem solving to be re-directed, relies on an
analysis of the goal and subgoal structure being considered by the
problem solver. This goal structure will be called the "approach"
taken by the system. It specifies the order in which individual
goals are being attempted and any precedence relationships between them
(say because one goal is a precondition of an action to achieve
another). We argue that the goal structure of a problem contains
information which is simpler and more meaningful than the actual plan
(sequence of actions) being considered. We then show how an
analysis of the goal structure of a problem, and the correction of such
a structure in the light of any interaction, can direct the search
towards a successful solution.
Interaction problems pose particular difficulties for most
current problem solvers because they achieve each part of a composite
goal independently and assume that the resulting plans
can be concatenated to achieve the overall goal. This assumption is
beneficial in that it can drastically reduce the search necessary in
many problems. However, it does restrict the range of problems which
can be tackled. The problem solver, INTERPLAN, to be described as a
result of this investigation, also assumes that subgoals can be solved
independently, but when an interaction is detected it performs an
analysis of the goal structure of the problem to re-direct the search.
INTERPLAN is an efficient system which allows the class of
interaction problems to be coped with.
INTERPLAN uses a data structure called a "ticklist" as the basis
of its mechanism for keeping track of the search it performs. The
ticklist allows a very simple method to be employed for detecting and
correcting for interactions by providing a summary of the goal structure
of the problem being tried.