Institute for Systems Research

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

Browse

Author: search.filters.author.Hendler, James A.

Search Results

Now showing 1 - 10 of 21
  • Thumbnail Image
    Item
    Language, Behaviors, Hybrid Architectures and Motion Control
    (1997) Manikonda, Vikram; Krishnaprasad, Perinkulam S.; Hendler, James A.; ISR
    In 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.
  • Thumbnail Image
    Item
    Advances in High Performance Knowledge Representation
    (1996) Stoffel, K.; Taylor, M.; Hendler, James A.; Saltz, J.; Andersen, William; ISR
    Real 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.
  • Thumbnail Image
    Item
    UM Translog: A Planning Domain for the Development and Benchmarking of Planning Systems
    (1995) Andrews, Scott; Kettler, Brian; Erol, Kutluhan; Hendler, James A.; ISR
    The 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.

  • Thumbnail Image
    Item
    Using the Parka Parallel Knowledge Representation System (Version 3.2)
    (1995) Kettler, Brian; Andersen, William; Hendler, James A.; Luke, Sean; ISR
    Parka is a symbolic, semantic network knowledge representation system that takes advantage of the massive parallelism of supercomputers such as the Connection Machine. The Parka language has many of the features of traditional semantic net/frame-based knowledge representation languages but also supports several kinds of rapid parallel inference mechanisms that scale to large knowledge-bases of hundreds of thousands of frames or more. Parka is intended for general-purpose use and has been used thus far to support, A.I. systems for case-based reasoning and data mining.

    This document is a user manual for the current version of Parka, version 3.2. It describes the Parka language and presents some examples of knowledge representation using Parka. Details about the parallel algorithms, implementation, and empirical results are presented elsewhere.

  • Thumbnail Image
    Item
    A Critical Look at Critics in HTN Planning
    (1995) Erol, Kutluhan; Hendler, James A.; Nau, D.S.; Tsuneto, R.; ISR
    Detecting 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.
  • Thumbnail Image
    Item
    A Motion Description Language and a Hybrid Architecture for Motion Planning with Nonholonomic Robots
    (1995) Manikonda, Vikram; Krishnaprasad, Perinkulam S.; Hendler, James A.; ISR
    This 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.
  • Thumbnail Image
    Item
    Complexity Results for HTN Planning
    (1995) 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 (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.

  • Thumbnail Image
    Item
    Semantics for Hierarchical Task-Network Planning
    (1995) Erol, Kutluhan; Hendler, James A.; Nau, Dana S.; ISR
    One 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.

  • Thumbnail Image
    Item
    Supervenient Hierarchies of Behaviors: Lessons Learned from a Vacuuming Robot
    (1994) Seeliger, O.; Hendler, James A.; ISR
    In 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.
  • 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.