Complexity of Planning in Action Formalisms Based on Description Logics

From International Center for Computational Logic

Toggle side column

Complexity of Planning in Action Formalisms Based on Description Logics

Maja MilicicMaja Milicic
Maja Milicic
Complexity of Planning in Action Formalisms Based on Description Logics
Proceedings of the 14th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2007), Lecture Notes in Artificial Intelligence, 2007. Springer
  • KurzfassungAbstract
    In this paper, we continue the recently started work on integrating action formalisms with description logics (DLs), by investigating planning in the context of DLs. We prove that the plan existence problem is decidable for actions described in fragments of ALCQIO. More precisely, we show that its computational complexity coincides with the one of projection for DLs between ALC and ALCQIO if operators contain only unconditional post-conditions. If we allow for conditional post-conditions, the plan existence problem is shown to be in 2-ExpSpace.
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
The final publication is available at Springer.
@inproceedings{ Milicic-LPAR07,
  author = {Maja {Milicic}},
  booktitle = {Proceedings of the 14th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning ({LPAR 2007})},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Artificial Intelligence},
  title = {Complexity of Planning in Action Formalisms Based on Description Logics},
  year = {2007},
}