Complexity, decidability and undecidability results for domain-independent planning. (English) Zbl 1013.68548
Summary: 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:
\(\bullet\) whether or not function symbols are allowed;
\(\bullet\) whether or not delete lists are allowed;
\(\bullet\) whether or not negative preconditions are allowed;
\(\bullet\) whether or not the predicates are restricted to be propositional (i.e., 0-ary);
\(\bullet\) whether the planning operators are given as part of the input to the planning problem, or instead are fixed in advance.
\(\bullet\) whether or not the operators can have conditional effects.
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:
\(\bullet\) whether or not function symbols are allowed;
\(\bullet\) whether or not delete lists are allowed;
\(\bullet\) whether or not negative preconditions are allowed;
\(\bullet\) whether or not the predicates are restricted to be propositional (i.e., 0-ary);
\(\bullet\) whether the planning operators are given as part of the input to the planning problem, or instead are fixed in advance.
\(\bullet\) whether or not the operators can have conditional effects.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
References:
| [1] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., (The Design and Analysis of Computer Algorithms (1976), Addison-Wesley: Addison-Wesley Reading, MA) |
| [2] | Bäckström, C.; Klein, I., Planning in polynomial time: the sas-pubs class, Comput. Intell., 7 (1991) |
| [3] | Bylander, T., Complexity results for planning, (Proceedings IJCAI-91. Proceedings IJCAI-91, Sydney, Australia (1991)) · Zbl 0745.68101 |
| [4] | Bylander, T., Complexity results for extended planning, (Proceedings First International Conference on AI Planning Systems (1992)) · Zbl 0745.68101 |
| [5] | Chapman, D., Planning for conjunctive goals, Artif. Intell., 32, 333-379 (1987) · Zbl 0642.68171 |
| [6] | Charniak, E.; McDermott, D., (Introduction to Artificial Intelligence (1985), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0605.68083 |
| [7] | Chenoweth, S. V., On the NP-hardness of blocks world, (Proceedings AAAI-91. Proceedings AAAI-91, Anaheim, CA (1991)), 623-628 |
| [8] | Dean, T. L.; Boddy, M., Reasoning about partially ordered events, Artif. Intell., 36, 375-399 (1988) · Zbl 0688.68083 |
| [9] | K. Erol, J.A. Hendler and D.S. Nau, Complexity results for hierarchical task-network planning (Submitted).; K. Erol, J.A. Hendler and D.S. Nau, Complexity results for hierarchical task-network planning (Submitted). · Zbl 0891.68104 |
| [10] | Erol, K.; Nau, D. S.; Subrahmanian, V. S., Complexity, decidability and undecidability results for domain-independent planning, (Technical Report CS-TR-2797, UMIACS-TR-91-154, SRC-TR-91-96 (1991), Computer Science Department and Institute for Systems Research, University of Maryland: Computer Science Department and Institute for Systems Research, University of Maryland College Park, MD) · Zbl 1013.68548 |
| [11] | Erol, K.; Nau, D. S.; Subrahmanian, V. S., When is planning decidable?, (Proceedings First International Conference on A1 Planning Systems (1992)), 222-227 |
| [12] | Erol, K.; Nau, D. S.; Hendler, J. A., Toward a general framework for hierarchical task-network planning, (Proceedings AAAI Spring Symposium. Proceedings AAAI Spring Symposium, Stanford, CA (1993)) |
| [13] | Fikes, R. E.; Nilsson, N. J., STRIPS: a new approach to the application of theorem proving to problem solving, Artif. Intell., 2, 3/4, 189-208 (1971) · Zbl 0234.68036 |
| [14] | Garey, M. R.; Johnson, D. S., (Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York) · Zbl 0411.68039 |
| [15] | Graham, R. L.; Knuth, D. E.; Patashnik, O., (Concrete Mathematics: A Foundation for Computer Science (1989), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0668.00003 |
| [16] | Gupta, N.; Nau, D. S., Complexity results for blocks-world planning, (Proceedings AAAI-9I. Proceedings AAAI-9I, Anaheim, CA (1991)), Honorable mention for the Best Paper Award |
| [17] | Gupta, N.; Nau, D. S., On the complexity of blocks-world planning, Artif. Intell., 56, 2-3, 223-254 (1992) · Zbl 0785.68046 |
| [18] | Korf, R. E., Planning as search: a quantitative approach, Artif. Intell., 33, 1, 65-88 (1987) |
| [19] | Lifschitz, V., On the semantics of STRIPS, (Allen, J. F.; Hendler, J. A.; Tate, A., Readings in Planning (1990), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 523-530 |
| [20] | McAllester, D.; Rosenblitt, D., Systematic nonlinear planning, (Proceedings AAAI-91. Proceedings AAAI-91, Anaheim, CA (1991)), 634-639 |
| [21] | McDermott, D., Regression planning, Int. J. Intell. Syst., 6, 357-416 (1991) · Zbl 0734.68087 |
| [22] | Minton, S.; Bresna, J.; Drummond, M., Commitment strategies in planning, (Proceedings IJCAI-91. Proceedings IJCAI-91, Sydney, Australia (1991)) |
| [23] | Nau, D. S., On the complexity of possible truth, (Proceedings AAAI Spring Symposium. Proceedings AAAI Spring Symposium, Stanford, CA (1993)) |
| [24] | Nilsson, N. J., (Principles of Artificial Intelligence (1980), Tioga: Tioga Palo Alto) · Zbl 0422.68039 |
| [25] | Pednault, E. P.D., Synthesizing plans that contain actions with context-dependent effects, Comput. Intell., 4, 356-372 (1988) |
| [26] | Peot, M. A., Conditional nonlinear planning, (Proceedings First International Conference on AI Planning Systems (1992)), 189-197 |
| [27] | Sacerdoti, E. D., Planning in a hierarchy of abstraction spaces, Artif. Intell., 5, 115-135 (1974) · Zbl 0288.68052 |
| [28] | Sacerdoti, E. D., (Proceedings IJCAI-75. Proceedings IJCAI-75, Tblisi, Georgia (1975)), 206-214, Originally appeared in: |
| [29] | Shoenfield, J., (Mathematical Logic (1967), Academic Press: Academic Press New York) · Zbl 0155.01102 |
| [30] | Subrahmanian, V. S.; Zaniolo, C., Database updates and AI planning domains, (Technical Report CS-TR-3173, UMIACS-TR-93-118 (1993), Computer Science Department, University of Maryland: Computer Science Department, University of Maryland College Park, MD) |
| [31] | Tate, A.; Hendler, J. A.; Drummond, M., A review of AI planning techniques, (Allen, J. F.; Hendler, J. A.; Tate, A., Readings in Planning (1990), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 26-49 |
| [32] | Tate, A., Generating project networks, (Proceedings IJCAI-77. Proceedings IJCAI-77, Cambridge, MA (1977)) |
| [33] | Wilkins, D. E., Artif. Intell., 22, 3, 269-301 (1984), Originally appeared in: |
| [34] | Yang, Q.; Nau, D. S.; Hendler, J. A., Optimization of multiple-goal plans with limited interaction, (Proceedings DARPA Workshop on Innovative Approaches to Planning, Scheduling and Control (1990)) |
| [35] | Yang, Q.; Nau, D. S.; Hendler, J. A., Merging separately generated plans with restricted interactions, Comput. Intell., 8, 2, 648-676 (1992) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
