Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 30320
Genetic-Based Planning with Recursive Subgoals

Authors: Han Yu, Dan C. Marinescu, Annie S. Wu, Howard Jay Siegel


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.

Keywords: Planning, Genetic Algorithms, recursive subgoals, Sliding-tile puzzle, subgoal interaction

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1111


[1] Tower of Hanoi,
[2] A. Barrett and D. S. Weld. "Characterizing subgoal interactions for planning." In Proc. of the 13th International Joint Conference on Artificial Intelligence (IJCAI-93), pages 1388-1393, Chambery, France, 1993.
[3] A. Barrett and D. S. Weld. "Partial-order planning: evaluating possible efficiency gains." Journal of Artificial Intelligence, 67:71-112, 1994.
[4] J. Cheng and K. B. Irani. "Ordering problem subgoals." In Proc. of the 11th International Joint Conference on Artificial Intelligence (IJCAI- 89), pages 931-936, Detroit, USA, 1989.
[5] M. Drummond and K. Currie. "Goal ordering in partially ordered plans." In Proc. of the 11th International Joint Conference on Artificial Intelligence (IJCAI-89), pages 960-965, Detroit, USA, 1989.
[6] O. Etzioni. "Acquiring search-control knowledge via static analysis." Journal of Artificial Intelligence, 62:255-301,1993.
[7] R. Fikes and N. Nilsson. "STRIPS: A new approach to the application of theorem proving to problem solving." Journal of Artificial Intelligence, 2(3/4):189-208, 1971.
[8] J. Hertzberg and A. Horz. "Towards a theory of conflict detection and resolution in nonlinear plans." In Proc. of the 11th International Joint Conference on Artificial Intelligence (IJCAI-89), pages 937-942, Detroit, USA, 1989.
[9] W. W. Johnson and W. E. Story. "Notes on the ÔÇÿ15- puzzle." American Journal of Mathematics, 2(4):397-404, 1879.
[10] J. Koehler and J. Hoffmann. "Planning with goal agendas." Technical Report 110, Institute for Computer Science, Albert Ludwigs University, Freiburg, Germany, 1998.
[11] R. E. Korf. "Planning as search: A quantitative approach." Journal of Artificial Intelligence, 33:65-88, 1987.
[12] R. E. Korf, personal communication, 2003.
[13] R. E. Korf and A. Felner. "Disjoint pattern database heuristics." Journal of Artificial Intelligence, 134:9-22, 2002.
[14] R. E. Korf and L. A. Taylor. "Finding optimal solutions to the twentyfour puzzle." In Proc. of the Thirteenth National Conference on Artificial Intelligence (AAAI 96), pages 1202-1207, Portland, OR, 1996.
[15] F. Lin. "An ordering on subgoals for planning." Annals of Mathematics and Artificial Intelligence, 21(2-4):321-342, 1997.
[16] S. J. Russell and P. Norvig. "Artificial Intelligence: A Modern Approach." Prentice Hall, Upper Saddle River, NJ, 1995.
[17] H. Yu, D. C. Marinescu, A. S.Wu, and H. J. Siegel. "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, CA, ISBN 0-7695-1926-1, 2003.