Institute for Systems Research

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

Browse

Author: search.filters.author.Erol, Kutluhan

Search Results

Now showing 1 - 8 of 8
  • Thumbnail Image
    Item
    AVIS: An Advanced Video Information System
    (1997) Adali, Sibel; Candan, K. Selcuk; Erol, Kutluhan; Subrahmanian, V.S.; ISR
    During the last few years, the advent of the CD-Rom, and the introduction of high bandwidth communications networks has caused a spectacular explosion in the availability of large video- libraries. While a great deal of effort has been invested in problems of how to effectively utilize bandwidth to communicate large bodies of data across the network, relatively little effort has gone into how to organize, and access, video databases. In this paper, we describe how video data may be organized and structured so as to facilitate queries. We develop a formal model of video data and show how spatial data structures, suitably modified, provide an elegant way of storing such data. We develop algorithms to process various kinds of video queries and show that in most cases, the complexity of these algorithms is linear. We develop algorithms to update these video databases. A prototype system called AVIS ("Advanced Video Information System") has been designed at the University of Maryland based on these concepts.
  • Thumbnail Image
    Item
    Hierarchical Task Network Planning: Formalization, Analysis, and Implementation
    (1996) Erol, Kutluhan; Nau, D.; Hendler, J.; ISR
    Planning is a central activity in many areas including robotics, manufacturing, space mission sequencing, and logistics. as the size and complexity of planning problems grow, there is great economic pressure to automate this process in order to reduce the cost of planning effort, and to improve the quality of produced plans.

    AI planning research has focused on general-purpose planning systems which can process the specifications of an application domain and generate solutions to planning problems in that domain. Unfortunately, there is a big gap between theoretical and application oriented work in AI planning. The theoretical work has been mostly based on state-based planning, which has limited practical applications. The application- oriented work has been based on hierarchical task network (HTN) planning, which lacks a theoretical foundation. As a result, in spite of many years of research, building planning applications remains a formidable task.

    The goal of this dissertation is to facilitate building reliable and effective planning applications. The methodology includes design of a mathematical framework for HTN planning, analysis of this framework, development of provably correct algorithms based on this analysis, and the implementation of these algorithms for further evaluation and exploration. The representation, analyses, and algorithms described in this thesis will make it easier to apply HTN planning techniques effectively and correctly to planning applications. The precise and mathematical nature of the descriptions will also help teaching about HTN planning, will clarify misconceptions in the literature, and will stimulate further research.

  • 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
    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
    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
    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
    Complexity, Decidability and Undecidability Results for Domain- Independent Planning
    (1991) Erol, Kutluhan; Nau, D.S.; Subrahmanian, V.S.; ISR
    In this paper, we examine how the complexity of domain- independent planning with STRIPS-like operators depends on the nature of the planning operators.

    We show conditions under which planning is decidable and undecidable. Our results on this topic solve an open problem posed by Chapman [4], and clear up some difficulties with his undecidability theorems.

    For those cases where planning 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 delete lists are allowed; whether or not negative preconditions are allowed; whether or not the predicates are restricted to be propositional (i.e., 0-ary); whether the planning operators are given as part of the input to the planning problem, or instead are fixed in advance.