What is planning in the resence of sensing?*

Despite the existence of programs that are able to generate so-called conditional plans, there has yet to emerge a clear and general specification of what it is these programs are looking for: what exactly is a plan in this setting, and when is it correct? In this paper, we develop and motivate a speci-fication within the situation calculus of conditional and iter-ative plans over domains that include binary sensing actions. The account is built on an existing theory of action which includes a solution to the frame problem, and an extension to it that handles sensing actions and the effect they have on the knowledge of a robot. Plans are taken to be programs in a new simple robot program language, and the planning task is to find a program that would be known by the robot at the outset to lead to a final situation where the goal is sat-isfied. This specification is used to analyze the correctness of a small example plan, as well as variants that have redun-dant or missing sensing actions. We also investigate whether the proposed robot program language is powerful enough to serve for any intuitively achievable goal. Much of high-level symbolic AI research has been con-cerned with planning: specifying the behaviour of intelli-gent agents by providing goals to be achieved or maintained. In the simplest case, the output of a planner is a sequence of actions to be performed by the agent. However, a number of researchers are investigating the topic of conditional plan-ning (see for example, [3, 9, 14, 171) where the output, for one reason or another, is not expected to be a fixed sequence of actions, but a more general specification involving con-ditionals and iteration. In this paper, we will be concerned with conditional planning problems where what action to perform next in a plan may depend on the result of an ear-lier sensing action. Consider the following motivating example: *Thanks to the members of the University of Toronto Cognitiv