A state space analysis of propose-and-revise

A central research topic in the area of knowledge engineering is the reuse of problem-solving methods for developing knowledge based systems. For being able to reuse a problem-solving method it is important to know under which restrictions a problem-solving method is appropriate to solve a given problem. This paper describes the problem-solving method propose-and-revise as well as the way this problem-solving method searches in its problem space for a solution. A quantitative analysis of the efficiency of this search process is given. Additionally, task and domain specific properties and restrictions and their influence on the efficiency of the search process are considered. For these purposes an instance of the problem-solving method is transformed to a corresponding instance of a Stanford Research Institute Problem Solver (STRIPS) planning system. Then the problem-solving method is considered as an additional control strategy for such a planning system. By this way the various insights and analysis results which are available in the area of planning systems may be exploited for the analysis of problem-solving methods. ©1999 John Wiley & Sons, Inc.     

Structured development of problem solving methods

Problem solving methods (PSMs) describe the reasoning components of knowledge-based systems as patterns of behavior that can be reused across applications. While the availability of extensive problem solving method libraries and the emerging consensus on problem solving method specification languages indicate the maturity of the field, a number of important research issues are still open. In particular, very little progress has been achieved on foundational and methodological issues. Hence, despite the number of libraries which have been developed, it is still not clear what organization principles should be adopted to construct truly comprehensive libraries, covering large numbers of applications and encompassing both task-specific and task-independent problem solving methods. In this paper, we address these "fundamental" issues and present a comprehensive and detailed framework for characterizing problem solving methods and their development process. In particular, we suggest that PSM development consists of introducing assumptions and commitments along a three-dimensional space defined in terms of problem-solving strategy, task commitments, and domain (knowledge) assumptions. Individual moves through this space can be formally described by means of adapters. In the paper, we illustrate our approach and argue that our architecture provides answers to three fundamental problems related to research in problem solving methods: 1) what is the epistemological structure and what are the modeling primitives of PSMs? 2) how can we model the PSM development process? and 3) how can we develop and organize truly comprehensive and manageable libraries of problem solving methods?     

Verifying ontological commitment in knowledge-based systems

An ontology defines the terminology of a domain of knowledge: the concepts that constitute the domain, and the relationships between those concepts. In order for two or more knowledge-based systems to interoperate—for example, by exchanging knowledge, or collaborating as agents in a co-operative problem-solving process—they must commit to the definitions in a common ontology. Verifying such commitment is therefore a prerequisite for reliable knowledge-based system interoperability. This article shows how existing knowledge base verification techniques can be applied to verify the commitment of a knowledge-based system to a given ontology. The method takes account of the fact that an ontology will typically be expressed using a different knowledge representation language to the knowledge base, by incorporating translation into the verification procedure. While the representation languages used are specific to a particular project, their features are general and the method has broad applicability.     

Framework of knowledge-based systems : Multiple meta-level architecture for representing problems and problem-solving processes

Currently available expert systems have a performance limit because of the lack of capability to describe problems and problem-solving methods. It is closely related with knowledge representation language, but this is not the only concern with this issue. Real world problems and problem-solving methods are not so simple as to be represented always in the same way by the same language. Their representations must be different depending on various factors involved in the problems themselves and the situations these problems are surrounded with. In this paper, the author discusses first the intrinsic nature of problem representation and problem-solving process representation. The requirements for and the conceptual framework of a knowledge-based system that is suited for dealing with various problems then become apparent quite naturally. The author asserts that a multiple meta-level architecture is necessary as well as a knowledge-representation language that can describe complex data structures as the basic framework of knowledge-based systems.     

Toward an engineering science of knowledge-based design

In this paper, we present a framework for organizing, evaluating, and developing knowledge-based models of the design process. We argue that evaluation of a design process model can be carried out from three usefully distinguished perspectives: the knowledge it embodies; the functionality of the design process, from a problem-solving viewpoint; and the implementation of the design process as an actual program. This paper focuses on the first two perspective. We systematically introduce a set of basic functional components, and show how existing approaches or systems can be viewed as configurations of these components, in which domain knowledge has been incorporated. As we lay out this framework, we illustrate it in a simple way by using it to describe knowledge-based house floorplanners. We then complete our presentation by analysing a more complex knowledge-based system (DONTE) that designs circuits.     

Hierarchical representation of problem-solving knowledge in a frame-based process planning system

In most frame-based reasoning systems, the information being manipulated is represetned using frames, but the problem-solving knowledge that manipulates the frames is represented as production rules. One problem with this approach is that rules are not always a natrual way to represent knowledge; another is that systems containing lots of rules may suffer from problems with “exponetial blowup” in the amount of computation required. This paper describes a way to address these problems by organizing the problem-solving knowledge not as rules, but in a particular kind of frame hierarchy. the approach described in this paper has been implemented in a problem-solving system called SIPP (Semi-Intelligent Process Planner), which produces plans of action for the manufacture of metal parts. the paper gives an overview of SIPP, compares its knowledge representation and problem solving methods to approaches used in other knowledge-based systems, and describes goals for further research.     

Modeling tasks with mechanisms

Building a problem solver and acquiring the knowledge needed to operate it are the two central goals of knowledge engineering. to achieve these goals, knowledge engineers construct models of the domain and of the task of interest. the various approaches used for modeling, however, have so far failed to define methods and techniques that can be applied across domains and tasks, and to produce models that can be reused in future applications. In this article, we propose that both of these objectives can be achieved by the use of building blocks called mechanisms. We examine the composition of mechanisms and also show how these mechanisms can be manipulated to construct problemsolving methods. We present PROTÉGÉ-II, a knowledge-acquisition shell that uses problem-solving methods to drive the modeling of tasks, the automatic generation of knowledge-acquisition tools, and the control flow of the problem solver. the modeling of tasks, within the context of PROTÉGÉ-II, is illustrated with two examples: one from the game domain and another from the medical-therapy domain. In addition, we introduce the conceptual basis for a library of mechanisms that serves as a repository of reusable knowledge components. © 1993 John Wiley & Sons, Inc.     

知识系统的知识重用方法

KADS方法的主要贡献是提出了层次化的知识模型,这有助于领域知识和PSM的重用。但是,要真正实现领域知识和PSM的重用,还需要引入本体来实现各层次间的灵活配置,将相互独立的层次紧密地联系在一起,共同组成一个完整的系统。文中介绍了知识系统的本体的种类及其可重用性,讨论了在知识系统中引入本体以实现系统知识重用的方法。     

Compositional Verification of Knowledge-Based Task Models and Problem-Solving Methods

In this paper a compositional verification method for task models and problem-solving methods for knowledge-based systems is introduced. Required properties of a system are formally verified by deriving them from assumptions that themselves are properties of sub-components, which in their turn may be derived from assumptions on sub-sub-components, and so on. The method is based on properties that are formalized in terms of temporal semantics; both static and dynamic properties are covered. The compositional verification method imposes structure on the verification process. Because of the possibility of focusing at one level of abstraction (information and process hiding), compositional verification provides transparency and limits the complexity per level. Since verification proofs are structured in a compositional manner, they can be reused in the event of reuse of models or modification of an existing system. The method is illustrated for a generic model for diagnostic reasoning.     

Domain-oriented design environments

The field of knowledge-based software engineering has been undergoing a shift in emphasis from automatic programming to human augmentation and empowerment. In our research work, we support this shift with an approach that embedshuman-computer cooperative problem-solving tools intodomain-oriented, knowledge-based design environments. Domain orientation reduces the large conceptual distance between problem-domain semantics and software artifacts. Integrated environments support the coevolution of specification and construction while allowing designers to access relevant knowledge at each stage within the software development process.This paper argues thatdomain-oriented design environments (DODEs) are complementary to the approaches pursued withknowledge-based software assistant systems (KBSAs). The DODE extends the KBSA framework by emphasizing a human-centered and domain-oriented approach facilitating communication about evolving systems among all stakeholders. The paper discusses the major challenges for software systems, develops a conceptual framework to address these problems, illustrates DODE with two examples, and assesses the contributions of the KBSA and DODE approaches toward solving these problems.     

ON KNOWLEDGE REPRESENTATION FOR INFERENCES IN CAST METHOD BANKS

This article explains why aspects of knowledge representation must be considered in the context of computer aided systems theory (CAST). CAST method banks support human experts during the process of problem solving. They should be understood as decision support systems, as assistants of their human expert users. One key to making this approach work is the communication between the expert and the system. The assistant should provide systematical and goal-directive information about the current problem state for the human expert. Another, even more important requirement is the assistant's knowledge about all available methods at a certain problem-solving state and their expected impact on the further problem-solving process. Knowledge representation denotes how the problem domain is represented within the support system and how it is used. We investigate different forms of knowledge representations and summarize criteria for the applicability of different forms of knowledge representations in CAST systems.     

Task-Structures,Knowledge Acquisition and Learning

One of the old saws about learning in AI is that an agent can only learn what it can be told, i.e., the agent has to have a vocabulary for the target structure which is to be acquired by learning. What this vocabulary is, for various tasks, is an issue that is common to whether one is building a knowledge system by learning or by other more direct forms of knowledge acquisition. I long have argued that both the forms of declarative knowledge required for problem solving as well as problem-solving strategies are functions of the problem-solving task and have identified a family of generic tasks that can be used as building blocks for the construction of knowledge systems. In this editorial, I discuss the implication of this line of research for knowledge acquisition and learning.     

Hardware-Software Partitioning at the Knowledge Level

Hardware-software co-design addresses the development of complex heterogeneous systems looking for the best tradeoffs among the different solutions. The basic idea is to combine the hardware and software design cycles. This article shows how knowledge-based techniques can be used to solve the hardware-software partitioning problem, the co-design task that makes the decision on the best implementation of the different components of a digital system. In particular, a fuzzy-logic-based expert system, SHAPES, has been developed based on the CommonKADS methodology. This tool takes advantage of two important artificial intelligence bases: the use of an expert's knowledge in the decision-making process and the possibility of dealing with imprecise and usually uncertain values by the definition of fuzzy magnitudes.Expert system construction has adopted a knowledge modeling approach, following the knowledge level and knowledge separation principles. This expertise model is the center of the knowledge-based system development. It is based in the problem-solving method Propose and Revise with a previous heuristic classification.     

Applying rule-base anomalies to KADS inference structures

The literature on validation and verification of knowledge-based systems contains a catalogue of anomalies for knowledge-based systems, such as redundant, contradictory or deficient knowledge. Detecting such anomalies is a method for verifying knowledge-based systems. Unfortunately, the traditional formulation of the anomalies in the literature is very specific to a rule-based knowledge representation, which greatly restricts their applicability. In this paper, we show how the traditional anomalies can be reinterpreted in terms of conceptual models (in particular KADS inference structures). For this purpose, we present a formalisation of KADS inference structures which enables us to apply the traditional rule-base anomalies to these inference structures. This greatly improves the usefulness of the anomalies, since they can now be applied to a much wider class of knowledge-based systems. Besides this reformulation and wider applicability of the traditional anomalies, further contributions of this paper are a novel formalisation of KADS inference structures and a number of improvements to the existing formalisation of the traditional anomalies.     

Supporting software designers with integrated domain-orienteddesign environments

An approach that embeds human-computer cooperative problem-solving tools into knowledge-based design environments that work in conjunction with human software designers in specific application domains is described. This human-centered approach takes advantage of peoples' ability to understand and incrementally reformulate their problems, while allowing them to contribute to the gradual improvement of the underlying knowledge base. The notion of evolution circumvents the inability of the original builders of a design environment to anticipate all future needs and knowledge for complete coverage of a domain. The access and development of knowledge is supported in a cycle of location, comprehension, and modification. Modification includes the evolution of the knowledge base and tools. A framework for building such tools and mechanisms is described and illustrated in terms of three systems: CATALOGEXPLORER, EXPLAINER, and MODIFIER. User studies of these systems demonstrate the promise and the limitations of the design environment approach     

A Delphi-based approach to developing expert systems with the cooperation of multiple experts

Knowledge acquisition has been a critical bottleneck in building knowledge-based systems. In past decades, several methods and systems have been proposed to cope with this problem. Most of these methods and systems were proposed to deal with the acquisition of domain knowledge from single expert. However, as multiple experts may have different experiences and knowledge on the same application domain, it is necessary to elicit and integrate knowledge from multiple experts in building an effective expert system. Moreover, the recent literature has depicted that “time” is an important parameter that might significantly affect the accuracy of inference results of an expert system; therefore, while discussing the elicitation of domain expertise from multiple experts, it becomes an challenging and important issue to take the “time” factor into consideration. To cope with these problems, in this study, we propose a Delphi-based approach to eliciting knowledge from multiple experts. An application on the diagnosis of Severe Acute Respiratory Syndrome has depicted the superiority of the novel approach.     

A state-based knowledge representation approach for information logical inconsistency detection in warning systems

Detecting logical inconsistency in collected information is a vital function when deploying a knowledge-based warning system to monitor a specific application domain for the reason that logical inconsistency is often hidden from seemingly consistent information and may lead to unexpected results. Existing logical inconsistency detection methods usually focus on information stored in a knowledge base by using a well-defined general purpose knowledge representation approach, and therefore cannot fulfill the demands of a domain-specific situation. This paper first proposes a state-based knowledge representation approach, in which domain-specific knowledge is expressed by combinations of the relevant objects’ states. Based on this approach, a method for information logical inconsistency detection (ILID) is developed which can flexibly handle the demands of various domain-specific situations through reducing part of restrictions in existing methods. Finally, two real-case based examples are presented to illustrate the ILID method and its advantages.     

HOW TO HELP INTELLIGENT SYSTEMS WITH DIFFERENT UNCERTAINTY REPRESENTATIONS COOPERATE WITH EACH OTHER

In order to solve a complicated problem one must use the knowledge from different domains. Therefore, if we want to automatize the solution of these problems, we have to help the knowledge-based systems that correspond to these domains cooperate, that is. communicate facts and conclusions to each other in the process of decision making. One of the main obstacles to such cooperation is the fact that different intelligent systems use differenl methods of knowledge acquisition and different methods and formalisms for uncertainty representation. So we need an interface f, “translating” the values x, y, which represent uncertainly of the experts’ knowledge in one system, into the values f(x), f(y) appropriate for another one.

In the present report we formulate the problem of designing such an interface as a mathematical problem, and solve it. We show that the interface must be fractionally linear: f(x) = (ax + b)/(cx + d).