Taming the complexity of linear time BDI logics

Reasoning about the mental states of agents is important in various settings, and has been recognized as vital for teamwork. But the complexity of some of the more well-known agent logics that facilitate reasoning about mental states prohibits the use of these logics in practice. An alternative is to investigate fragments of these logics that have a lower complexity but are still expressive enough for reasoning about the mental states of (other) agents. We explore this alternative and take as our starting point the linear time variant of BDI logic (BDIltl). We summarize some of the relevant known complexity results for e.g. LTL, KD45n, and BDIltl itself. We present a tableau-based method for establishing complexity bounds, and provide a map of the complexity of (various fragments of) BDIltl- Finally, we identify a few fragments that may be usefully applied for reasoning about mental states. Categories and Subject Descriptors 1.2.11 [Artificial Intelligence]: Distributed Artificial Intelligence-Multiagent Systems; 1.2.4 [Artificial Intelligence]: Knowledge Representation Formalisms and Methods-Modal logic General Terms Theory, Verification.