Optimizing plans through analysis of action dependencies and independencies

Lukáš Chrpa, Thomas Leo McCluskey, Hugh Osborne

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

9 Citations (Scopus)

Abstract

The problem of automated planning is known to be intractable in general. Moreover, it has been proven that in some cases finding an optimal solution is much harder than finding any solution. Existing techniques have to compromise between speed of the planning process and quality of solutions. For example, techniques based on greedy search often are able to obtain solutions quickly, but the quality of the solutions is usually low. Similarly, adding macro-operators to planning domains often enables planning speed-up, but solution sequences are typically longer. In this paper, we propose a method for optimizing plans with respect to their length, by post-planning analysis. The method is based on analyzing action dependencies and independencies by which we are able to identify redundant actions or non-optimal sub-plans. To evaluate the process we provide preliminary empirical evidence using benchmark domains.

Original languageEnglish
Title of host publicationICAPS 2012 - Proceedings of the 22nd International Conference on Automated Planning and Scheduling
Pages338-342
Number of pages5
Publication statusPublished - 2012
Event22nd International Conference on Automated Planning and Scheduling - Atibaia, Sao Paulo, Brazil
Duration: 25 Jun 201229 Jun 2012
Conference number: 22
http://icaps12.icaps-conference.org/ (Link to Conference Details)

Conference

Conference22nd International Conference on Automated Planning and Scheduling
Abbreviated titleICAPS 2012
CountryBrazil
CitySao Paulo
Period25/06/1229/06/12
Internet address

Fingerprint

Planning
Empirical evidence
Benchmark
Compromise
Operator
Optimal solution
Planning process

Cite this

Chrpa, L., McCluskey, T. L., & Osborne, H. (2012). Optimizing plans through analysis of action dependencies and independencies. In ICAPS 2012 - Proceedings of the 22nd International Conference on Automated Planning and Scheduling (pp. 338-342)
Chrpa, Lukáš ; McCluskey, Thomas Leo ; Osborne, Hugh. / Optimizing plans through analysis of action dependencies and independencies. ICAPS 2012 - Proceedings of the 22nd International Conference on Automated Planning and Scheduling. 2012. pp. 338-342
@inproceedings{9f3a8769d34d4db193a5e05cc8047a39,
title = "Optimizing plans through analysis of action dependencies and independencies",
abstract = "The problem of automated planning is known to be intractable in general. Moreover, it has been proven that in some cases finding an optimal solution is much harder than finding any solution. Existing techniques have to compromise between speed of the planning process and quality of solutions. For example, techniques based on greedy search often are able to obtain solutions quickly, but the quality of the solutions is usually low. Similarly, adding macro-operators to planning domains often enables planning speed-up, but solution sequences are typically longer. In this paper, we propose a method for optimizing plans with respect to their length, by post-planning analysis. The method is based on analyzing action dependencies and independencies by which we are able to identify redundant actions or non-optimal sub-plans. To evaluate the process we provide preliminary empirical evidence using benchmark domains.",
author = "Luk{\'a}š Chrpa and McCluskey, {Thomas Leo} and Hugh Osborne",
year = "2012",
language = "English",
isbn = "9781577355625",
pages = "338--342",
booktitle = "ICAPS 2012 - Proceedings of the 22nd International Conference on Automated Planning and Scheduling",

}

Chrpa, L, McCluskey, TL & Osborne, H 2012, Optimizing plans through analysis of action dependencies and independencies. in ICAPS 2012 - Proceedings of the 22nd International Conference on Automated Planning and Scheduling. pp. 338-342, 22nd International Conference on Automated Planning and Scheduling, Sao Paulo, Brazil, 25/06/12.

Optimizing plans through analysis of action dependencies and independencies. / Chrpa, Lukáš; McCluskey, Thomas Leo; Osborne, Hugh.

ICAPS 2012 - Proceedings of the 22nd International Conference on Automated Planning and Scheduling. 2012. p. 338-342.

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

TY - GEN

T1 - Optimizing plans through analysis of action dependencies and independencies

AU - Chrpa, Lukáš

AU - McCluskey, Thomas Leo

AU - Osborne, Hugh

PY - 2012

Y1 - 2012

N2 - The problem of automated planning is known to be intractable in general. Moreover, it has been proven that in some cases finding an optimal solution is much harder than finding any solution. Existing techniques have to compromise between speed of the planning process and quality of solutions. For example, techniques based on greedy search often are able to obtain solutions quickly, but the quality of the solutions is usually low. Similarly, adding macro-operators to planning domains often enables planning speed-up, but solution sequences are typically longer. In this paper, we propose a method for optimizing plans with respect to their length, by post-planning analysis. The method is based on analyzing action dependencies and independencies by which we are able to identify redundant actions or non-optimal sub-plans. To evaluate the process we provide preliminary empirical evidence using benchmark domains.

AB - The problem of automated planning is known to be intractable in general. Moreover, it has been proven that in some cases finding an optimal solution is much harder than finding any solution. Existing techniques have to compromise between speed of the planning process and quality of solutions. For example, techniques based on greedy search often are able to obtain solutions quickly, but the quality of the solutions is usually low. Similarly, adding macro-operators to planning domains often enables planning speed-up, but solution sequences are typically longer. In this paper, we propose a method for optimizing plans with respect to their length, by post-planning analysis. The method is based on analyzing action dependencies and independencies by which we are able to identify redundant actions or non-optimal sub-plans. To evaluate the process we provide preliminary empirical evidence using benchmark domains.

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

M3 - Conference contribution

SN - 9781577355625

SP - 338

EP - 342

BT - ICAPS 2012 - Proceedings of the 22nd International Conference on Automated Planning and Scheduling

ER -

Chrpa L, McCluskey TL, Osborne H. Optimizing plans through analysis of action dependencies and independencies. In ICAPS 2012 - Proceedings of the 22nd International Conference on Automated Planning and Scheduling. 2012. p. 338-342