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