An approach to user-directed search in interactive problem solving

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.