Abstract
Automated web service composition faces a significant challenge: the "data value explosion." Traditional AI planning techniques struggle when services handle large or infinite ranges of data values. This paper presents a framework that abstracts services into a Knowledge Level (KL) representation, allowing for efficient composition independent of specific data values.
Introduction
In modern web architecture, complex tasks are often fulfilled by stitching together multiple independent services—such as a furniture store, a credit card processor, and a shipping provider. Manually composing these services is tedious and error-prone. While AI planning offers a path toward automation, web services present unique difficulties: they are nondeterministic, asynchronous, and data-heavy. Standard planning techniques that track every possible value for every variable quickly encounter a state-space explosion, rendering them impractical for real-world applications.
Methodology
The authors propose a framework that shifts planning from the "data level" to the "knowledge level." Instead of tracking raw values (e.g., price = $50), the system tracks propositions about the data (e.g., K_v(price), meaning "the value of the price is known").
Key components of this approach include:
- Knowledge Base (KB) Abstraction: Tracking the state of knowledge rather than specific data values.
- Automatic Translation: A tool to automatically translate industry-standard BPEL4WS process descriptions into formal knowledge-level models.
- Planning as Model Checking: Adapting symbolic model checking to search for a controller that manages service interactions to reach a goal despite nondeterministic outcomes.
- Private Actions: Allowing the composite service to perform internal logic (like calculating totals) without external communication.
Experimental Evaluation
The approach was evaluated using two primary benchmarks. The first is the Purchase & Ship (P&S) scenario, which models the interactions between a User, a furniture Producer, and a Shipper.
The second benchmark involved Parametrized Synthetic Domains designed to test scalability across varying numbers of services and protocol complexities.
Key Results
The most significant finding is the robustness of the Knowledge Level approach against data range expansion. In the P&S example, "ground-level" planning (which tracks specific values) became unmanageable as the number of possible data values increased. In contrast, the KL approach maintained a near-constant execution time.
Furthermore, the system demonstrated strong scalability, successfully composing up to 14 services in approximately 20 minutes. Even with complex protocols requiring heavy message interleaving, the system handled compositions of up to 8 services efficiently.
Conclusion and Future Work
By planning based on the state of knowledge rather than raw data, the authors demonstrate that the complexity of service composition can be made independent of data value ranges. Future work will focus on expanding BPEL4WS coverage (e.g., handling fault handlers and compensation logic) and extending the framework to OWL-S to incorporate semantic reasoning into the planning process.
Summary updated