Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Author: search.filters.author.Erol, KutluhanSubject: search.filters.subject.computational complexity

Search Results

Now showing 1 - 3 of 3
  • 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
    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.