Author name cluster

Kutluhan Erol

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

AIJ Journal 1995 Journal Article

Complexity, decidability and undecidability results for domain-independent planning

Kutluhan Erol
Dana S. Nau
V.S. Subrahmanian

In this paper, we examine how the complexity of domain-independent planning with STRIPS-style 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 (1987), and clear up some difficulties with his undecidability theorems. For those cases where planning is decidable, we explain 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. • • whether or not the operators can have conditional effects.

Details DOI

AAAI Conference 1994 Conference Paper

HTN Planning: Complexity and Expressivity

Kutluhan Erol

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. networks are required to be totally ordered, and (3) whether variables are allowed. From this table, we can draw the following conclusions:

PDF Details

ICAPS Conference 1994 Conference Paper

UMCP: A Sound and Complete Procedure for Hierarchical Task-network Planning

Kutluhan Erol
James A. Hendler
Dana S. Nau

One big obstacle to understanding the nature of hierarchical task network(HTN)planning has been the lack of a dear theoretical framework. In particular, no one has yet presented a clear and concise HTNalgorithm that is sound and complete. In this paper, we present a formal syntax and semantics for HTNplanning. Based on this syntax and semantics, we are able to define an algo~thm for HTNplanning and prove it sound m~dcomplete.

Details

AAAI Conference 1992 Conference Paper

On the Complexity of Domain-Independent Planning

Kutluhan Erol

In this paper, we examine how the complexity of domain-independent planning with STRIPS-Style operators depends on the nature of the planning operators. We show how the time complexity varies depending on a wide variety of conditions: whether or not delete lists are allowed; whether or not negative preconditions are allowed; whether or not the predicates are restricted to be propositions (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.

PDF Details