On the complexity of domain-independent planning
作者： Dana S. Nau , Kutluhan Erol , V. S. Subrahmanian
DOI:
关键词:
摘要: In this paper, we examine how the complexity of domain-independent planning with STRIPS-style operators depends on nature operators. We show time varies depending a wide variety conditions: • whether or not delete lists are allowed; negative preconditions predicates restricted to be propositions (i.e., 0-ary); given as part input problem, instead fixed in advance.
参考文章(17)
Kutluhan Erol, Dana S. Nau, V.S. Subrahmanian, When is Planning Decidable?**This work was supported in part by NSF Grant NSFD CDR-88003012 to the University of Maryland Systems Research Center, as well as NSF grants IRI-8907890 and IRI-9109755. Artificial Intelligence Planning Systems. pp. 222- 227 ,(1992) , 10.1016/B978-0-08-049944-4.50031-8
Dana Nau, Qiang Yang, James Hendler, Optimization of multiple-goal plans with limited interaction Innovative Approaches to Planning, Scheduling and Control. pp. 160- ,(1990)
Tom Bylander, Complexity results for planning international joint conference on artificial intelligence. pp. 274- 279 ,(1991)
David McAllester, David Rosenblitt, Systematic nonlinear planning national conference on artificial intelligence. pp. 634- 639 ,(1991)
Dana S. Nau, Naresh Gupta, Complexity results for blocks-world planning national conference on artificial intelligence. pp. 629- 633 ,(1991)
Richard Waldinger, Achieving Several Goals Simultaneously Morgan Kaufmann. pp. 250- 271 ,(1981) , 10.1016/B978-0-934613-03-3.50022-2
John Bresina, Steven Minton, Mark Drummond, Commitment strategies in planning: a comparative analysis international joint conference on artificial intelligence. pp. 259- 265 ,(1991)
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
Eugene Charniak, None, Introduction to Artificial Intelligence ,(1985)
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)