With a growing number of available services, each having slightly different parameters, preconditions and effects, automated planning on general semantic services become highly relevant. However, most exiting planners only consider PDDL, or if they claim to use OWL-S, they usually translate it to PDDL, losing much of the semantics on the way.
 In this paper, we propose a new domain-independent heuristic based on a semantic distance that can be used by generic planning algorithms such as A* for automated planning of semantic services described with OWL-S. For the heuristic to include more relevant information we calculate the heuristic at runtime. Using this heuristic, we are able to produce better results (fewer expanded states) in less time than with established techniques. We motivate our work by the need of a heuristic for AI planning. Since the search space of domain-independent planners for large problems becomes computationally intractable BID9 we need heuristics to guide our search through the state space.For domain-specific planners that have a special purpose (e.g., finding a route from one place to another for a GPS traffic guidance systems), a heuristic can easily be provided e.g. the Manhattan-Distance or the Euclidean distance. But for an agent which has the capability of creating general plans, these heuristics are not sufficient. This means it is impossible for our general purpose planner to create a problem specific heuristic at design time.Even reusing old ones like it is done for meta-heuristics or learning parameters of hyper-heuristics have only been successfully applied to simple problems BID20 . Meta-heuristics or hyper-heuristics have an additional drawback: they need a learning phase to gather information about the problem to be solved.The calculation of the heuristic during runtime is motivated by the additional information available like the grounding information which could consist of concrete in-dividuals to abstract classes describing e.g. the parameters of a service.The creation of heuristics during runtime can lead to the encounter of new concepts used in an interface definition like a service description, which then lead us back to a fundamental question in AI research: How can AI make sense of new concepts? For heuristics this means interpreting the new concepts and adding information to classical heuristic approaches. A function H : state → R + is called heuristic (Russel and Norvig 2002, p. 92) and estimates the distance from a state to a given goal. We extend this definition of heuristic to H : service × state × goal → R + making the heuristic more dynamic since now it is able to adapt with changing goals and services. With that, the heuristic determines the usefulness of the given service in the current state regarding a current goal. This is done because if an alone state would be the information source for the heuristic, information like the service description would be lost.The interested reader is referred to (Pearl 1985) for a formal description of heuristics and their properties. During our analysis of this topic, we have found that understanding the described functionality of a service is an AI-hard task BID26 . This is because interpretation of what a description creator might have understood the service to be, might not be entirely reflected in the description. Furthermore, the service can have multiple interpretations in different contexts. Here the context we defined is the additional information relevant to our problem. As an example strategy for problem-solving using a heuristic, we have selected planning. This means our context consists of the start and goal state which include a domain description.Starting from this setup, we need to evaluate if a capability is useful in the endeavour of finding a plan solving our problem.The approach presented in in Figure 1 is a goal-oriented heuristic at runtime utilizing the semantics of the goal and capability description. The heuristic is thought for a oneshop-planning problem, where it is expensive for the agent to try out services since we are looking at possible worldaltering capabilities, which means a learning phase should be kept as short as possible. This is done at runtime so that we know the goal we want to fulfill and can create a heuris- Figure 1: Abstract approach to a greedy heuristic tic reflecting the given problem. We do so by looking at the goal and the capability description we encounter to calculate the usefulness of a capability. Here the idea of the heuristic is to find useful capabilities to try in our search to the goal state, and reprobate others. The heuristic additionally estimates how much of the precondition is fulfilled to see which capabilities are more likely to be executed. These two evaluations of the service are then combined to create our heuristic. In this section we will first look at the state of the art of heuristics in Section 2. Then we create our goal oriented heuristic in Section 3, select a data set to test this heuristic on in Section 4 and discuss the results in Section 5. We conclude this experiment in Section 6.
Describing a semantic heuristics which builds upon an OWL-S service description and uses word and sentence distance measures to evaluate the usefulness of services for a given goal. 
{"src": "scitldr-AIC_train", "paper_id": "rJMK4bD6vE"}