Towards Enhanced Efficiency And Expressiveness Of Automated Planning

As one of the most forefront and activity research areas on artificial intelli-gence, planning has an abroad application in aerospace, robots, industrial control, etc. Over the years, the demand of planning applications have been promoting the development of planning algorithm research. The performance of planning systems have been enhanced by several orders of magnitude in the past ten years. On the other hand, the planning algorithm research provides the essential theory and technical support, which largely boosts planning systems’usage in industrial applications. However, it still takes very long time, a few days or even months, to solve many large practical problems, even using the state-of-the-art planning algorithms, which obviously is unacceptable in realistic applications. On the oth-er hand, many practical problems have complex features, such as considering the time, resources, uncertainty, partially observable environment, etc., which can not be handled by most efficient classical planning algorithms. Therefore, the study towards enhanced efficiency and expressiveness of planning is quite essential to facilitate the usage of planning systems in practical problems.Mainstream efficient planning algorithms include heuristic state space search and planning as satisfiability. In order to improve the performance of state space search algorithms, most existing works are limited to one single thing:to improve heuristic functions. However, recent studies have shown that even if we have near-ideal heuristics, the number of searching states are still exponential. Therefore, we attempts to use some different methods, such as the random walk exploration and powerful computing platform, to improve the performance of state space search algorithms. On the other hand, we also propose a new SAT-based encoding strat-egy to extend the expressiveness of planning algorithms to handle more complex temporal features. Specifically, the main work, contributions, and innovation of this dissertation are as follows.(1) Improve the efficiency of planning with random-walk exploration. A well-observed phenomenon called "plateau exploration" is a common obstacle of state space search algorithms. The time spending on plateau exploration consists most of the search time in state-of-the-art planning algorithms. In this dissertation, we study the Monte-Carlo Random Walk (MRW) exploration, and propose a random-walk assisted best-first search algorithm for planning which invokes a random walk procedure to find exits when the best-first search is stuck on a plateau. Our experimental results show the advantages of using random-walk to assist best-first search for planning problems.(2) Improve the efficiency of planning with cloud computing. A direct way to enhance the efficiency of planning is using a powerful computing platform. Cloud computing is emerging as a prominent computing model. It is very desirable to develop suitable algorithms for cloud computing to exploit the large, affordable computational power, which obviously can largely improve the efficiency of planning. However, the high latency in inter-process commu-nication in cloud computing makes most existing parallel planning algorithms unsuitable for cloud computing. We study the running time distribution of Monte-Carlo Random Walk (MRW) search, and propose a portfolio stochastic-search framework that takes advantage of and is suitable for cloud comput-ing. Experimental results show that our algorithm achieves good, in many cases superlinear, speedup, greatly reduces the running time variance of the stochastic search, and improves the solution quality. Moreover, our scheme is economically sensible and robust under processor failures.(3) Extend the expressiveness of planning with new SAT-based encoding strat-egy. An essential quality of a planner is its capacity of modeling real-world problems, which is one of the main drawback of many efficient planning sys-tems. In this dissertation, based on the planning as satisfiability framework, we propose a new encoding scheme to handle a challenging real-word problem, cost-sensitive temporally expressive (CSTE) planning which requires concur-rency of durative actions concurrency and optimization of action costs. Our algorithm can find solution plans with optimal temporal makespan and min-imal total action costs at the optimal makespan. The experimental results show that our planner compares favorably to the state-of-the-art temporally expressive planners in both efficiency and quality.