Reasoning about Actions and Planning in LTL Action Theories

Diego Calvanese, Giuseppe De Giacomo, and Moshe Y. Vardi

Proc. of the 8th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 2002). 2002.

In this paper, we study reasoning about actions and planning with incomplete information in a setting where the dynamic system is specified by adopting Linear Temporal Logic (LTL). Specifically we study: (i) reasoning about action effects (i.e., projection, historical queries, etc.), in such a setting; (ii) when actions can be legally executed, assuming a non-prescriptive approach, where executing an action is possible in a given situation unless forbidden by the system specification; (iii) the problem of finding conformant plans for temporally extended goals that consist of arbitrary LTL formulas, thus allowing for expressing sophisticated dynamic requirements. For each of these problems we establish techniques and characterize the computational complexity. For the last two problems we make use of a second-order variant of LTL.


@inproceedings{KR-2002,
   title = "Reasoning about Actions and Planning in LTL Action Theories",
   year = "2002",
  author = "Diego Calvanese and De Giacomo, Giuseppe and Moshe Y. Vardi",
   booktitle = "Proc. of the 8th Int. Conf. on the Principles of Knowledge
Representation and Reasoning (KR 2002)",
   pages = "593--602",
}
ps.gz pdf