Search

One of the important obligations of an expanding research area is to discuss how to approach the teaching of the subject. Without this discussion, we may find that the word is not spread properly, and thus that the results are not properly utilized in industry. Furthermore, discussing teaching the research area gives additional insight into the research area and its underlying theoretical foundation. In this paper we will report on our approach to teaching programming languages as a whole and especially teaching object-oriented programming. The prime message to be told is that working from a theoretical foundation pays off. Without a theoretical foundation, the discussions are often centered around features of different languages. With a foundation, discussions may be conducted on solid pound. Furthermore, the students have significantly fewer difficulties in grasping the concrete programming languages when they have been presented with the theoretical foundation than without it. [ABSTRACT FROM AUTHOR]

This paper presents the user interface to programs and their execution in the Mjølner Programming Environment. The key idea is to present the programming language abstractions, such as classes and procedures, as individual windows which the user can interact with directly. This approach is used consistently to visualize both a program and its execution. The windows are arranged hierarchically reflecting the static nesting of blocks. The window hierarchy gives powerful support for interaction and navigation in a program. Incremental compilation techniques are used to make a high level of interaction and integration possible. [ABSTRACT FROM AUTHOR]

At the specification level, inheritance can be defined as subtyping by means of order sorted specifications [GM85]. Subtyping is, obviously, a very important notion, allowing not only to work with a non rigid type structure, but also providing an adequate basis for error handling in algebraic specifications. However, in our opinion, subtyping and order sorted specifications do not play the same rûle as inheritance in program design. In this paper, we will present a hierarchical organization for specifications, based on a different concept of inheritance which, we think, corresponds, methodologically, to the usual inheritance relation defined at the programming level. This new relation allows to work with incomplete specifications with several levels of detail and, as a side-effect, it may play the rûle of genericity. The use of this notion of inheritance is shown by means of the GSBL specification language built around this new concept, whose use and formal semantics are sketched. [ABSTRACT FROM AUTHOR]

Supporting multiple classification in object-oriented programming languages is the topic of discussion in this paper. Supporting multiple classification gives rise to one important question — namely the question of inheritance of attributes with identical names from multiple paths in the classification hierarchy. The problem is to decide how these multiple classification paths are reflected in the class being defined. One of the conclusions in this paper is, that by choosing strict and simple inheritance rules, one is excluding some particular usages of multiple classification. This leads to the notion of attribute-resolution at class definition, which means that the programmer in some cases is forced or allowed to resolve the potential ambiguity of the inherited names. The concept of attribute-resolution is managed through the identification of two conceptually different utilizations of specialization (unification and intersection), and two different attribute properties (plural and singleton) to guide the attribute-resolution. [ABSTRACT FROM AUTHOR]

This paper presents the design of a minimal set of instruction for a class system embedded in Lisp: ObjVLisp. We re-use the set of postulates describing the operational behaviour of ObjVLisp to discuss and derive a new implementation based on a reduced set of functions and a more self-contained description. Then we develop the ObjVLisp experience in building metaclass architecture to propose a layered and incremental metaobject protocol for CLOS. [ABSTRACT FROM AUTHOR]

We present an original exception handling system especially designed for object-oriented languages. making actual information hiding possible and taking into account specific issues of object-oriented languages. It allows association of handlers with expressions as well as with object classes, using a well defined semantics. It offers an object-oriented and extensible representation of exceptions, handlers and knowledge about exceptions. Handlers can specify both resumption and termination. There are no distinctions between system and user defined exceptions. With this system. fault tolerant programs and well specified encapsulations can be written, simple and powerful integration of new user-defined exceptions and secure as well as readable non local moves can be implemented. In this paper, we examine object oriented specific issues related to exception handling. We discuss the exception handling mechanisms available in current object-oriented languages and explain why they do not provide he ability to define fault tolerant encapsulations. Our system description shows how the utilization of the object-oriented formalism solves, in an efficient and simple way, some well known problems related to exception handling such as: how to create exception hierarchies, how to signal fatal or continuable exceptions with the same primitive, how to pass arguments to handlers. and so on. [ABSTRACT FROM AUTHOR]

An Integrated Electronic Book (IEB) represents a complex network of integrated information and "know how" on a given subject. In the design phase of WEBS (Woven Electronic Book System), we soon realized that, because we were describing the IEB in terms of "objects" and "methods," and because we wanted WEBS to be easily expandable and to offer a consistent user interface, we should use an object-oriented development system. This paper does not fully discuss the concept of electronic book systems, but rather describes our own experiences developing a complex software system with an object-oriented language. The first part explains our choice of an object-oriented language and software framework. The rest describes the software architecture of WEBS, which is a class hierarchy of three layers: a software framework (MacApp) layer, a system-specific layer; and an application-specific layer. [ABSTRACT FROM AUTHOR]

This paper describes DistributedSmalltalk, which consists of a number of cooperating Smalltalk virtual machines distributed over a network, that provide complete distribution transparency to the image level, including transparent message passing across machine boundaries. As a result no modifications are necessary at the image level and e.g. the standard Smalltalk debugger can be used for system wide debugging. Transparent I/O is provided by means of a concept called "home objects". The performance degradation is acceptable, due to replication and the home object concept. Replication is transparent and replication consistency is guaranteed, so e.g. for replicated class objects no compatibility checking is needed. Distributed garbage, whether containing cycles or not, is collected incrementally without any synchronization being necessary. [ABSTRACT FROM AUTHOR]

One of the key concepts available in many object-oriented programming languages is that of type-inheritance, which permits new types to be derived from, and inherit the capabilities of, old types. This paper describes how to exploit this property in a very simple fashion to implement object-oriented concurrency control. We show how by using type-inheritance, objects may control their own level of concurrency in a type-specific manner. Simple examples demonstrate the applicability of the approach. The implementation technique described here is being used to develop Arjuna, a fault-tolerant distributed programming system supporting atomic actions. [ABSTRACT FROM AUTHOR]

This paper presents a debugging method for Concurrent Object-Oriented Systems. Our method is based upon a new notion called Object Groups. An Object Group is a collection of objects which forms a natural unit for performing collective tasks. An Object Group's Task differs from C. Manning's nested transaction which is based on the nested request-reply bilateral message passing structures. Each Object Group's Task permits more general message passing structures. The language constructs which specify and use Object Groups have been introduced into an object-oriented concurrent language ABCL/l. The paper also describes ABCL/l's debugging tools based on Object Groups. [ABSTRACT FROM AUTHOR]

The terminology in the area of databases and data models is inconsistent and inaccurate and thus often confusing. Some fundamental database concepts are described in this paper. The description of these concepts are based on general concepts related to the development of the object oriented languages SIMULA, DELTA and BETA. A database is defined as an information system providing information about a referent system (the modelled part of the world), and a data model is defined as "having an inherent structure and a set of tools and techniques used in the process of designing, constructing and manipulating model systems (in particular, databases)". The connection between databases, DBMS and data models and other concepts related to the development and use of databases are described in a process/structure hierarchy. [ABSTRACT FROM AUTHOR]

This paper provides a brief introduction to the OOPS+ knowledge-representation language. While basically object-oriented, OOPS+ integrates database concepts as well as classical knowledge-representation techniques such as rule-based inference and demons. In addition, the language supports types as first-class objects, inheritance, imperative function definition, and query facilities based on logic programming. [ABSTRACT FROM AUTHOR]

Constructing a visually informative drawing of an abstract graph is a problem of considerable practical importance, and has recently been the focus of much investigation. Displaying symmetry has emerged as one of the foremost criteria for achieving good drawings. Linear-time algorithms are already known for the detection and display of symmetry in trees, outerplanar graphs, and embedded planar graphs. The central results of this paper show that for general graphs, however, detecting the presence of even a single axial or rotational symmetry is NP-complete. A number of related results are also established, including the #P-completeness of counting the axial or rotational symmetries of a graph. [ABSTRACT FROM AUTHOR]

Let Qn be the n-dimensional hypercube. If n=2k+1, then the subgraph Mn of Qn induced by the nodes having exactly k or k + 1 ones is called the middle cube of dimension n. A famous conjecture is that Mn is hamiltonian if n>1. Clearly, M3 has two oriented hamiltonian cycles. This paper includes the following new results:1.The number of oriented hamiltonian cycles of Mn is divisible by k!(k + 1)!.2.M5 has exactly 48 oriented hamiltonian cycles.3.M7 is hamiltonian.4.Some interesting new combinatorial identities which are relevant to the structure of Mn. [ABSTRACT FROM AUTHOR]

This paper introduces a mathematical evidence model for uncertain information in artificial intelligence. Each evidence model contains prior information as well as possible new evidence to appear later. Both Bayesian probability distribution and Dempster-Shafer's ignorance are special evidence models. A concept of independence is also introduced. Dempster-Shafer's combination rule becomes a formula to combine basic probabilities of independent models. [ABSTRACT FROM AUTHOR]

The major problem in the evaluation of expert systems is the selection of the appropriate statistical measures of performance consistent with the parameters of the system domain. The objective of this paper is to develop the statistical evaluation methodology needed to assess the performance of medical expert systems including MEDAS — the Medical Emergency Decision Assistance System. The measures of performance are selected so as to have an operational interpretation and also reflect the predictive diagnostic capacity of a medical expert system. Certain summary measures are used that represent the sensitivity, specificity, and system response of a medical expert system. Measures of agreement such as the kappa statistic and the measure of conditional agrement are used to measure the agreement between the medical expert system and the physician. Goodman and Kruskal's lambda and tau measures of predictive association are introduced to evaluate the predictive capacity of a medical expert system. This methodology has been partially implemented in the performance evaluation of MEDAS. [ABSTRACT FROM AUTHOR]

Information retrieval systems employ the classification of documents into various categories to facilitate retrieval. The problem of categorization depends on the successful solution to three subproblems: creation of categories, determining the relationship between categories, and maintenance of the categorization system. In existing document categorization systems, the categories are formed by using hit and trial methods. This increases the initial setup period for the system. The initial setup time is further affected by an empirical assignment of relationships between categories. In this paper, we propose a solution to the problem of developing categories by the application of techniques originating in knowledge acquisition. The approach is based on capturing the knowledge of a user to ensure continuity with the existing categorization system. The use of Personal Construct Theory for knowledge elicitation helps in making explicit the subconscious hierarchical relationships between various categories as perceived by the user. [ABSTRACT FROM AUTHOR]

Decision trees provide a powerful method of pattern classification. At each node in a binary tree a decision is made based upon the value of one of many possible attributes or features. The leaves of the tree represent the various classes that can be recognized. Various techniques have been used to select the feature and threshold to use at each node based upon a set of training data. Information theoretic methods are the most popular techniques used for designing each node in the tree. An alternate method uses the Kolmogorov-Smirnov test to design classification trees involving two classes. This paper presents an extension of this method that can produce a single decision tree when there are multiple classes. The relationship between this generalized Kolmogorov-Smirnov method and entropy minimization methods will be described. Experiments comparing classification results using this decision tree with results of using a Bayesian classifier will be presented. [ABSTRACT FROM AUTHOR]

In this paper, we analyze the delay of an average message going through an arbitrary link of the N-cube. We view each link as an M/M/1 queue and find analytic recursive relations for the arrival rate of messages at an arbitrary link. Then, we calculate the delay per link as a function of the message generation rate at the processor. We investigate two model of communication. The first, uniform communication where each processor communicate with any other processor with the same probability. The second is clustered communication, where neighboring processors communicate more than distant processors do. Finally, we investigate the effect of adding one more link at each node of the cube (Folded Hypercube) on the delay and the maximum number of hops. [ABSTRACT FROM AUTHOR]

This paper presents an improved lower bound on Conway's parallel sorting algorithm. It is shown that Conway's parallel sorting algorithm sorts N keys in (N+[N/2]-2) cycles, where [X] denotes the smallest integer which is larger than or equal to X. The original result proposed by Warshauer is (2N-3) cycles. With this improvement it can be saved (N-[N/2]-1) cycles for N keys. Consequently it is shown that 50(1-2/N) percent of cycles can be saved on the sorting process. Also with this improvement the modified algorithm for average behavior proposed by the authors in an earlier paper will become more efficient. [ABSTRACT FROM AUTHOR]

Evaluation of program performance on concurrent computers requires methods and tools that are part of an integrated environment for observing, analyzing, and displaying system performance. This paper describes a unique graphical approach for presenting performance data of concurrent computer systems, possibly having large numbers of processors. Performance data is generated and collected via instrumentation, reduced via conventional cluster analysis techniques, and converted into a graphical form to highlight important performance measures. A novel kind of data plot is introduced to visually display both temporal and spatial information describing system activity. A prototype implementation applied to two case studies is described. [ABSTRACT FROM AUTHOR]

Dendrograms have been used in cluster analysis and in hierarchical classification problems. In this paper we note that the Huffman method for producing optimal binary codes also produces only dendrograms. We define an equivalence relation on codes and give an algorithm to produce a prefix code in each class. We also define minimal and maximal total length functions and by exploiting the relationship between irreducible codes and dendrograms, we derive formulas for them. We also derive a measure of code extensibility. [ABSTRACT FROM AUTHOR]

Fractal approximations are used to generate data to mimic natural objects for realistic image synthesis. While many algorithms for generating fractal data for this purpose exist, the adaptive subdivision methods are in widespread use because of their computational efficiency. This paper discusses the adaptation of the triangular and rectangular subdivision algorithms originally described in [1] to massively parallel SIMD architectures. In addition, the algorithms are enhanced to permit more control over the characteristics of the surfaces. [ABSTRACT FROM AUTHOR]

A cryptographic system, called pgm, was invented in the late 1970's by S. Magliveras. pgm is based on the prolific existence of certain kinds of factorization sets, called logarithmic signatures, for finite permutation groups. Logarithmic signatures were initially motivated by C. Sims' bases and strong generators. A logarithmic signature α, for a given group G, induces a mapping $$\hat \alpha$$ from ZG to G. Hence it would be natural to use logarithmic signatures for generating random elements in a group. In this paper we focus on generating random permutations in the symmetric group Sn. Random permutations find applications in design of experiments, simulation, cryptology, voice-encryption etc. Given a logarithmic signature α for Sn and a seed s0, we could efficiently compute the following sequence : $$\hat \alpha$$ (s0), $$\hat \alpha$$ (s0 + 1)..., $$\hat \alpha$$ (s0 + r - 1) of r permutations. We claim that this sequence behaves like a sequence of random permutations. We undertake statistical tests to substantiate our claim. [ABSTRACT FROM AUTHOR]

This paper presents novel design techniques for Residue Number System based systolic arrays for arithmetic computation useful in digital signal processing applications. Design of a 5-bit pipelined adder is explained with emphasis on the basic systolic cell design, use of clocks, pipeline techniques, simulation, and layout optimization. This pipelined adder can be used to build systolic multipliers, correlators, computational structures for DFT, etc. [ABSTRACT FROM AUTHOR]

A parallel processor architecture is presented in this paper for the real-time engine and vehicle guidance control in a modern spacecraft. The system is designed to be fault-tolerant and will give diagnostic messages to aid repair. The architecture is based on the multiple shared bus concept. Multiple buses increase fault-tolerance and will enable computation of complex control equations within the required time frame. Each processor stage has a priority queue and any process that requires processing is inserted into the priority queue, if the current process under execution has a higher priority than the new process. Protocols are designed to run various routines on different processor stages under a prioritized system. [ABSTRACT FROM AUTHOR]

Modern industrial robots contain substantial amount of electronic hardware, both analog and digital. When an internal hardware fault develops, robot operations will be adversely effected. This paper presents three different diagnostic strategies, to locate hardware faults at the lowest replaceable integrated circuit level. First method is based on enumerating all paths in the circuit and designing test sequences for each path enumerated. Second method is based on identifying sets of test sequences with individual microinstructions of the robot controller and designing microinstruction routines for diagnosis. Third method is based on running software routines, designed exclusively to move the robot arm through pre-defined diagnostic moves. The data during these dummy arm movements are collected and compared with the expected data. Discrepancies between these two data sets will yield another set of diagnostic information. Diagnostic information obtained from each method is refined using the information from the other methods to give the fault location information at the desired level. In the presence of multiple faults, these three methods are applied repeatedly, after replacing the faulty chip located during the previous application. [ABSTRACT FROM AUTHOR]

This paper describes Protype, a prototyping tool for communication protocol specifications. The tool is based on extended finite state machine augmented with context variables and procedural information. The tool helps a protocol designer in developing error free protocols. It also helps protocol implementors in verifying protocols. [ABSTRACT FROM AUTHOR]

This paper describes the concepts and methodologies regarding personal directory and file management. It also presents a software system (SIFO), which provides a structured environment for program developers using an on-line template that provides guidance during program initiation and modification. This system can assist both experienced and inexperienced programmers in organizing and documenting files in a structured manner. [ABSTRACT FROM AUTHOR]

The problem of the search for an optimum database index selection problem is an NP-complete problem. Genetic algorithms have been shown to be robust algorithms for searching large spaces for optimal objective function values. Genetic algorithms use historical information to speculate about new areas in the search space with expected improved performance. The feasibility of the application of genetic algorithms to the optimal database index selection is studied in this paper. [ABSTRACT FROM AUTHOR]

Office-specific systems are often difficult and costly to implement and/or prototype. One reason for this difficulty is the unavailability of an appropriate office specification language. In this paper, we introduce an object-based language to formally specify the externally observable behavior of office objects as well as their computations. This language is called Absl and is based on the actor model. The overall structure of Absl objects as well as some of their properties are presented. [ABSTRACT FROM AUTHOR]

This paper describes our lexical acquisition system, which supplements knowledge in the lexical database with knowledge acquired from human informants. The database is organized to support the needs of natural language processing applications and facilitate the operation of acquisition system. [ABSTRACT FROM AUTHOR]

In this paper we consider a simultaneous reduction of three matrices. The described method is extended from the work presented in [3] to include rank deficient data. It is shown how, via an initial reduction, the problem becomes one of diagonalizing a product of three matrices. We compare three different algorithms for its computation and show why one is preferred over the others. [ABSTRACT FROM AUTHOR]

A number of recent papers have addressed the problem of constructing monotone piecewise cubic interpolants to monotone data. These have focused not only on the monotonicity of the interpolant, but also on properties such as "visual pleasure", and optimal order error bounds. We review some of these results, and generalize them by constructing C1 piecewise cubic polynomial interpolants to non-monotone data.These interpolants have a minimum number of changes in sign in the first derivative and approximate an underlying function and its first derivative with optimal order. [ABSTRACT FROM AUTHOR]

Hierarchical graph models are a powerful tool for describing VLSI circuits. They combine the representation of a hierarchical decomposition of a circuit with a graph description of its topological structure in terms of components and connections. Structured Graphs are an example of such models. In this paper we consider the graph-theoretic problems of spanning trees and Steiner trees in structured graphs. These have connections with the global routing problems in VLSI circuits. [ABSTRACT FROM AUTHOR]

Circuit bi-partitioning is an important step in placement algorithms based on the min-cut paradigm. In this paper, we present a stochastic algorithm for circuit bi-partitioning (BIPART) which minimizes the number of nets cut while maintaining a tight control on the sizes of the two parts. BIPART performs better than simulated annealing and the Fiduccia-Matheyses algorithm, and runs in linear time per iteration. [ABSTRACT FROM AUTHOR]

We are given a channel-routing problem in which all nets have either (1) all their terminals on the same side of the channel, or (2) all but their rightmost terminal on the same side. This is the only class of multi-terminal nets for which an optimal algorithm has been found. Our paper describes an algorithm that routes the channel in knock-knee mode using D tracks, where D is the channel density and is a trivial lower-bound for channel width. Our implementation has complexity O(nlog2D), where n is the number of columns in the channel. [ABSTRACT FROM AUTHOR]

This paper concerns a reliable broadcast protocol which we have been investigating within the context of programming distributed systems [Ram1989(a)]. The protocol can be used to simplify the design of distributed computation algorithms. We prove certain important properties of this protocol and provide a concise functional specification of this protocol. The specification is required in order to help understand the behavior of the protocol. [ABSTRACT FROM AUTHOR]

In a distributed computing system, a change in the state of the system usually requires that the new state be propagated to all active nodes so that they can correctly perform cooperative tasks. Since more than one node may detect a status change, conflicts in state determination and propagation are possible. In order to ensure that all nodes of a communicating group are at the same state, all nodes of the group must agree upon the election of a single leader (coordinator). In this paper, we present an Election Protocol for General Configuration networks (EPGC). The protocol was tested on different well known configurations and its performance was studied using simulation modeling techniques. The simulation study showed a trade off between the election time and the number of exchanged messages. A technique to minimize the number of messages was then introduced. Both positive and negative effects of this technique were observed. [ABSTRACT FROM AUTHOR]

The loop is a commonly used interconnection network for computer systems. In this paper we consider the problem of making a loop network fault-tolerant. Previous solutions employ the absolute minimum number of redundant components, for a specified level of fault tolerance. In our approach, "extra" redundancy is used to reduce the size and complexity of the interconnection network. Designs based on chordal rings are presented which can tolerate one and two processor failures. The examples given indicate that for large scale systems, the approach can produce improved designs, which are more in accord with the limitations of current technology. [ABSTRACT FROM AUTHOR]

Research has shown that physicians find a medical expert system much more attractive if the system can provide in addition to diagnostic support some relief from the heavy burden of responsibility for daily record keeping required in hospital practice. This paper introduces a sophisticated interactive system for generating daily progress notes designed to function as an integral part of MEDAS (the Medical Emergency Decision Assistance System). MEDAS is a pattern-recognition expert system, using multi-membership Bayesian inference. At hospital admission, the MEDAS diagnosis module and severity module produce a problem list and assign a severity code to each problem. In many hospitals, physicians are expected to provide daily progress notes discussing the patient's condition with respect to each problem area. For each problem, they need to consider subjective and objective information, assessment and make a plan for handling the problem. The items to be considered depend on the specific problem: remembering these items is a huge memory load; writing it all down is very time-consuming. Our system presents the physician with a series of problem-specific menus, making data entry easy and rapid. Finally, it automatically generates the necessary output for the patient record. [ABSTRACT FROM AUTHOR]

In a series of papers, we have developed a logical model, using category theory, for neurobiological processing. A schema is a functor C : C → Set It is essentially an action of a category C on Set. A model M = 〈F, α〉 of C′ : C′ → Set in C : C → Set is given by a functor F : C′ → C, and a natural transformation α : C º F $$\to$$ C′. In this paper, we develop a set of simple psychophysical gedankenexperiments and apply the general theory to work out some of the logic of the perceptual process. [ABSTRACT FROM AUTHOR]

The teaching of the fundamentals of parallel processing is becoming increasingly important in undergraduate Computer Engineering and Computer Science programs. This paper discusses the development of a simple laboratory environment designed for the study and testing of principles governing the performance of parallel processors. The laboratory environment is structured to be simple enough for undergraduate use, flexible enough to test the many facets of parallel processing, and sophisticated enough to give results applicable to larger scale parallel processors. Particular emphasis in this paper is placed on tests that were run to examine the suitability of the laboratory to support experimentation with shared memory multi-processors. The main test involved investigating the influence of communication and calculation times on the amount of synchronization overhead in the system. [ABSTRACT FROM AUTHOR]

This paper describes a semi-challenging compiler project appropriate for Compiler Construction course at the advanced undergraduate-graduate level at a non-PhD-granting institution. The compiler project is centered around a table-driven parser and associated syntax-directed semantic routines for a real programming language. Our experience indicates that the curriculum can be strengthened by putting students into the most challenging learning environment in which they can succeed. [ABSTRACT FROM AUTHOR]

In this paper we describe an architecture for agents that have to act in dynamic environments. The architecture, which has been partially implemented in Common Lisp, consists of a number of layers, each of which occupies a different position on the flexibility versus computational tractability trade-off. By integrating a high-level declarative planner with a reactive planner using situated-action rules, the architecture combines the flexibility of the former with the efficiency of the latter. Moreover, the lower levels of the architecture can be automatically configured on the basis of previous activities of the higher levels, thus avoiding the need for providing a complete set of situated-action rules that is inherent in a purely reactive planning approach. [ABSTRACT FROM AUTHOR]

This article outlines the design rationale behind the entity and time representation and reasoning system incorporated into the o-plan2 planner. The paper shows the advantages of splitting the planning entities (such as activities, events and time orderings) from the underlying temporal information of the domain. This allows a single architecture to be tailored to act as planner, scheduler or controller with only minor changes in the knowledge required. The paper concludes with a description of the current o-plan2 system together with our early results and future research direction. [ABSTRACT FROM AUTHOR]

In this paper we introduce a language for representing planning problems, planning decisions and plans in one formalism. This single representation supports the recognition and the analysis of dependencies between planning decisions and goals. The recognition and analysis of dependencies between decisions and goals is a central task for advanced planning procedures. A good support of this task directly improves the efficiency of the procedure and improves the quality of the generated plan. [ABSTRACT FROM AUTHOR]

Plans naturally contain subgoals about how the world must be. They arise as preconditions of actions in the plan — having keys in order to unlock doors and so on. Plans also contain subgoals about what the agent must know — combinations of safes, Mary's phone number, which way the outlaw went. Merely stipulating that actions and operands must be known is a hack. This paper offers an account of actions done under uncertainty. If the account is accepted, knowledge subgoals arise automatically, since plans done under uncertainty must still be adequate descriptions of what to do. Plans with knowledge subgoals turn out to be very like ordinary plans. [ABSTRACT FROM AUTHOR]

Automatically improving the performance of inference engines is a central issue in automated deduction research. This paper describes and evaluates mechanisms for speeding up search in an inference engine used in research on reactive planning. The inference engine is adaptive in the sense that its performance improves with experience. This improvement is obtained via a combination of several different learning mechanisms, including a novel explanation-based learning algorithm, bounded-overhead success and failure caches, and dynamic reordering and reformulation mechanisms. Experimental results show that the beneficial effect of multiple speedup techniques is greater than the beneficial effect of any individual technique. Thus a wide variety of learning methods can reinforce each other in improving the performance of an automated deduction system. [ABSTRACT FROM AUTHOR]

Domain-independent classical planning is faced with serious difficulties. Many of these are traceable to some facet of the frame problem. Perfect knowledge of the planner's world and operators is impossible for most domains. With anything less, small unmodeled errors can result in large discrepancies between the expected and observed worlds. Such discrepancies may interfere with the achievement of a goal. Reactivity provides an extreme response. It allows only sensor information after an action is taken to judge the action's effects, and abandons projection altogether. There must be a vast space of possibilities between the extremes of classical planning and reactivity. This paper describes two called computable planning and permissive planning. Machine learning, in the form of Explanation-Based Learning, is used in computable planning to recognize deferrable goals, resulting in many of the benefits offered by reactivity but in a domain independent form. In permissive planning, machine learning techniques are used to refine plans through experience so that they become less sensitive to the necessarily approximate knowledge. [ABSTRACT FROM AUTHOR]