Web Service Composition as Planning Revisited: Between Background Theories and Initial State Uncertainty

Thanks to its recent advances, AI Planning has become the underlying technique for several applications. Amongst these, one of the most prominent is automated Web Service Composition (WSC). However, one important issue in this context has been hardly addressed so far: WSC requires dealing with background ontologies. The support for background ontologies in current planning tools is severely limited. We introduce a planning framework that faithfully represents WSC. We show that, unsurprisingly, planning in such a framework is very hard. We then identify an interesting special case that covers many relevant WSC scenarios, and where the semantics are simpler and easier to deal with. This opens the way to the development of effective support tools for WSC. Furthermore, we show that if one additionally limits the amount of outputs that can be generated, then the problem can be compiled into a standard notion of initial state uncertainty. For this, effective tools exist; these can realize scalable WSC with powerful background ontologies. We demonstrate the potential of this idea with a set of experiments, showing how scaling WSC instances are comfortably solved by a tool incorporating modern planning heuristics.