US 4,943,932 AGrant
Architecture for Composing Computational Modules Uniformly Across Diverse Developmental Frameworks
Issue Date:1990-07-24
•84 Claims
•21 Drawing Sheets
Abstract
A Multi-Level Architecture for developing intelligent computer systems composes computational modules uniformly across diverse developmental framework. The modules interact via message passing and are assembled to form application-specific systems. A first level of the Multi-Level Architecture includes a cooperative operating system which provides support for message passing and resource allocation and is preferably based on a module-oriented programming (MOP) model. The first level, for example, defines a virtual machine which is mapped onto an underlying hardware and operating system environment. A second level of the Multi-Level Architecture supports a plurality of application-independent problem-solving frameworks (PSF's) or programming environments for building modules and combining modules of different frameworks into complex systems. A third level of Multi-Level Architecture includes a plurality of knowledge processing modules ranging from specialized modules to skeletal systems which provide nearly complete solutions to application problems. For building an application-specific system, domain-specific knowledge is added on top of the third level and typically a selected skeletal system is customized. Extension or refinement of the application-specific system is accomplished by replacing existing modules with more complex modules or by using additional modules. The Multi-Level Architecture is particularly useful for building a plan monitoring and replanning system which monitors whether an initially valid design remains valid prior to its implementation, incrementally modifies the design to insure validity despite changing conditions, applies control knowledge to control sequencing among the monitoring and replanning functions, and also applies knowledge to explain the nature of design failures.
Metadata
Assignee
- Cimflex Teknowledge Corporation
Inventors
- Jay S. Lark
- Lee D. Erman
- Michael Fehling
- Frederick Hayes-Roth
Application Information
Application Number:US 0388726
Filing Date:1987-04-15
Priority Date:1986-11-25
Art Unit:236
Classifications
IPC:
G06F 1520G06F 1518
Field of Search:
364382513;300;200 MS File;900 MS File14;15
Patent Drawings (21 sheets)
Description
Field of the Invention
The present invention generally relates to artificial intelligence and knowledge engineering. More particularly, this invention relates to programming environments or frameworks which provide support for construction of computer systems and which provide general purpose techniques for building system modules and assembling modules into composite modules or systems.
Background of the Invention
Computer systems are collections of computer program parts, called modules, that employ physical and computational resources to convert inputs into desired outputs. Current technology provides several levels of support for system construction. For example, programming languages such as FORTRAN or COBOL allow a programmer to define the behavior of a single module, which is a part of a computer program that employs physical and computational resources to convert inputs into desired outputs. Existing operating systems provide facilities for allocating resources and directing inputs and outputs. In combination with languages and operating systems, programming environments allow the programmer to specify how individual modules should be combined to build the entire system. In systems supporting multiple languages for program specification, the programs are combined into modules by use of linkloaders with programs inside a module communicating either by sharing data (example Common in FORTRAN) or by subroutine calls (including subroutines such as Functions that return data to the caller). Such subroutine calls establish a master-slave relationship by virtue of which the calling program gives control to the called subroutine and also passes it data in the form of arguments that bind to formal parameters in the subroutine definition; termination of the caller terminates the called subroutine.
Programming environments provided with current operating systems permit only a limited number of ways for building modules and assembling modules into bigger modules or systems. Each of such existing environments or "frameworks" provides a restricted syntax for describing the ways to combine parts and transfer a component's output to another component as input. Although these frameworks embody a language for describing the desired componential structure and overall behavior of the system and provide an implementation mechanism that combines the behaviors of the components in a manner that yields the specified desired behavior of the new modules, certain disadvantages are inherent to them. For instance, in system development, different languages embody different problem-solving approaches and, as a result, are best suited to solving different kinds of problems. Consequently, system designers prefer one kind of language for mathematical problem-solving (e.g., FORTRAN), another for commercial problem-solving (e.g., COBOL), another for AI programming (e.g., LISP), another for graphics (e.g., SMALLTALK), another for conventional data flow programming (e.g., some type of data flow language), and yet another for cooperative expert systems (e.g., a blackboard language). It hence becomes desirable, when an overall system embodies subproblems of different kinds, to use distinctly appropriate languages for each subproblem. This objective cannot be achieved with conventional systems because such diverse languages (e.g., SMALLTALK and DATAFLOW) produce modules that are incapable of being composed and integrated.
Although conventional operating systems such as UNIX and the IBM System/370 do provide some means for composing and integrating modules into larger or composite modules by sequencing of individual modules, i.e., by ensuring that data produced during the execution of the module is made available to subsequently executing modules, a significant disadvantage is that modules developed for use in one system (such as UNIX) generally cannot be assembled with modules in a different system (such as the IBM System/370). The resulting modules are dependent upon the framework in which they are assembled and consequently cannot be combined in different frameworks. Current technology is incapable of developing a module to provide a specified functionality unless the functionality is specified in terms of the framework in which the module is to be used.
Similarly, existing techniques for passing data between modules in one framework do not apply to modules connected in another framework. For example, there is no way to connect to the program steps in the IBM System/370 framework with the pipe construct of UNIX, nor is there a way to make a program that reads file records process another module's output files byte-by-byte.
In addition, if a system designer aims to assemble modules into a system with a more complex network of inputs and outputs and to employ a specific control regimen to govern the exact sequence of activities within the network of interacting modules, he is forced to resort to explicit low level programming instructions; current programming environments, including existing shells and high level languages, provide no support for such goals.
Another limitation of existing programming technology is that programming frameworks which are applicable to object-oriented or message-passing systems, in spite of providing a self-contained mechanism for implementing message-passing between objects, are incapable of allowing object sets to be composed into a module or the combination of modules with other modules in different programming frameworks in order to build heterogenous systems. For instance, it is not possible to incorporate into a SMALLTALK program a pre-existing computer program that is not a collection of SMALLTALK objects. Moreover, existing programming languages such as SMALLTALK do not provide general purpose techniques for expressing the connections among modules that are necessary to specify the system design. This constitutes a major deficiency in the building of complex systems where the structure and connection topology can make the difference between practical and excessive amounts of message-passing communication.
Accordingly, in order to efficiently build complex systems, there is a need for a flexible computing architecture for developing applications by the assembly of collections of modules into systems of parts that interact via message-passing, where the functionality of each module is independent of its implementation, and each module can be composed of an assembly of modules in a recursive fashion.
Computer systems are being called upon to perform increasingly complex planning and design tasks. In many applications the design process is so complex that a valid plan or design is obtained only after considerable human effort and machine time, and it is nearly impossible to provide a plan or design that can handle all anticipated situations of interest. Consequently, it has been necessary to provide a new plan or design when the overall situation has changed so far as to render the original design potentially invalid as a result of certain underlying or critical assumptions of the plan becomming no longer true.
Accordingly, to enhance the reliability of designs or plans and to facilitate the provision of a new design or plan to reflect changing conditions, there is a need for a novel computer system for testing designs or plans and modifying plans or designs so that a valid design or plan will be available at the time of implementing the plan or design.
Objects of the Invention
It is a primary object of this invention to provide a flexible computing architecture which supports module-oriented programming for developing complex systems composed of application-independent, interacting, composite modules implemented in diverse frameworks.
It is an important object of this invention to provide knowledge processing methodology which permits complex systems to be composed out of interacting component subsystems.
A related object of this invention is to provide such a methodology which provides knowledge processing capabilities that can be used effectively in a large variety of applications and which permits integration by virtue of an underlying architecture that can support a variety of system structures.
It is a specific object of this invention to provide software engineering tools (SET's) which permit integration of diverse component technologies and support large scale application system development by providing capabilities which support reuse of previously structured components.
A more specific object of this invention is to provide SET's which support alternative implementations of various software engineering functionalities as modules, and provide means for configuring software systems and software system tools out of these modules.
A related object is to provide such new tools which are based on a plurality of preprogrammed functional modules and which provide an effective technique for configuring the modules into large systems.
Another object of this invention is to provide SET's of the above type which, in addition to low level capabilities, provide high level generic solutions to diverse classes of problems.
Another related object of this invention is to provide SET's which, in addition to providing the above capabilities, allow the accumulation and incorporation of new and existing functional modules, both intelligent and conventional.
Still another object of the invention is to provide a more efficient and effective computing system for insuring that a plan or design is valid at the time of its implementation despite changing conditions.
Moreover, another object of the invention is to provide a plan monitoring and replanning facility in which the operation and sequencing of monitoring and replanning functions are explicit and flexible so as to be readily adapted to a variety of application domains.
These and other objects of this invention are achieved, according to the system of this invention, by providing a software engineering tool in the form of an architecture and methodology for building software systems by integrating heterogenous components, including both conventional and knowledge processing components. The tool includes a modular and expandable collection of knowledge and software engineering capabilities including skeletal system structures. A useful initial set of proven, valuable functional capabilities is provided and various levels of the architecture are accessible for modification and augmentation by making the various facilities, and their implementations, easily understandable. Accordingly, this invention provides a multilevel architecture for developing software systems (hereinafter referred to as "the Multilevel Architecture") which can compose computational modules uniformly across diverse developmental frameworks and supports aggregations of cooperating, autonomous, problem-solving components.
At the first level of the Multilevel Architecture, there lies a cooperative operating system which provides support for message-passing and resource allocation. This level is based on a general mode of computation called module-oriented programming (MOP) which is organized around communicating modules. This computational model provides the foundation and building blocks for the higher levels of the architecture for expressing designs of complex systems as interacting networks of problem-solving agents. The computational model also defines a virtual machine which can be mapped onto underlying hardware and operating system environments.
At its second level, the Multilevel Architecture supports various problem-solving frameworks (PSF's) which essentially are programming environments for building modules and module-based systems. The Multilevel Architecture provides for the combination of frameworks in order to construct systems for complex applications.
At its third level, the Multilevel Architecture contains functional processing modules ranging from specialized knowledge processing functions to modules which provide nearly complete solutions, known as "skeletal systems", to application problems.
At the highest level of the Multilevel Architecture, construction of systems for specific applications is conveniently accomplished by selecting a skeletal system and customizing it with domain-specific knowledge. Extension or refinement of such systems is made possible by using additional modules.
The Multilevel Architecture is useful in constructing a complex system by building up layers of capabilities in such a way that each layer draws on the capabilities made available by the layer beneath it and presents a new set to the layer above it. For instance, the MOP serves as a base architecture for building problem-solving frameworks, whereas the problem-solving frameworks form an architecture for building particular functional capabilities. New capabilities are developed by modifying, restricting or reconfiguring the capabilities from the next lower level. In effect, the Multilevel Architecture provides one or more frameworks in response to which a software engineering tool builder can supply corresponding functional processing modules, which might include capabilities such as a rule-interpreter and facilities for tasks such as maintaining knowledge bases and producing explanations of system behavior.
The Multilevel Architecture is configured to permit the creation of a skeletal system by adding structure to and control over a set of processing modules and their interactions with other facilities such as databases. Subsequently, the newly created skeletal system may be customized for a particular application domain by replacing some of the generic constructs with more appropriate terms. At its final level, the Multilevel Architecture provides a domain expert with the capacity to add to this skeletal system knowledge of specific objects and relationships to create a domain-specific application system. The particular choice of levels for the Multilevel Architecture is made in such a way that it supports the goals of building intelligent systems by selecting, customizing and combining modules from growing libraries.
The Multi-Level Architecture is particularly useful for building a plan monitoring and replanning system which monitors whether an initially valid design remains valid prior to its implementation, incrementally modifies the design to insure validity despite changing conditions, applies control knowledge to control sequencing among the monitoring and replanning functions, and also applies knowledge to explain the nature of design failures. A preferred plan monitoring and replanning system has several modular functions, including a plan assumption analyst to determine the "critical assumptions" or requirements of the plan that the plan's own actions do not accomplish, a situation monitor to poll a situation data base periodically to test whether the plan's critical assumptions are true, a situation data base to keep a model about the natural world expressed in terms of first-order predicate calculus, a plan failure explainer to express in a natural language an explanation of a failed plan, an incremental replanner to modify an original plan as needed by finding alternative values for decision parameters that allow the plan to be verified with minimal perturbation, and a plan change analyst to describe differences between an original plan and a modified plan.
Brief Description of the Drawings
Other objects and advantages of the present invention will become apparent upon reading the following detailed description and upon reference to the drawings, in which:
FIG. 1 is an illustration depicting the basic structure of the Multilevel Architecture of this invention;
FIG. 2 is a schematic diagram illustrating the organization of a typical module based on the cooperative operating system of the Multilevel Architecture of FIG. 1;
FIG. 3 is an illustration depicting the operation of a framework in the development of modules, according to the system of this invention;
FIG. 4 is a block diagram type representation of a composite module assembled by using a particular framework, according to a preferred embodiment of this invention;
FIG. 5 is a block diagram type illustration of a composite module assembled according to an alternative embodiment of this invention;
FIG. 6 is a flowchart representation of the sequence of operations undergone by a data-flow (DF) interpreter in executing a module;
FIG. 7 is a modular illustration of a plan monitoring and replanning (PMR) skeletal system for use with the illustrated Multilevel Architecture;
FIG. 8 is a flowchart representation of the sequence of operations undergone by a procedural module control (PMC) interpreter in executing a module;
FIG. 9 is an illustration of a catalog or menu of components provided at various levels of the Multilevel Architecture of FIG. 1; and
FIGS. 10 to 22 are successive screen displays during a trace of one cycle of a "PMR Travel Planner" incorporating the present invention.
While the invention will be described in connection with certain preferred embodiments, it will be understood that it is not intended to limit the invention to these particular embodiments. On the contrary, it is intended to cover all modifications, alternatives and equivalent arrangements as may be included within the spirit and scope of this invention as defined by the appended claims.
Description of the Preferred Embodiments
Referring now to FIG. 1, a multi-layer structure of applications 10 incorporating the present invention is shown to be based upon a Multilevel Architecture system 12 which itself rests on many supporting technologies 14, such as conventional computer hardware and networks. The Multilevel Architecture system 12 essentially comprises three discrete levels. The first level of the system 12 is a cooperative operating system, which includes a general purpose, open organization based computational model. The open organization provides flexibility in the construction of frameworks and the computational model provides a firm semantic basis for understanding the computational properties of the various systems built on the basis of the Multilevel Architecture. According to the preferred embodiment, the open organization is based on communicating modules, and the computational model is consequently called module-oriented programming (MOP). Level I of the Multilevel Architecture system 12 essentially functions to provide support for message-passing and resource allocation.
At level II of the Multilevel Architecture, a plurality of problem-solving frameworks are provided, each of which is a programming environment for building modules and module-based systems. The Multilevel Architecture system permits complex applications to be conveniently built by allowing the composition and combination of frameworks aimed at solving specific application-related problems.
The third level of the Multilevel Architecture supports a plurality of functional processing modules (IIIa) whose complexity ranges from relatively simple specialized knowledge processing functions to complex modules known as "skeletal systems" (IIIb) which provide nearly complete solutions to specific application problems.
At the highest level, a computer system for a specific application is constructed by selecting a desired skeletal system solution from level IIIb and customizing it with domain-specific knowledge. At this level, extension or refinement of the application may also be accomplished by the use of additional preprogrammed software modules.
A more detailed description of the various levels that define the Multilevel Architecture of this invention now follows. Level I of the Multilevel Architecture system 12 is defined by a virtual machine which functions as a cooperative operating system by providing services analogous to those provided by standard operating systems and including module and network creations, communication primitives, computational resource modeling and primitive resource allocation schemes. The virtual machine specifies the primitive operations and how a user may compose and configure those operations into higher level computations. According to a feature of this invention, the virtual machine is defined by a computational model based upon module-oriented programming (MOP) which is distinguished from and is an extension of the model of computation embraced in conventional object-oriented programming systems such as SMALLTALK and ACTORS. In conventional object-oriented systems, computation proceeds by a set of independent objects responding to messages sent explicitly to them by other objects. Under the MOP computational model of this invention, the concept of explicit message-passing invocation of an agent is optionally augmented with the notion of pattern-directed communication. In addition, MOP requires that any agent provide an explicit scheme for the control and distribution of processing resources to components of that module. The virtual machine at level I of the Multilevel system, as embodied by the MOP computational model, is preferably supported by a cooperative operating system which, in addition to providing conventional operating system functions, allows the Multilevel Architecture system to be implemented on arbitrary physical computing environments.
The MOP computational model of the Multilevel Architecture system uses pattern directed communication as the basic computational mechanism by replacing the construct of conventional object-oriented programming system messages with the more general construct of a broadcast message, a message being defined as an arbitrary datum in a medium, called a network, to which a module connects or has access. In MOP, a module responds to the occurrence of specific messages in the network with internally defined activities and the module may or may not react by producing response messages on the network. The set of external messages to which a module reacts as a whole is defined internally by the module. More specifically, if a module A is exposed to some message produced by another module, then module A will autonomously determine whether it will respond to this message. All modules in a given group interact by creating and responding to messages in a shared network which forms the communications medium for patterns that can potentially invoke some response from one or more modules having access to that network. Each module in the MOP model is an integral entity for performing one or more system functions. Thus, looking at an external view of a module, it represents a component in a larger module' s network, while the internal view of a non-primitive module depicts it as a group of component modules that interact with each other only via the local network of that module. The activities of a module as a whole are determined by the interaction of the component modules which comprise the larger composite module. This kind of recursive module definition progresses until all component modules are reduced to indivisible, primitive modules. Distinction between external and internal messages to and from modules is provided by control means which manage the transmission of messages between an external network and the module's own internal network.
The above description of the MOP computational module is further clarified with reference to FIG. 2 which shows the schematic of a typical module organization under the preferred MOP operating system. As shown, a standard module 20 essentially comprises an internal network 22 to which a plurality of component modules 24 are connected through their respective ports. The ports are designated to be either input ports or output ports and contain means, such as an interest filter, capable of tracking messages on the external network which are defined to be of interest to the module. Each module is provided with a local controller (LC) 26 which, among other functions, monitors external messages, i.e., any messages on any network to which a particular module connects. The LC 26 monitors messages of types declared to be of interest by the interest filter for any of its internal composite modules, and copies such external messages onto the internal network 22. The LC 26 also functions to monitor the internal network for specific types of messages and forwards such messages to an external network. According to the MOP computational model, a module can connect to more than one network so that the Multilevel Architecture is not limited to strict hierarchical organization. The above module organization ensures that computation, according to the module-oriented model, proceeds according to a basic message-response cycle which serves as a basic model upon which other functional/computational models, such as conventional functional or object-oriented programming, may be built.
According to another feature of this invention, a module is defined to model explicitly the management by the module of a given set of processor resources (processors, memory, cycles, etc.) in order to accomplish pending module actions. This provides the MOP model of this invention with the ability to represent computational systems with multiple lines of control and multiple processors. This removes the disadvantages that most conventional object-oriented systems possess by virtue of a computational module defined on the basis of either a single processor and a single thread of control (e.g., SMALLTALK) or on the basis of complete concurrency and full parallelism (e.g., ACTORS). In the illustrative MOP model, knowledge about a module's own activity, i.e., the complete control structure of the module, can be represented explicitly in terms of processor management. Thus, every module contains an LC responsible for managing the message response capabilities of the module as a whole. In addition, an LC manages processor resource distribution by dynamically distributing processors to the components of the module including the LC itself in order to carry out module activity. The LC is the only component of the module that has the authority to manage the various processors on behalf of the aggregation of module components; centralized control of module activity is achieved by the LC by deciding when to allocate processing resources to a module component that needs them. The MOP computational model is also permissive of more distributed models of control also. More specifically, since each component of the module is also a module, one or more such components may have their own, privately held processors; such a module is said to possess its own "local" processor resources and can carry out computations without intervention by the LC of an enclosing module. It is thus possible to extend the MOP model to such an extent that it defines a fully-distributed module in which every component has at least one processor.
Focusing now upon the preferred MOP operating system, it is designed to directly support the description and creation of modules, connection of modules to networks, communication of messages between modules via networks and transfer of processing resources among modules. Many of these services correspond to those provided by conventional operating systems, such as process creation and management and inter-process communication. The preferred MOP operating system is a multi-layered operating system which includes a run-time kernel for providing services such as module and network creation and inter-module communication; structural and behavioral description languages for allowing a user to describe a module in a language the run-time kernel can understand; a set of implementation languages in which the user may program primitive modules; and a set of primitive modules which is based upon the supported implementation languages and is available for incorporation within systems.
The run-time kernel in the preferred MOP operating system provides two distinct kinds of services:
(1) creation of modules and networks, a service class which includes, for example, creation of a new module from a class description of that module, creation of a new network, connection of a module to a network, and bookkeeping; and
(2) inter-module communication, including creation of a new message, transmission of a message to a set of recipients, and queuing incoming messages at a module. The run-time kernel provides a system-call interface to access these services. The modules generally do not directly invoke these services; instead the description languages provide the interface to the kernel services. According to the MOP computational model, the complete definition of a given module includes information pertaining to the behavioral and structural description of the module. Information representing the structural description of a module can include the initial set of modules on a network, the initial network topology, a specification of module sharing (i.e., non-hierarchical connections), the set of modules which may connect to a network at any point in time, and specification of whether the composition of a network is fixed or changeable. Information contained in a behavioral description of a module may include the set of input message types which the module is programmed to accept, the set of output message types that the module generates, the functions which the module computes and message protocols for invoking that function, high-level protocols the module understands and the type of local controller specified for the module.
The preferred MOP operating system provides compilers for translation of the module descriptions into run-time calls to the system kernel. The description of a module allows the module to be linked into the system after it has been coded in any supported implementation language, such as LISP or PROLOG. It will be noted that, although the preferred MOP operating system and the local controllers regulating the operation of the composite modules perform similar functions, they are distinguished by the fact that the preferred MOP operating system provides a particular set of services for dealing with modules, whereas a local controller is a program that uses those services to manage a particular set of modules. The preferred MOP operating system thus provides a language and means for building local controllers.
A program listing, written in LISP, for the preferred MOP operating system is represented in Appendix I.
Focusing now on the second level of the Multilevel Architecture, level II consists of problem-solving frameworks (PSF) which are also referred to as problem-solving architectures and are analogous to conventional programming languages. Each of these frameworks is basically a system for developing modules and constitutes a language that embodies an organizing principle that enables specification of which components are to be combined and how the components are to be combined to solve a particular problem and also provides means for implementing the desired effect in a manner consistent with the specification.
A problem-solving framework represents a collection of design choices including control and resource allocation regimens, communication protocols, shared languages, and computational organizing principles. Within the Multilevel Architecture system, these design choices manifest themselves within the local controller (LC) of a module, since the LC is defined to handle these responsibilities. According to the illustrative architecture, a plurality of different frameworks are provided. Two primary problem-solving frameworks, a data flow framework and a control flow framework based respectively on the concepts of standard data flow languages and structured flowcharts, designed specifically for use with the illustrative Multilevel Architecture will be described in detail below. It will be noted that the frameworks in the illustrated system present a view of the system quite different from that underlying the preferred MOP operating system in which modules are linked to specific networks. For instance, a framework may designate certain modules as having some special significance to the global operation of the system or the framework may provide its own visual representation which totally masks the underlying virtual machine.
Referring now to FIG. 3, there is shown an illustration of the basic components of a typical framework 50 for developing modules in accordance with the system of this invention. An essential component of every framework is a module production process 52 which is capable of incorporating necessary pre-existing modules 53 and converting a module description, written in some source language, into a module 54 which is an executable specification in some object language or an executable physical form. In addition, the framework may perform optional functions that aid the module development process. For example, a framework may include a module description process 56 which responds to specifications of desired module characteristics 58 and translates these into a module description 60 suitable for input to the module production process 52 or to a module editor 62.
The module editor 62 is capable of accepting either a specification of the desired module characteristics 58 or desired changes 64 in an existing module in addition to the particular module's existing description and subsequently translating these into a corresponding updated module description. The module editor may be capable of visualizing the module or producing a module portrayal 66. A framework may also be provided with a module analysis system 68 which is capable of accepting a particular module description 60 and/or a particular module 54 in order to produce as an output data of interest, such as execution traces of data values and communications or measures of resource consumption and performance. It is apparent from the above description that, in its basic form, a problem-solving framework functions to accept as inputs desired module characteristics and catalog of modules or descriptions in order to produce corresponding outputs such as the modules themselves or their module descriptions.
Referring now to FIG. 4, there is shown the organization of a typical composite module assembled using a particular framework. As shown, a composite module 100 essentially comprises a series of component modules 102, each possessing a plurality of input/output ports 103. Each of these component modules 102 is referenced in the module description provided by the framework being used (see FIG. 3). Each composite module is provided with an internal inter-module communications system ("Innernet") 104 which functions as a system for transmitting data between a module controller, such as the local controller described above with respect to FIG. 2, and the various modules included within the composite module. The Innernet 104 is capable of accepting as input data to be transmitted and producing a resultant output which causes the specified data to be delivered to the modules which specify an interest in the data. This functionality of the Innernet is provided by the preferred MOP operating system of this invention.
Any particular computer program is preferably realized by putting most of the logic into a module controller 106 which, in combination with an associated module memory 108, implements the program control function of the module and uses the Innernet to pass data between submodules and the program inside the controller. The module controller 106 may be an interpreter of a stored program represented as data inside the module memory or may directly implement a program. It will be apparent that part of the control over message passing between the controller and the various submodules may be implemented by the Innernet itself. The module memory 108 essentially comprises a storage section for the module data 110 and an associated input/output buffer 112 for accepting and transferring the module data through an external communication interface system 114, which includes a plurality of ports 116 functioning as connectors for external inputs and outputs. It should be noted that in the embodiment of FIG. 4, the composite module is organized in such a way that all the submodules which it references lie physically inside the composite module and the Innernet which connects the various submodules and the module controller also lies inside the composite module.
Referring now to FIG. 5, there is shown an alternative embodiment of a composite module in which the module is organized in such a way that the plurality of modules 102, which are referenced within the module description, lie physically outside the composite module. In this embodiment, communication between the submodules themselves and with the module controller is brought by the Innernet 104 which itself extends outside the composite module to the submodules. The operation of the composite module and the functionality of its various components, however, remains the same.
The third level of the Multilevel Architecture incorporates software engineering tools and spans a range with knowledge processing and other functional capabilities at the lower end and skeletal systems at the higher end. Using one or more frameworks provided at level II of the Multilevel Architecture, a tool builder can specify knowledge processing modules which include capabilities such as a rule interpreter, facilities for maintaining knowledge bases, running cases, creating English-like translations of rules and other constructs, and producing explanations of system behavior. The illustrated Multilevel Architecture provides a means for organizing and controlling knowledge in other facilities towards solving a class of problems by the creation of skeletal systems which are particular sets of modules defined within particular frameworks. At the engineering tools level of the Multilevel Architecture, a skeletal system can be created by adding structure to and control over the predefined functional processing modules and their interactions with other system facilities, such as databases. The modules defined within a particular framework and for a given skeletal system are provided with mechanisms for customization with application-specific knowledge. Some of these modules may serve as place holders, which can be conveniently replaced by totally new, but functionally equivalent, application-specific modules.
In essence, a skeletal system is a partially substantiated assembly of modules for solving a class of application problems. This feature provides the Multilevel Architecture with significant advantages over conventional software engineering methodologies, which typically construct a system by starting from a programming language and building up higher-level abstractions appropriate to a particular class of application problems. For instance, the explicit identification and design of generic, skeletal systems as provided by the Multilevel Architecture provides increased modularity of systems, increased reusability of solutions or parts of solutions, easier knowledge acquisition, and easier maintenance of the application.
A specific skeletal system known as the Plan Monitoring and Replanning (PMR) skeletal system implemented for use with the Multilevel Architecture will now be described in detail in order to illustrate the various concepts involved in the Multilevel Architecture as described above. The PMR is a generic structure for adaptive replanning which addresses the specific problem of keeping track of assumptions underlying some plan so that, as situations evolve, a pending plan can be modified appropriately. Although the PMR will be described below in connection with monitoring a design for actions to achieve certain desired effects under assumed conditions, it is equally applicable for monitoring a design for a product to be manufactured to have certain desired effects under assumed conditions.
The PMR system is capable of analyzing a plan to determine its assumptions about the world, monitoring a database describing the unfolding world situation, looking for key assumptions that no longer hold, incrementally replanning around these problems, and keeping selected agents informed of important changes in the situation and the plan. As is the case with all skeletal systems designed for use with the illustrated Multilevel Architecture, the PMR skeletal system is independent of any particular application or application domain.
The PMR skeletal system will be described with respect to its design on the basis of a data flow framework ("DF" framework) which is one of the problem-solving frameworks available at level 2 of the illustrated Multilevel Architecture. The DF framework implements many of the concepts found in standard data flow languages and for more information on these concepts, the reader is referred to the article entitled, "Data Flow Program Graphs," by Davis, A. L., IEEE Computer 15(2): 26-41, February, 1982. DF is a graphical language for expressing data flow programs; a program for the DF framework consists of a number of independent processing modules which perform computations and communicate with each other and the outside world. The DF framework includes special data structuring techniques which support the use of abstract data types (ADT) as tokens passed between processing modules. A semi-deterministic scheduler is also provided for supporting the building of programs with side effects, such as communication with external environments.
DF permits graphical expression of data flow programs and a DF program consists of nodes connected by arcs. In the DF framework, a knowledge-processing module is represented as a node in a DF graph and consequently takes a set of inputs and computes a set of outputs. Another type of node in a DF graph is a "place" which accepts a single input and generates a set of outputs. The various nodes in a DF graph are linked by data connections or data links. A data link indicates the outputs and inputs of a module and connects a module to a place or a place to a module. As in conventional data flow languages, computation in a DF program proceeds by the passing of tokens between modules. Specifically, ADT instances, also known as data tokens, flow along the data links and the various processing modules accept data tokens as inputs and produce new data tokens as outputs, with all data tokens being defined to reside in corresponding place nodes.
A given module is defined to be enabled when a data token resides in each of its input places. The combination of a module and a set of data tokens that enable it are called an enablement. In the DF framework, a module may be enabled more than once simultaneously, provided that more than one token is present in every one of the module's input places. When a data token participates in an enablement, the token is said to be bound by that enablement and no data token is permitted to contribute to more than one enablement. Computation proceeds by the execution of modules, and only enabled modules are permitted to be executed.
A DF interpreter is provided for executing a module, whereupon it passes the input data tokens that enabled that module to the module as input parameters. During the course of its execution, a module is permitted to create ADT instances for any of its output places and upon completion of execution, the module returns control to the interpreter along with its output tokens. The DF interpreter subsequently time stamps the output tokens and moves them into their respective places.
The DF framework supports source modules which are modules that have no data inputs and are always enabled and are hence handled specially. When a source module completes execution, it is capable of generating new output data tokens. Source modules within the DF framework model external asynchronous occurrences, such as clock ticks or other random events. Since every token is time stamped by the DF interpreter as it is created, no two tokens can have the same time stamp and consequently it is possible to compare the age of two tokens by comparing their respective time stamps. The DF interpreter is also responsible for selecting an enabled module for execution and then executing it with appropriate input and output parameters. It then recalculates the set of enabled modules and loops.
The selection or scheduling of an enabled module for execution is an important aspect of this process and is implemented by a DF scheduler. The DF scheduler maintains two internal data structures, namely an ordered list of all enabled modules, and a circular queue of source modules. The list of enabled modules also contains the set of data tokens that enabled the module. Provision is made for a module to be listed multiply as long as a disjoint set of data tokens is available for each occurrence. The scheduler maintains a priority ordering of the enabled module queue on the basis of the age of the data tokens that enable a module. Comparison of two enablements is performed by the DF scheduler on the basis of the following procedural steps:
1. The oldest token in each of the enablements are selected for comparison. If one token is found to be older than the other, the enablement from which it is derived is assigned a higher priority. If the tokens are found to be of the same age, i.e., they are the same token, the next oldest token is compared. This procedure is continued until an age difference between compared tokens is noted.
2. If the comparison procedure is not conclusive after all tokens in a particular enablement have been compared, that enablement is assigned a higher priority.
3. If two compared modules are found to have identical enabling data token sets, a higher priority is assigned at random to one of the two modules.
The DF scheduler monitors the enablement of new modules by the creation of new tokens and places new enablements into the priority queue at the appropriate location by using the priority ordering procedure described above. In addition, the scheduler manages a circular queue of all source modules. Since the DF interpreter considers source modules as being continuously enabled, the DF scheduler must treat source modules specially in order to prevent source modules from always being assigned the highest priority on the basis of the above priority ordering rule. Any time a source module is to be selected for execution, the DF scheduler is programmed to select the first source off the queue and when the selected module finishes execution, the scheduler returns it to the end of the queue. This procedure ensures that all source modules execute in turn once before any source module is allowed to execute again.
The operation of the DF interpreter will now be described under the assumption that a particular DF graph has been initialized with some data tokens and that the DF scheduler has added all enabled modules to the priority queue. The DF interpreter then executes modules according to the procedural steps outlined in the flow diagram of FIG. 6.
As shown in FIG. 6, the initial step 200 taken by the DF interpreter is to check whether the priority queue is empty. If the answer is found to be no, i.e., the priority queue contains at least one instance of enablement, step 202 is accessed whereby the interpreter selects the first enablement from the priority queue and then removes it from the queue at step 204. At the succeeding step 206, the selected enabled module is executed and at step 208 the DF interpreter calculates any new enablements resulting from the creation of new data tokens as a result of the execution. Subsequently, the program returns to step 200 in order to proceed with the selection, removal and execution of the succeeding enablements within the priority queue until the queue is empty.
If the priority queue is found to be empty at step 200, step 210 is accessed where the DF interpreter checks to see if the source model queue is empty and, if the answer is found to be yes, the action of the interpreter comes to a halt at step 218. However, if the source module queue is found not to be empty at step 210, step 212 is accessed where the interpreter selects the first source module in the queue, executes the selected source module at step 214 and subsequently returns the executed module to the end of the source model queue at step 216. The DF interpreter returns to step 208 in order to calculate again any new enablements resulting from the creation of new data tokens as a result of execution of a source module.
When the DF scheduler selects a module for execution, control is handed over to an executor in order to execute the module. The executor has the responsibility for passing the module its correct input parameters, collecting and distributing its output parameters, and notifying the scheduler of any new enabled modules. Execution of a module hence occurs as a result of the DF scheduler calling the executor when a module enablement takes place; upon being called, the executor calls the module with all of its input data tokens. When the module returns from execution, the executor time stamps and distributes the output tokens and finally checks for newly enabled modules and notifies the scheduler of newly established enablements. When the executor distributes a time-stamped output token to a place, it actually produces several virtual tokens, one for each arc leading out of the place, with all virtual tokens pointing to the same physical token. This type of mechanism ensures that every module that has a particular place as its input can process every token coming into that place. If it is found that more than one unbound token can contribute to the enablement, the executor selects the oldest token. The executor then informs the scheduler of the new enablement.
Program listings, written in LISP, for the DF framework and its various segments are represented in Appendix II.
With the above understanding of the data flow framework, a detailed description of the PMR skeletal system, as implemented in the DF framework, and the various modules that it comprises, is now described below.
According to the illustrated Multilevel Architecture, the PMR system is a generic skeletal system for adaptive replanning and is defined to be independent of any particular application or application domain. The PMR system is capable of accepting an input plan and analyzing is to determine its key assumptions about the world, monitoring a database describing the unfolding world situation, looking for key assumptions that no longer hold, incrementally replanning around the problem, and keeping selected agents informed of important changes in the situation and the plan.
Referring now to FIG. 7, there is shown a modular representation 270 of the data flow version of the PMR skeletal system. A plan assumption analyst (PAA) 272 is provided for accepting a new system plan that has to be monitored over time and replanned adaptively, if needed. This module determines what assumptions are built into the plan so that a database representing the world or application environment for the plan may be monitored in order to determine whether a particular assumption no longer holds. More specifically, the PAA module is capable of analyzing the structure of the plan, looking for prerequisites that the plan's own actions cannot guarantee; the analyst defines such prerequisites to be critical assumptions of the plan. For example, consider the case of a plan within which an airplane first takes off and then flies from a defined origin to some distant designated location. If the flying action has as a prerequisite the fact that the plane be airborne, the PAA can ascertain that the execution of the plan in general and, in particular, the prior execution of the take-off action, will by itself satisfy that prerequisite. However, if the take-off action has as its prerequisite the fact that the plane be available and there is no action in the plan itself that produces such a result, the PAA will include the availability of the plane as a critical assumption. On a functional level, the PAA accepts a system plan and its corresponding rationale as its input and provides a set of beliefs or critical plan assumptions 274 necessary for the elements of the plan to be effective as its output.
The critical plan assumptions 274 are accepted by a database monitor (DBM) 276 which actively verifies them against a situation database 277 and monitors the database for any subsequent updates via external agents 277a in order to detect and report any violated plan assumptions 278. The database monitor 276 itself is composed of two significant submodules, a belief-to-database pattern translator (BDPT) module 276a and an internal database monitor (IDM) module 276b.
The belief-to-database translator 276a translates the assumptions upon which a system plan is based into database queries. The database provided with the database monitor 276 contains information about the current state of the world. The BDPT module accepts as input a belief, a database schema, and a target query language in order to produce an intermediate result comprising an expression translatable to database queries equivalent to the stated belief. Subsequently, the BDPT module produces as its output a set of queries in the target query language that will return true/false/degree of truth status of the belief and paired sets of forms representing the response and interpretation, respectively, that characterize each possible result.
The internal database monitor (IDM) module 276b monitors the database using the queries generated by the BDPT module. The database is updated asynchronously by other agents and sensors, and is periodically polled by the PMR system.
The DBM module 276 accepts a set of pattern-action rules as its input and generates intermediate outputs comprising a set of queries to the database. Intermediate inputs comprising the database data in response to the queries are subsequently used by the DBM to generate the actions of rules satisfied by database patterns as its ultimate outputs.
Any violated plan assumptions 278 detected by the DBM 276 are communicated to a plan failure explainer (PFE) 280 which is a module for communicating the problems in the plan to concerned agents 281 and presenting the points of interest to those agents. The medium of presentation may be via radio test, graphics or other such media, depending upon the particular information to be communicated. The PFE module accepts as its input a set of violated plan beliefs or assumptions, a target recipient list, and a selection rule set indicative of the extent of interest to be attached to particular violated plan assumptions. In response, this module causes messages to be sent to the targets containing a translation of the interesting part of the set of violated beliefs, where the translation is appropriate for the recipient and formatted for a particular device through which the messages are to be delivered.
The PFE module 280 includes a submodule called the structure filter 280a which functions to select particular parts of the set of violated plan assumptions on the basis of predefined interest patterns by implementing a general pruning of a data structure. The structure filter module accepts as inputs a data structure, a corresponding data type description and selection rules defining a particular pattern to be excluded or included in the pruning of the data structure. This module includes an internal table specifying methods for building up a new structure of the given data type by joining included elements of the given data structure. In response to its inputs, the structure filter module generates as an output a copy of the interesting portion of the initial structure.
The violated plan assumptions 278 determined by the DBM module 276 are also fed to an incremental replanner module 282 which attempts to patch the old plan in order to eliminate the assumption violations and, if successful, generates a revised plan. This module 282 applies predefined rules in order to patch each instance of plan failure in turn, until the resulting plan meets the requirements and is satisfactory for the given conditions. The incremental planner includes three submodules including a top level replanner (TLR) module 282a, a one-problem-at-a-time replanner (OPAATR) module 282b, and a plan evaluator module (PE) 282c.
The top level replanner (TLR) module 282a selects the order of plan failures which are to be patched around. This module accepts as its input a tree of violated plan assumptions or beliefs and generates as an intermediate output a selected plan failure that has to be fixed. It also generates a succession of revised plans and rationale as intermediate results prior to generating a final output comprising a patched plan and its accompanying rationale.
The one-problem-at-a-time replanner (OPAATR) module 282b functions to fix a single problem within the plan. This module accepts as its inputs a plurality of plan-patching rules capable of combining a predefined planned result with a violated assumption and other prerequisites in order to produce a modified plan; a set of beliefs; a plan and its rationale; and a designated plan failure to be fixed, as defined by the top level replanner. In response to these inputs, the one-problem-at-a-time replanner module generates an output comprising a modified plane and its rationale.
The plan evaluator (PE) module 282c determines when a particular patch plan is acceptable as a new plan. This module accepts at its input a plan; defined requirements which serve as hard constraints; defined preferences serving as soft constraints; a combining function for preferences; and an acceptability test serving as a threshold of plan "goodness." The plan evaluator module, in response to these inputs, produces outputs comprising a set of plan failures; a composite rating of plan "goodness"; and the result of the acceptability test.
The incremental replanner module 282, in response to the violated plan assumptions 278 and by staying in contact with the situation database 277, produces a new plan with its rationale 284 which can then be fed back to the plan assumption analyst 272 in order to repeat the main PMR cycle in concurrence with other related activities. The PMR skeletal system also includes a plan change analyst (PCA) 286 which accepts the new plan 284 with its rationale along with the existing old plan 288 and its rationale in order to determine what element in a given plan has changed so that these plan changes 290 may be communicated efficiently to the agents that will follow the plan. The PCA module 286 accepts as its input an old plan; a new plan; and a plan interpretation rule set and generates an output comprising a plan change description.
A plan copier (PC) module 292 is provided for making a copy of a new plan emerging as a result of the patching process. This copy serves as an old plan after another revision of an existing plan occurs. Although this copy function can be implemented implicitly within the DF framework, making the copy operation explicit and separately implementable by the PC module makes the flow of data and its control more understandable from a user's point of view. The PC module accepts a specified plan as its input and generates a copy of the input plan as an output.
A plan change implementer module 294 is provided for communicating new instructions arising as a result of the plan changes 290 to those agents whose role in the plan has changed. This module accepts as its input a plan change description; a set of dispatch rules specifying the particular action to be implemented in response to a particular type of plan change, and a set of exception rules defining the notification or particular actions to be undertaken if a given type of plan change is found to be undispatchable. In response to these inputs, the module generates as its output a series of implementation actions and a series of exception-handling actions.
The plan changes 290 determined by the PCA module 286 are also communicated to a plan change explainer (PCE) module which functions to communicate changes of interest in the plan to various agents presenting only the parts of interest to a particular agent, the medium of presentation being dependent upon the information being communicated as well as the available device (text, graphics, etc.). This module accepts as its input the plan charge description, a set of plan actions, a set of plan implementation exceptions, the set of belief changes that motivated the replanning, a selection rule set indicative of the extent of interest, and a set of target recipients. The output generated by this module 298 comprises messages to the target recipients describing parts of interest of plan changes, justifications for these plan changes, plan implementation changes, plan implementation exceptions, and the corresponding changes in assumptions leading to the plan changes.
Program listings, written in LISP, for the plan monitoring and replanning (PMR) skeletal system and its various component modules are represented in Appendix VI.
In the data flow (DF) framework implementation of the PMR skeletal system, the operation of the PMR system is specified by specifying the modules and abstract data types (ADT's) used by the PMR and their interconnections. The DF framework provides implicit control over the execution of modules by monitoring token (data) flow. As described above, when a module has at least one token for each of its inputs, it changes to an enabled state and the DF interpreter selects one enabled module for execution, and then checks to see if any new modules have been enabled. It will be noted that the ordering of module execution is entirely determined by the data connection between modules.
The DF framework thus has certain inherent limitations because of its data-triggered nature. A system architect cannot force one module to execute before another unless there is a data flow link between them. When modules have side-effects, such as communicating to users or changing the state of the external world, control over the order of side-effects is critical. For example, when the database monitor produces some violated plan assumptions, both the incremental replanner and the plan failure explainer simultaneously become enabled. The system architect has no way of asserting that the failure explainer should execute first, telling interested agents what went wrong with the plan before replanning around those failures.
According to a feature of this system, limitations of the above type are significantly reduced by an alternative implementation of the PMR skeletal system that permits the system designer to specify explicitly the control flow in a system. In such a system, a module executes when the module preceding it finishes execution. Other modules can select among different control paths, causing a branching in the control flow. Still other modules explicitly start and halt execution of the system. This alternate embodiment of the PMR system is based upon a procedural module control (PMC) framework.
Referring now to FIG. 8, there is shown a flowchart indicating the steps the PMC interpreter goes through executing a module. The initial step 300 is to select the unique module labeled START. At the next step 302 the module is executed. At the next step 304 the interpreter tests if the module has been designated a halt module, and if so, the interpreter halts 306. If the module is not a halt module at step 304, it is tested at step 308 to determine if the module is a choice module. If it is, the interpreter at the next step 310 examines the value returned by the choice module when it was executed and selects the next module for execution based on that value. That module is then executed by the interpreter at step 302. If the module tested at step 308 is not a choice module, the interpreter at step 312 selects the unique next module following the just-executed module for execution at step 302.
Program listings, written in LISP, for the PMC framework are represented in Appendix III.
Under the PMC implementation, the database monitor of the PMR has a link pointing from it to the plan failure explainer, and from the plan failure explainer to the incremental replanner. This necessarily causes the plan failure explainer to execute before the incremental replanner. The implementor of the PMR can change the order of execution of other modules as well. For example, the plan change explainer can be made to run either before or after the plan change implementor, at the discretion of the system implementor. This provides great flexibility in controlling the overall operation of the PMR system.
The PMC framework thus provides a means for adding knowledge for controlling the sequence of actions involved in solving applications related problems; an operation which is difficult and at times impossible in the DF framework. It will be noted that since the implementation of modules in the illustrated Multilevel Architecture is separated from the framework used to combine them, it becomes possible to use in the PMC framework the same modules that have been defined for and used with the DF framework. In essence, the Multilevel Architecture provides a plurality of techniques for composing modules. For instance, modules assembled in one framework can hierarchically embed modules assembled in a different framework so that systems in one framework can contain modules that themselves contain subsystems implemented in some other framework. As an extension of this technique, the framework independent composition of the modules also allows the "meshing" of modules whereby systems implemented in different frameworks can conveniently be interconnected by sharing modules.
Referring now to FIG. 9, there is shown a catalog 300 of components provided at various levels of the illustrated Multilevel Architecture and which a system developer can use to construct a system by selecting, combining and refining specific components, as well as creating and storing new components when necessary. At the lowest level 321, there is provided a variety of programming languages including COMMON, LISP, PROLOG, CORAL (an object-oriented language developed by Teknowledge, Inc. of Palo Alto, Calif.), MRS (a knowledge representation and manipulation language developed by Stanford University; for further details, see "The Complete Guide to MRS", Rothschild, S., Technical Report KSL-85-12, Stanford University, 1985), and S.1 (a higher-level knowledge engineering shell which is a commercial product of Teknowledge, Inc. of Palo Alto, Calif.). The next level 322 houses the various frameworks which represent the different ways in which modules can be implemented. These include the data flow (DF) and control flow (PMC) frameworks that have been discussed above. The set of facilities for abstract data types (ADT's) may also be considered to be a framework. Another framework known as the transaction (TX) framework, which is especially applicable to the implementation of a server module (such as a database) that has one or more recipient modules, is also included.
Program listings, written in LISP, for the TX framework, and the logical formulae and plans for the ADT's are represented in Appendices IV and V, respectively.
A collection of modules of various capabilities 323 is provided above the frameworks. These include the actual ADT facilities such as modules representing a plan, action, critical assumptions and violated assumptions. Other capabilities are provided by modules representing the database monitor, the assumption analyst, the failure explainer and the change explainer.
At the highest level 324, skeletal systems 325 are provided and include the plan monitoring and replanning system (PMR), containing a situation database capability alternately implemented in two languages, MRS and PROLOG. Using the various capabilities 323, it is possible for a knowledge engineer to create different skeletal systems by adding structure to and control over the knowledge processing modules and their interactions with other facilities such as databases. The illustrated Multilevel Architecture also provides different "customizations" 326 which incorporate customizing knowledge for different domains and which can be used to build specific applications by customizing a selected skeletal system. More specifically, a knowledge engineer can customize a skeletal system for a particular application domain by replacing some of the generic constructs with more appropriate terms. For instance, an "Air Strike" (AS) customization is provided for customizing the PMR skeletal system to the application domain involving the planning of offensive air strike missions. In this application domain, the generic constructs of a particular implementation of the PMR are replaced by appropriate terms such as "flight", "target", and "ordnance" in order to yield a customized skeletal system called AS-PMR. Finally this customized skeletal system is augmented with knowledge of specific objects and relationships to create a domain-specific application system. In the case of the air strike customization of the PMR skeletal system, this domain knowledge includes such information as characteristics of particular aircraft models, targets, and ordinances. The domain-specific knowledge can also include the particular rules which govern the interaction of the defined characteristics, such as rules designating conditions under which a particular ordnance is available on a particular aircraft and the ability of the aircraft to destroy a particular target.
It will be noted that the ability to customize generic skeletal system structures allows standard components to be reapplied to applications which may differ dramatically in their specific domain characteristics, by using an appropriate customization which includes definitions for actions and states, plan structures, and example test-case plans and situations specific to the various applications. For example, the same PMR skeletal system used for the air strike application can be customized to a "Travel Planning" application by using the "Travel" customization which provides appropriate domain-specific knowledge pertinent to the handling of the trips from a traveler's home to one of a predefined set of hotels in a selected city.
The "Travel" customization demonstrates a number of the features of the PMR system and its method of implementation. The "Travel Planner" uses a PMR skeletal system including composite module definitions of the "Situation Monitor" and "MRS Replanner" in Appendix VII, core primitive module and abstract data type definitions in Appendix VIII, and definitions of underlying functions in Appendix IX. The skeletal system is customized by the addition of definitions of Travel Plan Actions and Data Inputs (including initial values for the situation data base) listed in Appendix X, along with the Plan Failure Explainer Rules of Appendix XI and the Plan Change Explainer Rules of Appendix XII.
The Travel Plan Actions of Appendix X define the general structure of the travel plan, and parameters referred to in the Travel Plan Actions take on values which further define a specific plan. The actions include "go-to-airport," take-flight," "go-to-hotel," "check-in," and "get-settled." The actions are defined as a hierarchy; for example, the action "get-settled" includes an ordered sequence of the actions "go-to-hotel" and "check-in."
In order to make a plan from an ordered sequence of actions, a function named "tp-make-plan" is also defined in Appendix II. In addition to a list of actions defined for the function, "tp-make-plan," there are defined at least one goal indicating the desired result of the plan to be made, and at least one set of choices for parameters which assume values to further specify the actions for implementing a specific plan. As shown on page 2 of Appendix X, a set of choices named "*tp-plan-1*" defines a plan for traveling from Menlo Park to Boston via flight AA-437, and a set of choices named "*tp-plan-2*" defines an alternative plan for traveling from Menlo Park to Boston via flight AA-453.
To be valid, the steps in the plan must be consistent with changing situations. In order to determine consistency, there is defined on page 3 of Appendix X a parameter named "*tp-consistency*" which, for example, indicates whether a succeeding step in a travel plan originates from the destination of an immediately preceding step in the plan. In order to determine consistency of the plan with changing conditions, there is also defined a parameter called "*tp-situation*" for monitoring the situation data base for changes in flight schedules, hotel room bookings, and ground transportation availability. Also shown on page 3 of Appendix X is a listing of the "Facts and Current States" which define the original world situation stored in the situation data base.
Shown in Appendix XI are Plan Failure Explainer Rules. The general nature of the Plan Failure Explainer is characterized by a shared rule named PRINT-INTRO which concludes that a certain plan will fail because a particular critical assumption is false which prevents a certain step or action from being properly implemented. Specific travel planning rules, shown on page 2, are provided to test for respective critical assumptions, including the assumptions that a traveler is able to go to an airport, take a flight, go to a hotel, and check in at the hotel. A general rule named GENERIC-PRINT-VPA is provided for explaining in English the pertinent criticality in the event of plan failure.
As shown in Appendix XII there is provided a Plan Change Analyst Rule named "compare-plans" which identifies changes between an original plan and a modified plan by comparing the old and new values of predefined parameters of a general plan, and explains the changes in English following the comment "Changes in Plan:."
The operation of the Travel Planner is further illustrated by the trace listing in Appendix XIII which corresponds to the output display screen listing in FIGS. 10 to 22. FIG. 10 shows the data flow version of PRM being selected for execution. Next, in FIG. 11, the Travel Planning customization of PRM is selected. In FIG. 12 the user selects the first predetermined travel plan for flight AA-437. The selected plan is then displayed as a hierarchy, as shown in FIG. 13.
As shown in FIG. 14, the user runs the Travel Planning System. The sequence of operation of the PMR modules is shown in the trace of Appendix XIII. The selected plan is fed as input to the Plan Assumption Analyst. The plan has the traveler leaving his home in Menlo Park and driving himself to San Francisco airport. The traveler should then take flight AA-437 which departs in the morning and arrives in Boston in the evening. The traveler should then take a taxi to the Ramada Inn on the east side of town.
The Plan Assumption Analyst looks at the sequence of actions which constitute the plan and determines which action prerequisites will not be met by previously executed plan actions. In the present case it finds five such prerequisites, called critical assumptions, which are:
(1) the traveler has a reservation at the Boston Ramada Inn;
(2) taxis will be available to get from the airport to the hotel's part of town in the evening;
(3) the traveler's flight is still scheduled;
(4) the traveler's car is available for use on the morning of the flight; and
(5) the traveler is located in Menlo Park that morning.
As shown in FIG. 14, the Situation Monitor receives these critical assumptions and periodically polls the Situation Database to verify the status of any which might change. In the present example, as shown in the Situation Change Message in FIG. 15 and the Hotel in FIG. 16, the Situation Database is informed that the traveler's reservation at the Boston Ramada Inn has been cancelled. When the Situation Monitor next polls the database, it discovers that this critical assumption has been violated, and exits after sending a report, which appears as a travel situation change message in FIG. 17.
Next, as shown in FIG. 18, the Replanner takes the violation and the original plan, and determines a minimal change which will patch around the problem. In the present example, the Replanner substitutes the Boston Sheraton for the Boston Ramada Inn. As shown in FIG. 19, the Plan Change Analyst then compares the modified plan to the original plan and determines that the only change was to the hotel, so it highlights this plan choice in its report shown on FIG. 20. In FIG. 21, the problem with the original plan is explained in English by the Plan Failure Explainer.
For monitoring of the modified plan, the Plan Assumption Analyst determines the critical assumptions of the new plan. Since the plan structure has not changed, the critical assumptions have not changed, except that the hotel has changed. As shown FIG. 22, the Situation Monitor then begins monitoring for any violations of the critical assumptions of the new plan. This completes a full cycle of operation of the Travel Planner.
In view of the above, there has been described a flexible computing architecture which supports module-oriented programming for developing complex systems composed of application-independent, interacting, composite modules implemented in diverse frameworks. A module production mechanism has been disclosed for the diverse frameworks which interprets descriptions of the functional characteristics of the module to be included in a desired application system. The functional characteristics may be specified apart from the framework in which the module is implemented. More specifically, diverse modules or module components are encapsulated in an outer shell that provides the appearance of modularity in the incorporated program functions so as to be uniformly includable in other modules, independent of which frameworks are used. Therefore, the functionality of a module is separable from the framework in which it is implemented, thereby accelerating the module production process and enhancing the capabilities for reusing and modifying modules. A mechanism for assembling collections of modules has also been described including message-passing means for intermodule communication between modules of various frameworks. Moreover, a specific modular collection of knowledge processing capabilities has been disclosed that can be used, modified, and reused effectively in a large variety of applications.
A specific application of plan monitoring and replanning has been described which illustrates the advantages of replaceable functional units and flexible control for planning functions. A specific set of planning and replanning functions has also been described for monitoring whether initially valid plans remain valid over a period of time prior to their execution, for scheduling plan monitoring activities, for incrementally modifying plans that have not already been executed, for explaining failed plans and plan changes, and testing plan feasibility by testing only the assumptions underlying the plan. Such a planning and replanning system is therefore espcially advantageous for management of designs or plans which are shelved for a while prior to execution, or which require a good deal of time and effort to modify to suit changing conditions.
Claims
What is claimed is:
1. A flexible computing system for developing application-specific computer systems, said flexible computing system comprising: module production means for generating functioning modules by interpreting preselected descriptions of the functional characteristics of modules to be included in a desired application-specific computing system, and module assembly means for generating said application-specific system by combining message passing means for intermodule communication along with the functioning modules generated by said module production means.
2. The flexible computing system as claimed in claim 1, wherein said module production means includes means for selecting module components by interpreting a preselected description of the functional characteristics of a module and means for combining the selected module components with a module controller for mediating interactions among said module components.
3. The flexible computing system as claimed in claim 2, wherein said means for combining the selected module components includes means for interconnecting said module controller and said selected module components via an intramodule communication network, and wherein said module controller includes means for controlling access to said intramodule communication network, means for controlling the execution of respective stored programs corresponding to the module components, means for storing and retrieving data local to the module, and means for mediating external communication with the module.
4. The flexible computing system as claimed in claim 1, wherein said module production means includes means for interpreting a description of the functional characteristicss of a module wherein said description is independent of the programming language framework in which the module is generated.
5. The flexible computing system as claimed in claim 4, wherein said module production means includes means for generating modules according to a selected one of a plurality of different programming language frameworks, and wherein said module assembly means includes means for combining modules of different programming language frameworks.
6. The flexible computing system as claimed in claim 5, further comprising framework editing means for editing a selected programming language framework to tailor it to the specific application.
7. The flexible computing system as claimed in claim 1, wherein said module production means includes means for generating modules according to a selected one of a plurality of different programming language frameworks, and wherein said module assembly means includes means for combining modules of different programming language frameworks.
8. The flexible computing system as claimed in claim 7, wherein a module of a first programming language framework is specified as a component of a module to be generated according to a second, different programming language framework, and wherein said module production means includes means for generating a module of the first programming language framework having embedded therein the specified modules of the second, different programming language framework.
9. The flexible computing system as claimed in claim 8, wherein said module production means includes means for selectively embedding said module of said second, different programming language framework either recursively in a new corresponding local environment or globally to provide simultaneous participation of said module of said second, different programming language framework when it is embedded in a number of different modules.
10. The flexible computing system as claimed in claim 8, wherein a plurality of modules are specified to be embedded in a module to be generated and the linking between the specified modules is described graphically, and wherein said module production means includes means for interpreting the graphical description of the linking to link the modules along correlated functions for combining of the modules with other module components and said module controller.
11. The flexible computing system as claimed in claim 8, wherein a plurality of modules are specified to be embedded in a module to be generated, and wherein said module production means includes means for interconnecting said modules for data communications using abstract data types wherein data is passed whenever one of the embedded modules produces an instance of abstract data type which conforms to a data input type requirement of another of the embedded modules, so that intermodule data communication is independent of data structure implementation.
12. The flexible computing system as claimed in claim 1, wherein said message passing means passes data according to abstract data types wherein data is passed whenever a module producing data produces an instance of an abstract data type which conforms to a data input type requirement of a recipient module, so that intermodule data communication is independent of data structure implementation.
13. The flexible computing system as claimed in claim 1, further comprising means for sequencing the execution of the modules within said application-specific system.
14. The flexible computing system as claimed in claim 1, further comprising means for assigning the modules within said application system to respective processors in a distributed processor computer for simultaneous execution of certain modules.
15. The flexible computing system as claimed in claim 1, further comprising module analysis means for identifying generated modules which fail to comply with predetermined conditions for the specific application, and module editing means for editing a module to comply with certain of said condition.
16. The flexible computing system as claimed in claim 15, wherein said module analysis means includes means for generating an explanation of the failure of a module to comply with said conditions.
17. The flexible computing system as claimed in claim 1, further comprising a collection of preexisting modules for performing various knowledge processing functions.
18. A computing system for producing a collection of executable modules which are capable of communicating with each other during execution according to a standard message-passing protocol, said computing system comprising a set of preexisting modules composed in a multiplicity of frameworks, and module production means for composing additional executable modules which are capable of communicating with each other and with said preexisting modules during execution according to said standard message-passing protocol, wherein said module production means composes said additional modules by combining selected ones of said preexisting modules, said selected ones of said preexisting modules including selected modules developed in different frameworks.
19. The computing system as claimed in claim 18, wherein said frameworks use different programming languages which describe system behavior in different ways.
20. The computing system as claimed in claim 18, wherein said frameworks use different connection topologies for connecting modules composed in the same framework.
21. The computing system as claimed in claim 18, wherein said module production means includes means for incorporating a new framework for composing said additional modules.
22. The computing system as claimed in claim 21, wherein said module production means includes a separate module production means for each of said frameworks, and said means for incorporating a new framework includes means for incorporating an additional module production means for said new framework.
23. The computing system as claimed in claim 21, wherein said means for incorporating a new framework includes means for modifying the connection topology of a selected one of said frameworks.
24. The computing system as claimed in claim 18, wherein said module production means composes additional executable modules which are capable of being combined by said module production means with selected ones of said preexisting modules which are developed in different frameworks in order to form new executable modules including said additional executable modules.
25. The computing system as claimed in claim 18, wherein said module production means includes means for composing an additional executable module having a specified functionality and for use in a specified one of a plurality of frameworks, wherein said functionality is specified independent of said specified frameworks.
26. The computing system as claimed in claim 18, wherein said module production means includes means for composing an additional executable module with a specified functionality in a multiplicity of frameworks so that the functionality is specified independent of its implementation.
27. The computing system as claimed in claim 18, wherein said module production means includes means for recursively composing said additional executable modules so that some of said additional executable modules are incorporated recursively as interacting objects within other of said additional executable modules.
28. The computing system as claimed in claim 18, wherein said module production means includes means for meshing interacting subsystems of modules to provide simultaneous participation of one module as a component of a plurality of modules.
29. The computing system as claimed in claim 18, wherein a plurality of modules are specified to be embedded in a module to be produced and the linking between specified modules is described graphically, and wherein said module production means includes means for interpreting the graphical description of the linking to link the modules along correlated functions for combining the modules.
30. The computing system as claimed in claim 18, wherein a plurality of modules are specified to be embedded in a module to be produced, and wherein said module production means includes means for interconnecting said modules for data communication using abstract data types wherein data are passed whenever one of the embedded modules produces an instance of abstract data type which conforms to a data input type requirement of another of the embedded modules, so that intermodule data communication is independent of data structure implementation.
31. The computing system as claimed in claim 18, further comprising module analysis means for identifying generated modules which fail to comply with predetermined conditions and module editing means for editing a module to comply with certain of said conditions.
32. The computing system as claimed in claim 31, wherein said module analysis means includes means for generating an explanation of the failure of a module to comply with said conditions.
33. A computing system for the development of an application-specific system comprising a collection of executable modules which are capable of communicating with each other during execution according to a standard message passing protocol, said computer system comprising: means for composing modules using selected ones of a set of frameworks in which the modules are composable, said set of frameworks including a plurality of different frameworks, and means for combining said modules, including modules composed in different ones of said frameworks, to form said collection of executable modules, wherein said means for composing modules includes means for composing a desired module in a selected one of said frameworks by including in the desired module a specified pre-existing module developed by said means for composing in any of said frameworks, so that said modules are uniformly composable.
34. The computing system as claimed in claim 33, wherein said set of frameworks includes a multiplicity of different frameworks, and said computing system further comprises a multiplicity of preexisting modules for various knowledge processing functions.
35. The computing system as claimed in claim 33, wherein said frameworks use different programming languages.
36. The computing system as claimed in claim 33, wherein said frameworks use different connection topologies for connecting modules composed in the same framework.
37. The computing system as claimed in claim 33, wherein said means for composing modules includes means for incorporating a new framework.
38. The computing system as claimed in claim 37, wherein said means for composing modules includes a separate module composing means for each of said frameworks, and said means for incorporating a new framework includes means for incorporating an additional module composing means for said new framework.
39. The computing system as claim in claim 33, wherein said means for incorporating a new framework includes means for modifying the connection topology of a selected one of said frameworks.
40. The computing system as claimed in claim 33, wherein said means for composing modules includes means for specifying the functionality of a module to be composed independent of the framework selected for implementing the module.
41. The computing system as claimed in claim 33, wherein said means for composing modules includes means for recursively composing said modules so that some of said modules are incorporated recursively as interacting objects within other of said modules.
42. The computing system as claimed in claim 33, wherein said means for composing modules includes means for meshing interacting systems of said modules to provide simultaneous participation of one module as a component of a plurality of others of said modules.
43. The computing system as claimed in claim 33, wherein a plurality of modules are specified to be embedded in a module to be composed and the linking between specified modules is described graphically, and wherein said means for composing modules includes means for interpreting the graphical description of the linking to link the modules along correlated functions for combining the embedded modules.
44. The computing system as claimed in claim 33, wherein a plurality of modules are specified to be embedded in a module to be composed, and wherein said means for composing modules includes means for interconnecting said modules for data communication using abstract data types wherein data are passed whenever one of the embedded modules produces an instance of abstract data type which conforms to a data input type requirement of another of the embedded modules, so that intermodule data communication is independent of data structure implementation.
45. The computing system as claimed in claim 33, further comprising module analysis means for identifying composed modules which fail to comply with predetermined conditions, and module editing means for editing a module to comply with certain of said conditions.
46. The computing system as claimed in claim 45, wherein said module analysis means includes means for generating an explanation of the failure of a module to comply with said conditions.
47. The computing system as claimed in claim 33, wherein said means for composing modules includes means for selecting module components by interpreting a preselected description of the module and means for combining the selected module components with a module controller for mediating interactions among said module components.
48. The computing system as claimed in claim 47, wherein said means for combining the selected module components includes means for interconnecting said module controller and said selected module components via an intramodule communication network, and wherein said module controller includes means for controlling access to said intramodule communication network, means for controlling the execution of respective stored programs corresponding to the module components, means for storing and retrieving data local to the module, and means for mediating external communication with the module.
49. The computing system as claimed in claim 33, wherein said means for combining said modules includes means for combining message passing means for intermodule communication along with said modules composed in different frameworks.
50. A computing system for the development of an application-specific system comprising a collection of executable modules which are capable of communicating with each other during execution, said computer system comprising: means for composing modules by combining specified module components in accordance with a predetermined framework, said framework providing an original connection topology for said module components, and means for combining said modules to form said collection of executable modules, wherein said means for composing modules includes means for modifying said connection topology to provide a new framework for composing modules.
51. The computing system as claimed in claim 50, wherein said means for composing includes means for combining, as module components, modules composed by said means for composing, including modules composed in both the original and the modified connection topology.
52. The computing system as claimed in claim 50, wherein said means for composing modules includes means for selecting module components by interpreting a preselected description of the functional characteristics of a module and means for combining the selected module components with a module controller for mediating interactions among said module components.
53. The computing system as claimed in claim 50, wherein said means for composing modules includes means for composing modules according to a selected one of a plurality of different programming language frameworks, and wherein said module assembly means includes means for combining modules of different programming language frameworks.
54. A computing system for the development of an application-specific system comprising a collection of executable modules which are capable of communicating with each other during execution, said computer system comprising: means for composing modules by combining specified module components with a module controller in accordance with an original predetermined framework, said module controller including means for controlling access of the module components to an intramodule communication network and means for controlling the execution of stored programs corresponding to the module components, and means for combining said modules to form said collection of executable modules, wherein said means for composing modules includes means for modifying said module controller to provide a new framework for composing modules.
55. The computing system as claimed in claim 54, wherein said means for composing includes means for combining, as module components, modules composed by said means for composing, including modules composed in both the original and the modified connection topology.
56. The computing system as claimed in claim 54, wherein said means for composing modules includes means for selecting module components by interpreting a preselected description of the functional characteristics of a module and means for combining the selected module components with a module controller for mediating interactions among said module components.
57. The computing system as claimed in claim 54, wherein said means for composing modules includes means for composing modules according to a selected one of a plurality of different programming language frameworks, and wherein said module assembly means includes means for combining modules of different programming language frameworks.
58. A computing system for the development of an application-specific system comprising a collection of executable modules which are capable of communication with each other during execution, said computer system comprising: means for composing modules by combining specified module components in accordance with specified ones of a multiplicity of frameworks, and means for combining said modules, including modules composed according to different ones of said frameworks, to form said collection of executable modules, wherein said means for composing includes means for combining, as module components, modules composed by said means for composing according to different frameworks, and said frameworks use different connection topologies for connecting module components; and further comprising means for specifying the frameworks used for implementing the connection topologies for connecting the modules and module components.
59. A computing system for developing intelligent computer systems including collections of executable modules which interact via message passing, said computing system comprising, in combination: a plurality of pre-programmed knowledge processing modules, a plurality of application-independent problem-solving frameworks for building additional modules and combining modules of different frameworks, and a cooperating operating system for supporting message passing and resource allocation among said knowledge processing modules and said additional modules.
60. The computing system as claimed in claim 59, wherein said pre-programmed knowledge processing modules include a skeletal system.
61. A computing system for monitoring a design, said computer system including a data base storing said design together with a model of the natural world, said design specifying an implementation in the natural world to achieve desired effects under assumed conditions, means for updating said model of the natural world to reflect changed conditions at a plurality of points in time prior to implementation of said design in the natural world, and means for monitoring said data base to test whether said design is capable of being implemented to achieve said desired effects under said changed conditions at said plurality of points in time.
62. The computing system as claimed in claim 61, wherein said design specifies a plan of action to be executed in the natural world.
63. The computing system as claimed in claim 61, wherein said design specifies a physical object to be manufactured in the natural world.
64. The computing system as claimed in claim 61, wherein said means for updating and said means for monitoring operate periodically to indicate when said design becomes incapable of being implemented to achieve said desired effects.
65. The computing system as claimed in claim 61, further comprising means for scheduling the monitoring of said data base to occur at predetermined times, and wherein said means for monitoring said data base is operated by said means for scheduling to determine whether said design is capable of being implemented at said predetermined times to achieve said desired effects under said changed conditions.
66. The computing system as claimed in claim 61, further comprising means for modifying said design when said means for monitoring determines that said design is incapable of being implemented to achieve said desired effects, so that said design is modified to be capable of being implemented to achieve said desired effects.
67. The computing system as claimed in claim 66, wherein said data base includes a knowledge base storing knowledge about how said means for modifying may modify said design in a manner requiring minimal perturbing changes to said design, and wherein said means for modifying includes means for interpreting said knowledge base so that said design is modified with minimal perturbing changes to said design.
68. The computing system as claimed in claim 61, wherein said design stored in said data base includes a set of related elements, said means for monitoring monitors a selected subset of said set of related elements to test whether said design is capable of being implemented to achieve said desired effects under said changed conditions, and further comprising means for analyzing said design to determine said selected subset of said set of related elements to be monitored by said means for monitoring.
69. The computing system as claimed in claim 68, wherein said selected subset selected by said means for analyzing determines prerequisites for actions that said design does not itself achieve.
70. The computing system as claimed in claim 69, further comprising means for translating said prerequisites for actions into database queries.
71. The computing system as claimed in claim 61, further comprising means for generating an explanation of why said design is incapable of being implemented when said means for monitoring determines that said design is incapable of being implemented to achieve said desired effects under said changed conditions.
72. The computing system as claimed in claim 71, wherein said explanation is expressed in a natural language.
73. A computer system for maintaining a design despite changing conditions so that said design is capable of being readily implemented in the natural world to achieve certain desired effects, said computer system including a data base storing said design together with a model of the natural world, means for updating said model of the natural world to reflect said changing conditions at a plurality of points in time before said design is implemented, and means for incrementally modifying said design a plurality of times prior to implementation to reflect said changing conditions at said plurality of points in time so that said design is modified to be readily capable of being implemented to achieve said desired effects.
74. The computing system as claimed in claim 73, wherein said data base includes a knowledge base storing knowledge about how said means for modifying may modify said design in a manner requiring minimal perturbing changes to said design, and wherein said means for modifying includes means for interpreting and applying said knowledge.
75. The computing system as claimed in claim 73, further comprising means for analyzing the nature of the changes in said design effected by said means for modifying so that the design changes are identified.
76. The computing system as claimed in claim 75, further comprising means for generating an explanation of the identified design changes.
77. A computing system including modular software for monitoring and successively modifying a design to reflect changing conditions so that said design is capable of being readily implemented in the natural world to obtain certain desired effects despite changing conditions, said computing system also including a data base storing said design together with a model of the natural world, said modular software including modules for monitoring said data base to test whether said design is capable of being implemented to achieve said desired effects under said changing conditions, and for modifying said design when said design is found to be incapable of being implemented to achieve said desired conditions.
78. The computing system as claimed in claim 77, wherein said modules include a module for monitoring said data base, and a module for incrementally modifying said design.
79. The computing system as claimed in claim 77, wherein said modules are replaceable functional units.
80. The computing system as claimed in claim 77, wherein at least one of the modules internally uses different kinds of architecture and control procedures.
81. The computing system as claimed in claim 77, wherein abstract data types are used for interfaces between said modules.
82. A computing system including a modular software architecture for monitoring and successively modifying a design to reflect changing conditions so that said design is capable of being readily implemented in the natural world to obtain certain desired effects despite changing conditions, said computing system including a data base storing said design together with a model of the natural world, said modular software including modules for monitoring said data base and for modifying said design to reflect changing conditions, wherein said modular architecture includes control knowledge which is interpreted and applied for flexible control of the sequence of execution of the software modules.
83. The computing system as claimed in claim 82, wherein at least one of the modules internally uses different kinds of architecture and control frameworks.
84. The computing system as claimed in claim 82, wherein said modules include an assumption analyst for determining critical assumptions of the design, a situation monitor for monitoring the data base to determine whether the critical assumptions are true, a failure explainer for explaining failures in the design when the critical assumptions are false, an incremental replanner for modifying the design when the critical assumptions are false, and a change analyst for comparing the modified design to the design before modification to identify and describe the modifications made to the design.
Patent Citations (7)
Non-Patent Literature (22)
- M. Callero, D. Waterman, J. Kipps, "TATR: A Prototype Expert System for Tactical Air Targeting", RAND R-3096-ARPA, Aug. 1984.
- D. Bobrow, M. Stefik, "The LOOPS Manual", PARC TR KB-VLSI-81-31, 1981.
- ABE: Architectural Overview, Lark et al., 26 Pages, Background Documentation for Workshop of Distributed Artificial Intelligence, Dec. 3-6, 1985, Sea Ranch, Calif.
- Earl D. Sacerdoti, "A Structure for Plans and Behavior," Technical Note 109, SRI International, (Aug. 1975).
- Richard E. Fikes, "Monitored Execution of Robot Plans Produced by STRIPS," Stanford Research Institute Project 8973, Technical Note 55, Menlo Park, Calif. 94025, (Apr. 1971).
- Philip J. Hayes, "A Representation for Robot Plans," Advance Papers of the Fourth International Joint Conference on Artificial Intelligence, Tbilisi, Georgia, USSR, (Sep. 3-8, 1975).
- Nils J. Nilsson, "Some Examples of AI Mechanisms for Goal Seeking, Planning and Reasoning," Stanford Research Institute Technical Note 130, (May, 1976).
- Robert B. Wesson, "Planning in the World of the Air Traffic Controller," Proceedings of the 5th International Joint Conference on Artificial Intelligence--1977, vol. 1, Massachusetts Institute of Technology, Cambridge, Mass., (Aug. 22-25, 1977).
- C. Engleman et al., "KNOBS: An Experimental Knowledge Based Tactical Air Mission Planning System and A Rule Based Aircraft Identification Simulation Facility", Proceedings of the 6th International Joint Conference on Artificial Intelligence, Tokyo, pp. 247-249, (1979).
- L. Erman et al., "The Hearsay-II Speech Understanding System: Integrating Knowledge to Resolve Uncertainty," Computing Surveys, 12(2), pp. 213-253, (Jun. 1980).
- A. Barr et al., The Handbook of Artificial Intelligence, HeurisTech Press, Stanford, Calif., vol. II, pp. 3-68, 79-86, 150-154, vol. III, pp. 515-530, 541-556; (1982).
- A. Davis et al., "Data Flow Program Graphs," IEEE Computer, 15(2), pp. 26-41, (Feb. 1982).
- Encyclopedia of Computer Science and Engineering, (A. Ralston, Ed.), Van Nostraud Reinhold Company, N.Y., pp. 1-2, (1983).
- B. Chandrasekaran, "Towards a Taxonomy of Problem Solving Types," AI Magazine, 4(1), pp. 9-17, (Winter/Spring 1983).
- A. Sloman et al., "POPLOG: A Multilanguage Program Development Environment," Information Technology: Research and Development, 2, pp. 109-122, (1983).
- William J. Clancey, "The Advantages of Abstract Control Knowledge in Expert System Design", Proceedings of the National Conference on Artificial Intelligence, Washington, D.C., pp. 74-78, (Aug. 1983).
- Symbolics Manual Version 6.1, vol. 2, pp. 415-469, (Mar. 1985).
- L. Erman et al., "Separating and Integrating Control in a Rule-Based Tool," Proceedings of the IEEE Workshops on Principles of Knowledge-Based Systems, Denver, Colo., pp. 37-43, (Dec. 1984).
- Stuart Russell, "The Compleat Guide to MRS," Technical Report KSL-85-12, Stanford Knowledge Systems Laboratory, Computer Science Department, Stanford Univerity, (1985).
- Geoffrey A. Pascoe,
- This invention was made with Government support under contract number F30602-85-C-0135 awarded by USAF AFSC Rome Air Development Center. The Government has certain rights in this invention.
- The present application is a continuation-in-part of Ser. No. 934,649 filed Nov. 25, 1986 abandoned.