Genetically evolved macro-actions in AI planning problems

M. A. H. Newton, J. Levine, M. Fox

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

Abstract

Despite recent progress in planning, many complex domains and even simple domains with large problems remain hard and challenging for current planners. A
macro-action, defined as a group of actions applied at one time, can make jumps to reach a goal at less depth in the search tree and thus problems, not solvable within a given time limit, might become solvable. FF Style planners like Macro-FF and MARVIN showed some improvement with macro-actions. But both of them somehow need knowledge about the domains and the search algorithms as Macro-FF uses static facts and MARVIN uses plateau escaping sequences to generate macroactions. There is no known method capable of learning good macros without any significant structural knowledge about the domains or the planning algorithms. Genetic algorithms are automatic learning methods that require just a method to seed the initial population, definitions of the genetic operators on the populations, and a method to evaluate individuals across the populations but no structural knowledge about the problem domains and the search algorithms. Genetic algorithms have promising results in learning control knowledge for a domain and some success in generating plans but have not yet been tried to evolve macro-actions. This paper presents initial results of applying a genetic algorithm to learn macro-actions in planning problems.
LanguageEnglish
Title of host publicationProceedings of the 24th Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG 2005)
Pages163-172
Number of pages10
Publication statusPublished - 1 Dec 2005

Fingerprint

Macros
Planning
Genetic algorithms
Seed

Keywords

  • macro-actions
  • planning problems
  • genetic algorithms
  • artificial intelligence

Cite this

Newton, M. A. H., Levine, J., & Fox, M. (2005). Genetically evolved macro-actions in AI planning problems. In Proceedings of the 24th Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG 2005) (pp. 163-172)
Newton, M. A. H. ; Levine, J. ; Fox, M. / Genetically evolved macro-actions in AI planning problems. Proceedings of the 24th Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG 2005). 2005. pp. 163-172
@inproceedings{ef41521f2b074bc08130854be8f5389e,
title = "Genetically evolved macro-actions in AI planning problems",
abstract = "Despite recent progress in planning, many complex domains and even simple domains with large problems remain hard and challenging for current planners. A macro-action, defined as a group of actions applied at one time, can make jumps to reach a goal at less depth in the search tree and thus problems, not solvable within a given time limit, might become solvable. FF Style planners like Macro-FF and MARVIN showed some improvement with macro-actions. But both of them somehow need knowledge about the domains and the search algorithms as Macro-FF uses static facts and MARVIN uses plateau escaping sequences to generate macroactions. There is no known method capable of learning good macros without any significant structural knowledge about the domains or the planning algorithms. Genetic algorithms are automatic learning methods that require just a method to seed the initial population, definitions of the genetic operators on the populations, and a method to evaluate individuals across the populations but no structural knowledge about the problem domains and the search algorithms. Genetic algorithms have promising results in learning control knowledge for a domain and some success in generating plans but have not yet been tried to evolve macro-actions. This paper presents initial results of applying a genetic algorithm to learn macro-actions in planning problems.",
keywords = "macro-actions, planning problems, genetic algorithms, artificial intelligence",
author = "Newton, {M. A. H.} and J. Levine and M. Fox",
year = "2005",
month = "12",
day = "1",
language = "English",
pages = "163--172",
booktitle = "Proceedings of the 24th Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG 2005)",

}

Newton, MAH, Levine, J & Fox, M 2005, Genetically evolved macro-actions in AI planning problems. in Proceedings of the 24th Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG 2005). pp. 163-172.

Genetically evolved macro-actions in AI planning problems. / Newton, M. A. H.; Levine, J.; Fox, M.

Proceedings of the 24th Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG 2005). 2005. p. 163-172.

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

TY - GEN

T1 - Genetically evolved macro-actions in AI planning problems

AU - Newton, M. A. H.

AU - Levine, J.

AU - Fox, M.

PY - 2005/12/1

Y1 - 2005/12/1

N2 - Despite recent progress in planning, many complex domains and even simple domains with large problems remain hard and challenging for current planners. A macro-action, defined as a group of actions applied at one time, can make jumps to reach a goal at less depth in the search tree and thus problems, not solvable within a given time limit, might become solvable. FF Style planners like Macro-FF and MARVIN showed some improvement with macro-actions. But both of them somehow need knowledge about the domains and the search algorithms as Macro-FF uses static facts and MARVIN uses plateau escaping sequences to generate macroactions. There is no known method capable of learning good macros without any significant structural knowledge about the domains or the planning algorithms. Genetic algorithms are automatic learning methods that require just a method to seed the initial population, definitions of the genetic operators on the populations, and a method to evaluate individuals across the populations but no structural knowledge about the problem domains and the search algorithms. Genetic algorithms have promising results in learning control knowledge for a domain and some success in generating plans but have not yet been tried to evolve macro-actions. This paper presents initial results of applying a genetic algorithm to learn macro-actions in planning problems.

AB - Despite recent progress in planning, many complex domains and even simple domains with large problems remain hard and challenging for current planners. A macro-action, defined as a group of actions applied at one time, can make jumps to reach a goal at less depth in the search tree and thus problems, not solvable within a given time limit, might become solvable. FF Style planners like Macro-FF and MARVIN showed some improvement with macro-actions. But both of them somehow need knowledge about the domains and the search algorithms as Macro-FF uses static facts and MARVIN uses plateau escaping sequences to generate macroactions. There is no known method capable of learning good macros without any significant structural knowledge about the domains or the planning algorithms. Genetic algorithms are automatic learning methods that require just a method to seed the initial population, definitions of the genetic operators on the populations, and a method to evaluate individuals across the populations but no structural knowledge about the problem domains and the search algorithms. Genetic algorithms have promising results in learning control knowledge for a domain and some success in generating plans but have not yet been tried to evolve macro-actions. This paper presents initial results of applying a genetic algorithm to learn macro-actions in planning problems.

KW - macro-actions

KW - planning problems

KW - genetic algorithms

KW - artificial intelligence

UR - http://www.cis.strath.ac.uk/cis/research/publications/papers/strath_cis_publication_2168.pdf

M3 - Conference contribution book

SP - 163

EP - 172

BT - Proceedings of the 24th Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG 2005)

ER -

Newton MAH, Levine J, Fox M. Genetically evolved macro-actions in AI planning problems. In Proceedings of the 24th Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG 2005). 2005. p. 163-172