In our previous work [JNP+10a, JNP+10b, DHJ+10] we introduced a common language to express what the services do. A plan how to reach a complex goal by combining simpler activities can be created automatically (or with a user interaction) by investigating relations between the descriptions of activities. However, our current experience in the field of the automatic composition and model checking indicates that even for relatively small environments the combinatorial explosion is the main obstacle in finding a solution in an effective way. While the size of the problem increases exponentially with the number of services, new intelligent algorithms have to be designed to cope with the WSC problem.
Another important issue in the domain of WSC is a planning with respect to time constraints. The temporal planning refers to the ability of planners to deal with temporal aspects of the planning problem [GSS06]. It takes into account the real duration of the actions and allows for their parallel execution. Concerning also these aspects, this makes the problem more difficult, but reflects better the real conditions of the problem the planner solves. An example of temporal aspects are durative actions, which play an important role in many domains. As a consequence the user may be interested in receiving from a planner exact times of services and time efficient plans. The next example of time aspects are temporally extended goals (user’s intentions), which do not only express classical goals of achieving some final state, but may also deal with temporal deadlines, safety, and maintenance goals.
In our solution we are going to take into account real time constraints. As before, to our best knowledge this constitutes an original contribution to the field of application of the combined evolutionary and model checking methods as the literature dealing with combining both the techniques does not consider the notion of real time. We intend to use here our experience acquired in the field of verification of real-time systems [NPS09, NPS10, KNN+08, KPS+10, PPo06]. The results of our preliminary research indicate that the use of two-phase planning is a good idea for reducing the search space. A successful solution seems to be also the use of tools and methods alleviating the exponential explosion, such as the SMT solvers and evolutionary algorithms. The results of combining approaches known from model checking and
artificial intelligence found in the literature [KPe08, KPe11, Joh07] are encouraging, which – together with our experience in these fields [Kpe05, KLN+06, PPo06, KNN+08, NPS09, NPS10, KNP+10, SND+10, SS07a, SS07c, SS08, SS09, SS09], and the area of WSC [JNP+10a, JNP+10b, NPP+10, DHJ+10] – justifies addressing the current project by our team.
The objective of this project is to develop effective and efficient methods of Web Services Composition (WSC). The problem of WSC suffers from a high computational complexity. To alleviate the combinatorial explosion while solving WSC we plan to introduce a new approach, which consists in combining symbolic methods known from model checking with evolutionary algorithms known from artificial intelligence. The proposed solution is a two-phase planning algorithm exploiting strengths of both the methods. As the final result of the project we intend to design and implement a system involving a uniform service description and supporting automatic and interactive WSC. Our software is to be deployed at CRiK – a medical facility in Łódź.