Service-Oriented Computing is a widely applied paradigm for establishing loosely coupled components on top of company networks and the World Wide Web. Services are reusable and interoperable entities that encapsulate business functionality behind standardized interfaces. Apart from the functional interface descriptions, service providers declare the Quality of Service (QoS), for instance the price and response time, of their services. By composing services, a virtually unlimited number of functionalities can be provided.

In the past decade, two main approaches towards service composition have emerged: service planning and service selection. The former approach employs AI planning to automatically generate workflows, whereas the latter refines given workflow templates. We claim that both approaches are insufficient to align the functional and non-functional requirements of the user. Planning lacks scalability and moreover neglects QoS aspects. Service selection on the other hand is inflexible; in case the required functionality changes, the template might become unusable. Moreover, functionally diverse services are not considered in selection algorithms. Both approaches rely on expensive ad-hoc replanning at runtime to deal with service failures. The major problem with such sequential application of composition and replanning is that it ignores the potential costs of replanning during the initial composition and they consequently are hidden from the user.

In this thesis, a holistic approach towards service composition is proposed that integrates service planning and service selection, bridging the gap between those two research areas. More specifically, we present the three following main contributions.

First, we propose a functional clustering of services that helps to determine backup services beforehand and to consider service functionalities. For each cluster, representative services are computed that are used in the following two contributions. An extended QoS model is introduced that estimates the impact of service failures on the QoS of a workflow.

Second, we present our planning algorithm, Keikaku, that computes workflows on an abstract level. By considering aforementioned representatives instead of single services, unnecessary comparisons of services can be avoided. This addresses the scalability issues of planning tools.

Third, we extend the original problem definition of service selection by considering functionally diverse services. In this setting, local optima are more likely, which leads to poorer results of heuristic algorithms that explore the search space in a more or less random manner. We propose two domain-specific extensions of Genetic Algorithms, called Shuuzen and Shuuri, that leverage our functional clustering as background knowledge to compute solutions efficiently.

We further present a holistic framework that unifies these three contributions and present a survey on the current usage of service computing.

本論文は「Robust Workflows by Applying Functional Clustering on Multi-Objective Service Composition(多目的のサービス合成における、機能クラスタリングの適用によるロバストなワークフローの構築) 」と題し,英文で記されており,8章から成る.利用可能なら多数のサービスに対し,機能および品質に関して求められる要求を満たすよう,サービスの組み合わせを自動合成することを目指した.わずかな差異が多くある機能側面を事前に整理するクラスタリング手法に基づき,機能と品質の双方,さらにサービスの障害の可能性も考慮した大きな問題設定に対し,スケーラビリティーのある手法を実現した.

様々なサービスの機能と品質を踏まえ,要求に応じてサービスを組み合わせるサービス合成問題は盛んに取り組まれてきた.従来,機能と品質が個別に順次取り組まれてきたが,機能の組み合わせをまず固定してしまうことにより最適とならない可能性がある.加えて,サービス障害などの可能性を踏まえて最適となるサービス合成は行われていない.以上において,こういった機能と品質,障害などの考慮などを十分に扱いつつスケーラビリティーを達成することは困難であった.

そこで本研究においては,複雑な機能差異を持つサービスの組み合わせを効率よく判定するためのクラスタリング手法を提案している.これにより直接的には機能的なプランニングを効率的に行えるようになる.本研究においてはさらに,このデータ構造により,総合的なサービス合成問題を効率的に解くことを可能としている.すなわち,サービス障害などの可能性,つまり代替えサービスの利用も予め考慮するように拡張しつつ,機能と品質の両面を総合的に扱うというサービス合成全体の問題に対し,クラスタリング手法に基づいた効率的な解法を提案している.

本論文は以下の8つの章から構成されている.

第1章では研究の概要を述べている.次に第2章では前提となる背景知識を説明し,課題を整理している.

第3章では本研究にて様々に活用される,サービスの機能に基づくクラスタリングが提案されている.これはサービスの入出力などのオントロジー,特に汎化・特化関係に基づくサービスの置換可能性を,効率よく探索できるように整理しておくものである.前述のように,この基本的な技術は,本研究において活用される.そのための準備として,サービス障害時などの代替えの観点から,サービスの集合に対する確率的な品質の定義や,提供者や地理が分散しているかの考慮などを行っている.また既存のデータセットを用い,クラスタの大きさなどの特性の評価を行っている.

第4章では,プランニングのための手法が提案されている.前章におけるクラスタリング結果を利用することで,プランニングのスケーラビリティーを高める手法を議論している.この際には,代替サービスも含めてサービスの候補集合を選ぶように問題を拡張しているほか,その候補集合に関する品質側面についても扱うようになっている.これにより,プランニングにおいて品質側面も行う既存研究(を本研究相当の問題を扱うよう拡張したもの)よりも高い品質(効用)を実現している.また,プランニングにおいて十分なスケーラビリティーを達成している.

第5章では,候補集合の中から,実際に利用するサービスの組み合わせを選択する問題を扱っている.このようなサービス選択問題は従来より盛んに扱われているが,その際には機能側面,特にサービス間の互換性は画一的に保証されていると仮定されていた.実際には機能(インターフェース)に差異があるため,それも考慮しつつ,品質を最適化するような組み合わせの選択が必要となる.本章では,遺伝アルゴリズムを拡張し適合させることにより,機能の差異のために入出力が結びつかない組み合わせを排除しつつ,品質を最適化する解法を提案している.具体的には,通常の遺伝アルゴリズムにおける種に対し,第3章のクラスタリング結果を用い,入出力を結び付けるような修正を加える.これにより,入出力が適切に結びつき,品質が最適に近い解を高速に求めることができるようになっている.

第6章では以上を統合する総合的なアプローチを提示し,人間の決定を支援するツールも構築,議論している.第7章では,実際にWebにて公開されているサービスのデータに関し,調査論文や自身による調査を通して議論し,本論文の実用性,将来性について議論している.第8章ではまとめを行っている.

以上のように本論文は,増加するWebサービスに対し,機能や品質,障害への対応といった様々な側面を考慮しての組み合わせという大きな目標に向けて着実に技術を進歩させている.特に従来の問題定義を統合,拡張しつつ,より困難な問題に対して十分にスケーラビリティーを達成する解法を提案している.特に提案した一つの基礎技術を,様々な応用,実用に適切に適合させ活用している.以上のように情報理工学における創造的実践の観点でも価値が認められる.

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる.