On Different Strategies for Eliminating Redundant Actions from Plans
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10285819" target="_blank" >RIV/00216208:11320/14:10285819 - isvavai.cz</a>
Výsledek na webu
<a href="http://www.aaai.org/ocs/index.php/SOCS/SOCS14/paper/view/8915" target="_blank" >http://www.aaai.org/ocs/index.php/SOCS/SOCS14/paper/view/8915</a>
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On Different Strategies for Eliminating Redundant Actions from Plans
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
On Different Strategies for Eliminating Redundant Actions from Plans
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2014
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Proceedings, The Seventh International Symposium on Combinatorial Search (SoCS 2014)
ISBN
978-1-57735-676-9
ISSN
—
e-ISSN
—
Počet stran výsledku
9
Strana od-do
10-18
Název nakladatele
AAAI Press
Místo vydání
Praha
Místo konání akce
Praha
Datum konání akce
15. 8. 2014
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—