Backdoors to Planning

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

KRONEGGER Martin ORDYNIAK Sebastian PFANDLER Andreas

Rok publikování 2014
Druh Článek ve sborníku
Konference AAAI Press
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www https://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8376
Obor Informatika
Klíčová slova parameterized complexity; planning; backdoors; causal graph
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.