Taming the complexity of linear time BDI logics

Nils Bulling, Koen V. Hindriks

Research output: Contribution to ConferencePaperAcademic

Abstract

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.

Original languageEnglish
Pages257-264
Number of pages8
Publication statusPublished - 1 Jan 2011
Externally publishedYes
Event10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 - Taipei, Taiwan, Province of China
Duration: 2 May 20116 May 2011

Conference

Conference10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011
CountryTaiwan, Province of China
CityTaipei
Period2/05/116/05/11

Fingerprint

Artificial intelligence
Knowledge representation
Multi agent systems

Keywords

  • Complexity
  • Linear time BDI logic
  • Reasoning about mental states
  • Satisfiability

Cite this

Bulling, N., & Hindriks, K. V. (2011). Taming the complexity of linear time BDI logics. 257-264. Paper presented at 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011, Taipei, Taiwan, Province of China.
Bulling, Nils ; Hindriks, Koen V. / Taming the complexity of linear time BDI logics. Paper presented at 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011, Taipei, Taiwan, Province of China.8 p.
@conference{789001f612bd4974a920b554a3902460,
title = "Taming the complexity of linear time BDI logics",
abstract = "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.",
keywords = "Complexity, Linear time BDI logic, Reasoning about mental states, Satisfiability",
author = "Nils Bulling and Hindriks, {Koen V.}",
year = "2011",
month = "1",
day = "1",
language = "English",
pages = "257--264",
note = "10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 ; Conference date: 02-05-2011 Through 06-05-2011",

}

Bulling, N & Hindriks, KV 2011, 'Taming the complexity of linear time BDI logics' Paper presented at 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011, Taipei, Taiwan, Province of China, 2/05/11 - 6/05/11, pp. 257-264.

Taming the complexity of linear time BDI logics. / Bulling, Nils; Hindriks, Koen V.

2011. 257-264 Paper presented at 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011, Taipei, Taiwan, Province of China.

Research output: Contribution to ConferencePaperAcademic

TY - CONF

T1 - Taming the complexity of linear time BDI logics

AU - Bulling, Nils

AU - Hindriks, Koen V.

PY - 2011/1/1

Y1 - 2011/1/1

N2 - 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.

AB - 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.

KW - Complexity

KW - Linear time BDI logic

KW - Reasoning about mental states

KW - Satisfiability

UR - http://www.scopus.com/inward/record.url?scp=84885006654&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84885006654&partnerID=8YFLogxK

M3 - Paper

SP - 257

EP - 264

ER -

Bulling N, Hindriks KV. Taming the complexity of linear time BDI logics. 2011. Paper presented at 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011, Taipei, Taiwan, Province of China.