作者：  （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 次，以考虑随机性并确保结果的可靠性。 该论文 。 可在 arxiv 上根据 CC 4.0 许可获取

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

EScholar Technologies

EScholar

該音頻是用故事的原始語言製作的！

太長; 讀書

Make resilience your competitive advantage

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

About Author

註釋

標籤

这篇文章刊登在

Related Stories

从论坛到信息流：社交媒体算法如何塑造数字互动

加密货币增长：创建有效的用户角色

释放人工智能的力量。前沿技术的系统评价：摘要与介绍

如何将您的工作流程提高 10 倍：17 个必备应用程序

从论坛到信息流：社交媒体算法如何塑造数字互动

加密货币增长：创建有效的用户角色

释放人工智能的力量。前沿技术的系统评价：摘要与介绍

如何将您的工作流程提高 10 倍：17 个必备应用程序

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps