Message-Based Web Service Composition, Integrity Constraints, and
  Planning under Uncertainty: A New Connection
  Thanks to recent advances, AI Planning has become the underlying technique
for several applications. Figuring prominently among these is automated Web
Service Composition (WSC) at the "capability" level, where services are
described in terms of preconditions and effects over ontological concepts. A
key issue in addressing WSC as planning is that ontologies are not only formal
vocabularies; they also axiomatize the possible relationships between concepts.
Such axioms correspond to what has been termed "integrity constraints" in the
actions and change literature, and applying a web service is essentially a
belief update operation. The reasoning required for belief update is known to
be harder than reasoning in the ontology itself. The support for belief update
is severely limited in current planning tools.
  Our first contribution consists in identifying an interesting special case of
WSC which is both significant and more tractable. The special case, which we
term "forward effects", is characterized by the fact that every ramification of
a web service application involves at least one new constant generated as
output by the web service. We show that, in this setting, the reasoning
required for belief update simplifies to standard reasoning in the ontology
itself. This relates to, and extends, current notions of "message-based" WSC,
where the need for belief update is removed by a strong (often implicit or
informal) assumption of "locality" of the individual messages. We clarify the
computational properties of the forward effects case, and point out a strong
relation to standard notions of planning under uncertainty, suggesting that
effective tools for the latter can be successfully adapted to address the
former.
  Furthermore, we identify a significant sub-case, named "strictly forward
effects", where an actual compilation into planning under uncertainty exists.
This enables us to exploit off-the-shelf planning tools to solve message-based
WSC in a general form that involves powerful ontologies, and requires reasoning
about partial matches between concepts. We provide empirical evidence that this
approach may be quite effective, using Conformant-FF as the underlying planner.
