An Efficient Syntactic Web Service Composition Algorithm Based on the Planning Graph Model

In this paper, we have studied a common Web service composition problem, the syntactic matching problem, where the output parameters of a Web service can be used as the input parameters of another Web service. Many automatic Web service composition algorithms based on AI planning techniques have been proposed. However, most of them do not scale well when the number of Web services increases, or may miss finding a solution even if one exists. The planning graph, another AI planning technique, provides a unique search space. We have found that when we model the Web service composition problem as a planning graph, it actually provides a trivial solution to the problem. Instead of following the usual way to find a solution by a backward search, we put our efforts into removing the redundant Web services contained in the planning graph. Our approach can find a solution in polynomial time, but with possible redundant Web services. We have tested our algorithms on the data set used in ICEBEpsila05 and compared our results with existing methods.