A distributed multi-agent planning approach for automated 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. It aims at selecting and inter-connecting services provided by different partners in response to client requests. Planning techniques are used widely in the literature to describe web services composition problem. However, since web services proliferate day after day, classical planners are no longer well suited to compose web services in a reasonable time. This weakness is due to the explosion of the search space caused by the large number of services and the broad range of data exchanged among services. Therefore it is more interesting to use a decentralized planner to distribute the search space and the computing load taking into account the distributed nature of the problem. In this paper, we propose a distributed multi-agent approach to solving the web services composition problem at runtime. Our approach consists of a set of web services 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 best global plan for the submitted request. The analysis of the complexity and the results of the implementation show the ability of our approach to scaling up when compared to the state-of-the-art techniques for automated web services composition. © 2012 - IOS Press and the authors. All rights reserved.