This position paper is concerned with the implications of limited computational resources and uncertainty on sensing and planning in robotic systems. To address the computational complexity of sensor interpretation and planning processes, we redefine their principal role. Following Agre and Chapman’s plan-as-communication approach, sensing and planning are treated as computational processes that provide information to an execution architecture and thus improve the overall performance of the system. We argue that robots must be able to trade off the quality of this information against its computational costs. Anytime algorithms, whose quality of results improves gradually as computation time increases, provide useful performance components for time-critical sensing and planning in robotic systems. The paper describes some of our current research directions and open problems.