【作者】 吕强；

【导师】 陈国良；

【作者基本信息】 中国科学技术大学 ， 计算机软件与理论， 2013， 博士

【摘要】 作为人工智能最前沿和最活跃的研究领域之一,规划在航空航天、智能机器人、工业控制等领域有着极为广泛的应用。长期以来,规划的应用需求推动着规划算法的不断发展,规划系统的性能在过去10年中提高了好几个数量级。另一方面,规划算法的研究为规划的应用提供了必要的理论和技术支持,相应的也促进了规划器在工业应用中更广泛的使用。但是,由于很多实际应用问题的规模过大,即使用最好的规划算法求解仍需要很长的时间,数天甚至数月,这在实际应用中是难以接受的。而且很多实际问题具有很复杂的特性,比如考虑时间、资源、不确定(随机)、部分可观察的环境等,这些都是当前很多规划算法所不能高效解决的。因此,研究高效和更具表达力(处理复杂特性)的规划算法对促进规划系统在实际问题中的应用是十分必要的。主流的高效规划算法主要包括(启发式)状态空间搜索和基于命题逻辑的规划算法。为了提高状态空间搜索算法的性能,当前大多数的研究工作都专注于改进启发式函数。然而,最近的研究表明即使找到近乎理想的启发式,搜索的状态数仍是指数级的。因此,本文尝试采用不同的方法,比如随机游走搜索和功能强大的计算平台,来提高状态空间搜索算法的性能。另一方面,本文也提出新的基于命题逻辑的编码策略,扩展规划算法的表达能力以处理更复杂的时序特性。面向高性能和强表达力的规划研究具有重要的学术价值和广泛的应用前景。具体而言,本文的主要研究成果、贡献和创新点可概括为以下几点：(1)通过随机游走搜索提高规划算法性能“高原搜索”是困扰状态空间搜索一个常见的问题,对于当前最优秀的规划算法来说,高原搜索期的时间占总搜索时间的绝大部分。本文通过深入的学习蒙特卡罗随机游走算法,提出一个随机游走协助下的最好优先搜索算法。当陷入高原搜索期时,算法调用随机游走子程序帮助其尽快跳出高原搜索期从而达到加速整个搜索的目的。实验结果表明本文的算法相比于单纯的最好优先搜索具有更好的性能,也间接证明了MRW搜索确实可以帮助最好优先搜索更快的找到高原搜索期出口。(2)使用云计算平台提高规划算法性能提高规划算法性能的一个直接方法即是使用功能更强大的计算平台。云计算作为新兴的优秀计算平台,具有低耗散、高可访问性、高可用性、高可扩展性,低管理费用等优势,开发适合该平台的算法以充分利用其巨大的计算资源将可以大大提高规划算法的性能。然而,云计算平台上处理器之间的高通信延迟使得现有的并行规划算法并不适合该模型。本文通过深入的学习蒙特卡罗随机游走算法的搜索时间分布特性,并在此基础上提出一个合理利用云计算平台特性的并行算法。在一个本地云平台和微软的云平台上的测试结果表明该算法具有很多优势,包括可以获得良好的加速比(在许多问题上甚至可以达到超线性加速)、提高规划解的质量、大大降低搜索时间分布的可变性、良好的扩展性、良好的容错性以及计算成本的经济性。(3)采用基于命题逻辑的编码策略扩展规划算法表达力描述现实世界特性的表达力是规划算法的一个重要特征,然而,这也正是制约很多高效规划系统应用的一个主要因素。本文在命题逻辑规划的框架下,提出一个新的编码策略,扩展经典规划算法的表达能力以处理一类具有时序依赖和数值耗散约束的问题,即耗散敏感的富时序规划问题。这类问题除了要求基本的时序规划要素外,还要求时序动作的并发执行和总动作耗散的优化。本文的算法不仅可以高效地求解耗散敏感的富时序规划问题,同时可以保证找到具有最小时序长度的规划解,并且在最优时序长度的条件下,最小化解的总动作耗散。实验结果表明本文的算法相比于当前最好的一些富时序规划器也具有很强的竞争力。更多还原

【Abstract】 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.更多还原