×

zbMATH — the first resource for mathematics

Planning as heuristic search. (English) Zbl 0971.68146
Summary: In the AIPS98 Planning Contest, the hsp planner showed that heuristic search planners can be competitive with state-of-the-art Graphplan and sat planners. Heuristic search planners like hsp transform planning problems into problems of heuristic search by automatically extracting heuristics from Strips encodings. They differ from specialized problem solvers such as those developed for the 24-Puzzle and Rubik’s Cube in that they use a general declarative language for stating problems and a general mechanism for extracting heuristics from these representations. In this paper, we study a family of heuristic search planners that are based on a simple and general heuristic that assumes that action preconditions are independent.
The heuristic is then used in the context of best-first and hill-climbing search algorithms, and is tested over a large collection of domains. We then consider variations and extensions such as reversing the direction of the search for speeding node evaluation, and extracting information about propositional invariants for avoiding dead-ends. We analyze the resulting planners, evaluate their performance, and explain when they do best. We also compare the performance of these planners with two state-of-the-art planners, and show that the simplest planner based on a pure best-first search yields the most solid performance over a large set of problems. We also discuss the strengths and limitations of this approach, establish a correspondence between heuristic search planning and Graphplan, and briefly survey recent ideas that can reduce the current gap in performance between general heuristic search planners and specialized solvers.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68P10 Searching and sorting
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahuja, R.; Magnanti, T.; Orlin, J., Network flows: theory, algorithms, and applications, (1993), Prentice-Hall Englewood Cliffs, NJ
[2] Anderson, C.; Smith, D.; Weld, D., Conditional effects in graphplan, (), 44-53
[3] Blum, A.; Furst, M., Fast planning through planning graph analysis, Artificial intelligence, 90, 1-2, 281-300, (1997) · Zbl 1017.68533
[4] Bonet, B.; Geffner, H., Planning as heuristic search: new results, (), 359-371 · Zbl 0971.68146
[5] Bacchus, F.; Kabanza, F., Using temporal logics to express search control knowledge for planning, Artificial intelligence, 116, 1-2, 123-191, (2000) · Zbl 0939.68827
[6] Bonet, B.; Loerincs, G.; Geffner, H., A robust fast action selection mechanism for planning, (), 714-719
[7] Carlier, J.; Pinson, E., An algorithm for solving the job shop problem, Management sci., 35, 2, 164-176, (1989) · Zbl 0677.90036
[8] Culberson, J.; Schaeffer, J., Pattern databases, Comput. intelligence, 14, 3, 318-334, (1998)
[9] Fikes, R.; Nilsson, N., STRIPS: A new approach to the application of theorem proving to problem solving, Artificial intelligence, 2, 189-208, (1971) · Zbl 0234.68036
[10] Geffner, H., Functional strips: A more general language for planning and problem solving, (1999), Logic-based AI Workshop Washington, DC
[11] Gerevini, A.; Schubert, L., Inferring state constraints for domain-independent planning, (), 905-912
[12] Harvey, W.; Ginsberg, M., Limited discrepancy search, (), 607-613
[13] Haslum, P.; Geffner, H., Admissible heuristics for optimal planning, (), 70-82
[14] Holte, R.; Hernadvolgyi, I., A space-time tradeoff for memory-based heuristics, (), 704-709
[15] Hoffmann, J., A heuristic for domain independent planning, and its use in an enforced Hill-climbing algorithm, (), 216-227 · Zbl 0983.68740
[16] Van Hentenryck, P.; Simonis, H.; Dincbas, M., Constraint satisfaction using constraint logic programming, Artificial intelligence, 58, 1-3, 113-159, (1992) · Zbl 0782.68028
[17] Junghanns, A.; Schaeffer, J., Domain-dependent single-agent search enhancements, (), 570-575
[18] Kambhampati, S.; Sanchez Nigenda, R., Distance based goal ordering heuristics for graphplan, (), 315-322
[19] Koehler, J.; Nebel, B.; Hoffman, J.; Dimopoulos, Y., Extending planning graphs to an ADL subset, (), 273-285
[20] Korf, R., Depth-first iterative-deepening: an optimal admissible tree search, Artificial intelligence, 27, 1, 97-109, (1985) · Zbl 0573.68030
[21] Korf, R., Real-time heuristic search, Artificial intelligence, 42, 2-3, 189-211, (1990) · Zbl 0718.68082
[22] Korf, R., Linear-space best-first search, Artificial intelligence, 62, 1, 41-78, (1993) · Zbl 0778.68079
[23] Korf, R., Finding optimal solutions to Rubik’s cube using pattern databases, (), 700-705
[24] Kautz, H.; Selman, B., Pushing the envelope: planning, propositional logic, and stochastic search, (), 1194-1201
[25] Kautz, H.; Selman, B., Unifying SAT-based and graph-based planning, (), 318-327
[26] Korf, R.; Taylor, L., Finding optimal solutions to the twenty-four puzzle, (), 1202-1207
[27] Long, D.; Fox, M., The efficient implementation of the plan-graph in STAN, J. artificial intelligence res., 10, 85-115, (1999) · Zbl 0914.68180
[28] Long, D.; Fox, M., Utilizing automatically inferred invariants in graph construction and search, (), 102-111
[29] Laborie, P.; Ghallab, M., Planning with sharable resources constraints, (), 1643-1649
[30] ()
[31] McDermott, D., A heuristic estimator for means-ends analysis in planning, (), 142-149
[32] McDermott, D., PDDL—the planning domain definition language, (1998), Available at http://www.cs.yale.edu/ dvm
[33] McDermott, D., Using regression-match graphs to control search in planning, Artificial intelligence, 109, 1-2, 111-159, (1999) · Zbl 0916.68145
[34] McDermott, D., The 1998 AI planning systems competition, AI magazine, 21, 2, 35-56, (2000)
[35] Nilsson, N., Principles of artificial intelligence, (1980), Tioga Palo Alto, CA · Zbl 0422.68039
[36] Nguyen, X.; Kambhampati, S., Extracting effective and admissible heuristics from the planning graph, ()
[37] Newell, A.; Simon, H., GPS: A program that simulates human thought, (), 279-293
[38] Newell, A.; Simon, H., Human problem solving, (1972), Prentice-Hall Englewood Cliffs, NJ
[39] Pearl, J., Heuristics, (1983), Morgan Kaufmann San Francisco, CA
[40] Pednault, E., ADL: exploring the middle ground between strips and the situation calculus, (), 324-332
[41] Prieditis, A., Machine discovery of effective admissible heuristics, Machine learning, 12, 117-141, (1993)
[42] Rintanen, J., A planning algorithm not based on directional search, (), 617-624
[43] Refanidis, I.; Vlahavas, I., GRT: A domain independent heuristic for strips worlds based on greedy regression tables, (), 346-358
[44] Sen, A.; Bagchi, A., Fast recursive formulations for BFS that allow controlled used of memory, (), 297-302
[45] van Beek, P.; Chen, X., Cplan: A constraint programming approach to planning, (), 585-590
[46] Weld, D., An introduction to least commitment planning, AI magazine, 15, 4, 27-61, (1994)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.