GOLOG is a high-level programming language for the specification of complex actions. It combines the situation calculus with control structures known from conventional programming languages. Given a suitable axiomatization of what the world is like initially and how the primitive actions change the world, the GOLOG interpreter derives for each program a corresponding linear sequence of legally executable primitive actions, if one exists. Despite its expressive power, GOLOG’s applicability is severely limited because the derivation of a linear sequence of actions requires that the outcome of each action is known beforehand. Sensing actions do not meet this requirement since their outcome can only be determined by executing them and not by reasoning about them. In this paper we extend GOLOG by incorporating sensing actions. Instead of producing a linear sequence of actions, the new interpreter yields a tree of actions. The idea is that a particular path in the tree represents a legal execution of primitive actions conditioned on the possible outcome of sensing actions along the way.