A Distributed Planning Approach for Web Services Composition

The ability to automatically answer a request that requires the composition of a set of web services has received much interest in the last decade, as it supports B2B applications. Planning techniques are used widely in the literature to describe the web services composition problem but they don´t scale up well. This weakness is due to the search space explosion caused by the large ranges of data exchanged among services. In addition, it is more interesting to use a decentralised planner because the nature of the problem is distributed. In this paper, we consider a set of web service agents where each agent has a set of services organised in a graph. To respond to a request, agents propose their best local partial plans which are partial paths in the graph. They then coordinate their partial plans to provide the global plan for the submitted request using an algorithm based on a distributed heuristic function. This function ensures the optimality and the completeness of the algorithm. Indeed, it is based not only on the agent capabilities to respond to a request, but also taking into account the plans proposed by other agents. The complexity of the algorithm is polynomial. The experiments show the ability of our approach to find the optimal solutions for automated web services composition taking into account the dependencies betwen the agents.