Abstract
In this paper, we introduce an effective strategy for subgoal division and ordering based upon recursive subgoals and combine this strategy with a genetic-based planning approach. This strategy can be applied to domains with conjunctive goals. The main idea is to recursively decompose a goal into a set of serializable subgoals and to specify a strict ordering among the subgoals. Empirical results show that the recursive subgoal strategy reduces the size of the search space and improves the quality of solutions to planning problems.
This is a preview of subscription content, log in via an institution to check access.
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
Tower of hanoi, http://www.cut-the-knot.com/recurrence/hanoi.shtml
Barrett, A., Weld, D.S.: Characterizing subgoal interactions for planning. In: Proc. of the 13th International Joint Conference on Artificial Intelligence (IJCAI 1993), Chambery, France, pp. 1388–1393 (1993)
Barrett, A., Weld, D.S.: Partial-order planning: evaluating possible efficiency gains. Journal of Artificial Intelligence 67, 71–112 (1994)
Cheng, J., Irani, K.B.: Ordering problem subgoals. In: Proc. of the 11th International Joint Conference on Artificial Intelligence (IJCAI 1989), Detroit, USA, pp. 931–936 (1989)
Drummond, M., Currie, K.: Goal ordering in partially ordered plans. In: Proc. of the 11th International Joint Conference on Artificial Intelligence (IJCAI 1989), Detroit, USA, pp. 960–965 (1989)
Etzioni, O.: Acquiring search-control knowledge via static analysis. Journal of Artificial Intelligence 62, 255–301 (1993)
Fikes, R., Nilsson, N.: STRIPS: A new approach to the application of theorem proving to problem solving. Journal of Artificial Intelligence 2(3/4), 189–208 (1971)
Hertzberg, J., Horz, A.: Towards a theory of conflict detection and resolution in nonlinear plans. In: Proc. of the 11th International Joint Conference on Artificial Intelligence (IJCAI 1989), Detroit, USA, pp. 937–942 (1989)
Johnson, W.W., Story, W.E.: Notes on the “15” puzzle. American Journal of Mathematics 2(4), 397–404 (1879)
Koehler, J., Hoffmann, J.: Planning with goal agendas. Technical Report 110, Institute for Computer Science, Albert Ludwigs University, Freiburg, Germany (1998)
Korf, R.E.: Planning as search: A quantitative approach. Journal of Artificial Intelligence 33, 65–88 (1987)
Lin, F.: An ordering on subgoals for planning. Annals of Mathematics and Artificial Intelligence 21(2-4), 321–342 (1997)
Russell, S.J., Norvig, P.: Artificial Intelligence: A Modern Approach. Prentice Hall, Upper Saddle River (1995)
Yu, H., Marinescu, D.C., Wu, A.S., Siegel, H.J.: A genetic approach to planning in heterogeneous computing environments. In: the 12th Heterogeneous Computing Workshop (HCW 2003), CD-ROM Proc. of the 17th International Parallel and Distributed Processing Symposium (IPDPS 2003). IEEE Computer Society Press, Los Alamitos (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yu, H., Marinescu, D.C., Wu, A.S., Siegel, H.J. (2004). Planning with Recursive Subgoals. In: Negoita, M.G., Howlett, R.J., Jain, L.C. (eds) Knowledge-Based Intelligent Information and Engineering Systems. KES 2004. Lecture Notes in Computer Science(), vol 3214. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30133-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-30133-2_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23206-3
Online ISBN: 978-3-540-30133-2
eBook Packages: Springer Book Archive