Genetic-Based Planning with Recursive Subgoals

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.

Authors:

• Han Yu
• Dan C. Marinescu
• Annie S. Wu
• Howard Jay Siegel

Keywords:

• Planning
• recursive subgoals
• Sliding-tile puzzle
• subgoal interaction
• genetic algorithms.

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.