网格环境中启发式搜索算法的性能指标

3 实验环境及性能指标

启发式搜索算法在机器人寻路等领域发挥着重要作用，因为它们可以根据起始位置和目标位置确定最佳路径。基于网格的环境通常用于表示现实世界的环境场景，这些算法可以在其中实现，例如在自主导航和机器人技术中 [6]。在本研究中，我们全面分析了不同网格环境中众所周知的启发式搜索算法，即 D*、D* Lite、LPA*、LRTA*、RTAA* 和 ARA*。我们使用欧几里得距离启发式来指导算法的搜索，并评估一些网格特征（例如障碍物密度和网格大小）对算法性能的影响。

在我们的研究中，我们使用基于网格的环境，因为它们简单易用，而且在研究界的路径规划任务中也经常使用。网格由白色单元组成，代表可穿越状态，而黑色单元代表不可穿越的障碍物。我们模拟中的代理可以向八个方向移动，水平和垂直移动的成本等于 1，对角线移动的成本等于 √ 2。我们使用了两种类型的网格环境：随机生成的网格环境和个性化网格环境。

随机生成的基于网格的环境：网格具有三个参数的特征：

网格大小 (NxN)、障碍物密度以及起始状态和目标状态之间的距离。为了研究每个参数对搜索算法性能的影响，我们独立地改变每个参数，同时保持其他参数不变。变化包括改变网格大小、改变起始到目标的距离以及改变障碍物密度。对于变化中的每个网格，我们生成了相同网格参数的十个随机实例（例如，障碍物密度为 0.25、尺寸为 300x300、起始到目标距离为 140 的网格有十个实例，这些实例是随机生成的）。

个性化网格环境：专为模拟更具体的场景而设计。这些网格具有固定大小（71x31 个单位）和固定起始状态和目标状态的位置，并根据障碍物配置分为两部分：

•水平墙配置：在这些实验中，我们每 10 个网格长度单位添加半个网格宽度的水平墙。我们在两个方向上添加墙：在新生成的网格中一次从左到右，一次从右到左。

•水平墙长度配置：在这里，我们添加所有可以放置在

网格长度，每次我们生成新的网格时，我们会将所有墙的长度增加 2 个单位。

我们采用这两种不同的环境进行全面分析，力求在两种不同的阻碍场景下揭示搜索算法性能的细微见解。在第一种情况下，障碍物随机散布在网格内，而在第二种情况下，墙状结构表现为一团相连的障碍物。

为了评估实验中使用的不同搜索算法的性能，我们选择了以下指标：

•路径成本：该指标衡量从起点到目标状态的路径长度或执行的操作数量。它表明解决方案的质量。

•内存消耗：衡量算法寻找解决方案所需的内存量。它与检查算法的可扩展性相关，以 KB 为单位。

•解决时间：表示算法在毫秒（ms）内找到解决方案的总时间。

我们在 3.30GHz 27 Intel i9 核心上进行了实验，配备了 250Gb RAM 并运行 Ubuntu Linux 22.04。使用以下设置：所有算法都使用欧几里得距离作为启发式函数。对于 LRTA* 和 RTAA*，我们将每次迭代的扩展节点数设置为 250。ARA* 算法以 2.5 的权重运行启发式算法。我们在每个网格上运行每个算法 100 次，以考虑随机性并确保结果的可靠性。