面向高性能和强表达力自动规划论文

《面向高性能和强表达力自动规划论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、I㈣燃56Y22801Univer∈CU．,ofScienceandTechnologyofhinaniversitvofScienceand1bchnologyofhinaAdissertationfordoctordegreeTowardsEnhancedEfficiencyandExpressivenessAuthorofAutomatedPlanningQiangLuSpeciality：ComputerSoftwareandTheorySupervisor：FinishedTimeProf．Gu

2、oliangChenMay，2012摘要作为人工智能最前沿和最活跃的研究领域之一，规划在航空航天、智能机器人、工业控制等领域有着极为广泛的应用。长期以来，规划的应用需求推动着规划算法的不断发展，规划系统的性能在过去10年中提高了好几个数量级。另一方面，规划算法的研究为规划的应用提供了必要的理论和技术支持，相应的也促进了规划器在工业应用中更广泛的使用。但是，由于很多实际应用问题的规模过大，即使用最好的规划算法求解仍需要很长的时间，数天甚至数月，这在实际应用中是难以接受的。而且很多实际问题具有很复杂的特性，比

3、如考虑时间、资源、不确定(随机)、部分可观察的环境等，这些都是当前很多规划算法所不能高效解决的。因此，研究高效和更具表达力(处理复杂特性)的规划算法对促进规划系统在实际问题中的应用是十分必要的。主流的高效规划算法主要包括(启发式)状态空间搜索和基于命题逻辑的规划算法。为了提高状态空间搜索算法的性能，当前大多数的研究工作都专注于改进启发式函数。然而，最近的研究表明即使找到近乎理想的启发式，搜索的状态数仍是指数级的。因此，本文尝试采用不同的方法，比如随机游走搜索和功能强大的计算平台，来提高状态空间搜索算法的性

4、能。另一方面，本文也提出新的基于命题逻辑的编码策略，扩展规划算法的表达能力以处理更复杂的时序特性。面向高性能和强表达力的规划研究具有重要的学术价值和广泛的应用前景。具体而言，本文的主要研究成果、贡献和创新点可概括为以下几点：f1)通过随机游走搜索提高规划算法性能“高原搜索”是困扰状态空间搜索一个常见的问题，对于当前最优秀的规划算法来说，高原搜索期的时间占总搜索时间的绝大部分。本文通过深入的学习蒙特卡罗随机游走算法，提出一个随机游走协助下的最好优先搜索算法。当陷入高原搜索期时，算法调用随机游走子程序帮助其尽

5、快跳出高原搜索期从而达到加速整个搜索的目的。实验结果表明本文的算法相比于单纯的最好优先搜索具有更好的性能，也摘要间接证明了MRW搜索确实可以帮助最好优先搜索更快的找到高原搜索期出口。f21使用云计算平台提高规划算法性能提高规划算法性能的一个直接方法即是使用功能更强大的计算平台。云计算作为新兴的优秀计算平台，具有低耗散、高可访问性、高可用性、高可扩展性，低管理费用等优势，开发适合该平台的算法以充分利用其巨大的计算资源将可以大大提高规划算法的性能。然而，云计算平台上处理器之间的高通信延迟使得现有的并行规划算法

6、并不适合该模型。本文通过深入的学习蒙特卡罗随机游走算法的搜索时间分布特性，并在此基础上提出一个合理利用云计算平台特性的并行算法。在一个本地云平台和微软的云平台上的测试结果表明该算法具有很多优势，包括可以获得良好的加速比(在许多问题上甚至可以达到超线性加速)、提高规划解的质量、大大降低搜索时间分布的可变性、良好的扩展性、良好的容错性以及计算成本的经济性。(3)采用基于命题逻辑的编码策略扩展规划算法表达力描述现实世界特性的表达力是规划算法的一个重要特征，然而，这也正是制约很多高效规划系统应用的一个主要因素。本

7、文在命题逻辑规划的框架下，提出一个新的编码策略，扩展经典规划算法的表达能力以处理一类具有时序依赖和数值耗散约束的问题，即耗散敏感的富时序规划问题。这类问题除了要求基本的时序规划要素外，还要求时序动作的并发执行和总动作耗散的优化。本文的算法不仅可以高效地求解耗散敏感的富时序规划问题，同时可以保证找到具有最小时序长度的规划解，并且在最优时序长度的条件下，最小化解的总动作耗散。实验结果表明本文的算法相比于当前最好的一些富时序规划器也具有很强的竞争力。关键词：自动规划状态空间搜索蒙特卡罗随机游走搜索云计算并行规划

8、富时序规划命题逻辑规划I工ABSTRACTAsoneofthemostforefrontandactivityresearchareasonartificialintelli—gence，planninghasanabroadapplicationinaerospace，robots，industrialcontrol，etc．Overtheyears，thedemandofplanningapplicationshavebe