An end to end view of the web service composition process involves the creation of an executable plan (work flow) that realizes the functionality of a new service and its deployment on an execution engine. A number of planning based techniques have been proposed recently for web service composition. However, in order to choose a suitable technique for an application scenario, one needs a formal classification and evaluation of these approaches. To this end, we first introduce a formalization of the Web service composition and execution process. Next, we classify popular service composition techniques found in the literature into four planning based approaches. We distinguish these approaches based on the type of input specifications they take, and the amount of control they give to a user who is supervising the process. Further, we analyse these approaches on the basis of multiple metrics that are relevant in the context of Web service composition. Finally, we present a case study by picking a service composition problem in the telecom domain, reasoning about our choice of approach for solving the problem, and providing an outline of the problem solution.