Various essential tasks in multi-agent systems (MAS) such as planning, negotiation, decision making, coordination and cooperation require agents to have some capabilities to represent and reason about meta-belief (belief of other agents・ belief) and self-belief (belief about its own belief). In MAS that employ the game-theoretic approach, an agent needs to anticipate the actions of others in order to make rational decisions on what actions it should take. This requires an agent to model its own reasoning processes as well as the mental processes of other agents.Hence, an agent needs to build a belief model of itself and belief models of other agents. The self-descriptive model is necessary to specify what an agent expect others would do and models of other agents are needed to specify what others expects the agent would do. The pioneering work of Hintikka・s epistemic logic provides a formalism that can naturally capture the notions meta-belief and self-belief. However, Hintikka・s logic suffers from the logical omniscience problem.
Logical omniscience presupposes that an agent knows all logical consequences of its beliefs and all valid sentences (including tautologies).One of the most crucial problems associated with logical omniscience is that it results in computational intractability since the agent is required to compute all logical consequences of its beliefs.In practice, resource-bounded agents usually do not have sufficient time or memory to derive an explicit representation of each sentence.In the literature of epistemic reasoning, many logics were proposed to mitigate the logical omniscience problem. Although these logics have surface dissimilarities, a closer examination shows that they have strong resemblance. One of the contributions of this research establishing comparisons among existing logics and to address the issue of unification among them. This research considers a unifying logic that subsumes the semantics of various existing epistemic logics such asthe logic of implicit and explicit belief, the logic of awareness, the Cadoli-Schaerf epistemic model, Non-standard epistemic logic, the logic of local reasoning,Epistemic structures, the logic of implicit and explicit propositions and Fusion epistemic models.
Furthermore, it is noted that in most existing epistemic logics, the information in an agent・s knowledge base is usually represented by the two absolute notions of total belief and total disbelief. Unfortunately, restricting to such a belief-disbelief dichotomy limits the expressiveness of these logics because they lack the capabilities to represent comparative strength of belief which are common in real world applications. Multi-valued logic has been imported into artificial intelligence to deal with the notion of degree of belief. Of particular interest is Ginsberg・s multi-valued logic where various level of information such as incomplete information, default information, certain information and inconsistent information can be represented. These notions are particularly important in many sub-areas of artificial intelligence. For example, in default reasoning, (artificial) agents require the ability to reason with incomplete information. This is because in the real world complete information is hard to come by even in the most contrived situation. Furthermore, in multi-agent reasoning, an agent often has to deal with information coming from different sources (or other agents). In this context, inconsistencies may arise because the information that an agent receives from different agents may not always agree.
This research formulates a multi-valued epistemic logic (MEL) which combines the features of both multi-valued logic and epistemic logic, allowing the various notions of self-belief, meta-belief, degree of belief and degree of meta-belief to be represented. Additionally, MEL provides two methods for deriving belief : deductive-theoretic and model-theoretic. In the deductive-theoretic approach, an agent describes the state of the world (and the beliefs of other agents) with a collection of axioms and the conjunction of these axioms constitute its knowledge base. Consequently, the agent derives a belief by trying to prove or disprove whether it is a logical consequence ofits knowledge base. Under this interpretation, what the agent believes is exactly what can be deduced from its knowledge base using the rules of inference and axioms of the logic. This rests on the fact that the logic has a sound and complete axiomatization.In this research, it is proven that not only does MEL has a sound and complete axiomatization, but it also has a model-checking algorithm for deriving belief.
This research was carried out at the former Knowledge Science Institute (formerly, home of the International Journal of Human-computer Studies) at the University of Calgary, in Alberta, Canada.
Related Publications
In the model-theoretic approach, MEL characterizes the knowledge base of an agent with a class of semantics models (in this context, a model consists of a set of possible states representing the real world and a set of binary relations on these states). Thus, in MEL one can also derive a belief by checking whether it is true in each of the class of semantic models. Consequently, a belief which is true in all these models will also be provable because MEL has a complete axiomatization. Therefore, the problem of proving or disproving whether a belief is a logical consequence of an agent・s knowledge basecan be reduced to an instance of model-checking. In addition, it is shown that a belief in MEL can be checked in a finite number of steps.This is due to the fact that MEL is not only determined by (or sound and complete with respect to) a class of models, but it is also determined by a class of finite models and there is an algorithm to examine if a sentence is true in these models.It is proven that the algorithm to perform model-checking in MEL is of polynomial time complexity.
In outline, this thesis presents a logic that not only has a sound and complete axiomatization and is decidable, but also (i) has a unifying semantics for representing belief, (ii) provides a means to represent degree of belief and (iii) adopts both the deductive-theoretic and the model-theoretic approach for characterizing belief.
September, 1997 K. M. Sim