We describe an implemented grid planner that has been used to compose workflows and schedule tasks on a computational Grid to solve scientific problems. We then discuss two issues that will demand further attention to make Grid and web service planners a reality. First, the planner must interact not only with external services that are to be composed in the final workflow, but also with external reasoners or knowledge bases containing information that is needed for the planning task, for example resource constraints and policies. Second, the planning system must provide for monitoring and re-planning strategies in order to manage the execution of a workflow in a dynamic environment.