Beliefs of a resource-bounded agent

Abstract

Logics of belief and knowledge are typically formulated in terms of modal languages. A possible world semantics is traditionally used for such languages but when a formula A is read as "The agent believes that A", the problem of logical omniscience cannot be avoided. Given a set of possible worlds, this means that the agent believes all valid fomulae and believes all the logical consequences of his (initial) beliefs. This is not a good description of most situations in "real life" because both humans and robots are not ideal reasoners. They are resource-bounded: time or space is not adequate to infer all the logical consequences of their beliefs. Furthermore, an agent's rules by which he derives "new" beliefs from "old" ones are often incomplete so that even with unlimited time he cannot arrive at all the consequences. The database consisting of the beliefs of such an agent may be inconsistent without being contradictory. In Konolige's deduction model of belief he addresses the problem of resource-bounded agents. His semantics was developed in an effort to define accurate models of the beliefs of robots. By considering robots the (incomplete) set of rules of the agent is available to us, the outside observers. The semantics involves a set of initial beliefs and some algorithm which can be applied to these beliefs in order to derive new beliefs. The only assumption about the belief set of an agent will be that it is deductively closed, i.e. that no further beliefs will be produced if the algorithm is applied further. The terms deduction structure, belief set and deductively closed will be defined and the semantics explained. Several examples dealing with a propositional modal language will be given.