Skip to content. | Skip to navigation

Personal tools

Florian Marquardt (2009)

Evaluation of Planning Algorithms for Service Composition in Adhoc Multi Media Environments

In: Proceedings des gemeinsamen Workshops der Informatik-Graduiertenkollegs und Forschungskollegs 2009, ed. by Artin Avanes and Dirk Fahland and Johanna Geibig and Siamak Haschemi and Sebanstian Heglmeier and Daniel A. Sadilek and Falko Theisselmann and Guido Wachsmuth and Stephan Weißleder, pp. 149-150, Schloss Dagstuhl, GITO-Verlag Berlin.

Smart environments are characterized by dynamic ensembles of devices that offer individual services to the user in an unobtrusive manner. This user assistance in smart environments can be distinguished in four steps: Identifying of user intentions, deriving goals, synthesizing strategies and finally the execution of the strategy. Composition of services takes place in the third phase (strategy synthesis). Each composition method used during the synthesis phase aims at combining existing services to fulfill the identified goal. Many different methods for composing services exists, they are as different as the smart environments in which they shall work. Therefore, methods are required to select promising strategies for the smart environment at hand. AI planning is one possibility to realize service composition. To keep the composition process as unobtrusive as possible it must be fast and resource saving. Therefore different AI planning methods and algorithms must be characterized against its runtime and resource behavior. Composition in smart environments is based on the actual state of the environment, the available devices, and the intentions of the user(s).
We will consider all aspects of the current state of the world as the actual environment's context. This world state consists of sensor measurements and of assumptions that are made of this measures, e.g. by using models. Each device offers one or more services. These services are described by planning operators using preconditions and effects. Finally the users intentions are used to infer the planning goals. The result of a planning run is a plan. This plan represents a composition of services. The execution of this plan can be regarded as a new more complex service. Different planners have been evaluated referring to qualities like execution time and plan length. The evaluation results showed that current planners like UCPOP, SGP, and particularly LPG and blackbox, are suitable for composing services in time in a typical smart environment. However, their runtime behavior is irregular and contains peaks in the runtime of the planning process. The occurrence of these peaks was almost always caused by problems for which no plan does exist. However, this does not imply that such problems must cause a peak and that all planners need that long to identify a non-existing plan. Planners, that do not recognize that no plan exist in reasonable time, still consume resources. Resources are sparse in smart environments. So one option to avoid wasting resources would be to simply cancel a planner as soon as its runtime exceeds a certain threshold. Another option is to exploit the insight that due to their different algorithms planners do not behave similarly to same problems. Thus, to be really sure that no plan does exist, instead of simply cancel the current planer when a certain threshold is reached, another planer can be invoked which will return the result whether a plan exist or not, probably faster. Choosing the optimal threshold has one hard requirement. It should cut off all unnecessary planning runs, but must not abandon runs that will result in a plan. The amount of this threshold may be different for every planner requiring equal quality of the planning result. There is no reasonable way to identify the threshold analytical as we can not analyze the internal structure of the planner's implementations, thus it must be found experimental. The parameters for the planning experiments were number of planning operators, number of propositions (or state variables), number of goal states, number of initial world states and number of preconditions and effects. We used ten different values for each parameter which results in 10^5 theoretical domain/problem configurations. Due to some restrictions we gained 55.000 different configurations. Each configuration was initialized with 100 different seeds for the random number generator. And each of this 5.500.000 instances was tested with three planners (SGP, LPG and blackbox). Overall we conducted about 16.5 million experiment runs. The evaluation of this results is part of the ongoing work. A distributed and web service based architecture was designed and implemented to demonstrate the capabilities of AI-planning for service composition in smart environments in reality. Some of the effects gained in our experiments will be leveraged in this architecture.

ISBN-13: 9783940019738
Document Actions