Automated vVeb service composition is becoming an increasingly important research topic. It describes the automatic process of composing atomic services into a chain of services that provide a specific functionality that could not be achieved by atomic services alone. A service-oriented environment is dynamic in nature, meaning that services come online and go offiine, services change their functionality, etc. Current classical AI planning techniques suffer from the assumption of deterministic behavior of \Veb services and require execution monitoring for service failures. To address this concern, Partially Observable Markov Decision Processes (POMDP) in workflow composition has been used. POMDPs provide a powerful mathematical framework for planning and decision making in noisy and/ or dynamic environments. PO:\1DPs have been widely used to model many real-world problems. This thesis develops, implements and analyzes the suitability of the POMDP approach to the Web service composition problem. iii