The increase in the use of mobile & embedded devices, coupled with ad-hoc, short range wireless networking is enabling pervasive computing. This pervasive computing environment and the wired Grid infrastructure can be combined to make the Computation and Information Grid truly pervasive. This paper identifies some of the interesting research issues and challenges in creating such a pervasive Grid, and describes some preliminary work we have done to that end. We propose a runtime environment for the Pervasive Grid that utilizes a multi agent framework, and provides for discovery of services being offered by sensors, embedded and mobile devices, and their composition. The computation in this environment needs to be dynamically partitioned between the traditional Grid and elements that constitute the pervasive environment, like sensors, with limited computing and communication capabilities.