On Different Strategies for Eliminating Redundant Actions from Plans

Lukáš Chrpa, Asma Kilani, Tomas Balyo

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

3 Citations (Scopus)

Abstract

Satisficing planning engines are often able to generate plans in a reasonable time, however, plans are often far from optimal. Such plans often contain a high number of redundant actions, that are actions, which can be removed without affecting the validity of the plans. Existing approaches for determining and eliminating redundant actions work in polynomial time, however, do not guarantee eliminating the "best" set of redundant actions, since such a problem is NP-complete. We introduce an approach which encodes the problem of determining the "best" set of redundant actions (i.e. having the maximum total-cost) as a weighted MaxSAT problem. Moreover, we adapt the existing polynomial technique which greedily tries to eliminate an action and its dependants from the plan in order to eliminate more expensive redundant actions. The proposed approaches are empirically compared to existing approaches on plans generated by state-of-the-art planning engines on standard planning benchmarks.
LanguageEnglish
Title of host publicationProceedings of the Seventh Annual Symposium on Combinatorial Search
Subtitle of host publication(SoCs 2014)
EditorsStefan Edelkamp, Roman Bartak
Place of PublicationPrague
PublisherAAAI press
Pages10-18
Number of pages9
ISBN (Print)9781577356769
Publication statusPublished - Sep 2014

Fingerprint

Planning
Polynomials
Engines
Computational complexity
Costs

Cite this

Chrpa, L., Kilani, A., & Balyo, T. (2014). On Different Strategies for Eliminating Redundant Actions from Plans. In S. Edelkamp, & R. Bartak (Eds.), Proceedings of the Seventh Annual Symposium on Combinatorial Search: (SoCs 2014) (pp. 10-18). Prague: AAAI press.
Chrpa, Lukáš ; Kilani, Asma ; Balyo, Tomas. / On Different Strategies for Eliminating Redundant Actions from Plans. Proceedings of the Seventh Annual Symposium on Combinatorial Search: (SoCs 2014). editor / Stefan Edelkamp ; Roman Bartak. Prague : AAAI press, 2014. pp. 10-18
@inproceedings{e78a1053bece44e2a4d21eb3af5a505e,
title = "On Different Strategies for Eliminating Redundant Actions from Plans",
abstract = "Satisficing planning engines are often able to generate plans in a reasonable time, however, plans are often far from optimal. Such plans often contain a high number of redundant actions, that are actions, which can be removed without affecting the validity of the plans. Existing approaches for determining and eliminating redundant actions work in polynomial time, however, do not guarantee eliminating the {"}best{"} set of redundant actions, since such a problem is NP-complete. We introduce an approach which encodes the problem of determining the {"}best{"} set of redundant actions (i.e. having the maximum total-cost) as a weighted MaxSAT problem. Moreover, we adapt the existing polynomial technique which greedily tries to eliminate an action and its dependants from the plan in order to eliminate more expensive redundant actions. The proposed approaches are empirically compared to existing approaches on plans generated by state-of-the-art planning engines on standard planning benchmarks.",
keywords = "Automated Planning",
author = "Luk{\'a}š Chrpa and Asma Kilani and Tomas Balyo",
year = "2014",
month = "9",
language = "English",
isbn = "9781577356769",
pages = "10--18",
editor = "Stefan Edelkamp and Roman Bartak",
booktitle = "Proceedings of the Seventh Annual Symposium on Combinatorial Search",
publisher = "AAAI press",

}

Chrpa, L, Kilani, A & Balyo, T 2014, On Different Strategies for Eliminating Redundant Actions from Plans. in S Edelkamp & R Bartak (eds), Proceedings of the Seventh Annual Symposium on Combinatorial Search: (SoCs 2014). AAAI press, Prague, pp. 10-18.

On Different Strategies for Eliminating Redundant Actions from Plans. / Chrpa, Lukáš; Kilani, Asma; Balyo, Tomas.

Proceedings of the Seventh Annual Symposium on Combinatorial Search: (SoCs 2014). ed. / Stefan Edelkamp; Roman Bartak. Prague : AAAI press, 2014. p. 10-18.

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

TY - GEN

T1 - On Different Strategies for Eliminating Redundant Actions from Plans

AU - Chrpa, Lukáš

AU - Kilani, Asma

AU - Balyo, Tomas

PY - 2014/9

Y1 - 2014/9

N2 - Satisficing planning engines are often able to generate plans in a reasonable time, however, plans are often far from optimal. Such plans often contain a high number of redundant actions, that are actions, which can be removed without affecting the validity of the plans. Existing approaches for determining and eliminating redundant actions work in polynomial time, however, do not guarantee eliminating the "best" set of redundant actions, since such a problem is NP-complete. We introduce an approach which encodes the problem of determining the "best" set of redundant actions (i.e. having the maximum total-cost) as a weighted MaxSAT problem. Moreover, we adapt the existing polynomial technique which greedily tries to eliminate an action and its dependants from the plan in order to eliminate more expensive redundant actions. The proposed approaches are empirically compared to existing approaches on plans generated by state-of-the-art planning engines on standard planning benchmarks.

AB - Satisficing planning engines are often able to generate plans in a reasonable time, however, plans are often far from optimal. Such plans often contain a high number of redundant actions, that are actions, which can be removed without affecting the validity of the plans. Existing approaches for determining and eliminating redundant actions work in polynomial time, however, do not guarantee eliminating the "best" set of redundant actions, since such a problem is NP-complete. We introduce an approach which encodes the problem of determining the "best" set of redundant actions (i.e. having the maximum total-cost) as a weighted MaxSAT problem. Moreover, we adapt the existing polynomial technique which greedily tries to eliminate an action and its dependants from the plan in order to eliminate more expensive redundant actions. The proposed approaches are empirically compared to existing approaches on plans generated by state-of-the-art planning engines on standard planning benchmarks.

KW - Automated Planning

M3 - Conference contribution

SN - 9781577356769

SP - 10

EP - 18

BT - Proceedings of the Seventh Annual Symposium on Combinatorial Search

A2 - Edelkamp, Stefan

A2 - Bartak, Roman

PB - AAAI press

CY - Prague

ER -

Chrpa L, Kilani A, Balyo T. On Different Strategies for Eliminating Redundant Actions from Plans. In Edelkamp S, Bartak R, editors, Proceedings of the Seventh Annual Symposium on Combinatorial Search: (SoCs 2014). Prague: AAAI press. 2014. p. 10-18