An approach to user-directed search in interactive problem solving
Date
1991
Authors
Qin Yang
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis studies some problems which are important in establishing interactive
problem solving systems. An interactive problem solving system is characterized
by the intensive interaction between the user and the system. In order to converge
on a solution which satisfies the user, we present a new problem solving scheme -
user-directed search (UDS) - where the solution search is directed in a step-by-step
manner by the user. Because of its wide applicability, UDS can be very useful for
many practic~l cases.
The user-directed problem solving is realized by introducing a particular communication
mechanism between the user and the system. This enables a user to
guide the solution searching in his most preferred directions. Thus the system can
first explore the solutions which are more likely to match the user-desired solution.
We have developed UDS using two different approaches.
In the first approach, additional deduction rules can be created upon the user's
request and/or upon changes in practical environments. For this purpose, we have
created, in the user interface, an environment which enables a user to add his new
requirements in the form of deduction rules. To improve efficiency, we have used a
particular backjump search which can first find, and then backjump to, the point
which contradicts the user's new requirements. To establish the dependency for this
backjumping, we have used assumption-based truth maintenance systems (ATMS)
and KEEworlds in the knowledge engineering environment(KEE). In the second approach, we have introduced particular variable groups. In this
approach, the user's new requirements are introduced through a scheme in which the
user divides the variable set into several different variable groups. By dividing these variable groups according to his choice, a user can effectively control and instruct
the search during the process of problem solving. We have introduced here a scheme
which we call proximal minimum (closeness) change. The proximal minimum change
ensures that, in the direction specified by the user, a closest solution to the previous
one will be found if it actually exists.
In another aspect, in order to improve efficiency of solution search on a general
basis, we have applied some techniques from Constraint Satisfaction Problems
(CSP) in establishing non-CSP expert systems, e.g. rule-based and frame-structured
expert systems on KEE. We find that these CSP techniques can be used to improve
efficiency by performing consistency checking prior to searching for a solution, which
we call pre-processing. This pre-processing is introduced to eliminate a number of
variable values which are inconsistent with certain unary and binary constraints. In
practical applications, this method can be used to avoid a considerable amount of
useless backtracking. We have developed an independent module for applying CSP
techniques in general purpose programming in KEE. This CSP module provides
KEE with ability to establish more versatile expert systems.
Through case studies of the truck dispatching problem and the word puzzle problem,
we demonstrate how to achieve UDS and how to implement various techniques
which we have presented to improve efficiency in UDS. Some of the advantages of
UDS are shown in the case studies.
Description
Keywords
Citation
Collections
Source
Type
Thesis (Masters)
Book Title
Entity type
Access Statement
License Rights
Restricted until
Downloads
File
Description