ECAI 2004 Conference Paper

[full paper]

From knowledge-based programs to graded belief-based programs, Part I: On-line reasoning

Noel Laverny, Jerome Lang

Knowledge-based programs are a powerful notion for expressing action policies in which branching conditions refer to implicit knowledge and call for a deliberation task at execution time. However, branching contitions in knowledge-based programs cannot refer to possibly erroneous beliefs or to graded belief, such as ``if my belief that $\varphi$ holds is high then do some action $\alpha$ else perform some sensing action $\beta$''. The purpose of this paper is to build a framework where such programs can be expressed. In this paper we focus on the execution of such a program (a companion paper investigates issues relevant to the off-line evaluation and construction of such programs). We define a simple graded version of doxastic logic KD45 as the basis for the definition of belief-based programs. Then we study the way the agent's belief state is maintained when executing such programs, which calls for revising belief states by obvservations (possibly unreliable or imprecise) and progressing belief states by an physical action (which may have both normal and execptional effects).

Keywords: kmowledge representation, reasoning about action, belief revision and update, planning, reasoning under uncertainty

Citation: Noel Laverny, Jerome Lang: From knowledge-based programs to graded belief-based programs, Part I: On-line reasoning. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.368-372.