Non-Markovian control in the Situation Calculus

In reasoning about actions, it is commonly assumed that the dynamics of domains satisfies the Markov Property: the executability conditions and the effects of all actions are fully determined by the present state of the system. This is true in particular in Reiter's Basic Action Theories in the Situation Calculus. In this paper, we generalize Basic Action Theories by removing the Markov property restriction, making it possible to directly axiomatize actions whose effects and executability conditions may depend on past and even alternative, hypothetical situations. We then generalize Reiter's regression operator, which is the main computational mechanism used for reasoning with Basic Action Theories, so that it can be used with non-Markovian theories.