We address two central problems causing a breakdown between planning and plan execution in robots. The first is the difficulty in reliably maintaining an accurate world model over time. Especially hard is the problem of perceptually segmenting objects and then tracking those objects. We suggest a representation language for plans that is based on perceptual data, not objects. The second major problem we address is the brittleness of plan operators. The execution of plan operators on actual robots has revealed the myriad of ways that the assumptions built into the construction of those operators can break. We suggest interleaving the execution of plans that contain sequences of motor and perceptual primitives, including operator failure. Having dramatically increased the size of each plan, we suggest a case-based representation as a means of keeping the search space tractable.