【CMU博士论文】具有高计算代价边的图的并行搜索，126页pdf

基于搜索的规划算法使得机器人能够为实现特定任务目标制定基于合理推理的长期规划。它们将问题表述为在域状态空间中嵌入的图上的最短路径问题。许多研究致力于实现更快的规划速度，以使机器人能够快速响应环境变化。此外，随着任务复杂性的增加，在规划过程中纳入更复杂的模型，如模拟器变得尤为重要。然而，这些复杂模型的计算代价高昂，严重降低了规划速度。由于CPU时钟速度的停滞，单线程规划算法的性能已达到了瓶颈。另一方面，CPU核心数量显著增长，这一趋势可能将继续。这就需要能够利用并行化的规划算法。然而，与基于采样的规划算法不同，由于其顺序性质，要保持最优性或有界次优性，对基于搜索的规划算法进行并行化并非易事。机器人领域的一个关键特征是，在规划过程中，大部分计算工作都花在计算动作的结果和产生的边的代价上，而非搜索图。在本论文中，我们利用这一见解，开发了几种能够利用现代处理器的多线程功能并行计算边的并行搜索规划算法。我们证明了这些新颖算法在多个领域大大提高了规划速度。我们的第一个贡献是一个并行化的懒惰搜索算法，大规模并行懒惰规划（MPLP）。现有的懒惰搜索算法旨在作为单个进程运行，并通过在搜索图和评估边之间智能平衡计算工作以实现更快的规划。MPLP利用的关键思想是，搜索图和评估边可以异步并行执行。在理论上，我们证明了MPLP具有完整性和有界次优性的严格保证。

与所有懒惰搜索算法一样，MPLP假设后继状态可以在不评估边的情况下生成，从而使算法能够推迟边的评估并懒惰地进行搜索。然而，这个假设并不总是成立，例如，在使用计算量很大的模拟器生成后继状态的仿真规划中。为此，我们的第二个贡献是针对慢速评估的基于边的并行A*（ePA*SE），它在保证最优性的同时，将规划与边的并行评估交织进行。我们还提出了其有界次优变体，用规划速度换取最优性。

对于实时机器人领域的适用性，ePASE必须在时间预算下计算规划，因此具有随时性能。尽管期望降低解决方案的成本，但在这样的环境下，它并不是首要考虑的因素。我们的第三个贡献是随时适用的针对慢速评估的基于边的并行A（A-ePASE），它为ePASE带来了随时性能。

ePASE针对边计算时间昂贵但相似的领域。然而，在许多机器人领域，动作空间在评估动作结果及其成本所需的计算工作方面具有异质性。因此，我们的第四个贡献是通用的针对慢速评估的基于边的并行A（GePASE），它将ePASE推广到边计算差异显著的领域。我们展示了GePASE在异质动作领域优于ePASE和其他基线，因为它采用了一种并行化策略，明确考虑了评估所需的计算工作。

最后，我们在一个将图搜索技术与轨迹优化相结合的算法（INSAT）中展示了并行化的实用性。由于轨迹优化的计算成本高昂，在单线程上运行INSAT限制了其实际应用。所提出的并行版本——并行搜索与轨迹优化交织（PINSAT）实现了规划速度的数倍提升，并显著提高了成功率。