Cost-Sensitive Probabilistic Contingent Planning for Web Service Composition

This article presents a cost sensitive probabilistic contingent planning approach for automated semantic web service composition, under the assumptions that the execution of each web service incurs some cost; its alternative outcomes along with their probabilities of occurring are known in advance; and actions do not involve delete effects. The implemented planner, MAPPPA2, produces a contingent plan in the form of a decision tree, by integrating multiple alternative deterministic plans computed by solving a determinized version of the original problem. Both the generation of the alternative deterministic plans, as well as the merging process attempt to maximize the expected utility of the final contingent plan. The article presents evaluation results regarding the approach, based on three web service composition domains.