Improve Planning Efficiency by Problem Reformulation to Facilitate Automated Service Composition

The Internet of Things (IoT) is an emerging paradigm where practically everything, including both physical and cyber things, is interconnected via the Internet to offer a wide spectrum of physical and cyber services. Traditionally, atomic services are composed to create more complex and value-added business processes. However, since many tasks in the IoT world arise dynamically, IoT services also need to be composed dynamically. To deal with this dynamic requirement, service composition in IoT should be automated to reduce human effort, especially for complicated real-world problems. In the literature, AI planning techniques have been widely applied to automate service composition. However, some major challenges still exist in automated IoT service composition research. First, IoT systems involve physical services which are quite different from software services, and a modified service model is required to deal with the mix of physical and software services. Also, to apply AI planning to automate service composition, an automated mapping framework is essential for converting service composition problems into planning problems. Existing mapping techniques neither consider physical services nor QoS-related properties and constraints on physical objects, while these missing elements add significant complexity to the framework and demand advanced research. The second challenge is the scalability of the planning algorithms. The vast collections of physical things and their services result in huge action and state sets in the planning problems, making it infeasible to derive solutions in a reasonable time limit. The third challenge is related to the traditional two-stage handling of QoS service composition (QSC) problems. Existing techniques assume that a predefined workflow is available. Though the workflow can be derived based on functional requirements, the independent processing potentially impacts the problem solvability and solution optimality. To overcome these challenges, this dissertation aims at developing solutions to facilitate feasible and efficient automating service composition using AI planning, especially for IoT applications. Correspondingly, we have developed three solutions in this dissertation. First, to facilitate applying existing planners in IoT service composition, we have developed a service model to properly define IoT services and physical things and the techniques that automatically map service composition problems to planning problems. Second, for the scalability challenge, we propose a Two-Level Planning (TLP) framework, which partitions a planning problem with a huge action set into two stages, each involving a significantly smaller action set. The first stage applies a planner to identify the actions relevant to the problem, and the second stage performs the planning process on the relevant action set to derive the final solution. With TLP, since the problems in both levels are much simpler than the original one, the overall planning efficiency is significantly improved. Experimental results show that TLP can effectively reduce the action sets by 39% and reduce the problem-solving time by up to more than two times. For the third challenge, we adopt the existing numeric AI planning techniques. To cope with the scalability issue, we introduce Provider Cardinality Reduction, a novel problem reformulation technique to improve planners’ efficiency in handling QSC problems and achieve efficient integrated QoS-based service composition. Our approach focuses on reducing the object set in the planning problems corresponding to QSC problems. Particularly, we estimate the number of providers (objects) required for the problems by analyzing the service influence relation. Also, we develop techniques to force the planners to select up to the estimated number of objects when searching for plans. As a result, the ground action set and the state space are greatly reduced, and the planners achieve significant speed-up. Experimental results show that our approach can reduce the QSC problem-solving time by up to 25 folds while retaining a competitive plan quality. Our work significantly enhances the state-of-the-art technologies in automated service composition, especially in improving planning efficiency by planning problem reformulation. Also, our problem reformulation solutions can be applied not only to automated service composition but also to a wide variety of application domains, allowing much more efficient problem solving for both classical and numeric planning problems.