SLOPE: Search with Learned Optimal Pruning-based Expansion

📄 arXiv: 2406.04935v1 📥 PDF

作者: Davor Bokan, Zlatan Ajanovic, Bakir Lacevic

分类: cs.AI, cs.LG

发布日期: 2024-06-07

备注: presented at the ICAPS 2024 workshop on Bridging the Planning and Reinforcement Learning

🔗 代码/项目: GITHUB

💡 一句话要点

提出基于学习最优剪枝扩展的搜索算法SLOPE，提升运动规划效率。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 启发式搜索 运动规划 路径寻找 剪枝算法 机器学习 最优路径 空间复杂度

📋 核心要点

  1. 启发式搜索在运动规划中面临空间复杂度挑战，大量节点存储和排序消耗资源。
  2. SLOPE学习节点到最优路径的距离，剪枝远离最优路径的节点，减小搜索空间。
  3. 实验表明SLOPE能有效降低开放列表大小，并可与现有启发式方法结合使用。

📝 摘要（中文）

本文提出了一种名为“基于学习最优剪枝扩展的搜索”（SLOPE）算法，用于解决启发式搜索在运动规划和路径寻找问题中空间复杂度高的难题。与学习代价估计值的传统方法不同，SLOPE学习节点到潜在最优路径的距离，并根据该距离剪枝不被看好的节点，从而减小开放列表的大小。这确保了搜索仅探索接近最优路径的区域，同时降低了内存和计算成本。该方法与代价估计启发式算法正交，为提高搜索效率提供了一种互补策略。实验表明，SLOPE作为独立搜索方法以及与学习的启发式函数结合使用时，在降低开放列表中子节点数量的同时，实现了可比甚至更好的节点扩展指标。代码已开源。

🔬 方法详解

问题定义：启发式搜索，如A*算法，在运动规划等问题中需要维护一个开放列表，存储所有已扩展但未访问的节点。当问题规模增大时，开放列表会变得非常庞大，导致内存消耗过高，排序操作耗时，限制了算法在实时性和计算资源受限场景下的应用。现有方法主要集中于优化启发式函数，以更准确地估计代价，但无法直接减少开放列表的大小。

核心思路：SLOPE的核心思想是学习一个“节点到最优路径的距离”的概念。不同于学习代价估计（cost-to-go），SLOPE旨在预测一个节点是否位于或接近最优路径。基于这个距离，算法可以安全地剪枝那些远离最优路径的节点，从而显著减小开放列表的大小，降低内存和计算负担。

技术框架：SLOPE算法主要包含以下几个阶段：1）训练阶段：使用监督学习，训练一个模型来预测节点到最优路径的距离。训练数据通过在已知最优路径的图上采样获得。2）搜索阶段：在搜索过程中，对于每个新生成的节点，使用训练好的模型预测其到最优路径的距离。3）剪枝阶段：根据预测的距离，将距离超过一定阈值的节点从开放列表中移除，从而减小开放列表的大小。4）扩展阶段：从剩余的开放列表中选择最优节点进行扩展，重复步骤2和3，直到找到目标节点。

关键创新：SLOPE的关键创新在于它学习的是节点到最优路径的距离，而不是传统的代价估计。这种方法与代价估计是正交的，可以作为一种互补的策略来提高搜索效率。通过直接剪枝远离最优路径的节点，SLOPE能够更有效地减小搜索空间，降低内存和计算成本。

关键设计：SLOPE算法的关键设计包括：1）距离度量：如何定义和计算节点到最优路径的距离。论文中可能使用了某种图距离或几何距离。2）模型选择：选择合适的机器学习模型来预测节点到最优路径的距离。3）损失函数：设计合适的损失函数来训练模型，例如，可以使用均方误差或交叉熵损失。4）剪枝阈值：设置合适的剪枝阈值，以平衡搜索效率和最优性。阈值过小可能导致错过最优路径，阈值过大则剪枝效果不明显。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，SLOPE算法在降低开放列表大小方面表现出色，能够显著减少需要存储和排序的节点数量。在某些场景下，SLOPE能够实现与传统A*算法相当甚至更好的节点扩展性能，同时显著降低内存占用。此外，SLOPE可以与学习的启发式函数结合使用，进一步提高搜索效率。

🎯 应用场景

SLOPE算法适用于各种需要在有限计算资源下进行高效路径规划的场景，例如机器人导航、游戏AI、自动驾驶等。通过降低内存和计算成本，SLOPE可以使这些应用在嵌入式系统或实时环境中更加可行。该方法还可以与其他启发式搜索优化技术结合使用，进一步提高搜索效率。

📄 摘要（原文）

Heuristic search is often used for motion planning and pathfinding problems, for finding the shortest path in a graph while also promising completeness and optimal efficiency. The drawback is it's space complexity, specifically storing all expanded child nodes in memory and sorting large lists of active nodes, which can be a problem in real-time scenarios with limited on-board computation. To combat this, we present the Search with Learned Optimal Pruning-based Expansion (SLOPE), which, learns the distance of a node from a possible optimal path, unlike other approaches that learn a cost-to-go value. The unfavored nodes are then pruned according to the said distance, which in turn reduces the size of the open list. This ensures that the search explores only the region close to optimal paths while lowering memory and computational costs. Unlike traditional learning methods, our approach is orthogonal to estimating cost-to-go heuristics, offering a complementary strategy for improving search efficiency. We demonstrate the effectiveness of our approach evaluating it as a standalone search method and in conjunction with learned heuristic functions, achieving comparable-or-better node expansion metrics, while lowering the number of child nodes in the open list. Our code is available at https://github.com/dbokan1/SLOPE.