Talk:Hierarchical task network

Expressivity of HTN planning and STRIPS planning

I'm not entirely sure I want to open this can of worms, but here goes. Full disclosure: I am one of Dana Nau's former research students; I have never done research in planning complexity; however, I have enough experience in theoretical computer science to talk about complexity results intelligently, and enough experience in planning to talk about HTN planning intelligently.

The Lekavý and Návrat paper starts its alleged proof by stating as fact that "[t]he plan-space of HTN-like planning domain is finite". It is clearly not finite. For example, you can make an HTN with one compound task symbol and one primitive task symbol that includes two decompositions for the compound task symbol: one to itself and the primitive task symbol; one to the primitive task symbol alone. You've just created an infinite plan-space.

The paper criticizes the Erol/Hendler/Nau work by saying "The proof was, however, based on the assumption, that the HTN planner can use an infinite set of symbols to mark the tasks." The proof was clearly not based on this assumption: the HTN planner uses one symbol for each terminal or non-terminal in a context-free grammar, and a context-free grammar is certainly based on a finite number of terminals and non-terminals.

So my proposal is to revert to something to this language: "HTN-like planning is strictly more expressive than STRIPS [reference to the Erol/Hendler/Nau work]", and to delete the reference to the Lekavý and Návrat paper. (Were the papers submitted to KES-AMSTA 2007 even reviewed, or is the citation of this paper essentially an attempt to circumvent WP:NOR?)

Any thoughts? Incremental Improvements (talk) 20:18, 29 May 2009 (UTC)

After reading this over again, my language in "essentially an attempt to circumvent WP:NOR" seems unnecessarily harsh. Sorry about that; I did not mean to imply that the reference to the Lekavý and Návrat paper was added with nefarious intent. What I was trying to convey is that a paper from a symposium whose peer-review process seems to have been inadequate at best should not pull Wikipedia away from the mainstream AI literature. Incremental Improvements (talk) 14:48, 1 June 2009 (UTC)

The proof in the removed paper is based on the assumption, that every implementation of every planner has to use some kind of restrictions to make the computation finite. Based on this assumption, it shows, that both approaches are equally expressive. The paper never stated, that HTN in it's pure form is finite. It states, that every practically usable implementation (called HTN-like planning in this paper) is finite.

For the finite/infinite symbols: The Erol et al. paper states clearly: "Formally, the vocabulary of HTN language L is a tuple <V,C,P,F,T,N>, where ... and N=... is an infinite set of symbols used for labeling tasks." And from the paper it is clear, that these symbols are used to label tasks during computation - not tasks in the domain definition, but instances of tasks, which are a part of the found plan (or part of the found decomposition, to be exact).

What I propose is to modify the statement, so that it is clear, that the "pure" HTN is more expressive, but as a practically usable approaches, their expressivity is identical.

147.175.158.196 (talk) 17:08, 10 June 2009 (UTC)

This is only true if the translation provided by Lekavý and Návrat is a practical method for HTN planning, for which I've seen no results. Ronwalf (talk) 03:33, 4 April 2012 (UTC)

The Lekavý and Návrat paper provides a proof, not a method.147.175.158.189 (talk) 16:20, 8 June 2012 (UTC)

The proof uses a definition of expressiveness that admits non-polynomial encodings. I can use the same method to proof that STRIPS planning is no more "expressive" than SAT, or any other decision problem. Here's a more specific counter example: Totally-ordered propositional HTN planning is EXP-time complete . If you can provide a poly-time transform from totally-ordered HTNs to propositional STRIPS planning (PSPACE-complete), all the more power to you. Otherwise, for any bounded definition of expressiveness, HTN planning is in fact more expressive than classical planning. The statement of equivalence is sloppy and should be removed. Ronwalf (talk) 20:44, 27 May 2014 (UTC)

Your definition of expressivity is different. In fact, both definitions are used and make sense. The one in the paper is based on WHAT can be expressed. Your definition is (probably) based on HOW FAST something can be expressed. I write probably, because in your thesis, you don't write which definition you use. The HOW FAST definition is usually used for programming languages to say, how fast a programmer can write a program.

Anyway, if you disagree with the definition, you should provide a reference which says, the definition is wrong. It is easy to change an axiom and then show that the original reasoning is not correct with the new axiom. If you provide such reference, we can change the wording from current "the same expressivity (i.e. can solve the same domains)" to simply "can solve the same domains", so that we would avoid the problematic term "expressivity".

Btw. I am glad you used the depth limitation mechanism proposed by the Lekavy & Navrat paper and you also use a similar algorithm for simulating of HTN by STRIPS. But a citation of that paper would probably not hurt ;) 85.237.227.35 (talk) 18:15, 22 September 2014 (UTC)

If you would like to argue language expressivity, then totally-ordered (and thus decidable) HTN problems can encode context-free grammars, and thus no encoding into classical planning has the same set of solutions as the original problem. Ronwalf (talk) 23:09, 15 December 2014 (UTC)

OK, HTN can recognise CF languages, no problem with that. And my private opinion is, that HTN can recognise even more than just CF languages. But please, look at the Lekavy & Navrat paper, Theorem 2. STRIPS can emulate a Turing machine with finite tape. That means, it can emulate LBA (which is a kind of Turing machine with finite tape, but has another restriction, that tape length is a linear function of input length). That means STRIPS can recognise (at least) CS languages.147.175.167.208 (talk) 20:44, 25 January 2015 (UTC)

I have read it. I don't cite it because the conclusions the authors make are enormously misleading. Erol takes the absolute weakest definition of expressivity ("is there a decidable transformation from HTN to STRIPS"), and answers it by showing that HTN planning is undecidable. Lekavy took the same definition, and flipped its purpose on its head, saying that if you place a time or space bound on a Turing Machine, questions about it suddenly become decidable. This is really, really obvious, to the point that the results of the Lekavy paper can be replicated by two line proof. That's what happens when you adopt a definition of expressivity that literally can't distinguish between any decidable classes of problems. You asked me to point to a more accepted definition of expressivity, and I pointed to Chomsky hierarchy. Höller et. al. show that STRIPS and classical planning generate different grammars over the solutions of actions, and even decidable fragments of HTN planning are more expressive in that framework. HTN and classical planning are separate in their complexity classes, in grammars over their solution sets, and in the algorithms needed to efficiently find solutions. Ronwalf (talk) 19:52, 26 January 2015 (UTC)

Finally, we're getting off topic. The original question was whether they solve the same problems. The Lekavy paper says yes, but only if we are executing them on arbitrarily space-bounded Turing machines and don't care about efficiency . Indeed, finding solutions for partially-ordered tail-recursive propositional HTN problems is in EXPSPACE (Alford 2012, SoCS), and the Lekavy translation of said problems would need a doubly-exponential amount of space to be sound and complete. I have my doubts on how "practical" this is, especially when even low-order polynomial increases in instance size have deleterious effects on current classical planners. There are currently many projects using HTN planners, and many using PDDL (a STRIPS successor). The Lekavy paper, despite their claims, is not evidence that the two are interchangeable. Ronwalf (talk) 22:49, 26 January 2015 (UTC)

OK, you make several claims, so I will go through some them one by one. I don't agree with few of them, but please don't take it as an offense. Just discussing.

1. "Erol takes the absolute weakest definition of expressivity ("is there a decidable transformation from HTN to STRIPS"), <...> Lekavy took the same definition <...>" - Thank you for agreeing on this. So... I guess we have a common definition of expressivity now. Well, at least the 2 papers might have.

2. "saying that if you place a time or space bound on a Turing Machine, questions about it suddenly become decidable" - No, the bound is placed on HTN, not TM. And I think you have reversed the implication here. Making HTN decidable (somehow) is an assumption and the Lekavy and Navrat paper writes about what happens if we do that.

3. "That's what happens when you adopt a definition of expressivity that literally can't distinguish between any decidable classes of problems." - actually, it can distinguish. If we are talking about the definition you wrote ("is there a decidable transformation from <...> to <...>"). For example there is no decidable translation from LBA to FSM (i.e. from CS to REG). (Can I take any LBA and transform it to a FSM that recognises the same language? I don't think so.) But, based on theorem 2 from Lekavy and Navrat, I can take any LBA and transform it to a STRIPS domain that recognises the same language.

4. "and I pointed to Chomsky hierarchy" - Yes, you did. But somehow you ignore the fact, that STRIPS is at least CS.

5. "Höller et. al. show that STRIPS and classical planning generate different grammars over the solutions of actions, and even decidable fragments of HTN planning are more expressive in that framework" - Please, provide the paper that claims that. The Höller et. al. paper you cited before only makes claims about HTN, almost exclusively. I don't see there any claims about expressivity of classical (not-HTN) planning. Of course, I might have misread it, so please point me to the theorem making this claim about classical planning.

6. "The Lekavy paper says yes, but only if we are executing them on arbitrarily space-bounded Turing machines" - No. The Lekavy and Navrat paper shows, that an arbitrarily space-bounded Turing machine can be executed in STRIPS. The paper makes no claim about where STRIPS or HTN is executed.

7. "I have my doubts on how "practical" this is" - OK, your doubts are noted. But practicallity and expressivity are not the same thing. Plus you shouldn't really use the construction from a proof about existence to make claims about minimal possible complexity.

8. "I don't cite it because the conclusions the authors make are enormously misleading." - Articles are cited because you used them, not because you agree with them. If you use a construction mechanism proposed by some paper, it doesn't become your own idea, just because you don't agree with the conclusions... Seeing people doing this makes me kind of sad.

147.175.146.180 (talk) 19:27, 5 February 2015 (UTC)

1. On definitions of expressivity. Actually, I took a look back at the Erol 1994 tech report and the 1996 journal paper, and I seem to have misremembered them. He defines three different forms of expressivity: Model-theoretic, operational, and complexity-based expressivity. The last one is the only one he answered with the proof of undecidability, and its a more precise definition of expressivity than the space-limited def in the 1994 NCAI paper (though the NCAI definition preserves the solution set, not just solvability).

Since the Lekavy paper cites that proof and does not cite any other definition of expressivity, I assume it is also using the complexity definition (especially since they explicitly state their translation is poly-time, which we'll get to below).

2. On bounded HTN planning. There are numerous ways to make HTN planning decidable. Lekavy picks three (acyclic, totally-ordered, and bounded depth, which I guess devolves to a form of acyclic. Critically, they claim to be able to translate HTNs with any of these restrictions into STRIPS in low-order polynomial time. I give a reference below showing that this is not possible unless PSPACE=NEXPTIME. In specific, by making a new task symbol only for each direct parent, the translation falls apart for partially-ordered HTNs with a hierarchy of depth >2, and after that it would allow inappropriate subtask sharing between tasks. I also don't see any method for enforcing the ordering of the subtasks (total or partial)!

3. On simulating an LBA with propositional STRIPS. If that's all we're talking about, we should be referencing Bylander (1994), also cited in more detail below. However, (a) this doesn't show that you can translate an acyclic HTN into STRIPS in low-order polynomial time(see answer 8), and (b) translations of totally-ordered HTN planning into STRIPS cannot preserve the set of solutions.

4-5. Take a closer look at the Höller paper. It is talking about the languages expressed by the solution set. There are trivial encoding of STRIPS into both task-insertion HTN planning that preserves action grammar, and so this is an upper bound on the expressivity of STRIPS. A better reference for this would have been the Erol 1994 HTN paper. Lekavy also cites this as showing that solution sets to STRIPS are regular

6-7. On the Lekavy translation of HTNs to STRIPS. I'm not using it to argue minimum complexity. The specific line in the article we are talking about mentions "HTN planning, as practically used, ...can solve the same domains as STRIPS. This line specifically brings up practicality, but then answers it by citing a proof which is imminently unpractical given its exponential blowup.

8. "Articles are cited because you used them." In the case of my translation, I did not use the Lekavy paper. The PDDL translation was roughly contemporaneous with the Lekavy paper (started in early 2007, published in 2009), and focuses on totally-ordered tail-recursive HTN planning (bounded non-tail recursion, not overall acyclicity).

More over, there's a good case that the Lekavy paper should be retracted. Take one of the central claims of the paper: "In the next sections, we will show how to transform a HTN-like domain into a STRIPS-like domain in low-order polynomial time, using STRIPS for emulating the HTN decomposition." The definition of "HTN-like" includes totally-ordered HTN problems, which are EXPTIME-complete for propositional and 2EXPTIME-complete for lifted HTN planning. Since Lekavy did not show that EXPSPACE=2EXPTIME, Lekavy's main claim of a polynomial translation is false, and so are conclusions derived from that. The same goes for acyclic problems which are partially ordered (NEXPTIME- and 2NEXPTIME-complete for propositional and lifted problems, respectively). It repeats a similarly false claim in the conclusions.

There's another statement in the conclusions, specifically, "Finally, this paper shows that STRIPS expressivity is equal to the expressivity of a Turing machine with finite tape, i.e. all problems that can be solved by a (common) computer can also be solved by STRIPS." Although it presented a proof (Theorem 2), this proof is not novel. It's been done at least twice before: in the (uncited) proof of Erol's that lifted classical planning is EXSPACE-complete or, more relevantly, Bylander's proof that propositional STRIPS is PSPACE-complete.

Thus, given that (a) the Lekavy translation is not correct for partially-ordered acyclic HTNs (and is broken, but potentially fixable for acyclic totally-ordered HTNs) and (b) the Lekavy proof of simulating an LBA is a decade and a half away from being novel, there's not much left to the paper.

Ronwalf (talk) 00:42, 6 February 2015 (UTC)

After publication season ends, I plan to this reorganize this section to provide a coherent arguments against the specific statement in the Wikipedia article. However, we've drifted way off the original topics, and are now talking about separate issues as they relate to the Lekavy paper and HTN planning more generally. I will respond to points here, but this is a bit inappropriate of a forum. You should be able to find my email address with ease from my homepage (linked to from Google Scholar). Please email me there, I'd be happy to continue this discussion. Ronwalf (talk) 15:17, 6 February 2015 (UTC)

You are right, we have drifted off. And this is definitely not the forum for this discussion, as we are far beyond WP:NOR now. Moreover it becomes very time-consuming for me. Therefore I withdraw all my objections here. As far as I am concerned, I trust you to modify/improve the article based on the current state-of-art knowledge and without bias. Based on your articles, you seem to be a capable researcher in this field. So you are free to do the modifications you want.

Even though I don't agree with several of your arguments, I will only answer number 8. here. I want to say I am sorry for implying any form of scientific misconduct. I didn't realize how offensive that actually might have been. Sorry for that.147.175.146.180 (talk) 18:07, 7 February 2015 (UTC)

Defining STRIPS

Someone who knows more about the STRIPS planner should add a quick introduction to STRIPS, as it's referenced throughout the article with no definition.209.65.56.40 (talk) 01:35, 15 November 2018 (UTC)