Tractable Reasoning about Group Beliefs
2014 (English)In: ENGINEERING MULTI-AGENT SYSTEMS, EMAS 2014, SPRINGER INT PUBLISHING AG , 2014, Vol. 8758, 328-350 p.Conference paper (Refereed)
In contemporary autonomous systems, like robotics, the need to apply group knowledge has been growing consistently with the increasing complexity of applications, especially those involving teamwork. However, classical notions of common knowledge and common belief, as well as their weaker versions, are too complex. Also, when modeling real-world situations, lack of knowledge and inconsistency of information naturally appear. Therefore, we propose a shift in perspective from reasoning in multi-modal logics to querying paraconsistent knowledge bases. This opens the possibility for exploring a new approach to group beliefs. To demonstrate expressiveness of our approach, examples of social procedures leading to complex belief structures are constructed via the use of epistemic profiles. To achieve tractability without compromising the expressiveness, as an implementation tool we choose 4QL, a four-valued rule-based query language. This permits both to tame inconsistency in individual and group beliefs and to execute the social procedures in polynomial time. Therefore, a marked improvement in efficiency has been achieved over systems such as (dynamic) epistemic logics with common knowledge and ATL, for which problems like model checking and satisfiability are PSPACE- or even EXPTIME-hard.
Place, publisher, year, edition, pages
SPRINGER INT PUBLISHING AG , 2014. Vol. 8758, 328-350 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 8758
Cooperation; reasoning for robotic agents; formal models of agency; knowledge representation; tractability
Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-119280DOI: 10.1007/978-3-319-14484-9_17ISI: 000354765300017ISBN: 978-3-319-14484-9ISBN: 978-3-319-14483-2OAI: oai:DiVA.org:liu-119280DiVA: diva2:820504
2nd International Workshop on Engineering Multi-Agent Systems (EMAS)