Abstract of the Ph.D. thesis:

Resource-Bounded Reasoning about Knowledge

submitted by Ho Ngoc Duc

The main goal of the thesis is to develop a framework for modeling
resource-bounded reasoning of realistic agents and to provide formal
theories of rational agency with a solid epistemic foundation.

The concept "agent" has turned out to be a very useful abstraction for
conceptualization in different areas of Computer science. In most
agent theories, agents are treated as intensional systems which are
characterized by means of mentalistic concepts like knowledge,
beliefs, goals, and intentions. Among them, the epistemic concepts
(knowledge and belief) are among the most important ones and have been
studied most intensively. They are usually formalized using systems of
modal logic. However, the modal approach to epistemic logic has a
major drawback: it suffers from the so-called logical omniscience
problem (LOP). It requires agents to know all logical truths and all
logical consequences of their knowledge. So the modal approach to
epistemic logic is not suited to formalize resource-bounded reasoning,
and the issue of resource-boundedness remains one of the main
foundational problems of any agent theory that is developed on the
basis of modal epistemic logic.

To solve the LOP I propose a strategy of modeling knowledge that takes
the cost of reasoning seriously. The main intuition is that an agent
may not know the consequences of his knowledge if he does not perform
the necessary reasoning actions. Because reasoning requires resources,
it cannot be safely assumed that the agent can compute his (implicit)
knowledge if he does not have enough resources to perform the required
reasoning. In modal epistemic logic, the usual form of an epistenmic
axiom is: "if an agent knows all premises of a valid inference rule
then he also knows the conclusion". In contrast, I have argued that
the correct form of epistemic axioms should be: "if an agent knows all
premises of a valid inference rule and if he performs the right
reasoning, then he will know the conclusion as well". This idea is
captured formally using a variant of dynamic logic: the result is a
family of dynamic-epistemic logics that formalizes the concept of
explicit knowledge, which solve all variants of the logical
omniscience problem and at the same time account for the intuition
that agents are rational.

Explicit knowledge can - in contrast to implicit knowledge - provide
justification for actions. However, explicit knowledge alone is not
enough for modeling agency. First, there are too few statements about
explicit knowledge that can claim validity. Second, it is not the only
kind of knowledge that agents can act upon. Certain actions not only
depend on what agents currently know but also on what they can compute
within specific amounts of time. If an agent needs to make a decision
within 1 hour then anything that he can compute within that time is
relevant for his decision. Thus, in order to predict and to explain an
agent's action correctly we need a framework for describing what an
agent can know under some specified resource constraints. For that
purpose I have introduced a concept of knowledge which contains a
direct reference to the amount of available resources. It can be
described informally as follows. An agent knows p within n time units
if he can compute p _reliably_ within n units of time. That is, if he
chooses to compute p then he will succeed after at most n time
units. The qualification "reliable" makes the agent's action
predictable: agents can act upon knowledge that can be computed
reliably. For formalizing this concept of knowledge, I have provided a
framework that combines epistemic logic with complexity analysis. I
have shown that within that framework, resouce-bounded reasoning can
be formalized correctly, the relationship between knowledge,
reasoning, and the availability of resources can be established, the
problems of traditional approaches can be avoided, and rich epistemic
logics can be developed which can account adequately for our
intuitions about knowledge.