Institute for Systems Research

Permanent URI for this communityhttp://hdl.handle.net/1903/4375

Browse

Author: search.filters.author.Hendler, James A.Subject: search.filters.subject.Systems Integration

Search Results

Now showing 1 - 10 of 10
  • Thumbnail Image
    Item
    Complexity Results for HTN Planning
    (1994) Erol, Kutluhan; Hendler, James A.; Nau, D.S.; ISR
    Most practical work on AI planning systems during the last fifteen years has been based on hierarchical task network decomposition, but until now, there has been very little analytical work on the properties of HTN planners. This paper describes how the complexity of HTN planning varies with various conditions on the task networks, and how it compares to STRIPS- style planning.
  • Thumbnail Image
    Item
    Linking Symbolic and Subsymbolic Computing
    (1993) Wilson, A.; Hendler, James A.; ISR
    The growing interest in integrating symbolic and subsymbolic computing techniques is manifested by the increasing number of hybrid systems that employ both methods of processing. This paper presents an analysis of some of these systems with respect to their symbolic/subsymbolic interactions. Then, a general purpose mechanism for linking symbolic and sub symbolic computing is introduced. Through the use of programming abstractions, an intermediary agent called a supervisor is created and bound to each subsymbolic network. The role of a supervisor is to monitor and control the network behavior and interpret its output. Details of the subsymbolic computation are hidden behind a higher level interface, enabling symbolic and subsymbolic components to interact at corresponding conceptual levels. Module level parallelism is achieved because subsymbolic modules execute independently. Methods for construction of hierarchical systems of subsymbolic modules are also provided.
  • Thumbnail Image
    Item
    Complexity, Decidability and Undecidability Results for Rule- Based Expert Systems
    (1992) Blanksteen, Scott; Hendler, James A.; Nau, Dana S.; ISR
    We prove the equivalence of domain-independent planning systems and rule-based expert systems. We use this equivalence to examine how the complexity of deriving conclusions in rule-based expert systems depends on the nature of the rules. We show conditions under which conclusion derivation is decidable and undecidable. For those cases where the problem is decidable, we show how the time complexity varies depending on a wide variety of conditions: whether or not function symbols are allowed; whether or not rules may retract facts; whether or not negative conditions are allowed; whether or not the rules are allowed to take arguments; and whether the rules are given as part of the input to the expert system, or instead are fixed in advance.
  • Thumbnail Image
    Item
    Knowledge Representation in PARKA - Part 2: Experiments, Analysis, and Enhancements
    (1992) Spector, Lee; Andersen, William; Hendler, James A.; Kettler, Brian; Schwartzman, Eugene; Woods, Cynthia; Evett, Matthew; ISR
    Our research group has designed and implemented a symbolic knowledge representation system called PARKA which runs on the Connection Machine, a massively parallel SIMD computer [9]. The semantics of this system are discussed in [11]. The details of the Connection Machine implementation and discussions of performance considerations can be found in [3], [4], [5], [6] and [7]. In the past year the PARKA project has made significant advances along several fronts of both theoretical and practical significance. This paper summarizes some of this work and outlines directions for further research.
  • Thumbnail Image
    Item
    PRA: Massively Parallel Heuristic Search
    (1991) Evett, Matthew; Hendler, James A.; Mahanti, Ambuj; Nau, D.; ISR
    In this paper we describe a variant of A* search designed to run on the massively parallel, SIMD Connection Machine. The algorithm is designed to run in a limited memory by use of a retraction technique which allows nodes with poor heuristic values to be removed from the open list, until such time as they may need reexpansion, more promising paths having failed. Our algorithm, called PRA* (for Parallel Retraction A*), is designed to maximize use of the Connection Machine's memory and processors. In addition, the algorithm is guaranteed to return an optimal path when an admissable heuristic is used. Results comparing PRA* to Korf's IDA* for the fifteen-puzzle show significantly fewer node expansions for PRA*. In addition, empirical results show significant parallel speedups, indicative of the algorithm's design for high processor utilization.
  • Thumbnail Image
    Item
    Integrating Neural Network and Export Reasoning: An Example
    (1991) Hendler, James A.; Dickens, Leonard; ISR
    In this paper we describe a shell which has been developed to allow an integration of neural network and expert systems technology. The system, SCRuFFy, is based on an analysis of the different abilities and time courses of NN and AI systems. Critical to the processing of this system is a temporal pattern matcher which is used to mediate between the two subsystems, providing a "signal to symbol" mapping. This mapping allows the expert system to reason about the time course of signals which are classified by a connectionist network which is trained via classical back-propagation of error during a separate training phase. An example of the simulated control of the temperature of an underwater welding robot is presented to demonstrate these capabilities.
  • Thumbnail Image
    Item
    Computer Similarity in a Reuse Library System: An AI-based Approach
    (1991) Ostertag, Eduardo J.; Hendler, James A.; Prieto-Diaz, Ruben; Braun, Christine; ISR
    This paper presents an AI-based library system for software reuse, called AIRS, that allows a developer to browse a software library in search of components that best meet some stated requirement. A component is described by a set of (feature,term) pairs. A feature represents a classification criterion, and is defined by a set of related terms. AIRS also allows for the representation of packages, that is, logical units that group a set of related components. As with components, packages are described in terms of features. Unlike components, a package description includes a set of member components. Candidate reuse components (and packages) are selected from the library based on the degree of similarity between their descriptions and a given target description. Similarity is quantified by a non-negative magnitude (called distance) that represents the expected effort required to obtain the target given a candidate. Distances are computed by functions called comparators. Three such functions are presented: the subsumption, the closeness, and the package comparators. We present a formalization of the concepts on which the AIRS classification approach is based. The functionality of a prototype implementation of the AIRS system is illustrated by application to two different software libraries: a set of Ada packages for data structure manipulation, and a set of C components for use in Command, Control, and Information Systems. Finally, we discuss some of the ideas we are currently exploring to automate the construction of AIRS classification libraries.
  • Thumbnail Image
    Item
    Knowledge Strata Reactive Planning with a Multi-level Architecture
    (1990) Spector, L.; Hendler, James A.; ISR
    This report demonstrates the use of "multi-level" or "layered" knowledge representation in Artificial Intelligence planning systems. Although multi-level representation schemes have been in use since the earliest days of AI, certain principles and advantages of knowledge stratification have never been made fully explicit. In this paper we examine issues of multi-level knowledge representation in the context of "reactive planning systems"; that is, in systems which extend the applicability of AI planning systems to complex, dynamic domains. The complexity and real-time requirements of reactive planning have lead several researchers to propose multi-level approaches. Our aim is to improve upon the state of the art in reactive planning by bringing to bear an analysis of the principles of multi-level event and action representation. Our work has lead to the implementation of a prototype architecture (called APE, for Abstraction-Partitioned Evaluator) and, within this architecture, a reactive planner (HomeBot) which operates in a household task domain.
  • Thumbnail Image
    Item
    Planning in Uncertain, Unpredictable or Changing Environments
    (1990) Hendler, James A.; ISR
    This report is a compendium of the extended abstracts submitted by participants at the 1990 AAAI Spring Symposium entitled Planning in Uncertain, Unpredictable or Changing environments. The papers concentrate on extending planning systems and/or intelligent agent architectures for use in dynamic domains. Three main themes include: the integration of planning and machine learning, the use of probabilistic and decision-theoretic information during planning, and the integration of planning with reaction.
  • Thumbnail Image
    Item
    Exploiting Limited Interactions in Plan Optimization
    (1990) Yang, Q.; Nau, D.S.; Hendler, James A.; ISR
    Past Planning systems have generally focused on structures capable of working in all domains (domain-independent planning) or on specific heuristics for a particular applied domain (domain-dependent planning). An alternate approach is to abstract the kinds of goal and subgoal interactions that occur in some set of related problem domains, and develop planning techniques capable of performing relatively efficiently in all domains in which no other kinds of interactions occur. In this paper we will demonstrate this approach on a particular formulation of multiple-goal planning problems. In particular, we demonstrate that for cases where multiple-goal planning can be performed by generating individual separate plans for each goal independently and then optimizing the conjunction, we can define a set of limitations on the allowable interactions between goals that allow efficient planning to occur where the restrictions hold. We further argue that these restrictions are satisfied across a significant class of planning domains. We present algorithms which are efficient for special cases of multiple-goal planning, propose a heuristic search algorithm that performs well in a more general case, and describe a statistical study that demonstrates the efficiency of this search algorithm.