Backdoors to Planning
| Autoři | |
|---|---|
| Rok publikování | 2014 |
| Druh | Článek ve sborníku |
| Konference | AAAI Press |
| Fakulta / Pracoviště MU | |
| 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: |