Backdoors to Planning

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

Basic information

• Original name: Backdoors to Planning
• Authors: KRONEGGER, Martin (40 Austria), Sebastian ORDYNIAK (276 Germany, guarantor, belonging to the institution) and Andreas PFANDLER (40 Austria).
• Edition: Quebec, AAAI Press, p. 2300-2307, 8 pp. 2014.
• Publisher: AAAI Press

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: United States of America
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: printed version "print"
• WWW: URL
• RIV identification code: RIV/00216224:14330/14:00077723
• Organization unit: Faculty of Informatics
• ISBN: 978-1-57735-679-0
• Keywords in English: parameterized complexity; planning; backdoors; causal graph
• Tags: core_A, firank_1
• Tags: International impact, Reviewed

Abstract

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.

Links

• EE2.3.30.0009, research and development project: Name: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci