Evolutionary-based learning of generalised policies for AI planning domains

ABSTRACT

This work investigates the application of Evolutionary Computation (EC) to the induction of generalised policies used to solve AI planning problems. A policy is defined as an ordered list of rules that specifies which action to perform under which conditions; a solution (plan) to a planning problem is a sequence of actions suggested by the policy. We compare an evolved policy with one produced by a state-of-the art approximate policy iteration approach. We discuss the relative merits of the two approaches with a focus on the impact of the knowledge representation and the learning strategy. In particular we note that a strategy commonly and successfully used for the induction of classification rules, that of Iterative Rule Learning, is not necessarily an optimal strategy for the induction of generalised policies aimed at minimising the number of actions in a plan.

REFERENCES

• 1: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 2: Mario Martín , Hector Geffner, Learning Generalized Policies from Planning Examples Using Concept Languages, Applied Intelligence, v.20 n.1, p.9-19, January-February 2004 [doi>10.1023/B:APIN.0000011138.20292.dd]
• 3: M. Fox and D. Long. PDDL2.1: An extension to pddl for expressing temporal planning domains. Journal of Artificial Intelligence Research, 20:61--124, 2003.
• 4: J. Levine and D. Humphreys. Learning action strategies for planning domains using genetic programming. In Applications of Evolutionary Computing, EvoWorkshops2003: EvoBIO, EvoCOP, EvoIASP, EvoMUSART, EvoROB, EvoSTIM, pages 684--695, 2003.
• 5: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 6: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 7: Lee Spector, Genetic programming and AI planning systems, Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.1329-1334, October 1994, Seattle, Washington, United States
• 8: Gilles Venturini, SIA: A Supervised Inductive Algorithm with Genetic Search for Learning Attributes based Concepts, Proceedings of the European Conference on Machine Learning, p.280-296, April 05-07, 1993
• 9: M. Galea and Q. Shen. Fuzzy rules from ant-inspired computation. In Proceedings of the IEEE International Conference on Fuzzy Systems, pages 1691--1696, 2004.
• 10: Johannes Fürnkranz, Separate-and-Conquer Rule Learning, Artificial Intelligence Review, v.13 n.1, p.3-54, Jan. 1999 [doi>10.1023/A:1006524209794]
• 11: Roni Khardon, Learning action strategies for planning domains, Artificial Intelligence, v.113 n.1-2, p.125-148, Sept. 1999 [doi>10.1016/S0004-3702(99)00060-0]
• 12: John Slaney , Sylvie Thiébaux, Blocks World revisited, Artificial Intelligence, v.125 n.1-2, p.119-153, Jan. 2001 [doi>10.1016/S0004-3702(00)00079-5]
• 13: M. Manuela Magalhaes A. Veloso, Learning by analogical reasoning in general problem-solving, Carnegie Mellon University, Pittsburgh, PA, 1992
• 14: Franz Baader , Diego Calvanese , Deborah L. McGuinness , Daniele Nardi , Peter F. Patel-Schneider, The description logic handbook: theory, implementation, and applications, Cambridge University Press, New York, NY, 2003
• 15: A. Fern, S. Yoon, and R. Givan. Approximate policy iteration with a policy language bias: Solving relational markov decision processes. Journal of Artificial Intelligence Research, 25:75--118, 2006.
• 16: G. Tesauro and G. Galperin. On-line policy improvement using Monte-Carlo search. In Advances in Neural Information Processing 9, 1996.
• 17: J. Hoffmann and B. Nebel. The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14:263--302, 2001.
• 18: B. L. Miller and D. E. Goldberg. Genetic algorithms, tournament selection, and the effects of noise. Technical Report 95006, Department of General Engineering, University of Illinois at Urbana-Champaign, Urbana, IL, 1995.
• 19: E. P. D. Pednault, Toward a mathematical theory of plan synthesis, Stanford University, Stanford, CA, 1987
• 20: E. P. D. Pednault, Toward a mathematical theory of plan synthesis, Stanford University, Stanford, CA, 1987

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Performance

Keywords:
automated planning, decision list learning, inductive learning, iterative rule learning, rule order optimisation