Web service composition (WSC) problems involve using domain knowledge about the underlying problem domains during the composition process. Existing research on Web service composition procedures has generally assumed that this domain knowledge is encoded as a single ontology that must be provided as an input to a composition procedure. In composition problems that span over knowledge across multiple ontologies that are connected via concept inheritence/ extension, the users must examine the available ontologies and services in order to decide for the extent of the domain knowledge and the set of services relevant to their composition problems in hand.

In this paper, we describe an automated way to generate solutions for service composition problems that span over multiple ontologies that have similar but not exactly the same structure. Our approach is based on a Hierarchical Task Network (HTN) planning model and extends the HTN-DL framework. This HTN planning model allows ontological problem decomposition in order to evaluate structural properties that span across multiple ontologies that are relevant to an input composition problem. We present a demonstration of the advantages of this approach.