zbMATH — the first resource for mathematics

Reasoning about knowledge. (English) Zbl 0839.68095
Cambridge, MA: MIT Press. xiii, 477 p. (1995).
This book is concerned with reasoning about knowledge, in particular, reasoning about the knowledge of agents who reason about the world and each other’s knowledge. In the introduction, the authors give a simple, yet quite powerful formal semantic model for knowledge, and a language for reasoning about knowledge based on the notion of possible worlds. This model is applied to the analysis of the “muddy children” puzzle, a variant of the well-known “wise men” puzzle. In the following chapter, a complete characterization of the properties of knowledge in the possible-worlds model is given. Two approaches to its characterization are chosen. The first approach is proof-theoretic (showing that all properties of knowledge can be proved from the properties of the given possible-worlds model), the second one is algorithmic (studying algorithms that can determine whether a given property holds under the supplied definition of knowledge, and also considering the computational complexity of doing this). In the next chapters, the authors show how this semantic model of knowledge can be used to ascribe knowledge to agents in a multi-agent system, and they extend the model to incorporate actions, protocols, and programs. This allows a more careful analysis of how changes come about in multi-agent systems. Also the notion of a specification is defined, and the authors consider what it means for a protocol or program to satisfy a specification.
In the following chapter, the focus is shifted to common knowledge as a prerequisite for agreement and simultaneous coordination of actions. Given this framework, the notion of programs is extended to consider knowledge-based programs, which can be viewed as a high-level language in which to program or specify a system. A number of examples are given showing the usefulness of reasoning and programming at the knowledge level. In the next chapter, the focus is on how knowledge evolves over time in multiagent systems, and the formal implications this has on the properties of knowledge and associated system behavior. While the given framework, so far, implicitly assumes agents to be logically omniscient, in the next chapter this assumption is removed and several approaches are described for constructing abstract models that do not have the logical omniscience property. While the authors have argued, up to this point, for a notion of externally ascribed knowledge in multiagent systems, they now consider several applications, in which agents need to act on their knowledge, i.e., they have to be able to compute this knowledge on their own.
In the next chapter, the topic of common knowledge is reconsidered by treating situations in which common knowledge cannot be attained by the agents. So the paradox arises that common knowledge is considered a prereqisite for agreement and coordinated action, while at the time it cannot be attained in specific situations. The authors examine this paradox and suggest a number of weaker notions that can be attained in practice and that are often sufficient for acting in the real world.

68T30 Knowledge representation
68T01 General topics in artificial intelligence
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science