[Zurück]


Zeitschriftenartikel:

M. Kronegger, S. Ordyniak, A. Pfandler:
"Backdoors to planning";
Artificial Intelligence, 269 (2019), S. 49 - 75.



Kurzfassung englisch:
Backdoors measure the distance to tractable fragments and have become an important tool to find fixed-parameter tractable (fpt) algorithms for hard problems in AI and beyond. 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. For several interesting cases we achieve the most desirable outcome: detection and evaluation are fpt. In addition, we explore the power of polynomial preprocessing for all fpt-results, i.e., we investigate whether polynomial kernels exist. We show that for the detection problems, polynomial kernels exist whereas we rule out the existence of polynomial kernels for the evaluation problems.

Schlagworte:
Planning, Backdoors, Causal graph, Fixed-parameter tractable algorithms, (Parameterized) complexity


"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.artint.2018.10.002



Zugeordnete Projekte:
Projektleitung Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen

Projektleitung Stefan Woltran:
START


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.