Pervasive Computing envisions a world with users interacting naturally with device-rich environments to perform various kinds of tasks. These environments must, thus, be self-managing and autonomic systems, receiving only high-level guidance from users. However, these environments are also highly dynamic — the context and resources available in these environments can change rapidly. They are also prone to failures — one or more entities can fail due to variety of reasons. The dynamic and fault-prone nature of these environments poses major challenges to their autonomic operation. In this paper we present a new paradigm for the operation of pervasive computing environments that is based on goal specification and STRIPS-based planning. Users as well as application developers can describe tasks to be performed in terms of abstract goals and a planning framework decides how these goals are to be achieved. This paradigm helps improve the fault-tolerance, adaptability, ease of programming and usability of these environments. We have developed and used a prototype planning system within our pervasive computing system, Gaia.