最优广义规划的并行策略算法哈希规划器启发式

ParallelStrategiesforBest-FirstGeneralizedPlanning

最优广义规划的并行策略

摘要

近年来，人们对缩小最先进的规划求解器与广义规划（GP）之间的性能差距重新产生了兴趣。广义规划是人工智能（AI）的一个研究领域，旨在研究如何自动合成能够解决多个经典规划实例的类算法解决方案。当前的一项进展是引入了基于最佳优先搜索（Best-FirstGeneralizedPlanning,BFGP）的广义规划算法，该算法基于一种新颖的解空间，可以通过启发式搜索进行探索，而启发式搜索是现代规划器的基础之一。本文评估了并行搜索技术在BFGP中的应用，这是缩小性能差距的另一个关键组成部分。我们首先讨论了BFGP为何适合并行化，以及它与经典规划器的一些区别特征。然后，我们提出了两种简单的共享内存并行策略，这些策略能够随着核心数量的增加实现良好的扩展。

1引言

广义规划（GP）一直是人工智能（AI）中长期研究的一个领域[6,15]。广义规划的基础是自动规划，它研究如何构建从特定初始状态到目标状态的动作序列（通常称为计划）[3]。由于规划是一个难题（PSPACE完全问题）[1]，解决来自同一领域的多个问题实例在计算上是昂贵的。鉴于这一认识，广义规划研究如何合成能够解决来自同一领域的多个问题实例的通用计划，从而将计算复杂度降低为一次性前期成本[5,14]。

最先进的规划求解器通常是基于启发式的规划器[16]。这些规划器使用启发式方法引导从初始状态到目标状态的组合搜索，通常基于计算放松计划的解成本作为到达实际解的估计成本[2]。鉴于启发式搜索在规划中的成功，Segovia-Aguas等人[11,13]提出了一种基于启发式的广义规划方法，称为最佳优先广义规划（BFGP）。BFGP利用一组新颖的广义规划原生启发式方法和一个独立于输入实例数量的新解空间，来计算通用的算法解决方案。

尽管将并行技术用于经典规划器是一个活跃的研究课题，但其在广义规划中的应用却较少被探索。在本文中，我们讨论了BFGP算法如何通过设计轻松实现并行化。此外，我们提出了两种共享内存并行化策略，这些策略能够随着核心数量的增加实现线性扩展。

2最佳优先广义规划对并行化的适用性

3并行最佳优先广义规划

以下部分介绍了我们用于并行化BFGP的两种策略，并在9个不同的经典规划领域中评估了它们的性能；其中3个是命题领域（corridor、gripper和visitall），另外6个是数值领域（fibonacci、find、reverse、select、sorting和triangularsum）。

并行策略#1。该策略按顺序扩展节点，直到每个线程至少有N个节点。然后，它开始并行搜索，其中每个线程独立运行，不与其他线程共享节点。为了确保工作负载的平衡分配，N的值应根据需要更多程序行才能达到解的规划领域进行调整。表1评估了该策略的扩展性（单线程执行对应于原始BFGP实现）。

并行策略#2。在这种策略中，线程在并行搜索阶段分发有前途的节点，因此在搜索最有前途的状态和最小化通信开销之间存在权衡。在我们的解决方案中，我们计算每个生成节点的成本到目标值，如果该值等于或优于最后扩展的节点，我们将新节点发送给另一个线程。与HDA*不同，HDA*使用哈希函数确定哪个进程将接收节点，我们只是简单地在所有线程之间循环。这种方法是可行的，因为BFGP不需要执行重复检测。表2评估了该策略的扩展性。