Browsing by Author "Hendler, James A."
Now showing 1 - 20 of 21
Results Per Page
Sort Options
Item Advances in High Performance Knowledge Representation(1996) Stoffel, K.; Taylor, M.; Hendler, James A.; Saltz, J.; Andersen, William; ISRReal world applications are demanding that KR systems provide support for knowledge bases containing millions of assertions. We present Parka-DB, a high-performance reimplementation of the Parka KR language which uses a standard relational DBMS. The integration of a DBMS and the Parka KR language allows us to efficiently support complex queries on extremely large KBs using a single processor, as opposed to our earlier massively parallel system. In addition, the system can make good use of secondary memory, with the whole system needing less than 16MB of RAM to hold a KB of over 2,000,000 assertions. We demonstrate empirically that this reduction in primary storage requires only about 10% overhead in time, and decreases the load time of very large KBs by more than two orders of magnitude.Item BackProp: A Tool for Learning About Connectionist Architectures.(1988) Pollack, Jordan; Evett, Matthew; Hendler, James A.; ISRThis paper provides an implementation, in Common Lisp, of an "epoch learning algorithm," a simple modification of the standard back-propagation algorithm. This implementation is not intended to be a general purpose, high powered back-propagation learning system. Rather, this paper seeks only to provide a simple implementation of a popular and easily understood connectionist learning algorithm. It is intended to be a, teaching tool for AI researchers wishing to familiarize themselves or their students with back-propagation in a language with which they are comfortable.Item Complexity Results for HTN Planning(1995) Erol, Kutluhan; Hendler, James A.; Nau, D.S.; ISRMost practical work on AI planning systems during the last fifteen years has been based on hierarchical task network (HTN) 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.Item Complexity Results for HTN Planning(1994) Erol, Kutluhan; Hendler, James A.; Nau, D.S.; ISRMost 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.Item Complexity, Decidability and Undecidability Results for Rule- Based Expert Systems(1992) Blanksteen, Scott; Hendler, James A.; Nau, Dana S.; ISRWe 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.Item Computer Similarity in a Reuse Library System: An AI-based Approach(1991) Ostertag, Eduardo J.; Hendler, James A.; Prieto-Diaz, Ruben; Braun, Christine; ISRThis 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.Item A Critical Look at Critics in HTN Planning(1995) Erol, Kutluhan; Hendler, James A.; Nau, D.S.; Tsuneto, R.; ISRDetecting interactions and resolving conflicts in one of the key issues for generative planning systems. Hierarchical Task Network (HTN) planning systems use critics for this purpose. Critics have provided extra efficiency and flexibility to HTN planning systems, but their procedural -- and sometimes domain- specific - - nature has not been amenable to analytical studies. As a result, little work is available on the correctness or efficiency of critics. This paper describes a principled approach to handling conflicts, as implemented in UMCP, an HTN planning system. Critics in UMCP have desirable properties such as systematicity, and the preservation of soundness and completeness.Item Exploiting Limited Interactions in Plan Optimization(1990) Yang, Q.; Nau, D.S.; Hendler, James A.; ISRPast 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.Item Integrating Neural Network and Export Reasoning: An Example(1991) Hendler, James A.; Dickens, Leonard; ISRIn 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.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; ISROur 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.Item Knowledge Strata Reactive Planning with a Multi-level Architecture(1990) Spector, L.; Hendler, James A.; ISRThis 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.Item Language, Behaviors, Hybrid Architectures and Motion Control(1997) Manikonda, Vikram; Krishnaprasad, Perinkulam S.; Hendler, James A.; ISRIn this paper we put forward a framework that integrates features of reactive planning models with modern control-theory-based approaches to motion control of robots. We introduce a motion description language, MDLe, that provides a formal basis for robot programming using behaviors, and at the same time permits incorporation of kinematic and dynamic models of robots given in the form of differential equations. In particular, behaviors for robots are formalized in terms of kinetic state machines, a motion description language, and the interaction of the kinetic state machine with real-time information from (limited range) sensors. This formalization allows us to create a mathematical basis for the study of such systems, including techniques for integrating sets of behaviors. In addition we suggest optimality criteria for comparing both atomic and compound behaviors in various environments. We demonstrate the use of MDLe in the area of motion planning for nonholonomic robots. Such models impose limitations on the stabilizability via smooth feedback; piecing together open loop and closed loop trajectories becomes essential in these circumstances, and MDLe enables one to describe such piecing together in a systematic manner. A reactive planner using the formalism of the paper is described. We demonstrate obstacle avoidance with limited range sensors as a test of this planner.Item Linking Symbolic and Subsymbolic Computing(1993) Wilson, A.; Hendler, James A.; ISRThe 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.Item A Motion Description Language and a Hybrid Architecture for Motion Planning with Nonholonomic Robots(1995) Manikonda, Vikram; Krishnaprasad, Perinkulam S.; Hendler, James A.; ISRThis paper puts forward a formal basis for behavior-based robotics, using techniques that have been successful in control- theory-based approaches for steering and stabilizing robots that are subject to nonholonomic constraints. In particular, behaviors for robots are formalized in terms of kinetic state machines, a motion description language, and the interaction of the kinetic state machine with real-time information from (limited range) sensors. This formalization allows us to create a mathematical basis for the study of such systems, including techniques for integrating sets of behaviors. In addition we suggest optimality criteria for comparing both atomic and compound behaviors in various environments. A hybrid architecture for the implementation of path planners that uses the motion description language is also presented.Item Planning in Uncertain, Unpredictable or Changing Environments(1990) Hendler, James A.; ISRThis 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.Item PRA: Massively Parallel Heuristic Search(1991) Evett, Matthew; Hendler, James A.; Mahanti, Ambuj; Nau, D.; ISRIn 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.Item Semantics for Hierarchical Task-Network Planning(1995) Erol, Kutluhan; Hendler, James A.; Nau, Dana S.; ISROne big obstacle to understanding the nature of hierarchical task network (HTN) planning has been the lack of a clear theoretical framework. In particular, no one has yet presented a clear and concise HTN algorithm that is sound and complete. In this paper, we present a formal syntax and semantics for HTN planning. Based on this syntax and semantics, we are able to define an algorithm for HTN planning and prove it sound and complete. We also develop several definitions of expressivity for planning languages and prove that HTN planning is strictly more expressive than STRIPS- style planning according to those definitions.Item Supervenient Hierarchies of Behaviors: Lessons Learned from a Vacuuming Robot(1994) Seeliger, O.; Hendler, James A.; ISRIn this paper we describe the use of behavior hierarchies based on ﲭerging two models of multi-layer architecture -- the supervenience model of [1] and the subsumption model of [4]. The behavior hierarchy approach allows us to use the robustness of reactivity in behavior design. It also encourages the design of modular behaviors that can be reused or more importantly recalibrated in different situations. We argue that behavior hierarchies extend our ability to design and program effective solutions that do not require any explicit planning. We also describe ongoing work in using this model for integrating planning and reacting. This work is being used in support of an implemented system in which an autonomous mobile robot performs a vacuuming task.Item Towards Dynamic Planning.(1987) Sanborn, J.C.; Hendler, James A.; ISRMany desirable application domains for planning are inherently dynamic: representation of the domain is ill-specified or incomplete, the existence or verity of information changes with time, and situations arise during plan execution that were not taken into account at plan generation time. Unfortunately, the traditional approach to planning and problem solving has concentrated most heavily on generating plans, with little attention given to problems associated with plan execution. As a result, these planners have not been generally successful when applied to many physical domains.Item UM Translog: A Planning Domain for the Development and Benchmarking of Planning Systems(1995) Andrews, Scott; Kettler, Brian; Erol, Kutluhan; Hendler, James A.; ISRThe last twenty years of AI planning research has discovered a wide variety of planning techniques such as state-space search, hierarchical planning, case-based planning and reactive planning. These techniques have been implemented in numerous planning systems (e.g., [12,8,9,10,11]). Initially, a number of simple toy domains have been devised to assist in the analysis and evaluation of planning systems and techniques. The most well know examples are ﲂlocks World and ﲔowers of Hanoi . As planning systems grow in sophistication and capabilities, however, there is a clear need for planning benchmarks with matching complexity to evaluate those new features and capabilities. UM Translog is a planning domain designed specifically for this purpose.UM Translog was inspired by the CMU Transport Logistics domain developed by Manuela Veloso. UM Translog is an order of magnitude larger in size (41 actions versus 6), number of features and types interactions. It provides a rich set of entities, attributes, actions and conditions, which can be used to specify rather complex planning problems with a variety of plan interactions. The detailed set of operators provides long plans (40 steps) with many possible solutions to the same problem, and thus this domain can also be used to evaluate the solution quality of planning systems. The UM Translog domain has been used with the UMCP, UM Nonlin, and CaPER planning systems thus far.