Composition of web services using Markov decision processes and dynamic programming.

Area of Science:

• Computer Science
• Artificial Intelligence
• Operations Research

Background:

• Web service composition (WSC) is crucial for integrating distributed applications.
• Existing methods may struggle with large-scale WSC problems.
• Optimizing WSC for Quality of Service (QoS) attributes is a key challenge.

Purpose of the Study:

• To propose and validate a Markov decision process (MDP) model for solving the WSC problem.
• To evaluate the efficiency and effectiveness of different algorithms for WSC.
• To compare the proposed MDP approach with existing reinforcement learning techniques.

Main Methods:

• Formulation of the WSC problem as a Markov decision process.
• Experimental validation using iterative policy evaluation, value iteration, and policy iteration algorithms.
• Comparison with sarsa and Q-learning reinforcement learning algorithms.

Main Results:

• Policy iteration demonstrated superior performance, requiring fewer iterations for optimal policy estimation and achieving higher QoS.
• The MDP model efficiently solved large-scale WSC problems (100,000 services, 1,000 selected) in under 200 seconds.
• Real-world WSC problems with 7 services were solved in less than 0.08 seconds.
• MDP-based methods significantly outperformed sarsa and Q-learning in terms of computation time.

Conclusions:

• The proposed MDP model provides a reliable and efficient solution for the Web service composition problem.
• Policy iteration is the most effective algorithm within the MDP framework for WSC.
• The MDP approach offers a significant computational advantage over traditional reinforcement learning algorithms for WSC.