Belief change in the presence of actions and observations: A transition system approach

The beliefs of an agent should change due to actions and observations. In particular, actions cause an agent to perform belief update, and observations cause an agent to perform belief revision. However, the interaction between actions and observations can be non-elementary; there are simple examples where it is clear that simply updating and revising in succession does not lead to plausible results. In this dissertation, we consider the belief change that occurs due to an iterated sequence of actions and observations. We assume that the effects of actions are given by a transition system, which can be used to define a belief update operator. We introduce a set of basic postulates that should intuitively be satisfied when a revision is followed by an update, and we use these postulates to define a new belief change operator. The new operator provides a plausible model of iterated belief change in the presence of actions, and it can be characterized by a modified class of systems of spheres. One limitation of this approach to iterated belief change is that it assumes the agent has perfect knowledge of the history of actions executed. We relax this assumption by using ranking functions to represent uncertainty about the actions executed at each point in time. The resulting formalism is able to represent fallible knowledge, erroneous perception, exogenous actions, and failed actions. Our work is distinguished from related work in that we explicitly consider the manner in which action histories affect the interpretation of observations. Our formal tools are useful not only for the representation of simple action domains, but also for the evaluation of related formalisms involving iterated belief change due to action.