Dynamisch adaptive Planung individualisierter Touren

Abstract

Living in a dynamic and mobile environment being "always on" and "always connected", surrounded by smart devices and intelligent sensors, makes the vision of "ambient assisted living" in everyday life appear desirable and feasible. WebServices and the Semantic Web provide the technical means to find and use virtually offered relevant every day services pursuing the vision of developing personalized service-roadmaps. With "personal information environments" (PIE) Isbell and Pierce bridge the gap between virtual and physical worlds. This dissertation proposes dynamic adaptive planning of individualized tours as part of a PIE, an augmented reality connected to the real world with the need to navigate therein. It shows itself as alternative for navigating through a vast variety of physical signs providing unfiltered information for everyone. Introducing Frankfurt Airport as one representative of the problem domain clarifies the multi-dimensional orientation problem in dynamic environments. This formally corresponds to solving instances of Trip-Planning-Problems as has been outlined by Godard. Thus the very subject of this work is adaptive tour planning, which yields optimal personalized configuration of services and at the same time a spatially optimized order of services - an optimal tour. One the one hand, the complexity of the problem results from the combination of configuration and tour planning. On the other hand, it is due to the task of continual replanning in dynamic environments. In the first main part of this dissertation a new planning method has been developed, that computes personalized tours under time constraints and optimizes tours for maximum use and with respect to spatial criteria like locality and proximity. A hierarchical method consistently expands minimal tours and traces down the task to navigation planning between areas and configuration planning inside areas. The method plans minimal consistent tours for mandatory stages instantiating plan schemata taking the user context into account and iteratively extends these tours by areas of maximum use. It is shown that the method reduces the exponential planning problem to computationally feasible parts. Further on, for these parts an optimal and exact solution for the Trip-Planning-Problem is provided. Correctness and the computational complexity of methods and algorithms are proved.Spatial prerequisites - the building and route model - are also provided as a service and user model.In the second main part of this dissertation a dynamic and adaptive planning method has been developed, which supports users executing their tour plans and intervenes as soon as the plan execution appears to fail or may be optimized because of improving preconditions. The method integrates adhoc appearing, probably more relevant services into an existing plan, detects increasing or decreasing time quota during execution and adapts a plan to altering preconditions. Proactive and reactive plan monitoring strategies are introduced that continuously control preconditions during execution and act in advance with local corrections in order to defer expensive replanning tasks. In case of a user rejects a local correction, it is shown how replanning can be reduced to the incremental planning method introduced in the first main part. Comparing the results of the planning and replanning method of this dissertation with the results of an exact method shows that the method of planning maximum areas yields near optimal solutions and better solutions as far as the spatial optimization criteria are concerned.