Improved Features for Runtime Prediction of Domain-Independent Planners

Chris Fawcett, Mauro Vallati, Frank Hutter, Jorg Hoffmann, Holger H. Hoos, Kevin Leyton-Brown

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

24 Citations (Scopus)

Abstract

State-of-the-art planners often exhibit substantial runtime variation, making it useful to be able to efficiently predict how long a given planner will take to run on a given instance. In other areas of AI, such needs are met by building so-called empirical performance models (EPMs), statistical models derived from sets of problem instances and performance observations. Historically, such models have been less accurate for predicting the running times of planners. A key hurdle has been a relative weakness in instance features for characterizing instances: mappings from problem instances to real numbers that serve as the starting point for learning an EPM. We propose a new, extensive set of instance features for planning, and investigate its effectiveness across a range of model families. We built EPMs for various prominent planning systems on several thousand benchmark problems from the planning literature and from IPC benchmark sets, and conclude that our models predict runtime much more accurately than the previous state of the art. We also study the relative importance of these features.
LanguageEnglish
Title of host publicationProceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014)
EditorsSteve Chien, Alan Fern, Wheeler Ruml, Minh Do
PublisherAAAI press
Pages355-359
Number of pages5
ISBN (Print)9781577356608
Publication statusPublished - Aug 2014
Event24th International Conference on Automated Planning and Scheduling - Portsmouth, United States
Duration: 21 Jun 201426 Jun 2014
Conference number: 24
http://icaps14.icaps-conference.org/ (Link to Conference Website)

Conference

Conference24th International Conference on Automated Planning and Scheduling
Abbreviated titleICAPS 2014
CountryUnited States
CityPortsmouth
Period21/06/1426/06/14
Internet address

Fingerprint

Planning
Statistical Models

Cite this

Fawcett, C., Vallati, M., Hutter, F., Hoffmann, J., Hoos, H. H., & Leyton-Brown, K. (2014). Improved Features for Runtime Prediction of Domain-Independent Planners. In S. Chien, A. Fern, W. Ruml, & M. Do (Eds.), Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014) (pp. 355-359). AAAI press.
Fawcett, Chris ; Vallati, Mauro ; Hutter, Frank ; Hoffmann, Jorg ; Hoos, Holger H. ; Leyton-Brown, Kevin. / Improved Features for Runtime Prediction of Domain-Independent Planners. Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014). editor / Steve Chien ; Alan Fern ; Wheeler Ruml ; Minh Do. AAAI press, 2014. pp. 355-359
@inproceedings{1259325dbc1349558d9914cb0299f535,
title = "Improved Features for Runtime Prediction of Domain-Independent Planners",
abstract = "State-of-the-art planners often exhibit substantial runtime variation, making it useful to be able to efficiently predict how long a given planner will take to run on a given instance. In other areas of AI, such needs are met by building so-called empirical performance models (EPMs), statistical models derived from sets of problem instances and performance observations. Historically, such models have been less accurate for predicting the running times of planners. A key hurdle has been a relative weakness in instance features for characterizing instances: mappings from problem instances to real numbers that serve as the starting point for learning an EPM. We propose a new, extensive set of instance features for planning, and investigate its effectiveness across a range of model families. We built EPMs for various prominent planning systems on several thousand benchmark problems from the planning literature and from IPC benchmark sets, and conclude that our models predict runtime much more accurately than the previous state of the art. We also study the relative importance of these features.",
author = "Chris Fawcett and Mauro Vallati and Frank Hutter and Jorg Hoffmann and Hoos, {Holger H.} and Kevin Leyton-Brown",
year = "2014",
month = "8",
language = "English",
isbn = "9781577356608",
pages = "355--359",
editor = "Steve Chien and Alan Fern and Wheeler Ruml and Minh Do",
booktitle = "Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014)",
publisher = "AAAI press",

}

Fawcett, C, Vallati, M, Hutter, F, Hoffmann, J, Hoos, HH & Leyton-Brown, K 2014, Improved Features for Runtime Prediction of Domain-Independent Planners. in S Chien, A Fern, W Ruml & M Do (eds), Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014). AAAI press, pp. 355-359, 24th International Conference on Automated Planning and Scheduling, Portsmouth, United States, 21/06/14.

Improved Features for Runtime Prediction of Domain-Independent Planners. / Fawcett, Chris; Vallati, Mauro; Hutter, Frank; Hoffmann, Jorg; Hoos, Holger H.; Leyton-Brown, Kevin.

Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014). ed. / Steve Chien; Alan Fern; Wheeler Ruml; Minh Do. AAAI press, 2014. p. 355-359.

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

TY - GEN

T1 - Improved Features for Runtime Prediction of Domain-Independent Planners

AU - Fawcett, Chris

AU - Vallati, Mauro

AU - Hutter, Frank

AU - Hoffmann, Jorg

AU - Hoos, Holger H.

AU - Leyton-Brown, Kevin

PY - 2014/8

Y1 - 2014/8

N2 - State-of-the-art planners often exhibit substantial runtime variation, making it useful to be able to efficiently predict how long a given planner will take to run on a given instance. In other areas of AI, such needs are met by building so-called empirical performance models (EPMs), statistical models derived from sets of problem instances and performance observations. Historically, such models have been less accurate for predicting the running times of planners. A key hurdle has been a relative weakness in instance features for characterizing instances: mappings from problem instances to real numbers that serve as the starting point for learning an EPM. We propose a new, extensive set of instance features for planning, and investigate its effectiveness across a range of model families. We built EPMs for various prominent planning systems on several thousand benchmark problems from the planning literature and from IPC benchmark sets, and conclude that our models predict runtime much more accurately than the previous state of the art. We also study the relative importance of these features.

AB - State-of-the-art planners often exhibit substantial runtime variation, making it useful to be able to efficiently predict how long a given planner will take to run on a given instance. In other areas of AI, such needs are met by building so-called empirical performance models (EPMs), statistical models derived from sets of problem instances and performance observations. Historically, such models have been less accurate for predicting the running times of planners. A key hurdle has been a relative weakness in instance features for characterizing instances: mappings from problem instances to real numbers that serve as the starting point for learning an EPM. We propose a new, extensive set of instance features for planning, and investigate its effectiveness across a range of model families. We built EPMs for various prominent planning systems on several thousand benchmark problems from the planning literature and from IPC benchmark sets, and conclude that our models predict runtime much more accurately than the previous state of the art. We also study the relative importance of these features.

UR - https://www.aaai.org/Press/Proceedings/icaps14.php

M3 - Conference contribution

SN - 9781577356608

SP - 355

EP - 359

BT - Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014)

A2 - Chien, Steve

A2 - Fern, Alan

A2 - Ruml, Wheeler

A2 - Do, Minh

PB - AAAI press

ER -

Fawcett C, Vallati M, Hutter F, Hoffmann J, Hoos HH, Leyton-Brown K. Improved Features for Runtime Prediction of Domain-Independent Planners. In Chien S, Fern A, Ruml W, Do M, editors, Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014). AAAI press. 2014. p. 355-359