2014
Backdoors to Planning
KRONEGGER, Martin, Sebastian ORDYNIAK a Andreas PFANDLERZákladní údaje
Originální název
Backdoors to Planning
Autoři
KRONEGGER, Martin (40 Rakousko), Sebastian ORDYNIAK (276 Německo, garant, domácí) a Andreas PFANDLER (40 Rakousko)
Vydání
Quebec, AAAI Press, od s. 2300-2307, 8 s. 2014
Nakladatel
AAAI Press
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
tištěná verze "print"
Odkazy
Kód RIV
RIV/00216224:14330/14:00077723
Organizační jednotka
Fakulta informatiky
ISBN
978-1-57735-679-0
Klíčová slova anglicky
parameterized complexity; planning; backdoors; causal graph
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 12. 5. 2020 19:52, RNDr. Pavel Šmerk, Ph.D.
Anotace
V originále
Backdoors measure the distance to tractable fragments and have become an important tool to find fixed-parameter tractable (fpt) algorithms. Despite their success, backdoors have not been used for planning, a central problem in AI that has a high computational complexity. In this work, we introduce two notions of backdoors building upon the causal graph. We analyze the complexity of finding a small backdoor (detection) and using the backdoor to solve the problem (evaluation) in the light of planning with (un)bounded plan length/domain of the variables. For each setting we present either an fpt-result or rule out the existence thereof by showing parameterized intractability. In three cases we achieve the most desirable outcome: detection and evaluation are fpt.
Návaznosti
| EE2.3.30.0009, projekt VaV |
|