MUM: A technique for maximising the utility of macro-operators by constrained generation and use

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

Research into techniques that reformulate problems to make general solvers more efficiently derive solutions has attracted much attention, in particular when the reformulation process is to some degree solver and domain independent. There are major challenges to overcome when applying such techniques to automated planning, however: reformulation methods such as adding macro-operators (macros, for short) can be detrimental because they tend to increase branching factors during solution search, while other methods such as learning entanglements can limit a planner's space of potentially solvable problems (its coverage) through over-pruning. These techniques may therefore work well with some domain-problem-planner combinations, but work poorly with others. In this paper we introduce a new learning technique (MUM) for synthesising macros from training example plans in order to improve the speed and coverage of do-main independent automated planning engines. MUM embodies domain independent constraints for selecting macro candidates, for generating macros, and for lim-iting the size of the grounding set of learned macros, therefore maximising the utility of used macros. Our empirical results with IPC benchmark domains and a range of state of the art planners demonstrate the ad-vance that MUM makes to the increased coverage and efficiency of the planners. Comparisons with a previous leading macro learning mechanism further demonstrate MUM's capability.

LanguageEnglish
Pages65-73
Number of pages9
JournalProceedings International Conference on Automated Planning and Scheduling, ICAPS
Volume2014-January
Issue numberJanuary
Publication statusPublished - 2014

Fingerprint

Macros
Planning
Operator
Electric grounding
Engines

Cite this

@article{b719723bc9b34ab0b5dd325174e95aa4,
title = "MUM: A technique for maximising the utility of macro-operators by constrained generation and use",
abstract = "Research into techniques that reformulate problems to make general solvers more efficiently derive solutions has attracted much attention, in particular when the reformulation process is to some degree solver and domain independent. There are major challenges to overcome when applying such techniques to automated planning, however: reformulation methods such as adding macro-operators (macros, for short) can be detrimental because they tend to increase branching factors during solution search, while other methods such as learning entanglements can limit a planner's space of potentially solvable problems (its coverage) through over-pruning. These techniques may therefore work well with some domain-problem-planner combinations, but work poorly with others. In this paper we introduce a new learning technique (MUM) for synthesising macros from training example plans in order to improve the speed and coverage of do-main independent automated planning engines. MUM embodies domain independent constraints for selecting macro candidates, for generating macros, and for lim-iting the size of the grounding set of learned macros, therefore maximising the utility of used macros. Our empirical results with IPC benchmark domains and a range of state of the art planners demonstrate the ad-vance that MUM makes to the increased coverage and efficiency of the planners. Comparisons with a previous leading macro learning mechanism further demonstrate MUM's capability.",
author = "Luk{\'a}š Chrpa and Mauro Vallati and McCluskey, {Thomas Leo}",
year = "2014",
language = "English",
volume = "2014-January",
pages = "65--73",
journal = "Proceedings International Conference on Automated Planning and Scheduling, ICAPS",
issn = "2334-0835",
number = "January",

}

TY - JOUR

T1 - MUM

T2 - Proceedings International Conference on Automated Planning and Scheduling, ICAPS

AU - Chrpa, Lukáš

AU - Vallati, Mauro

AU - McCluskey, Thomas Leo

PY - 2014

Y1 - 2014

N2 - Research into techniques that reformulate problems to make general solvers more efficiently derive solutions has attracted much attention, in particular when the reformulation process is to some degree solver and domain independent. There are major challenges to overcome when applying such techniques to automated planning, however: reformulation methods such as adding macro-operators (macros, for short) can be detrimental because they tend to increase branching factors during solution search, while other methods such as learning entanglements can limit a planner's space of potentially solvable problems (its coverage) through over-pruning. These techniques may therefore work well with some domain-problem-planner combinations, but work poorly with others. In this paper we introduce a new learning technique (MUM) for synthesising macros from training example plans in order to improve the speed and coverage of do-main independent automated planning engines. MUM embodies domain independent constraints for selecting macro candidates, for generating macros, and for lim-iting the size of the grounding set of learned macros, therefore maximising the utility of used macros. Our empirical results with IPC benchmark domains and a range of state of the art planners demonstrate the ad-vance that MUM makes to the increased coverage and efficiency of the planners. Comparisons with a previous leading macro learning mechanism further demonstrate MUM's capability.

AB - Research into techniques that reformulate problems to make general solvers more efficiently derive solutions has attracted much attention, in particular when the reformulation process is to some degree solver and domain independent. There are major challenges to overcome when applying such techniques to automated planning, however: reformulation methods such as adding macro-operators (macros, for short) can be detrimental because they tend to increase branching factors during solution search, while other methods such as learning entanglements can limit a planner's space of potentially solvable problems (its coverage) through over-pruning. These techniques may therefore work well with some domain-problem-planner combinations, but work poorly with others. In this paper we introduce a new learning technique (MUM) for synthesising macros from training example plans in order to improve the speed and coverage of do-main independent automated planning engines. MUM embodies domain independent constraints for selecting macro candidates, for generating macros, and for lim-iting the size of the grounding set of learned macros, therefore maximising the utility of used macros. Our empirical results with IPC benchmark domains and a range of state of the art planners demonstrate the ad-vance that MUM makes to the increased coverage and efficiency of the planners. Comparisons with a previous leading macro learning mechanism further demonstrate MUM's capability.

UR - http://www.scopus.com/inward/record.url?scp=84933052246&partnerID=8YFLogxK

M3 - Article

VL - 2014-January

SP - 65

EP - 73

JO - Proceedings International Conference on Automated Planning and Scheduling, ICAPS

JF - Proceedings International Conference on Automated Planning and Scheduling, ICAPS

SN - 2334-0835

IS - January

ER -