Automatic composition of Web services is a very active area of research which has provided a lot of important results [10, 1, 15, 6] as well as many implemented approaches [11, 12, 2, 3, 13]. In this paper we present the system TripICS - a real-life application of our Web service composition system PlanICS [8, 9, 13] to planning trips and travels around the world. While there are systems offering some support for planning excursions and travels [4, 5], our system uses advanced automated concrete planning methods [13, 16, 14]. TripICS is a specialization of the concrete planning viewed as a constrained optimization problem to the ontology containing services provided by hotels, airlines, railways, museums etc. The system finds an optimal plan (solution) satisfying the requirements of the user by applying the most efficient concrete planners of PlanICS based on a combination of an SMT-solver [7] with the nature inspired algorithm: GA, SA, and GEO [16, 14]. Contrary to PlanICS, the first phase of planning, called abstract planning, is realized by TripICS in a semi-automatic way by giving the user a possibility to choose the elements of an abstract plan using a Graphical User Interface (GUI). In the remainder we present: the description of the system TripICS, the theory behind it, and the implementation followed by some experimental results and conclusions.
Our system is to allow the user for an easy and user-friendly planning of visits to interesting cities and places around the world in combination with travels in and out, arranged in the way satisfying the user’s requirements. The general assumption is that the user would like to receive an optimal plan of a travel starting and ending in given locations and offering a possibility of visiting some specified cities within some specified dates. A plan is optimal if its quality value is the highest according to the given criteria. Below, we make the above description much more precise by giving three lists of requirements: 1) the user has to set (obligatory requirements), 2) the user can optionally set (optional requirements), and 3) the predefined quality requirements. 2.1
Obligatory Requirements 1. Trip starts and ends in two given locations (cities), 2. Trip starts from a given date (or a period of time) and lasts for a given number of days (optionally can be shorter or longer by a specified number of days), 3. Trip involves visiting given cities, each city within a specified minimal/maximal number of days, 4. Hotels with the free cancellation option are booked (optionally free cancellation is not required if this reduces the price by a given factor in %), 5. In each city to be visited, the attractions specified in the optional rules, are available within the period of stay. 2.2
1. In each city, attractions (museums, exhibitions, matches, concerts, restaurants etc.)
to attend are specified,
2. Quality of hotels is specified by giving a minimal number of stars (
Clearly, a plan should be optimal in the sense that the travels should conveniently fit to the stays and the prices should be as low as possible for a required quality of hotels. The aim of TripICS is to return such plans if they exist. Formally, these plans need to satisfy the user requirements as well as the quality requirements specified below. 2.3
1. A travel connection between two cities is always direct if it exists, 2. Costs, durations, and the numbers of breaks of the travels are minimized, 3. Costs of the visits are minimized while their standards and durations are maximized. 3
Typically, PlanICS realizes planning in three well defined phases called: abstract planning, offer collecting, and concrete planing, after receiving a user query specifying the requirements. In TripICS we depart from using an abstract planner, which does free the user from formulating a user query in the specification language. Instead, the user is given a possibility to set the obligatory and optional requirements about expected plans using GUI, described briefly in Section 3.2. All the user’s choices, as well as the quality requirements, are automatically encoded as a user query and passed to the offer collector and the concrete planners. The available options result from the underlying ontology. 3.1
This section discusses the ontology exploited by TripICS. Fig. 1 shows a part of the ontology corresponding to a travel domain. The ontology defines three service types T ravel, Stay, and Entertainment aimed at providing instances of the T icket, Attraction, and Accommodation object types (and operating also on objects of type P erson and Location) which are the trip elements constituting (among others) the abstract plan.
A ticket represents a journey from one location to another, for a certain price. An accommodation corresponds to a stay in some location, for a certain price as well. An attraction represents an admission ticket for an event, a reservation, or a confirmation that the attraction is available at the specified time. All these objects contain attributes describing contexts and details of the particular trip elements. We introduce also two auxiliary object types: ABlock and V Block. This is to avoid duplication of common attributes using the inheritance mechanism.
Artifact Location ABlock Ticket VBlock
Thing Stamp
Person Accommodation Attraction
Service Location continent, country, city: String
P erson name: String; loc: Location Travel Stay ABlock begin, end: Date; price: Real; type: String Entertainment T icket f rom; to: Location; breaks: int
V Block reviews: Real; loc: Location Accommodation stars: Int; f reeCancel: Bool
Attraction reserved: Bool
For example, all the mentioned trip elements are described by the attributes begin, end, price, and type, and therefore they are inherited from the object type ABlock. The type attribute defines the transportation type (bus, train, plane, ship, etc.), the accommodation type (hotel, guest house, hostel, apartment, etc.), or the attraction type (museum, exhibition, match, concert, restaurant etc.), when used in the T icket, Accommodation, or Attraction object, respectively. On the other hand, the number of breaks is specific to travels only, and thus the attribute breaks is introduced in the object type T icket. Each accommodation (and attraction) has been assigned a number stored in the attribute reviews corresponding to the average score given by people who stayed there (or enjoyed the attraction) before. Similarly, since a fixed location is a common feature of accommodations and attractions, the attribute loc of type Location is introduced in the class V Block and inherited by Attraction and Accommodation object types. The attributes are summarized in Fig. 1. Note that their meanings follow intuitively from their names. 3.2
First, using an intuitive GUI, the user inputs information about the dates and trip duration. The next step is to select the cities to be visited by clicking on the map or searching them by name. The cities are added to the list at the left hand side (see Fig. 2). Then, the user adds accommodations and attractions to enjoy in the particular cities, and inputs his preferences in the forms attached to the list.
Finally, the user starts the planning process using the dedicated button, and optionally sets some planner options, such as a planning algorithm (SMT, GA, IPH, SCGEO, SCSA3 [16, 14]), timeout, maximal number of offers etc., as well as some parameters specific to the particular planning method, e.g., a population size of GA and IPH. 3.3
Basing on the city list and other data provided in the previous step, an abstract plan, i.e., a sequence of service types, is built. Next, this abstract plan is used by the offer collector (OC), i.e., the tool which in cooperation with the service registry queries real-world services. The service registry keeps an evidence of web services, registered accordingly to the service type system. Usually, each service type of the ontology represents a set of real-world services of similar functionality. For example, using the service type Stay one could register Booking.com as well as Hilton service.
OC queries web services of types present in the abstract plan and retrieves data called offers. An offer is a tuple of values representing a possible realization of one 3 SMT - the SMT-based planner, GA- the GA-based planner, IPH - the initial population hybrid planner (SMT + GA), SCGEO - the SMT combined with GEO planner, SCSA - the SMT combined with SA planner, where SMT (Satisfiability Modulo Theories), GA (Genetic Algorithm), SA (Simulated Annealing), GEO (Generalised Extremal Optimization) service type of the plan. Each value corresponds to an attribute of some object processed by the service type. The offers collected from a single service type of the plan constitute so called offer sets. The offers are searched by a concrete planner in order to find the best solution satisfying all constraints and maximizing the quality function. Thus, the concrete planning problem can be formulated as a constrained optimization problem (see [13]). Its solution consists in selecting one offer from each offer set such that all constraints are satisfied and the value of the quality function is maximized.
The constraints and the quality function result from the user requirements and preferences what is shown in the next subsection. 3.4
The constraints and the quality function play a crucial role in the planning process. In this section, using a simple example, we show how the user requirements and preferences in combination with several general rules (described in Sec. 2) result in a set of constraints and a quality function.
Example 1. Assume that the user wants to make a trip on the 15th of August from Warsaw (W) to Berlin (B) and then back in a few days. In Berlin, he prefers to stay in a 3-star hotel for 3 days and during the visit he plans to take a city tour and attend a concert. The specified requirements result in an abstract plan consisting of the following 5 service types: (T ravel, Stay, Entertainment, Entertainment, T ravel). Then, OC searches for the matching offers, and retrieves the following example five offer sets (O1; : : : ; O5).
O1(T ravel) id begin end price type from to breaks 1 15.08, 10:40 15.08, 12:05 565 plane W B 0 2 15.08, 06:20 15.08, 07:45 565 plane W B 0 3 15.08, 07:20 15.08, 12:05 533 plane W B 1 4 15.08, 14:05 15.08, 19:18 170 train W B 0 5 15.08, 18:05 15.08, 22:58 276 train W B 0 possible realizations. Thus, the search space is of size 55 = 3125 as there is so many we take constraints into account.
For example, assume that the user wants to synchronise travels and hotel in such a way that the time between arrival and hotel check-in is not longer than 3 hours. Similarly, the return travel should be not later than 3 hours after the hotel checkout time. After adding these two constraints the number of the possible solutions decreases to 2200. Another constraint could be to have at least a three-hour break between attractions. When this constraint is taken into account, there are only 1408 possible solutions. The underlying constraints are encoded by the following expressions: (o2:begin o1:end 3), (o5:begin o2:end 3), (o4:begin o3:end 3), where oi represents an offer from the i-th offer set.
As to the quality function, the user can choose between several schemes, but he can also enable/disable some of the function components. For example, if the user prefers only to minimize the total price, the quality function is expressed by Wprice Pi=1::5 oi:price, and the optimal solution is (4; 4; 5; 3; 4) with the price 1561, where Wprice is some negative constant (a weight). The numbers in the sequence correspond to the numbers of the offers in the corresponding offer sets. That is, both the travels are by train for the price of 170 each, the stay is in the cheapest hotel, and the cheapest tour and concert are chosen. However, if the user also wants to maximize the reviews of the stay and attractions, the quality function is then as follows: Wprice Pi=1::5 oi:price + Wscore Pi=2::4 oi:score. Assuming Wprice = 1 and Wscore = 10, we obtain the optimal solution (4; 1; 3; 2; 4) where the accommodation and attractions with a low price and a high score are chosen. Fig. 3 presents the resulting plan.
The TripICS application is implemented in Java. It consists of several planning engines, Offer Collector, and the GUI module. GUI exploits GMapsFX [17] project which provides a wrapper to the Google Map’s Javascript API, allowing to exploit and interact with maps using a pure Java. The map is the central component in GUI. It is used to specify user requirements as well as to visualize plans. The application is still being extended and improved.
We have evaluated the efficiency of TripICS focusing on the planning modules. At the moment our Offer Collector supports only a limited number of services. Thus, we have used several benchmarks generated by our software Offer Generator. They have been scaled by the length of a plan and the number of offers. Plans of length 5 have been found for the benchmarks T1, T2, and T3, of length 9 for T4, T5, and T6, and of length 13 for the remaining examples. The number of offers equals 28 = 256 for the benchmarks T1, T4, and T7; 29 = 512 for T2, T5, and T8; and 210 = 1024 for the other cases. This gives a number of the potential solutions varying from 2565 = 240 for T1 to 102413 = 2130 for T9. The tested examples involved from 13 to 43 constraints. We have compared several planning algorithms taking into account the computation time and the quality of the solutions found. The methods combining SMT with natureinspired algorithms appear to be the most efficient. They are able to find solutions of very high quality within a few seconds only, which makes them acceptable for the user. The detailed results are given in Table 1 and summarised in Fig. 4.
250 200 )150 Q ( G VA100 50 0
SMT
SCSA
SCGEO
IPH500 GA
IPH1 160 140 120 )P100 * (t/Q80 G VA60 40 20 0
SMT
SCSA
SCGEO
GA
IPH1
IPH500 Concreteplanningmethods
Concreteplanningmethods We have presented a preliminary version of our system TripICS, which can be used for planning trips and travels around the world. Our motivation for developing this system was twofold. Firstly, we wanted to show that web service composition can be successfully used in practice for real-life applications, and secondly our aim is to offer a new useful tool, which could be publicly used.