paint-brush
网格环境中启发式搜索算法的性能指标经过@escholar
390 讀數
390 讀數

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

太長; 讀書

该研究深入研究了不同网格环境中的启发式搜索算法(D*、D* Lite、LPA*、LRTA*、RTAA* 和 ARA*),评估了障碍物密度、网格大小和欧几里德距离启发式影响等因素。研究仔细检查了路径成本、内存消耗和求解时间等性能指标,深入了解了路径规划算法的有效性。
featured image - 网格环境中启发式搜索算法的性能指标
EScholar: Electronic Academic Papers for Scholars HackerNoon profile picture
0-item

作者:

(1)Aya Kherrour,特伦托大学信息工程与计算机科学系;

(2) Marco Robol,特伦托大学信息工程与计算机科学系;

(3) Marco Roveri,特伦托大学信息工程与计算机科学系;

(4)Paolo Giorgini,特伦托大学信息工程与计算机科学系


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 次,以考虑随机性并确保结果的可靠性。