Genetic-Based Planning with Recursive Subgoals

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

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.

Keywords: Planning, recursive subgoals, Sliding-tile puzzle, subgoal interaction, genetic algorithms.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1080694

References:

[1] Tower of Hanoi, http://www.cut-the-knot.com/recurrence/hanoi.shtml.
[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.