Inner entanglements: Narrowing the search in classical planning by problem reformulation

Research output: Contribution to journalArticle

Abstract

In the field of automated planning, the central research focus is on domain-independent planning engines that accept planning tasks (domain models and problem descriptions) in a description language, such as Planning Domain Definition Language, and return solution plans. The performance of planning engines can be improved by gathering additional knowledge about specific planning domain models/tasks (such as control rules) that can narrow the search for a solution plan. Such knowledge is often learned from training plans and solutions of simple tasks. Using techniques to reformulate the given planning task to incorporate additional knowledge, while keeping to the same input language, allows to exploit off-the-shelf planning engines. In this paper, we present inner entanglements that are relations between pairs of operators and predicates that represent the exclusivity of predicate achievement or requirement between the given operators. Inner entanglements can be encoded into a planner's input language by transforming the original planning task; hence, planning engines can exploit them. The contribution of this paper is to provide an in-depth analysis and evaluation of inner entanglements, covering theoretical aspects such as complexity results, and an extensive empirical study using International Planning Competition benchmarks and state-of-the-art planning engines.

LanguageEnglish
Pages395-429
Number of pages35
JournalComputational Intelligence
Volume35
Issue number2
Early online date22 Mar 2019
DOIs
Publication statusPublished - May 2019

Fingerprint

Reformulation
Entanglement
Planning
Engine
Engines
Domain Model
Predicate
Task Model
Operator
Empirical Study
Covering
Benchmark

Cite this

@article{8e8c97bf2536408d98bc49790dd3fb85,
title = "Inner entanglements: Narrowing the search in classical planning by problem reformulation",
abstract = "In the field of automated planning, the central research focus is on domain-independent planning engines that accept planning tasks (domain models and problem descriptions) in a description language, such as Planning Domain Definition Language, and return solution plans. The performance of planning engines can be improved by gathering additional knowledge about specific planning domain models/tasks (such as control rules) that can narrow the search for a solution plan. Such knowledge is often learned from training plans and solutions of simple tasks. Using techniques to reformulate the given planning task to incorporate additional knowledge, while keeping to the same input language, allows to exploit off-the-shelf planning engines. In this paper, we present inner entanglements that are relations between pairs of operators and predicates that represent the exclusivity of predicate achievement or requirement between the given operators. Inner entanglements can be encoded into a planner's input language by transforming the original planning task; hence, planning engines can exploit them. The contribution of this paper is to provide an in-depth analysis and evaluation of inner entanglements, covering theoretical aspects such as complexity results, and an extensive empirical study using International Planning Competition benchmarks and state-of-the-art planning engines.",
keywords = "Knowledge Representation, Classical Planning, Machine Learning, Problem Reformulation",
author = "Luk{\'a}š Chrpa and Mauro Vallati and Thomas McCluskey",
year = "2019",
month = "5",
doi = "10.1111/coin.12203",
language = "English",
volume = "35",
pages = "395--429",
journal = "Computational Intelligence",
issn = "0824-7935",
publisher = "Wiley-Blackwell",
number = "2",

}

Inner entanglements : Narrowing the search in classical planning by problem reformulation. / Chrpa, Lukáš; Vallati, Mauro; McCluskey, Thomas.

In: Computational Intelligence, Vol. 35, No. 2, 05.2019, p. 395-429.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Inner entanglements

T2 - Computational Intelligence

AU - Chrpa, Lukáš

AU - Vallati, Mauro

AU - McCluskey, Thomas

PY - 2019/5

Y1 - 2019/5

N2 - In the field of automated planning, the central research focus is on domain-independent planning engines that accept planning tasks (domain models and problem descriptions) in a description language, such as Planning Domain Definition Language, and return solution plans. The performance of planning engines can be improved by gathering additional knowledge about specific planning domain models/tasks (such as control rules) that can narrow the search for a solution plan. Such knowledge is often learned from training plans and solutions of simple tasks. Using techniques to reformulate the given planning task to incorporate additional knowledge, while keeping to the same input language, allows to exploit off-the-shelf planning engines. In this paper, we present inner entanglements that are relations between pairs of operators and predicates that represent the exclusivity of predicate achievement or requirement between the given operators. Inner entanglements can be encoded into a planner's input language by transforming the original planning task; hence, planning engines can exploit them. The contribution of this paper is to provide an in-depth analysis and evaluation of inner entanglements, covering theoretical aspects such as complexity results, and an extensive empirical study using International Planning Competition benchmarks and state-of-the-art planning engines.

AB - In the field of automated planning, the central research focus is on domain-independent planning engines that accept planning tasks (domain models and problem descriptions) in a description language, such as Planning Domain Definition Language, and return solution plans. The performance of planning engines can be improved by gathering additional knowledge about specific planning domain models/tasks (such as control rules) that can narrow the search for a solution plan. Such knowledge is often learned from training plans and solutions of simple tasks. Using techniques to reformulate the given planning task to incorporate additional knowledge, while keeping to the same input language, allows to exploit off-the-shelf planning engines. In this paper, we present inner entanglements that are relations between pairs of operators and predicates that represent the exclusivity of predicate achievement or requirement between the given operators. Inner entanglements can be encoded into a planner's input language by transforming the original planning task; hence, planning engines can exploit them. The contribution of this paper is to provide an in-depth analysis and evaluation of inner entanglements, covering theoretical aspects such as complexity results, and an extensive empirical study using International Planning Competition benchmarks and state-of-the-art planning engines.

KW - Knowledge Representation

KW - Classical Planning

KW - Machine Learning

KW - Problem Reformulation

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

U2 - 10.1111/coin.12203

DO - 10.1111/coin.12203

M3 - Article

VL - 35

SP - 395

EP - 429

JO - Computational Intelligence

JF - Computational Intelligence

SN - 0824-7935

IS - 2

ER -