Abstract
In the recent AIPS98 Planning Competition, the hsp planner, based on a forward state search and a domain-independent heuristic, showed that heuristic search planners can be competitive with state of the art Graphplan and Satisfiability planners. hsp solved more problems than the other planners but it often took more time or produced longer plans. The main bottleneck in hsp is the computation of the heuristic for every new state. This computation may take up to 85% of the processing time. In this paper, we present a solution to this problem that uses a simple change in the direction of the search. The new planner, that we call hspr, is based on the same ideas and heuristic as hsp , but searches backward from the goal rather than forward from the initial state. This allows hspr to compute the heuristic estimates only once. As a result, hspr can produce better plans, often in less time. For example, hspr solves each of the 30 logistics problems from Kautz and Selman in less than 3 seconds. This is two orders of magnitude faster than blackbox. At the same time, in almost all cases, the plans are substantially smaller. hspr is also more robust than hsp as it visits a larger number of states, makes deterministic decisions, and relies on a single adjustable parameter than can be fixed for most domains. hspr, however, is not better than hsp accross all domains and in particular, in the blocks world, hspr fails on some large instances that hsp can solve. We discuss also the relation between hspr and Graphplan, and argue that Graphplan can also be understood as a heuristic search planner with a precise heuristic function and search algorithm.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anderson, C., Smith, D., Weld, D.: Conditional effects in graphplan. In: Proc. AIPS 1998. AAAI Press, Menlo Park (1998)
Blum, A., Furst, M.: Fast planning through planning graph analysis. In: Proceedings of IJCAI 1995, Montreal, Canada (1995)
Bonet, B., Geffner, H.: HSP: Planning as heuristic search (1998), http://www.ldc.usb.ve/~hector
Bacchus, F., Kabanza, F.: Using temporal logics to express search control knowledge for planning (1998) (Submitted), At http://www.lpaig.uwaterloo.ca/~fbacchus
Bonet, B., Loerincs, G., Geffner, H.: A robust and fast action selection mechanism for planning. In: Proceedings of AAAI 1997 (1997)
Geffner, H.: Functional strips: a more general language for planning and problem solving. Presented at the Logic-based AI Workshop, Washington D.C. (June 1999), At http://www.ldc.usb.ve/~hector
Harvey, W., Ginsberg, M.: Limited discrepancy search. In: Proc. IJCAI 1995 (1995)
Junghanns, A., Schaeffer, J.: Domain-dependent single-agent search enhancements. In: Proc. IJCAI 1999. Morgan Kaufmann, San Francisco (1999)
Kambhampati, S., Lambrecht, E., Parker, E.: Understanding and extending Graphplan. In: Steel, S. (ed.) ECP 1997. LNCS (LNAI), vol. 1348. Springer, Heidelberg (1997)
Koehler, J., Nebel, B., Hoffman, J., Dimopoulos, Y.: Extending planning graphs to an ADL subset. In: Steel, S. (ed.) ECP 1997. LNCS (LNAI), vol. 1348. Springer, Heidelberg (1997)
Korf, R.: Real-time heuristic search. Art. Intelligence 42, 189–211 (1990)
Korf, R.: Linear-space best-first search. Art. Intelligence 62, 41–78 (1993)
Korf, R.: Finding optimal solutions to to Rubik’s cube using pattern data- bases. In: Proceedings of AAAI 1998, pp. 1202–1207 (1998)
Kautz, H., Selman, B.: Pushing the envelope: Planning, propositional logic, and stochastic search. In: Proceedings of AAAI 1996 (1996)
Kautz, H., Selman, B.: Unifying SAT-based and Graph-based planning. In: Proceedings IJCAI 1999 (1999)
Korf, R., Taylor, L.: Finding optimal solutions to the twenty-four puzzle. In: Proceedings of AAAI 1996, pp. 1202–1207. MIT Press, Cambridge (1996)
Long, D., Fox, M.: The efficient implementation of the plan-graph. JAIR (1999)
McDermott, D.: A heuristic estimator for means-ends analysis in planning. In: Proc. Third Int. Conf. on AI Planning Systems, AIPS 1996 (1996)
McDermott, D.: AIPS 1998 Planning Competition Results (1998), http://ftp.cs.yale.edu/mcdermott/aipscomp-results.html
Nilsson, N.: Principles of Artificial Intelligence. Tioga (1980)
Pearl, J.: Heuristics. Morgan Kaufmann, San Francisco (1983)
Sen, A., Bagchi, A.: Fast recursive formulations for BFS that allow controlled used of memory. In: Proc. IJCAI 1989, pp. 297–302 (1989)
Weld, D.: An introduction to least commitment planning. AI Magazine (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bonet, B., Geffner, H. (2000). Planning as Heuristic Search: New Results. In: Biundo, S., Fox, M. (eds) Recent Advances in AI Planning. ECP 1999. Lecture Notes in Computer Science(), vol 1809. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10720246_28
Download citation
DOI: https://doi.org/10.1007/10720246_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67866-3
Online ISBN: 978-3-540-44657-6
eBook Packages: Springer Book Archive