Reasoning with Incomplete Initial Information and Nondeterminism in Situation Calculus

Abstract

Situation Calculus is arguably the most widely studied and used formalism for reasoning about action and change. The main reason for its popularity is the ability to reason about different action sequences as explicit objects. In particular, planning can be formulated as an existence problem. This paper shows how these properties break down when incomplete information about the initial state and nondeterministic action effects are introduced, basically due to the fact that this incompleteness is not adequately manifested on the object level. A version of Situation Calculus is presented which adequately models the alternative ways the world can develop relative to a choice of actions. 1 Introduction The contribution of this paper is to highlight some problems that arise in Situation Calculus when incomplete initial information or non-deterministic actions are considered, in particular when reasoning about plans. A new version of Situation Calculus is proposed that avoids these proble...