Grid computing is emerging as key enabling infrastructure for science. A key challenge for distributed computation over the Grid is the synthesis on-demand of end-toend scientific applications of unprecedented scale that draw from pools of specialized scientific components to derive elaborate new results. In this paper, we outline the technical issues that need to be addressed in order to meet this challenge, including usability, robustness, and scale. We describe Pegasus, a system to generate executable grid workflows given a high-level specification of desired results. Pegasus uses Artificial Intelligence planning techniques to compose valid end-to-end workflows, and has been used in several scientific applications. We also outline our design for a more distributed and knowledge-rich architecture.