PROCASE: a case-based process planning system for machining of rotational parts

This paper introduces a case-based process planning system PROCASE which generates new process routines through learning from existing process routines. In contrast to traditional rule-based systems, the process planning knowledge of the PROCASE is represented in terms of cases instead of production rules. The planning basically comprises case retrieving and case adaptation rather than chaining applicable rules together to form process plans. The advantages are, first, the system is cheaper to build as it saves the expense of knowledge acquisition. Second, the system is able to advance its knowledge automatically through planning practice. Third, it is robust, because the reasoning is not based on pattern matching but similarity comparison. PROCASE has three modules: the retriever, the adapter and the simulator. It is supported by a feature-based representation scheme which naturally serves as the case indices for case retrieving and adaptation. The retriever uses a similarity metric to retrieve an old case which is the most similar case, among all old ones, to the new case. The adapter is then activated to adapt the process plan of the retrieved case to fit the needs for the new case. The simulator is used to verify the feasibility of the adapted plan. PROCASE is implemented on a Silicon Graphics IRIS workstation using C++ . An example is given to demonstrate how the process routine is generated by the system proposed by the authors.     

Enhancing the performance of an agent-based manufacturing system through learning and forecasting

Agent-based technology has been identified as an important approach for developing next generation manufacturing systems. One of the key techniques needed for implementing such advanced systems will be learning. This paper first discusses learning issues in agent-based manufacturing systems and reviews related approaches, then describes how to enhance the performance of an agent-based manufacturing system through learning from history (based on distributed case-based learning and reasoning) and learning from the future (through system forecasting simulation). Learning from history is used to enhance coordination capabilities by minimizing communication and processing overheads. Learning from the future is used to adjust promissory schedules through forecasting simulation, by taking into account the shop floor interactions, production and transportation time. Detailed learning and reasoning mechanisms are described and partial experimental results are presented.     

Conceptual indexing and active retrieval of video for interactive learning environments

Selecting an instructive story from a video case base is an information retrieval problem, but standard indexing and retrieval techniques [1] were not developed with such applications in mind. The classical model assumes a passive retrieval system queried by interested and well-informed users. In educational situations, students cannot be expected to form appropriate queries or to identify their own ignorance. Systems that teach must, therefore, be active retrievers that formulate their own retrieval cues and reason about the appropriateness of intervention.

The Story Producer for InteractivE Learning (SPIEL) is an active retrieval system for recalling stories to tell to students who are learning social skills in a simulated environment [2, 3]. SPIEL is a component of the Guided Social Simulation (GuSS) architecture [4] used to build YELLO, a program that teaches account executives the fine points of selling Yellow Pages advertising. SPIEL uses structured, conceptual indices derived from research in case-based reasoning [5, 6]. SPIEL's manually-created indices are detailed representations of what stories are about, and they are needed to make precise assessments of stories' relevance.

SPIEL's opportunistic retrieval architecture operates in two phases. During the storage phase, the system uses its educational knowledge encapsulated in a library of “storytelling strategies” to determine, for each story, what an opportunity to tell that story would look like. During the retrieval phase, the system tries to recognize those opportunities while the student interacts with the simulation. This design is similar to “opportunistic memory” architectures proposed for opportunistic planning [7, 8].     

Introspective reasoning for index refinement in case-based reasoning

Introspective reasoning can enable a reasoner to learn by refining its own reasoning processes. In order to perform this learning, the system must monitor the course of its reasoning to detect learning opportunities and then apply appropriate learning strategies. This article describes lessons learned from research on a computer model of how introspective reasoning can guide failure-driven learning. The computer model monitors its own reasoning by comparing it to a model of the desired behaviour of its reasoning, and learns in response to deviations from the ideal defined by the model. The approach is applied to the problem of determining indices for selecting cases from a case-based planner's memory. Experiments show that learning driven by this introspective reasoning both decreases retrieval effort and improves the quality of plans retrieved, increasing the overall performance of the planning system compared to case learning alone.     

ON-LINE CASE-BASED PLANNING

Some domains, such as real-time strategy (RTS) games, pose several challenges to traditional planning and machine learning techniques. In this article, we present a novel on-line case-based planning architecture that addresses some of these problems. Our architecture addresses issues of plan acquisition, on-line plan execution, interleaved planning and execution, and on-line plan adaptation. We also introduce the Darmok system, which implements this architecture to play Wargus (an open source clone of the well-known RTS game Warcraft II ). We present empirical evaluation of the performance of Darmok and show that it successfully learns to play the Wargus game.     

Planning as Propositional CSP: From Walksat to Local Search Techniques for Action Graphs

Graphplan-style of planning can be formulated as an incremental propositional CSP where the (boolean) variables correspond to operator instantiations (actions) that are or are not scheduled at certain time steps. In this paper we present a framework for solving this class of propositional CSPs using local search in planning graphs. The search space consists of particular subgraphs of a planning graph corresponding to (complete) variable assignments, and representing partial plans. The operators for moving from one search state to the next one are graph modifications corresponding to revisions of the current variable assignment (partial plan), or to an extension of the represented CSP.Our techniques are implemented in a planner called LPG using various types of heuristics based on a parametrized objective function, where the parameters weight different constraint violations, and are dynamically evaluated using Lagrange multipliers. LPG's basic heuristic was inspired by Walksat, which in Kautz and Selman's Blackbox can be used to solve the SAT-encoding of a planning graph. An advantage of LPG is that its heuristics exploit the structure of the planning graph, while Blackbox relies on general heuristics for SAT-problems, and requires the translation of the planning graph into propositional clauses. Another major difference is that LPG can handle action execution costs to produce good quality plans. This is achieved by an anytime process minimizing an objective function based on the number of constraint violations in a plan and on its overall cost. Experimental results illustrate the efficiency of our approach, showing, in particular, that LPG is significantly faster than Blackbox and other planners based on planning graphs.     

Robotic inspection plan optimizationby case-based reasoning

Inspection planning is discussed in a framework where a rich choice of instruments is available and robots can also participate in the inspection process. The problem of constrained plan optimization is exposed, and a solution is suggested that is based on task grouping. After outlining the overall planning process, we give details of the optimization stage where case-based reasoning is applied. Finally, it will be shown how the implemented knowledge-based system can operate as a knowledge server.     

Explanation-Based Learning for Diagnosis

We present explanation-based learning (EBL) methods aimed at improving the performance of diagnosis systems integrating associational and model-based components. We consider multiple-fault model-based diagnosis (MBD) systems and describe two learning architectures. One, EBLIA, is a method for learning in advance. The other, EBL(p), is a method for learning while doing. EBLIA precompiles models into associations and relies only on the associations during diagnosis. EBL(p) performs compilation during diagnosis whenever reliance on previously learned associational rules results in unsatisfactory performance—as defined by a given performance threshold p. We present results of empirical studies comparing MBD without learning versus EBLIA and EBL(p). The main conclusions are as follows. EBLIA is superior when it is feasible, but it is not feasible for large devices. EBL(p) can speed-up MBD and scale-up to larger devices in situations where perfect accuracy is not required.     

Indexing,Elaboration and Refinement: Incremental Learning of Explanatory Cases

This article describes how a reasoner can improve its understanding of an incompletely understood domain through the application of what it already knows to novel problems in that domain. Case-based reasoning is the process of using past experiences stored in the reasoner's memory to understand novel situations or solve novel problems. However, this process assumes that past experiences are well understood and provide good lessons to be used for future situations. This assumption is usually false when one is learning about a novel domain, since situations encountered previously in this domain might not have been understood completely. Furthermore, the reasoner may not even have a case that adequately deals with the new situation, or may not be able to access the case using existing indices. We present a theory of incremental learning based on the revision of previously existing case knowledge in response to experiences in such situations. The theory has been implemented in a case-based story understanding program that can (a) learn a new case in situations where no case already exists, (b) learn how to index the case in memory, and (c) incrementally refine its understanding of the case by using it to reason about new situations, thus evolving a better understanding of its domain through experience. This research complements work in case-based reasoning by providing mechanisms by which a case library can be automatically built for use by a case-based reasoning program.     

CaBMA: a case-based reasoning system for capturing,refining, and reusing project plans

In this paper, we present CaBMA, a prototype of a knowledge-based system designed to assist with project planning tasks using case-based reasoning. CaBMA introduces a novel approach to project planning in that, for the first time, a knowledge layer is added on top of traditional project management software. Project management software provides editing and bookkeeping capabilities. CaBMA enhances these capabilities by automatically capturing project plans in the form of cases, refining these cases over time to avoid potential inconsistency between them, reusing these cases to generate plans for new projects, and indicating possible repairs for project plans when they derive away from existing knowledge. We will give an overview of the system, provide a detailed explanation on each component, and present an empirical study based on synthetic data.     

A Survey on Case-Based Planning

Case-based planning is the reuse of past successful plansin order to solve new planning problems.This paper presents a survey of case-based planning, in terms ofits historical roots, underlying foundations, methods andtechniques currently used, limitations, and future trends.Several authors have given overviews on case-based reasoningand specific topics such as case retrieval, case adaptation,and learning. This overview differs in focus.Its aim is to emphasize the case-based approach to planning,its methodological issues, and its relation to classical planningand the other kinds of case-based reasoning.It also provides some reference models.     

On the complexity of case-based planning

This paper analyses the computational complexity of problems related to case-based planning: planning when a plan for a similar instance is known, and planning from a library of plans. It is proven that planning from a single case has the same complexity than generative planning (i.e. planning ‘from scratch’); using an extended definition of cases, complexity is reduced if the domain stored in the case is similar to the one to search plans for. Planning from a library of cases is shown to have the same complexity. In both cases, the complexity of planning remains, in the worst case, PSPACE-complete.     

Marr's three levels: A re-evaluation

Marr's account of the analysis of complex information-processing tasks as having three levels — the levels of computational theory, representation and algorithm, and hardware implementation — is reconsidered. I argue that the notion of level here runs together two distinctive sort of explanatory shifts — that of grain and that of contextual function. I then offer a revision of the account which avoids this problem, and suggest how this might play a role in the practice of theory evaluation.     

A hierarchical approach for the redesign of chemical processes

An approach to improve the management of complexity during the redesign of technical processes is proposed. The approach consists of two abstract steps. In the first step, model-based reasoning is used to generate automatically alternative representations of an existing process at several levels of abstraction. In the second step, process alternatives are generated through the application of case-based reasoning. The key point of our framework is the modeling approach, which is an extension of the Multimodeling and Multilevel Flow Modeling methodologies. These, together with a systematic design methodology, are used to represent a process hierarchically, thus improving the identification of analogous equipment/sections from different processes. The hierarchical representation results in sets of equipment/sections organized according to their functions and intentions. A case-based reasoning system then retrieves from a library of cases similar equipment/sections to the one selected by the user. The final output is a set of equipment/sections ordered according to their similarity. Human intervention is necessary to adapt the most promising case within the original process.     

A blackboard model of reasoning in product liability claims evaluation

The SKADE 2 is a blackboard system that evaluates product liability claims and makes settlement decisions. The system has three knowledge sources, namely, Legal, Insurance Adjuster, and Manager. The combined expertise from each of these is required to analyze a product liability claim. A control component coordinates the communication between the various knowledge sources on the blackboard. Based on the latest changes to the data or in the hypotheses, it selects and executes the next knowledge source. The model described here reproduces the domain's decision makers' reasoning processes.The results of validation and analysis of a hypothetical case through a series of experiments with the system confirm that the blackboard is an appropriate model for development of expert systems in the product liability domain. The initial success with the SKADE 2 system suggests that further work needs to be done to see whether more complex models can be built to incorporate a broader range of determinants of product liability claims evaluation.     

A Note on the Rational Closure of Knowledge Bases with Both Positive and Negative Knowledge

The notion of the rational closure of a positive knowledge base K of conditional assertions | (standing for if then normally ) was first introduced by Lehmann (1989) and developed by Lehmann and Magidor (1992). Following those authors we would also argue that the rational closure is, in a strong sense, the minimal information, or simplest, rational consequence relation satisfying K. In practice, however, one might expect a knowledge base to consist not just of positive conditional assertions, | , but also negative conditional assertions, _i (standing for not if then normally . Restricting ourselves to a finite language we show that the rational closure still exists for satisfiable knowledge bases containing both positive and negative conditional assertions and has similar properties to those exhibited in Lehmann and Magidor (1992). In particular an algorithm in Lehmann and Magidor (1992) which constructs the rational closure can be adapted to this case and yields, in turn, completeness theorems for the conditional assertions entailed by such a mixed knowledge base.     

Integrating Computer Algebra into Proof Planning

Mechanized reasoning systems and computer algebra systems have different objectives. Their integration is highly desirable, since formal proofs often involve both of the two different tasks proving and calculating. Even more important, proof and computation are often interwoven and not easily separable.In this article we advocate an integration of computer algebra into mechanized reasoning systems at the proof plan level. This approach allows us to view the computer algebra algorithms as methods, that is, declarative representations of the problem-solving knowledge specific to a certain mathematical domain. Automation can be achieved in many cases by searching for a hierarchic proof plan at the method level by using suitable domain-specific control knowledge about the mathematical algorithms. In other words, the uniform framework of proof planning allows us to solve a large class of problems that are not automatically solvable by separate systems.Our approach also gives an answer to the correctness problems inherent in such an integration. We advocate an approach where the computer algebra system produces high-level protocol information that can be processed by an interface to derive proof plans. Such a proof plan in turn can be expanded to proofs at different levels of abstraction, so the approach is well suited for producing a high-level verbalized explication as well as for a low-level, machine-checkable, calculus-level proof.We present an implementation of our ideas and exemplify them using an automatically solved example.Changes in the criterion of rigor of the proof' engender major revolutions in mathematics. H. Poincaré, 1905