Backdoors to Planning

KRONEGGER, Martin, Sebastian ORDYNIAK a Andreas PFANDLER. Backdoors to Planning. In Carla E. Brodley and Peter Stone. AAAI Press. Quebec: AAAI Press, 2014, s. 2300-2307. ISBN 978-1-57735-679-0.

Zá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

• Originální 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"
• WWW: URL
• 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
• Štítky: core_A, firank_1
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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: Název: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci