While based on the Situation Calculus, current implementations of the
agent control language Golog typically avoid offering full first-order
capabilities, but rather resort to the closed-world assumption for the
sake of efficiency. On the other hand, realistic applications need to
deal with incomplete world knowledge including disjunctive
information. Recently Liu, Lakemeyer and Levesque proposed the logic
of limited belief SL, which lends itself to efficient reasoning in
incomplete first-order knowledge bases. In particular, SL defines
levels of belief which limit reasoning by cases in a principled
way. In this paper, we propose to apply SL-based reasoning in the
context of a Golog system. Central to our approach is a new search
operator that finds plans only within a fixed belief level k, and an
iterative-deepening-style variant where instead of considering plans
with increasing length, the belief level k is incremented in each
cycle. Thus, not the shortest plans are preferred, but those which are
the computationally cheapest to discover.