Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Kronegger, A. Pfandler, S. Ordyniak:
"Backdoors to Planning";
Vortrag: Twenty-Eighth AAAI Conference on Aritifical Intelligence (AAAI 2014),
Québec City, Québec, Canada;
27.07.2014
- 31.07.2014; in: "Proceedings of the Twenty-Eighth AAAI Conference on Aritifical Intelligence",
C. Brodley, P. Stone (Hrg.);
AAAI Press,
(2014),
ISBN: 978-1-57735-661-5;
S. 2300
- 2307.
Kurzfassung englisch:
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.
Zugeordnete Projekte:
Projektleitung Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.