Hierarchical and smoothed topographic path planning for large-scale virtual simulation environments

作者：Caroline Chagas , Eliakim Zacarias , Luís Alvaro de Lima Silva , Edison Pignaton de Freitas

Hierarchical pathfinding 、Path smoothing、 Terrain topography、 Agent-based simulations、 Simulation systems

文章目录

• Hierarchical and smoothed topographic path planning for large-scale virtual simulation environments
• • ABSTRACT
  • 1. Introduction
  • 2. Problem statement
  • 3. Background and related work
  • • 3.1. The exploration of the hierarchical approach for pathfinding
    • 3.2. Path smoothing
    • 3.3. Pathfinding with topographic terrain characteristics and agent movement constraints
  • 4. Overview of the proposed approach
  • 5. Using terrain relief inclinations in the computations of path costs
  • 6. The proposed HPATheta* algorithm
  • 7. Experiments and results
  • • 7.1. Pathfinding results with terrain ‘‘A’’
    • 7.2. Pathfinding results with terrain ‘‘B’’
    • 7.3. Pathfinding results with terrain ‘‘C’’
    • 7.4. Discussion
    • • 7.4.1. Cross analysis of the pathfinding results with the real-world terrain
      • 7.4.2. Analysis of the hierarchical pathfinding characteristics
      • 7.4.3. Efficiency analysis
      • 7.4.4. Accuracy analysis
  • 8. Final remarks

ABSTRACT

虚拟仿真系统应充分利用智能体的逼真行为，让用户感觉沉浸在模拟真实世界环境的虚拟场景中。基于智能体的仿真通常用于培训和教学目的，在开发计算机游戏时经常探索的人工智能解决方案需要考虑更多的要求。为了提供模拟智能体如何在真实世界地形中导航的宝贵印象，关键要求之一是在路径规划任务中需要考虑地形特征。这意味着所使用的寻路算法必须正确处理智能体导航能力的重要方面。在最先进的仿真系统中考虑大规模地形场景时，这个问题更具挑战性，因为在处理搜索空间较大的地形表征时，路径规划可能过于耗时。为了应对为插入基于仿真的学习环境中的智能体计算安全且真实的路径解决方案这一挑战，本研究讨论了一种名为 HPA Theta* 的分层寻路算法，展示了在处理大规模真实世界虚拟地形中的路径规划时，如何在合理的计算时间内计算地形起伏感知的平滑路径。通过使用不同的模拟真实世界虚拟地形，利用大规模虚拟地形表示进行了广泛的实验活动，验证了该建议。实验结果表明，与其他类似的路径规划算法相比，所提出的方法能够有效地解决目标问题，并显示出更好的效果。

1. Introduction

大规模真实虚拟地形中的寻路对于开发基于智能体的仿真系统至关重要（Abar, Theodoropoulos, Lemarinier, & O’Hare, 2017; Abar et al.） 在虚拟地形场景中，仿真智能体应具备规划和执行不同类型导航任务的能力，以实现所需的基于仿真的训练目标。当涉及到智能体在真实世界地形环境的虚拟表征中进行路径规划计算时，不同的地形特征可能会阻碍模拟智能体的导航任务，或者干脆使这种自主运动完全不可能实现（Abd Algfoor, Sunar, & Kolivand, 2015）。为了应对不同地形特征可能带来的智能体导航风险（如模拟车辆因丘陵地形特征而翻车和撞车），必须探索增强型路径规划算法，以保证智能体模拟的完整性和真实性（Brondani、de Lima Silva、Zacarias & de Freitas，2019）。

通过对文献中发现的不平整地形寻路问题的分析，这项工作的贡献在于提出了 HPA Theta* 寻路算法。该算法解决了与所代表的地形起伏倾斜特征相关的问题，在起点和目标位置之间寻找最直的可能路径和低成本路径。在此过程中，它考虑了智能体的移动限制，对分析路线中的微小偏差进行了平滑处理，避免了陡峭的地形倾斜阻碍模拟中智能体的安全移动。此外，HPA Theta* 算法还能在一定的响应时间内提供路径结果，即使是在大规模虚拟地形中计算出的长距离路径也不例外。这对于保持模拟的逼真度以及用户沉浸于模拟培训活动中至关重要。HPA Theta* 算法采用分层方法进行路径规划，可以更好地探索仿真系统中不规则和分层地形的结构。

本工作是对 Brondani 等人（2019 年）所做工作的延伸，其动机是作为 SIS-ASTROS 项目（SIS-ASTROS，2014 年）的一部分，虚拟战术仿真系统在不同方面不断发展和改进的路径规划需求。结合不同的技术，提供更逼真的寻路方法，以支持增强型仿真系统的构建，从而带来诸多益处，这项工作的贡献如下：

(1) 安全路径，尊重目标智能体的参数化运动限制。因此，所提出的 HPA Theta* 算法可以计算出平滑路径，避开陡峭的地形区域，而这种地形倾斜可能会给模拟智能体的导航带来风险；

(2) 高质量路径，因为该算法在平滑路径的同时还处理了路径的地形成本。这意味着所提出的 HPATheta* 算法在最短路径和最低成本路径之间取得了平衡，从而降低了在不平坦地形区域导航的难度；

(3) 即使在处理大规模虚拟地形时，也能优化执行时间。这是因为建议的解决方案将地形表示（即使用 QuadTree 结构）和路径规划的分层方法与前两项提到的优点结合起来。

为评估所提出的技术，在 SIS-ASTROS 模拟器使用的不同真实世界虚拟地形场景中进行了实验。需要强调的是，用于构建这些虚拟地形场景的地图都是真实世界的地图。实验使用寻路响应时间和路径成本值作为评估指标，将所提出的算法与文献中提出的其他分层寻路算法和基于平滑的寻路算法进行对比。此外，还对每种地形的实验结果进行了深入讨论，并对所有地形的实验结果进行了交叉分析。讨论还包括对 HPATheta* 算法分层特征相关性的分析。讨论最后分析了所建议技术的效率和准确性。

本文接下来的内容安排如下： 第 2 节介绍本文所要解决的问题。第 3 节回顾了寻路技术的背景概念和相关工作。第 4 节介绍了地形浮雕信息和大规模虚拟地形的表示结构。第 5 节解释了如何根据地形倾斜信息计算拟议寻路解决方案中使用的路径成本。第 6 节介绍了建议的 HPATheta* 算法。第 7 节介绍了实验并报告了获得的结果，第 8 节是本文的结论部分，为今后的工作指明了方向。

2. Problem statement

计算机仿真系统和计算机游戏在为用户提供虚拟场景方面有某些相似之处，除此之外，前者还提出了更多地形表示方面的挑战，特别是与使用真实世界地形数据有关的挑战。在最先进的仿真系统中，大规模地形必须在虚拟场景中建模，这就要求地形表示结构更加优化（Brondani et al 2019). 这种大规模的真实世界地形最终需要对模拟目的的目标地形特征进行优化表示和处理，从而使图形三维可视化算法和人工智能（AI）算法的计算不会受到负面影响。

从人工智能的角度来看，在这些大型虚拟地形中运行的寻路算法（Abd Algfoor 等人，2015 年）往往需要处理极其庞大的搜索空间，这很可能会影响在所需响应时间限制内计算不同类型的路径。==在基于计算机的培训活动中，在一定的处理时间限制（建议响应时间低于 1 秒（Nielsen，1994 年））内获得路径规划结果至关重要。==这是因为这些有时间限制的反应不会对模拟训练的流畅性和真实度产生负面影响。此外，在处理大量沉浸在模拟中的智能体时，受时间限制的路径规划任务不仅对最先进模拟系统的开发，而且对许多其他应用的改进计算解决方案的开发提出了更艰巨的人工智能挑战。

在复杂的模拟环境中（如 Hawe、Coates、Wilson 和 Crouch，2012；Heinze 等人，2002；Murphy 和 Perera，2002），依赖于大规模虚拟地形的模拟器通常必须对具有不同运动能力的多个智能体进行建模，其中一些智能体能够在陡峭的地形缓解倾斜中导航，而另一些则不能（Brondani、de Freitas 和 Silva，2017）。为了向用户提供有效的模拟学习，模拟器应能尽可能真实地模拟智能体的导航行为。如果模拟不符合这一要求，就有可能因用户沉浸于真实世界的虚拟场景而降低预期的模拟培训效益（例如，Fletcher，2009；Frutos-Pascual & Zapirain，2015）。例如，在 SIS-ASTROS 模拟器中，模拟目标之一是训练用户选择最佳地形位置来移动一组模拟车辆。如果模拟器不能让这些车辆沿着不同的地形特征进行真实的移动，用户就会从模拟中得到错误的反馈。由于在这种不真实的虚拟仿真中进行训练活动，当用户需要在实际情况中应用所获得的仿真知识时，他们很可能会做出不知情的、可能是错误的决定。无论仿真系统是否打算实现其仿真培训目标，都应避免这种情况。

特别是在模拟智能体探索路径的算法方面，模拟系统行业中使用的大多数算法都热衷于返回起点和目标地形位置之间距离较短的路径。虽然在许多电脑游戏场景中，这些结果足以达到预期的娱乐目的，但模拟问题在于，这些路径往往与模拟智能体在现实世界中选择的路线并不相似。除其他方面外，这些路径没有根据目标智能体的特定导航能力进行调整，这可能导致导航行为无法在虚拟仿真环境中捕捉到预期的真实世界中的智能体特征。在实践中，这可能会导致错误的智能体导航行为，如模拟车辆翻车（和撞车）、爬陡峭的山峰等。

有鉴于此，本文所要解决的问题==是如何在可接受的响应时间内，在大规模虚拟地形上计算出逼真的路径，以达到虚拟仿真的目的。==模拟智能体的路径规划算法需要根据地形起伏特征进行调整，即避开静态障碍物并尊重地形地貌，同时提供尽可能短的安全路径。考虑到地形起伏，生成的路径应尽可能接近现实生活中的路径选择，避免不必要的路径曲线和/或 "之 "字形导航行为，因为当路径规划算法在计算中严格避开所有其他地形起伏特征时，就会产生这样的结果。最后，生成的路径应为模拟智能体返回安全的导航路线，防止出现意料之外的智能体导航事故，而这些事故并不属于预期模拟的一部分。如何将这些特点结合起来是一个重要的研究课题，本作品将对其进行研究。根据所提出的建议，本工作范围之外的其他寻路问题也值得研究，如带有动态障碍物的寻路问题。

3. Background and related work

本研究提出的寻路方法基于不同的技术，旨在将路径成本处理、路径平滑和优化寻路响应时间等优势结合起来。因此，本节将回顾这些技术的背景概念，同时讨论相关工作。

3.1. The exploration of the hierarchical approach for pathfinding

在人工智能领域（Nilsson，1998 年），人们对 A* 寻路算法系列进行了大量研究（Abd Algfoor 等人，2015 年；Souissi 等人，2013 年）。A* 算法采用启发式方法来安排地形结构节点的处理顺序。考虑到评估地形节点（n）的优先级，该算法基于以下成本函数：f(n) = g(n) + h(n)，可描述如下：

• g(n)：它是评估当前节点（n）成本的函数；

• h(n)：这是一个估算从当前节点（n）到目标的成本的函数。该函数进行 “启发式”（h）评估，近似于精确的成本评估。

• f(n)：它是 g 和 h的总和，是给定节点（n）的总体成本评估结果。

A* 算法的效率是最优的，没有其他最优算法能保证在地形表示图中展开更少的节点（Dooms，2013；Souissi，等人，2013）。虽然 A* 算法在实现计算机游戏中角色的路径规划功能方面得到了广泛的探索（Huang，2020；Kapi、Sunar 和 Zamri，2020），但随着搜索空间的大小和虚拟场景中智能体数量的扩大，其计算成本可能会变得过高。在这种情况下，分层地形表示技术通常与寻路方法相结合，以处理大规模和复杂的虚拟地形环境，主要用于开发现实生活中的模拟应用（Brondani 等人，2019）。

分层寻路技术旨在减少使用标准 A* 寻路算法确定路径所需的计算时间。这些技术通常使用地形表示的分层抽象。这些抽象为同一虚拟地形创建了不同的表示层次，其中低层次层次通常能更准确地表示地形特征。与此相反，使用较不详细的表征会导致搜索空间更简单，其中存在较大的地形表征单元。实际上，==与使用更详细的地形表示结构相比，更简单的搜索空间能让寻路算法执行得更快。==在分层寻路研究领域，Botea、Müller 和 Schaeffer（2004 年）提出了分层寻路 A* (HPA* )。==其目的之一是降低与由规则网格表示的地形结构相关的寻路复杂性。==具体做法是将地形图抽象为预先计算好的簇。然后将这些簇分组，形成更大的簇。HPA* 找到抽象路径后，会对该路径进行细化，并将其作为搜索过程的结果返回。为了优化路径规划算法在大规模地形结构中执行时的响应时间，建议的工作采用了这种分层寻路方法。

在另一项工作中，Sturtevant（2013a）介绍了部分重构 A* (PRA* )，旨在以路径质量的小幅下降为代价加快寻路过程。在 PRA* 中，虚拟环境被细分为若干小块。相邻的瓦片形成小块，小块被组合起来，形成更抽象的地形表示层次。这一过程一直持续到用一块地砖代表整个地形环境为止。PRA* 算法在抽象地形表示层上执行搜索，直到找到抽象解决方案。在向下投影到地形表示的较低层次后，该粗略路径解决方案将在这些较低层次上进行细化，返回到虚拟地形的原始离散化。

除了将分层方法应用于地形表示网格结构外，==Pelechano 和 Fuentes（2016 年）还提出了一种探索导航网格结构的分层寻路方法。==其中，预处理阶段从多边形导航网格开始。该网格代表了三维环境的一个抽象分区。第一个导航回路被视为层次树的最低层。层次结构中的其余层级是通过递归方式将较低层次的图形划分为特定数量的节点来创建的。分区一直执行到最高层图形无法再细分为止。这样，就从表示多边形网格的输入图形中创建了小图形。虽然寻路是基于 HPA* 算法（Botea 等人，2004 年），但它已被调整为在名为 "分层导航网格图 "的表示结构中工作。在寻路过程中，起点和终点被插入搜索层次的所需层次。然后将它们连接到最高层。搜索在最高层次进行，并在此提取最佳子路径。虽然 Botea 等人（2004 年）提出的算法也采用了分层方法，但其执行结构与本研究提出的方法相似。

在 HPA*中，地形图被抽象为若干个簇，通过抽象搜索在大簇中找到 "最粗 "的路径。然后，建立一条具体路径，它是在每个簇中搜索得出的细化路径。正如 Botea 等人（2004 年）所描述的那样，这种技术降低了搜索的计算成本，生成的路径与理想路径的差距在 1%以内。虽然这种分层方法可以与不同的地形表示拓扑相结合，但它需要预先计算地形簇。

预处理方法见图 1。如图 1a 所示，一旦确定了集群，就有必要对每个网格内的路径进行预处理。确定每个簇的内部值后，就可以检测连接这些簇的边界节点（图 1b）。

一旦执行了分层算法，就会根据起点和终点发现初始地形簇和最终地形簇，因为它们都包含在各自的簇中。然后，从集群到集群，发现所有应计算的路径连接（图 1c）。发现与路径相关的集群后，在每个集群内部执行标准寻路算法，从而形成路径（图 1d）。一旦使用了这些经过预处理并存储在内存中的地形表示信息（作为地形图离线预处理任务的一部分），路径搜索时间就会比运行时执行点对点寻路算法所需的时间减少。

正如 van Elswijk、Sprinkhuizen-Kuyper 和 Wiedijk（2013 年）所提出的那样，目前这项工作中提出的建议详细介绍了一种分层算法，该算法还依赖于路径平滑技术，为模拟智能体的导航任务提供更具真实性的路线。

3.2. Path smoothing

寻路算法返回的路径将地形表示结构中的连续点（或节点）连接起来。一般情况下，这一过程会产生一段相对较短的路径。例如，A* 算法找到的路径是由连接相邻节点和相邻节点、从起点位置到终点位置的线段组成的。有时，这些连接会导致路径蜿蜒曲折，出现可以避免的小曲线。在许多模拟虚拟环境中执行的智能体运动中，与现实中的智能体形成的运动相比，遵循这种小曲线可能显得不切实际。在许多应用中，当智能体以最直接的方式向目的地移动时，就会出现逼真的移动行为。为了解决路径曲折和不真实的问题，可以在路径规划算法返回路径后执行平滑技术。

路径平滑算法可以消除生成路径上的多余点。只要没有需要避开的障碍物或不可导航的节点，这种情况就会发生，从而防止形成不需要的曲线的路径点被移除。图 2 展示了平滑的思路，只要路径上没有障碍物，就可以消除最终路径上的多余点。

Thorpe 和 Matthies（1984 年）采用了对 A* 算法返回的路径进行后处理平滑的方法。后处理平滑通常返回虚拟地形所使用的表示结构中可能的最短路径。虽然在执行这种平滑处理时路径长度可以减少，但寻路算法的总执行时间会增加。为便于比较，图 3 举例说明了最短路径、在搜索算法的每个步骤中使用网格的每个节点找到的路径，以及执行后处理平滑后找到的最短路径。

Botea 等人（2004 年）提出了一种平滑算法（算法 1）。该算法检查哪些属于路径的点或节点可以移除，用一条直线取代这些中间路径点之间的连接。该过程从解决方案的一侧开始。对于解中的每个节点，都要检查用直线到达后续路径节点的可能性。

如果是，两个节点之间的线性路径就会取代最初的次优路径节点序列。如算法 1 所示，后处理算法的输入是原始寻路算法返回的路径。一个名为??的计数变量从 0 开始，作为参数接收的初始路径节点被分配为新平滑路径的输入节点。之后，会执行一个循环，以验证是否有可能直接追踪路径到下一个路径点，从而消除不必要的节点。这可以从算法 1 的第 5 至第 7 行观察到。如果看不到下一个路径节点，即路径受阻，无法直接到达循环中的下一个节点，则更新新路径的节点计数器。这种更新会使计数器增量，并在平滑路径中添加一个新节点。这样，计数器索引中的节点就接收到了输入路径的节点，即循环中正在验证的节点，在本例中就是????。重复循环检查从输入路径起点到倒数第二个路径节点的节点。最后，平滑路径计数器递增，并将输入路径的最终节点分配给正在寻找的平滑路径的最终节点。这样，就能保证到达最终节点并返回后处理路径。与上述著作一样，本文提出的算法会从路径搜索算法返回的路径中删除可能不必要的点。在此过程中，该算法会检查路径障碍物和其他地形起伏特征，这些可能会阻碍沉浸在模拟场景中的智能体的自主导航模拟。

Theta* 算法（Nash、Daniel、Koenig 和 Felner，2007 年）使平滑成为可能。正如当前工作中所研究的那样，该算法还可以进行调整，以便在生成的路径中处理地形的倾斜度。Theta* 算法由 A* 算法发展而来，在将路径扩展到地形表示结构的下一个相邻节点时，Theta* 会检查是否有可能从当前节点的父节点追踪到算法打算扩展路径的相邻节点。Theta* 结合了在可见度图中搜索路径的 A* 思想和在网格结构中应用 A* 的思想。与 A* 算法不同的是，在更新成本 ?? 和可见的未扩展邻节点的父节点时，Theta* 会考虑两种寻路可能性。其中一种是 A* 算法的路径，它考虑的是从初始节点到当前已验证节点的路径（??），以及到其邻居节点的直线距离（??′）[= dist(s, s’)]。第二种方案考虑的是从初始节点到当前节点的父节点的路径。在此基础上，算法会检查是否有可能形成一条从父节点到可见邻居的路径[= dist(parent(s), s’)]，考虑的是直线距离。重要的是，当当前节点的父节点与可见邻居节点之间有一条视线时，第二种选择是可行的。有这样的视线意味着在观察节点（当前节点的父节点）和被观察节点（可见的邻居节点）之间没有任何阻碍从父节点到邻居节点的路径搜索的节点。图 4 展示了视线的概念。如果没有路径障碍，则使用路径 2。否则，使用路径 1。

上述 Theta* 方法之间的区别也可以从算法 2 中详细说明的伪代码中得到验证。在第 2 行中，函数返回值用于检查是否存在视线。这是选择路径的一个条件。如果返回值为 “true”，则使用路径 2（使用平滑原则）；否则使用路径 1，从当前节点到直接相邻节点。

Theta* 算法在应用平滑理念时非常高效。这是因为它已经平滑地规划了路径，不需要进一步的后处理。不过，这种算法允许在处理路径限制的基础上搜索路径，扩展了只检查节点是否可航行的思路。这种想法有利于当前的工作，其目的是处理与地形起伏的某些陡峭倾斜有关的智能体移动限制。一般来说，拥有一条平滑的路径，其智能体的移动限制得到了考虑和规划，这些特征都可以作为路径质量的指标。

总之，Botea 等人（2004 年）提出的分层算法处理了与执行时间和内存使用相关的问题。在这个方向上，van Elswijk 等人（2013 年）提出了分层路径搜索 Theta* (HPT* ) 的想法，将 HPA* 分层技术与 Theta* 路径搜索算法相结合（这两种算法都曾在本文中重新讨论过）。通过这种方式，HPT* 成功地结合了两种算法的优点，即 (1) Theta* 提供的路径质量；(2) HPA* 的计算时间和内存要求。HPT* 的路径预处理和搜索程序与 HPA* 非常相似，但有两个例外： (1) 作为预处理任务的一部分，如果集群内部节点之间有 Theta* 算法返回的路径，则将这些节点连接起来；(2) 作为运行时搜索具体路径的一部分，这项任务使用 Theta* 算法执行。因此，目前的工作是以 HPT* 算法为基础，同时采用 Theta* 算法和 HPA* 分层技术，前者在路径规划过程中平滑路径，后者则优化路径搜索算法的性能。

3.3. Pathfinding with topographic terrain characteristics and agent movement constraints

文献（Chen, Shi, & Liu, 2009; Ganganath, Cheng, & Chi, 2014, 2015; Marasinghe Arachchige, 2016; Pütz, Wiemann, Sprickerhof, & Hertzberg, 2016）描述了在虚拟地形表示结构中表示地形特征的不同方法。其中，可以对地形表示节点的面（即法向量）进行定向，例如表示每个地形区域的最大和最小地形高度。此外，如 Ganganath 等人（2014、2015 年）、Marasinghe Arachchige（2016 年）和 Pütz 等人（2016 年）所述，依赖加权图的表示方法可以从地形高程模型中实现。路径规划算法还能考虑不同性质的地形地貌特征导致的智能体移动限制。正如 Kapadia、Ninomiya、Shoulson、Garcia 和 Badler（2013 年）、Sturtevant（2013 年 b）以及 Ninomiya、Kapadia、Shoulson、Garcia 和 Badler（2015 年）中介绍的那样，将成本应用于地形特征和路径规划计算，可以搜索到与智能体在现实中探索的路径更为相似的路径。归根结底，路径规划可以看作是一个约束处理问题，其中所代表的地形表面信息就是在路径搜索过程中正确计算的路径成本。不过，将地形高度和倾斜度数据表示（或转换）为成本信息的形式可以多种多样。有必要考虑寻路算法必须提供路径解决方案的应用问题：防止智能体出现非预期行为、实现较低的智能体能耗，以及处理燃料或维护成本等智能体后勤问题。

陈等人（2009 年）提出的导航网格是一种出色的表示结构。这种地形表示结构中使用的每个多边形都有一个法向量。所有法向量的集合构成一个梯度图，其变化表示在两个多边形之间移动的难度。因此，在执行寻路算法时会对梯度变化进行评估。生成成本的方法考虑到三个方面：路径长度（始终寻找最短路径）、根据法线矢量指示的地形倾斜度移动的难度以及与每种智能体相关的偏好/限制。因此，导航成本是根据穿越每个地形节点的难度的线性组合计算得出的。根据两个多边形之间的地形倾斜度，寻路算法返回的路线变化平滑，表明智能体移动的难度较低。虽然这种寻路方法中使用的路径成本计算与本文提出的解决方案不同，但这些工作也说明了如何在路径规划中表示和计算地形信息。在此过程中，会对穿越每个地形节点的成本进行局部分析，这与当前工作中的做法类似。虽然他们提出了防止为不同种类的模拟智能体确定风险路径的相关方法，但目前这项工作还研究了在大规模虚拟地形中使用分层和平滑路径规划技术进行寻路的问题。

在 Ganganath 等人（2014、2015 年）和 Marasinghe Arachchige（2016 年）的研究中，使用了加权图来支持地面智能体（机器人）的路径规划。该图由高分辨率数字高程模型（DEM）创建，可精确表示与地形表面相关的高程信息。在这里，每个图形节点都对应地形表面上的一个点。地形的倾斜角度会影响智能体（或机器人）的能量消耗，从而影响路径的选择。在这种情况下，除了智能体与地形之间的摩擦力信息外，还在建立地形表示的节点中加入了权重。考虑到智能体的特性（及其约束条件），计算出智能体在地形区域内航行所需的能量成本，并将该成本应用于路径搜索算法的启发式。这一过程会在最短路径和执行移动所需的能量消耗之间达成平衡。因此，智能体可以使用更多现实生活中可导航的路径。尽管对后勤问题的处理，例如对某些路线的能源成本的考虑（这是 SIS-ASTROS 项目未来工作的一个相关问题），例如，目前的这项工作不仅计算了地形缓解感知路线（避免了对预期模拟来说很奇怪的智能体事故），而且还计算了拉直的和尽可能真实的路线。考虑到技术方面的问题，这项工作依赖于启发式计算，这种计算根据智能体的一些运动属性进行调整，与机器人导航相关，但对于本文所要模拟的情况来说过于详细。这项工作没有考虑启发式计算，而是侧重于根据当前地形表示节点的地形起伏特征确定本地导航成本。在路径搜索过程中会对该节点进行分析，而这项工作仍然使用标准的启发式寻路计算。

Pütz 等人（2016 年）讨论了用于粗糙地形区域路径规划的三维导航网格。生成虚拟地形结构的主要输入是由表面重建程序构建的三角形网格。这一过程生成的导航网格可应用图优化算法。通过这种结构，可以对地形表面的若干特征进行编码。这些特征用所有图形边的地形导航成本层来表示，每个边的成本函数合并为一个成本函数。在这些层中，有一层是指与局部地形起伏不平有关的成本。由于导航网格结构允许将法线矢量关联到网格的每个三角形和顶点，因此该成本也可以基于法线矢量的计算。因此，所代表的信息表明了当地地形的倾斜度。在路径搜索计算中，可以通过检查某条路线的可通行程度来获得该信息。总之，这项工作探索了法向量，以捕捉导航网格结构中每个三角形的地形倾斜度。同样，本作品还探讨了在地形表示节点的每个方向（北、南、东、西）使用此类法向量表示地形起伏倾斜特征的问题。路径成本计算过程中的一个不同点是，他们的工作使用了不同的地形特征（在地形表示图的不同层中表示），这些特征在确定路径成本值时被结合在一起，而目前的工作关注的是仅考虑地形起伏倾斜度的寻路计算。不过，与这项工作类似，该工作中描述的路径搜索过程也是在本地计算地形起伏的路径成本。

Abd Algfoor、Sunar 和 Abdullah（2017 年）通过三种不同的技术提出了在寻路计算中使用权重信息的想法。第一种是基于与一组权重??相关联的启发式搜索算法的迭代。第二种是基于起点节点和终点节点之间的长度，然后将其与?? 相关联。后者基于与一组权重??相关的轨迹成本。一般来说，探索这些特征的目的是确定如何改进由此产生的寻路算法，使之与其他更传统的方法相比较。由于这项工作探索了在搜索过程中计算这些权重的不同方法，因此是本研究中需要考虑的相关方法。尽管地形信息可以作为路径搜索过程中需要考虑的一组权重值来获取，但他们的工作展示了如何将这些权重作为启发式路径搜索计算的一部分。这与目前的建议不同，因为它仍在探索寻路算法中的标准启发式函数。他们的工作与本文提出的工作之间的另一个对比是所开发实验中使用的算法。与他们不同的是，这项研究对比了使用和不使用路径成本值（可作为权重）的不同算法，并展示了如何从所代表的地形特征中得出这些值。

在 Perkins、Marais、Gain 和 Berman（2013 年）的研究中，提出了一种计算机器人最近路径的算法。一旦为这类智能体设计出这样的路径，它们就会在具有不同特征的地形中导航，该算法在路径搜索中还会考虑加权地形区域。该算法一般用于网格或 QuadTree 数据结构，需要高分辨率才能准确模拟不规则结构的边界。在这项工作中，所使用的成本函数已扩展到在二维三角形模型和三维四面体网格所代表的结构上运行，它们能更精确地模拟世界的多边形结构。与目前的建议类似，这项工作关注的是地形的详细分层表示，尽管在捕捉大规模地形时对网格结构的探索可能不利于计算有时间限制的寻路答案。与本文提出的工作一样，他们工作中使用的启发式方法优先确定最短路径，并在本地进行必要调整，以考虑相关地形区域的路径成本。虽然没有采用路径平滑技术，但他们的工作也研究了不规则地形表示结构中的路径计算。

在 Sturtevant、Sigurdson、Taylor 和 Gibson（2019、2020 年）中，动态成本被应用于代表地形的图形。成本是根据智能体要穿越的土地类型（草地、道路、水域等）的特征分配的。因此，我们提出了一种分层寻路方法，即根据成本信息定义的地形类型，在较大的地形区域内搜索路径。然后，在确定最终路径时进行路径细化。地形的成本由路径搜索算法计算，路径成本被用作算法质量的衡量标准。与当前的工作类似，他们的工作使用了与不同类型地形特征相关的路径成本计算，这种详细分析超出了当前建议的范围。他们的工作与本文介绍的工作的另一个共同点是使用了分层方法，这在处理大规模地形时具有相关性。不过，在他们的动态地形环境中没有研究平滑技术，而这项工作仅在处理静态地形表征时采用了这种寻路技术。

Uggelberg 和 Lundblom（2017）所做的工作研究了应用于 A* 算法的不同权重信息如何影响寻路执行时间。它还研究了这些权重对路径准确性的影响程度。将权重应用于代表虚拟地形环境的图节点，虽然得到的路径看起来更真实，但路径计算变得更加复杂。这种权重被应用于代表虚拟地形环境不同区域的结构；大权重被应用于智能体应避免的地形区域，而小权重则被应用于首选导航区域。此外，还存在不可导航的地形区域。通过这种方式，算法可以进行路径搜索，从而使最终路径的成本最小化。在这项工作中，所使用的启发式函数也是加权的，即根据待导航区域的面积对欧氏距离进行加权。与这项工作类似，这里提出的方法也呈现了不同的地形区域及其相应的地形特征。虽然这种类似吸引力和排斥力的方法似乎可以避免智能体路线的风险，但由此产生的路径可能会呈现不必要的曲线，与现实生活中的路径选择并不相似。这就是为什么不仅要根据地形起伏特征来指导路径确定，还要平滑所产生的路径，以便为目标智能体提供尽可能笔直的路线。

在 Basiri (2020)一书中，作者提出了一种寻路算法，用于处理开放地形区域，如空地和公园，传统的路线规划应用软件无法适当支持这些区域（例如，它们最常处理的是地图上的道路）。提议的算法根据轮椅移动应用进行了调整，这取决于不同的因素。这些因素考虑了轮椅使用者在规划路线时所受到的限制。这样，作为地形表示结构的增强可见度图的可见度点之间的链接就有了权重。该可见度图考虑到了障碍物、障碍等方面。链接的权重基于距离信息和地表条件、坡度等。这些因素是从轨迹挖掘算法和机器学习技术获得的运动模式中学习的。分配给每个可见度图链接的权重是所学因素的平均值。因此，在进行搜索时，应考虑地形结构的权重，寻找成本较低的路径。在根据目标智能体调整路径规划解决方案的同时，这项工作还考虑到了所提出的方法，其重点是处理智能体的导航要求，即在标准寻路解决方案通常无法接近的地形区域搜索路径。与本文介绍的方法不同，该方法利用机器学习来学习智能体的约束条件，并在确定智能体路线时对其进行计算。迄今为止，由于对机器学习方法的探索，这种改进寻路计算的方法尚未在本文介绍的研究项目中得到研究。

Li 和 Chou（2018）采用了基于约束的目标函数。在计算目标函数时，会权衡路径长度约束、平滑和碰撞风险，旨在最小化运动成本并平衡不同的约束条件。利用粒子群优化算法，计算出的函数可用于机器人在复杂环境中的运动规划。虽然通过基于约束条件的优化算法实现目标函数的最大化/最小化是解决现实路径确定问题的合理方法，但优化技术可能会带来寻路响应时间的延迟，不利于现实模拟的开发。虽然目前的工作只侧重于由于所表现的地形起伏而产生的导航约束，但它解决了路径规划的分层技术，以同时应对大规模虚拟地形和有限的响应时间要求。

要在虚拟地形图中表示倾角信息，就必须表示每个地形区域的地形特征，这些特征保存在相应的表示节点中。虽然采用了不同的技术来表示和使用有关地形不平整度的信息，但这些信息是由路径规划功能计算出来的，然后转换成导航成本。路径搜索算法会使用这些成本，还可以处理分配给智能体的其他运动限制。在当前的工作中，我们决定使用法向量来表示虚拟地形结构中的地形倾斜度信息。这一决定是基于这样一个事实，即 SIS-ASTROS 项目应用问题中涉及的智能体在通过包含陡峭倾斜度的地形区域时有移动限制（这些倾斜度是根据地形地面的法向量计算得出的）。

4. Overview of the proposed approach

用于构建仿真系统的大规模地形的地形信息表示和计算是本研究提出的寻路方法的相关特点。正如 Brondani 等人（2019）所讨论的，QuadTree 数据结构的层次性是优化地形表示和路径搜索的基础。这是因为现实世界中不同层次的地形细节都可以在生成的虚拟地图的层次结构中表达出来。因此，QuadTree 表示结构的叶节点表达了虚拟地形的不规则网格和分层表示（其中地形特征多的地形区域要比地形特征少的其他区域精细得多）。这样，层次结构中的最高级别就代表了虚拟地形的总面积。在层次结构中，节点越深，表示的地形区域的详细程度越高。

在激励这项工作的模拟系统中，在构建地形导航地图时对 QuadTree 表示结构的细分考虑了不同的地形特征，如植被密度、地形景观的形状和地形区域的陡峭程度，以及河流或其他水体的存在。如果在所使用的真实世界地图上发现了这些地形特征（在 SIS-ASTROS 项目中，虚拟地形是根据基于地理信息系统的真实地形区域地图数据构建的），则会相应地在 QuadTree 层次结构中构建一个新的层次。这个过程一直重复进行，直到满足 QuadTree 层次结构的最终细分条件为止，该细分条件是根据所代表的现实世界地形特征和达到 QuadTree 层次结构的最高级别确定的。

在Brondani等人（2019）提出的QuadTree结构寻路执行中，分层搜索过程可以减少地形导航地图中访问节点的数量，从而降低整体搜索成本。此外，访问节点的数量与搜索的处理时间直接相关。这样，即使在处理大规模真实世界虚拟地形时，也能接近路径规划计算所需的处理时间限制。这种特性与当前的工作息息相关，因为所提出的寻路技术完全基于这种地形表示方法。

正如 Brondani 等人（2019）所描述的，QuadTree 结构是一种 “有根的树”，其中每个节点（n）正好有四个子节点或没有子节点。作为导航 QuadTree，它由一个分层结构组成，用于表示虚拟地形。由该结构生成的不规则网格由分层表示法的叶节点表示。在生成的不规则网格表示法中，每个节点都有以下信息：

• 代表虚拟地形信息的属性：n<最小高度、最大高度、邻居、有河、有湖、有崖、可步行、正常北、正常南、正常东、正常西>。

• minHeight 和 maxHeight 属性提供了节点所代表的真实地形区域中的最小和最大地形高度信息；

• 可步行属性表示插入模拟中的智能体是否可以访问该节点。根据该节点所代表的地形特征，它是否允许地面智能体移动；

• 属性 normalNorth、normalSouth、normalEast 和 normalWest 是节点的四个法向量，分别指向每个节点的方向。它们提供了地形与向上矢量（平面的法向量，指向上方，在空间中的坐标为（0, 1, 0））相比的倾斜角度信息。

为了在寻路过程中探索分层表示法，我们使用 QuadTree 的较高层次来形成地形簇，第 3.1 节中解释了这一想法。这种层级的定义可能无法一概而论；这意味着应根据目标应用领域确定形成簇群的层级，以便优化抽象图中的搜索时间，并优化最终路径的搜索。为了在我们的项目中进行这样的分析，我们在模拟系统中进行了一系列测试，旨在了解什么是解决我们的应用问题最合适的聚类级别。这样，在执行寻路算法时，就有可能比只在叶子 QuadTree 节点上执行算法获得更高的性能。最后，如果叶节点比在层次结构中定义地形簇所选择的层次高一级，它就会成为一个簇，形成一个不规则的网格，也用于抽象路径计算（簇的层次）。

从已形成的地形簇出发，一旦底层模拟系统启动，就可以开始发现簇边界节点并对每个簇进行处理。集群处理的部分工作包括隔离边界节点（图 5.a）和搜索所有集群边界之间的路径距离（图 5.a）。为了找出这些距离，需要在每对边界节点中执行搜索算法，并将集群的输入和输出作为输入。在本文提出的方法中，除了处理集群边界节点对之间的距离外，还要计算每条路径的成本。在这种情况下，这些成本考虑了地形的倾斜度。之后，路径搜索算法将使用这些地形成本信息。例如，对于每个地形群节点，边界节点会被存储在一个列表中，以减少搜索时间。这一过程相当于在准备虚拟仿真场景时对地形表示结构进行预处理。

在执行搜索算法时，它首先通过集群边界连接规划集群之间的路径（图 6.a），搜索 “抽象路径”。然后，使用寻路算法在每个簇内部搜索路径，得到 “具体路径”。在每个集群中，在两个选定的边界节点之间搜索路径，同时考虑集群的路径入口和出口。每个集群返回的路径的联合构成结果路径。该路径由寻路算法的抽象和具体搜索步骤获得（图 6.b）。

在虚拟地形图的结构中插入了每个地形表示节点所代表的最大和最小地形高度值及其法向量（用于捕捉这些地形节点的起伏倾角）。之后，路径规划算法将使用这些节点属性来获取每个地形节点的起伏倾角。由于所开发的算法处理的是智能体在不平整地形图中的移动困难问题，因此决定使用倾斜度特征来表示地形的起伏特征，这一决定是基于第 3.3 节中的作品分析做出的。这种地形倾斜度被认为是智能体移动的障碍，因此，在模拟系统执行过程中，它们与为智能体计算更安全的路径有关。

在这项工作中，除了捕捉目标地形特征的属性外，与路径计算最相关的地形特征还包括节点是否受阻（可行走）。在这种情况下，与 Chen 等人（2009 年）提出的方法类似，浮雕倾斜信息由表示结构中每个节点的地形法向量表示。为了提高表示这种倾斜的准确性，使用了与组成地形表示节点的四个定向面（北、南、东、西）有关的法向量（normalNorth、normalSouth、normalEast 和 normalWest）。根据智能体的运动方向，这些有向法线向量有助于计算路径成本，路径规划算法会对路径成本进行分析。

法向量由组成每个三角形地形区域的向量的向量积构建而成。这些区域位于四叉树的叶节点内部（图 7）。这些法向量指的是各自节点的方向。这一过程使用节点四角的两个点（相对于正在建立的法线矢量方向（北、南、东、西））以及其中心点。根据这些点，可以得到构成三角形地形区域的矢量，从而计算出矢量乘积。因此，与这些三角形地形区域向量的正交向量就产生了。然后，这个法向量垂直于三角形地形区域的面。这样，就定义了法线北（NN）、法线南（NS）、法线东（NE）和法线西（NW）。有了它们，就可以在计算路径成本时只计算智能体将经过的浮雕倾斜值。根据智能体到达节点的方向，可以确定进入节点的成本；根据离开节点的成本，可以确定离开节点中心到与邻近节点交界处的成本。

法向量的计算方法如下：

有了关于四个节点方向的法向量表示法，就可以获得路径入口和出口的地形倾斜度。这使得地形信息的表示更加详细。同时，由于可以在计算路径时计算特定地形区域的成本，因此算法性能更加精确。

5. Using terrain relief inclinations in the computations of path costs

目前这项工作中提出的成本计算方法可以处理路径搜索过程中的地形倾斜问题，并保证智能体的行车路径安全。为此，有必要在寻路计算中加入地形高程的成本值。正如第 3.3 节所述，可以探索不同的方法将可用的地形数据转换为成本值，而方法的选择往往基于要解决的应用问题。在这项工作中，采用了一种处理地形起伏倾斜度的方法，因为模拟智能体的移动会受到一定倾斜角度的影响。

地形起伏信息通过四叉树每个三角形节点的法向量获得。在此基础上，根据所代表的地形起伏倾斜角的余弦值计算出一个权重值。该权重值会影响选择或不选择给定路径的决定。权重值越高的地形区域，相关成本越低。实际上，地形倾斜角度（??）越小，其余弦值就越大，权重值也就越大。因此，通过计算反余弦值，可以获得较低的成本。

由于 QuadTree 的每个叶节点都是由四个三角形区域（指节点方向）组成的，因此每个叶节点都有四个法向量。为了确定通过一个节点的成本，需要选择当前节点出口方向和相邻节点路径入口方向的地形起伏倾角。这些都是智能体在移动过程中要经过的节点部分。例如，如果智能体向东移动，它就会利用相应的法向量从东侧离开当前节点。这样，它就会根据自己的移动方向，使用节点一侧的法向量，从西侧边界进入邻近节点（见图 8）。尽管根据智能体经过的节点方向使用了地形倾斜信息，但仍有必要检查节点的其他法向量。这一点很重要，可以保证节点中是否存在急剧的地形倾斜，这种情况不允许智能体通过该地形区域。如果该节点所代表的地形倾斜度超过了智能体安全移动所允许的极限，则算法计算时将不考虑该节点。这样就可以跳过剩余的地形倾斜度验证过程，以及作为路径成本计算一部分的地形特征计算。

获得节点入口和出口的地形倾角后，检查这些倾角是否在 5 o 和 ?? 之间。在这项工作中，根据联合国提供的资料（Blyth，2002 年），5? 以上的地形倾角被视为山脉。?? 代表允许智能体移动的最大地形倾角值，这种寻路/智能体移动约束可以在所提出的寻路方法中进行参数化。如果地形倾斜度在规定范围内，则根据上述计算方法确定路径成本。如果低于该范围，则成本为单位成本，因为建议的算法只处理被认为与智能体安全导航相关的浮雕倾角。这意味着，数值 1 只反映了路径距离的成本，而没有分配给地形起伏的成本值。因此，路径成本计算可概括为

图 9.a 和 9.b 可以直观地分析搜索过程的有效性。首先，将路径成本应用于标准 A* 算法，该算法不考虑地形起伏的高程。这意味着只考虑起点和终点之间的最短距离，而忽略了对智能体的交通可能有危险的地形区域。唯一考虑到地形高度的寻路处理方法是阻止地形倾斜值超过一定限制的节点，这是一种用于处理导航障碍的更简单的寻路处理方法。第二步，改进路径搜索算法，以考虑地形的不平整性，解决可能对智能体移动造成负面干扰的问题，返回成本较低的路径，绕过可能被视为移动轨迹障碍的特定地形区域。从图 9.a 和图 9.b 中可以看出，与标准 A* 算法的路线所包含的区域相比，寻路算法所搜索的路线穿过的地形区域具有轻微的地形起伏倾斜。在这里，底层法向量图显示了地形的倾斜度：区域颜色越深，地形的倾斜度越大。在本例中，35? 的倾斜值被定义为目标智能体流量的极限值。

由于将成本值应用于 A * 算法反映了路径搜索结果与急剧地形倾斜的偏差，这也是这项工作的目标之一，因此开发了一种旨在平滑所获路径的方法。平滑的想法基于 Theta* 算法，该算法在计算路径的同时，使其与模拟智能体在现实世界中可能选择的路线更加相似。

6. The proposed HPATheta* algorithm

这项工作探讨了 Theta* 算法的路径成本计算。在此过程中，它允许根据选定的地形特征对计算出的路径进行平滑处理。除其他优点外，平滑还能改善路径规划算法得出的路径，通过避免蜿蜒曲折的路线使其更符合实际情况。因此，如果能返回智能体需要走过的最短距离，路径质量就会得到改善。如果路径偏离了非常陡峭的浮雕斜面，这些路径对智能体来说就会变得更加安全，这也是这些智能体沉浸在模拟环境中所需要的。因此，结合这两个优势的建议产生了一种高效的算法。

问题在于，当在路径规划计算中使用地形信息时，文献（Thorpe & Matthies, 1984）中描述的标准平滑技术会忽略地形起伏的哪些部分可能有利于智能体导航行为的模拟。为了缩短距离和降低路径成本，有必要在 Theta* 中处理地形起伏，这也是当前工作的探索方向。在这种情况下，仅仅检查当前位置与其相邻位置的地形倾斜度是不够的。在使用视线平滑技术时，有必要解决地形起伏倾角问题。这样才能确定地形起伏倾角是否不会阻碍视线。因此，在 HPA Theta* 算法中探索的拟议路径平滑技术具有以下特点：

(1) 当地形起伏倾斜度等于或大于??（允许智能体安全移动的最大倾斜度）时，阻碍视线；

(2) 将这些节点之间视线范围内遇到的进入和退出地形节点成本相加。这相当于在路径搜索计算中分配了一个视线成本；

(3) 像执行标准 A* 算法一样，沿着一个节点到其邻居的路径，检查从当前节点到下一个节点的移动成本。当视线受阻，无法进行平滑时，就会这样做。

建议对 HPATheta* 算法使用的视线技术进行调整的目的是：

(1) 只要没有给智能体移动带来风险从而导致无法导航的阻塞节点或地形起伏倾斜，就能避免路径障碍；

(2) 计算沿视线的浮雕倾斜度总和，以确定其产生的路径是否会给智能体造成导航困难。

总之，视线方案的特点是 “近视视线”（算法 3）。与 Theta* 算法使用的标准视线方法不同，这种近视方法表明，只要地形起伏倾斜的总成本低于其他路径可能性，就有可能出现自由平滑视线。这意味着，与小曲线路径的成本相比，平滑会降低路径的成本。

HPA Theta* 算法通过处理地形起伏倾斜度和路径平滑技术，在起点和终点位置之间找到了成本较低的路线（见本文提供的实验结果）。实际上，较低的成本意味着可以避开陡峭的地形坡度。该算法完成从初始节点 Ns 到目标节点 Ng 的路径所需的成本定义如下：

其中，成本函数 g(Ns, N) 是???? 到查询节点 ?? 的穿越成本。路径成本是通过累积组成路径的每个连续节点的穿越成本计算得出的。因此，它反映了从初始节点???? 到当前节点（即查询节点?? 的路径父节点）的路径成本，加上穿过当前节点 ????????????(??) 到查询节点?? 的成本，如图所示：

c(parent (N), N) 表示从当前父节点 (??)到查询节点 ?? 的旅行成本（考虑路径的缓解倾斜成本）。其定义如下

其中，d(父节点 (N)，N) 是父节点 (N) 到 N 的欧氏距离，再乘以第 5 节所述的 mScost 路径倾斜成本。综上所述，从 Ni 到 Nk 的路径成本是节点对之间的交叉成本之和，其值为

其中，?? NiNk 描述了从 Ni 到 Nk 的路径，代表节点序列，即每 i ≤ j ≤ k 有一条路径（Nj，Nj + 1）。

最后，h(N, Ng) 是启发式函数，反映了从当前节点 ?? 到目标节点 ?? 的估计路径成本。在 HPATheta* 算法中，该启发式函数是通过这些节点之间的欧氏距离计算得出的，尽管所提议的算法在进行路径规划的同时还处理了地形起伏倾斜问题。

根据提议的算法，搜索过程从在开放节点列表中插入初始节点开始（算法 4，第 3 行）。因此，??(????) = 0。

在探索当前节点的邻居节点时，如果该邻居节点既不是目标节点，也不是代价无限大的节点，则会将不在开放节点列表中的邻居节点纳入其中。然后将当前节点从列表中删除。如果被探索的邻居是目标节点，则会使用???? ??????????????????函数返回找到的路径，该函数会沿着 StartNode 和 TargetNode 之间的路径对节点进行排序。像往常一样，HPATheta* 算法会计算路径成本，并考虑列表中每个已探索的邻居。此时，算法会尝试应用平滑技术：使用 “近视视线”（算法 5，第 2 行）检查是否可以在当前节点的父节点和已访问的邻居之间找到一条直接路径。使用ε????????????????????????????????????ε函数检查两个节点之间视线相交的扩展节点。如果视线畅通，则考虑平滑路径计算路径（算法 5，第 3 行）；如果视线受阻，则不平滑计算路径，使用当前节点的直邻节点组成路径（算法 5，第 5 行）。然后，算法会更新函数??????????????????????????????????????????（计算穿越成本的函数、 算法 6，第 4 行）和（算法 7，第 5 行）。要更新该成本，需要使用 ??????????函数对所获得的穿越成本值的一致性进行检查。该函数将确保 ???????? ? ???????????????? 的值包含在距离和无穷大之间的区间内。如果得到的值小于????????????和????????????????节点之间的距离，则返回它们之间的距离。探索完当前节点后，将其插入封闭节点列表。在下一次迭代中，将探索开放节点集中成本值最低的节点 ?? (??)（算法 4，第 4 行）。

一般来说，HPATheta* 算法分析的路径方向可以根据检查每条视线时获得的成本而改变。这种处理方法指的是所谓的 “路径 2”（算法 6），其选择标准见第 3.2 节中描述 Theta* 搜索过程的伪代码中的算法 2。通过加权视线，如果 "近视 "视线没有受到阻碍，算法将返回一个路径成本，供路径决策时考虑（算法 5，第 2 行）、 其中的变量 ?????????????? ???????????? 返回 "??????????????????????’'函数计算的成本）。

但是，如果加权视线受阻或超重，要保持路线方向不变，则由 Theta* 执行所谓的 “路径 1”（算法 7），该算法也会在决策中使用地形倾斜成本。因此，在搜索过程中，地形地貌的处理是通过检查当前节点每个近邻节点的成本来完成的。

在算法中，路径成本是根据智能体的移动方向计算的。这意味着，该成本是根据出口节点方向的法向量（normalFrom）和邻近节点的入口法向量（normalTo）计算的，这两个法向量是智能体移动方向的一部分。?????????????????????????? ??????????????是计算穿越成本的函数，如第 5 节所述。对于视线来说，进入和离开地形表示节点的思路是相同的。经 ε????????????????????????????????????ε 函数验证的视线穿过的所有节点都会计算其输入和输出成本，如图 10 所示。在图中，三角形输出区域用浅灰色虚线边界表示。三角形输入区域用深灰色表示。进入和离开每个节点的成本都会被计算出来，并与视线中包含的其他节点相加，形成近视视线的成本。如图所示，视线穿过的所有节点都会计算其成本。然后将它们加入视线的最终成本中。这条视线以一个节点的中心为起点，以另一个节点的中心为终点，尽可能平滑。

正如 HPA Theta* 方法所探讨的那样，Theta* 能提供更高质量的路径。但是，它需要更长的执行时间和更多的内存。在处理地形起伏倾斜时，这种类似于 Theta* 的计算时间会变得更长。为了解决这个问题，本研究提出了分层寻路方法，从而降低了搜索的复杂性，缩短了执行时间，如 Botea 等人（2004 年）的研究。此外，Theta结果与 HPA * 结果相结合，成功地结合了HPA Theta算法，因为两种算法的优点（van Elswijk等人，2013）都得到了保证。

总之，HPATheta* 算法依靠 Theta* 平滑技术来解决智能体因地形起伏不平而产生的移动困难。它还将 Theta* 算法集成到了分层寻路方法中。在实践中，QuadTree 所描述的地形表示结构被抽象为簇。然后，这些集群由更高 QuadTree 层级的节点来表示。预处理在每个簇中寻找内部的 QuadTree 路径，并使用旨在处理地形倾斜的 Theta* 算法找到路径。按照第 3.1 节中描述的 HPA* 提出的想法，在地形表示结构中与其他可行走节点有边界的所有可行走节点之间都会进行这种预处理。此外，集群之间相邻的边界节点也会相互连接，从而提供集群之间的连接。运行时，在经过起点和终点时，会确定感兴趣的簇。然后，执行经适当扩展以处理地形起伏倾斜的 Theta* 算法，搜索具体路径。总之，HPATheta* 算法除了通过一种新的视线计算形式考虑地形的不平整外，还利用了 Theta* 和 HPA* 的优点。

这项工作使用 QuadTree 来支持分层地形表示和寻路。De Berg、Van Kreveld、Overmars 和 Schwarzkopf（1997 年）指出，作为预处理模拟活动的一部分，对于细分为 n 个节点的地形，构建 QuadTree 的复杂度为 O((??+1)??)，其中 d 是树的深度。此外，在这种层次结构中插入、移除和搜索节点的复杂度为 O(??????(??))。HPATheta* 首先会在更高层次的地形表示中搜索抽象路径。这是在 QuadTree 层次结构的某一中间层中进行的，地图簇就在这一层中表示。为了计算抽象路径，使用了类似 A* 的算法。实际上，A* 搜索需要构建一棵搜索树，其复杂度为 O(???? )，其中 d 是成本最低的解的深度，b 是搜索树的分支因子。考虑到抽象路径所经过的地形群，HPATheta* 算法对具体路径进行细化搜索。再次使用类似 A* 的算法在每个簇中找到一条具体路径。在此过程中，只使用属于目标簇的四叉树分支的叶节点。考虑到每个簇只包含代表一小部分地形的节点数，每个簇搜索的复杂度也是 O(???? )（搜索树缩小到簇的极限所代表的地形节点）。HPATheta* 算法基于 Theta* 算法（Nash 等人，2007 年）。它的时间复杂度是根据扩展节点的数量与搜索树的深度成指数关系来计算的，因此为 O(???? )。然而，在 HPATheta* 的复杂度中还必须考虑另一个因素，即与用于验证视线的节点数量相关的线性成本，从而导致路径平滑（Daniel、Nash、Koenig 和 Felner，2010 年；Nash 等人，2007 年）。因此，HPATheta* 的渐近复杂度为 O（???? + d）。

7. Experiments and results

本实验旨在评估 HPATheta* 算法在根据目标智能体的移动限制在虚拟地图中搜索路径时处理地形特征的有效性。我们的假设是，在路径规划过程中对地形起伏倾斜进行处理可能会产生低成本路径。最重要的是，拟议的 HPATheta* 应该能找到不会对模拟智能体的导航行为造成风险的路线，允许它们偏离具有陡峭地形特征的地形区域。

实验使用了大型虚拟地形图。作为 SIS-ASTROS 项目（SIS-ASTROS，2014 年）的一部分，这些地图代表了三个真实世界的地形，Engel、Frasson 和 Pozzer（2016 年）、do Nascimento、Franzin 和 Pozzer（2018 年）、Frasson、Engel 和 Pozzer（2018 年）对这一计算机制图过程进行了描述。 虚拟地形’‘B’‘的主要地形特征是高山，可以更好地测试 HPATheta* 算法的地形起伏倾角计算。相比之下，虚拟地形’‘A’‘的地形起伏倾角较小。地形’‘C’'虽然没有明显的地形起伏倾斜，但该区域有许多水体，导致表示结构中出现大量阻塞节点。每个地形的特征摘要见表 1。

针对每种地形，测试了六种不同的寻路算法，以便将拟议的 HPATheta* 算法与其他算法的结果进行比较。为便于比较，选定的算法包括：(i) 标准 Theta* （Nash 等人，2007 年）；(ii) 能够计算地形起伏倾斜度的改进 Theta* ；(iii) 基于标准 Theta* 的分层算法，称为 HPT* （van Elswijk 等人，2013 年）；(iv) Botea 等人（2004 年）提出的 HPA* ；以及 (v) 经过调整的 HPA*，以便在路径计算中处理地形起伏倾斜度。

值得一提的是，本研究对分层和非分层路径规划算法进行了比较。采用分层算法可以分析这种分层方法的影响，主要是在执行时间方面。此外，这些算法既可以使用与地形起伏倾斜度相关的路径计算，也可以不使用，从而可以根据这些地形特征比较寻路过程的成本。为了扩大围绕 HPATheta* 算法的分析和讨论，HPA* 算法（其在线版本称为 OHPA*）也被纳入实验中。这样，我们就可以比较是否使用路径平滑技术的算法。

对于每种算法，测试中都使用了以下指标：(i) 结果路径的长度（以米为单位的路径距离）；(ii) 路径搜索的执行时间（以毫秒为单位）；(iii) 结果路径的成本。成本是本研究中最相关的指标之一，因为它可以分析路径规划算法是否避免了可能损害目标智能体移动安全的救济倾斜。为了计算在路径规划中处理此类地形特征的成本，如第 5 节所述，我们定义了一系列相关的地形倾斜度。实际上，在路径规划计算中使用的地形起伏倾角在 5 o 度到 35 o 度之间。低于此范围的倾角值在路径计算中不予考虑。高于 35? 度的地形起伏倾角只被视为模拟智能体移动的障碍。

在我们的研究项目中，响应时间也是评估已测试路径规划算法的一个重要指标。根据 Nielsen（1994 年）的研究，人机交互研究中的响应时间有三个需要考虑的重要限制，主要是在仿真系统中，用户在其中扮演着与运行中的仿真互动的积极角色。这些时间分别为 0.1 秒、1.0 秒和 10 秒。在 0.1 秒内，用户认为系统会立即做出反应。从这个值开始到大约 1 秒的时间间隔被认为是 “用户的反应时间极限”，尽管他们可以处理一些系统延迟。当时间间隔在一秒到十秒之间时，用户会感觉与运行中的模拟越来越脱节。当等待系统响应的时间达到 10 秒左右时，只要系统不提供某种反馈信息来告知用户正在执行用户请求，用户就会开始觉得发生了错误。在这项工作中，这些系统响应时间限制与拟议的 HPATheta* 算法执行时间分析相关。

在测试中使用的每个虚拟地形的地图上都有 4,300 个起点和终点。这些点是在地形图的不同位置随机生成的。用于实验的计算机配置如下： CPU： 英特尔? 酷睿? i5-8400 CPU @ 2.80 GHz 2.81 GHz；内存：16 GB（2 个 8 GB 插槽，频率 2400 MHz）；显卡：NVIDIA GeForce GTX 6000 显卡（2 个 8 GB 插槽，频率 2400 MHz）： NVIDIA GeForce GTX 1660 Ti；固态硬盘：240 GB；Windows 10 Pro（版本 10.0.19043.1052）。

为了分析实验结果，使用了广义线性回归模型（McCullagh 和 Nelder，1989 年）。根据实验结果的类型，在构建回归模型时使用了伽马分布。在这种情况下，该分布能更好地代表正的实际值，也就是实验中计算的路径搜索执行时间和结果路径的成本值。实际上，每种测试算法的结果都包含在回归模型中，以便对这些技术进行比较。

用于分析和比较测试算法的路径规划执行时间和由此产生的路径成本的回归模型定义为 g(mu) = ????????0 + ????????1 * X + ????????2 * D1 + ????????3 * D2 + ????????4 * D3 + ????????5 * D4 + ????????6 * D5、 其中，g 为对数函数。在实践中，该模型表示找到的路径的各自成本值和搜索算法的执行时间，两者都是虚拟地形上起点和终点位置之间距离的函数，这些距离值由模型中的变量 X 表示。为了将不同的技术与本研究提出的基本方法（HPATheta* ）进行比较，本统计模型中的所谓虚拟变量 D1-D5 用于表示每种算法。因此，回归模型描述了当 D1 = D2 = D3 = D4 = D5 = 0 时 HPATheta* 算法的执行时间或路径成本，并分别描述了当 D1 = 1 时的 HPT* 算法、当 D2 = 1 时带浮雕倾斜计算的 OHPA* 算法、当 D3 = 1 时的 OHPA* 算法、当 D4 = 1 时带浮雕倾斜计算的 Theta* 算法和当 D5 = 1 时的 Theta* 算法。也就是说，要获得上述每种算法的结果，必须给代表第 i 种算法的变量 Di 赋值 1，而其他变量 D 的值必须为 =0。

通过比较 HPATheta*、HPT*、OHPA* 和 Theta*，统计估算值代表了 (i) 执行时间和 (ii) 与 (iii) 不同路径距离值相关的路径成本的平均值。回归模型中使用的连接函数是对数函数，因为该函数在统计方法中的结果可以代表任何实际值。为了进行统计分析，确定显著性水平为 0.01（1%）。因此，在 i = 1、2、3、4、5 和 6 时，分别以 ???????? = 0 或 ?????????? ≠ 0 定义了两个假设 H0 和 H1。然后，将 alpha 值与??值进行比较。如果 alpha < ??-值，则拒绝 H0；否则，不拒绝 H0。????????1>0意味着起点和终点位置之间的距离越远，算法返回这些距离的路径的执行时间就越长。对于??????????来说，当 i 取值为 2、3、4、5 和 6 时，?????????? = 0 意味着????方法等同于基本方法。?????????? > 0 表示 Di 所指的方法比基本方法慢。?????????? < 0 意味着 ???? 所代表的方法比基本方法快。

如图 12、图 14 和图 16 所示，在测试技术的寻路结果中，回归模型得到的 P 值均接近零，且低于 0.01 的α水平；因此，所有结果均具有统计学意义。因此，回归模型表明，对比技术之间存在显著差异。使用 HPT* 技术、OHPA* 技术以及有和无浮雕倾斜的 Theta* 技术，起点和目标位置之间路径距离的所有执行时间和成本值都与基准 HPATheta* 技术不同。以统计数据的分析为例，图 12A 中 D5 = Theta* 的路径成本值为 0.3224。由于 exp (0.3224) = 1.38（这里使用的是指数函数，因为链接函数使用的是对数），因此可以看出，在相同的路径距离下，Theta* 技术计算出的路径比 HPATheta* 技术多需要 1.38 个成本单位。图 12、图 14 和图 16 所示的其他结果也有类似的解释。由于上述图中的所有成本估计值均为正值，回归模型显示，使用 HPATheta* 算法进行路径搜索的成本低于 HPT* 、带浮雕倾斜的 OHPA*、OHPA*、带浮雕倾斜的 Theta* 和 Theta* 算法。

就两点之间的路径成本而言，我们最初的预期是，使用 HPATheta* 算法和带有浮雕倾斜度的 Theta* 算法所需的成本最低。在这种情况下，这些算法在进行路径规划时，会处理地形地貌的特殊性，并平滑所产生的路径。此外，OHPA* 算法很快就会出现，因为它考虑到了地形的起伏倾斜。不过，OHPA* 算法并没有对路径进行平滑处理，这也是影响最终路径成本的一个因素。从测试结果来看，最初的预期得到了部分证实。这是因为，每种地形的特殊性和是否使用分层搜索技术都会影响路径结果，进而影响路径成本。

7.1. Pathfinding results with terrain ‘‘A’’

与其他地形的测试结果相比，虚拟地形 A 的计算路径成本（以计算出的路径长度以及沿该路径的浮雕倾斜成本来衡量）在所有测试算法中差异最大。即便如此，随着路径距离的增加，返回路径成本曲线的增量也略有不同。由于地形 A 的浮雕倾斜度大多在 0 o 到 10 o 之间（对目标智能体来说是微妙的地形特征），而算法考虑的浮雕倾斜度从 5 o 开始，因此成本结果大多反映了每种算法返回的路径长度。这个地形 A 也与其他地形不同：它代表了一个经过预处理的不规则群集级网格（图 11b）。也就是说，当一个节点的维度大于集群网格节点时（相对于集群定义的层级，该节点在层级上高一级），该节点就会成为一个集群，从而形成抽象层级路径搜索的不规则网格。与其他地形相比，地形 A 中的一些簇在 QuadTree 层次结构中处于较高的层次，从而扩大了这些簇的维度（鉴于 QuadTree 的性质，该簇将比系统中定义的传统簇大四倍）。

在地形 A 中，与其他算法相比，HPATheta* 算法的路径成本最低。除此基本算法外，还有 HPT* 算法获得的路径成本，该算法是基本方法的一个版本，不处理虚拟地形的地形特征。由于 HPATheta* 算法和 HPT* 算法的寻路结果相差无几，而且与其他算法相比，HPATheta* 算法的路径成本最低，因此很明显，在图 11（a）所示的阻塞节点较少、地形倾斜度较小（绝大多数在 0 o 至 10 o 范围内）的地形中，具有路径平滑功能的分层搜索算法可以获得更好的路径成本结果。这是因为 HPATheta* 方法很容易找到平滑路径。这种平滑也仅限于计算出的地形群的极限，避免了很长的平滑距离。

当 HPATheta* 算法与分层 A* 算法（如带浮雕倾斜的 OHPA* 算法和标准 OHPA* 算法）进行比较时，得出的路径成本差异较大。与基本方法相比，带浮雕倾斜的 OHPA* 算法的路径成本增加了 1.3462 个单位。另一方面，OHPA* 算法的路径成本增加了约 1.3554 个单位。这表明，尽管处理地形特征会导致路径成本增加，但所选算法对最终路径结果有很大影响。当处理的地形没有大的阻塞区域和地形起伏相当平缓时，这种影响更大，这也导致虚拟地形的分层表示结构（在我们的工作中为 QuadTree）的精细度降低（图 11a）。使用 OHPA* 方法时，在地形簇内部执行的 A* 算法考虑了从当前节点到其近邻节点的路径规划，有时会导致路径中出现不必要的曲线和偏差（例如之字形行为）。当采用带地形坡度的 OHPA* 时，对每个地形群执行带地形坡度的 A* 时，会偏离坡度在相关范围内的区域。因此，虽然由于地形起伏而降低了成本，但却增加了路径长度方面的成本。如果不考虑浮雕倾斜造成的成本计算，那么不带浮雕倾斜的 OHPA* 版本即使寻求尽可能短的路径，也会导致较高的地形成本。因此，使用促进路径平滑的算法是有意义的，因为它能使得到的路径更加真实，避免可能增加最终路径距离的微小而不必要的路径偏差。

比较 Theta* 算法的分层版本和非分层版本，分层版本在搜索过程的计算时间和所产生的路径成本方面都具有优势。带有浮雕倾斜度的 Theta* 算法比基本方法高出 1.29 个成本单位，这表明在地形群层面限制路径平滑可能有利于搜索。在不使用测试过的分层技术的情况下，该算法对地图进行整体探索，能够平滑长距离路径。不过，在某些情况下，这种较大的平滑可能会忽略与最终路径相关的偏差。反过来，与 HPATheta* 基本方法相比，不带浮雕倾斜的 Theta* 算法会使生成路径的成本增加 1.38 个单位。这是因为 Theta* 可以在不考虑地形特征的情况下平滑长距离路径。它只将路径障碍物视为一些障碍因素。它还能找到更直接的路径，即距离更短的路径，因为它寻求的是最短最平滑的路径。不过，与其他测试算法相比，不考虑地形倾斜度的 Theta* 算法得到的路径成本要高得多。在对考虑和不考虑地形信息的非层次算法版本进行观察时，与其他技术相比，比较其考虑和不考虑地形信息的版本，所获得的成本值之间的差异更大。从 HPATheta* 算法到 HPT* 算法的成本增加约为 1.4%（路径增加 1.0138 个成本单位），而从带浮雕倾斜的 Theta* 算法到标准 Theta* 算法的成本增加约为 7%（途中增加 1.0694 个成本单位）。

在执行时间方面，OHPA* 算法的表现优于其他测试算法，这一点可以从报告结果中观察到。如果将 A* 算法与分层算法一起研究，它们的表现会更加令人满意，因为它们能获得更好的性能。与基本方法相比，OHPA* 算法的执行时间非常接近，但比其他算法快约 80%。不过，OHPA* 算法并没有将平滑路径作为其优势之一，这也是本研究要解决的一个重要方面。考虑到所提出的 HPATheta* 算法能满足在 1 秒内给出路径结果的时间限制（如本节开头所述），虽然它不是所有测试算法中速度最快的，但在响应时间和返回路径质量方面都能满足要求。这表明，使用分层方法进行地形表示和寻路是缩短路径搜索执行时间的根本。在这种情况下，标准 Theta* 算法的执行速度是基础方法的 9.15 倍。在 Theta* 算法中加入对地形地貌的处理，执行时间比 HPATheta* 算法慢 14.39 倍。

7.2. Pathfinding results with terrain ‘‘B’’

虚拟地形 B 在地形起伏不平方面非常复杂，约有 34.73% 的节点被遮挡，占虚拟地形总面积的 19.81%。由于地形起伏高度的变化，QuadTree 的细化程度更高，因此分层表示法的叶节点更小。在约 30 km × 30 km 的尺寸范围内，总共有 773 440 个法线矢量值来捕捉地形的倾斜度。其中，73.81% 属于与目标智能体相关的倾斜范围（介于 5° 和 35° 之间）。与地形 A 不同的是，该地形在群集层面上具有规则的网格结构（即节点代表具有相同尺寸的地形区域）。这是因为在构建 QuadTree 时使用了高度细化，因此节点较小。这意味着没有必要因为节点过大而扩展这种地形集群级别（如第 4 节所述）。

在地形 B 中，我们注意到测试算法得出的路径成本相对接近（图 14A）。这一结果与该地形结构中受阻节点的数量有关。该地形除了起伏高度变化大（导致地形表示节点受阻的一个因素）外，还有许多河流，这也是在表示结构中阻塞节点的一个因素。在某些地形群中，这些障碍物形成了有限的通航路径。例如，请看图 13 中以深色线段表示的河流之间的路径（在地形图的放大部分可以很容易地观察到）。虽然寻路结果彼此接近，但它们之间存在显著的统计差异。

在地形 B 的测试中，与其他算法相比，HPATheta* 算法的路径成本也是最低的。紧随其后的是 HPT* 算法，如统计模型所示，多出约 1.012 个成本单位。由于地形表示结构中的阻塞节点导致搜索空间有限，因此这些算法最终返回的路径彼此接近。尽管 HPATheta* 算法和 HPT* 算法得出的路径差别很小，但 HPATheta* 算法得出的路径成本更高。
由于使用分层 Theta* 算法得出的结果很相似，因此下一个得出较好路径成本的算法是带浮雕倾斜的 Theta*。与建议的基本方法相比，带浮雕倾斜的 Theta* 算法的路径成本增加了约 1.064 个单位。这是因为带浮雕倾斜的 Theta* 并没有将搜索空间限制在属于抽象路径的地形集群区域。因此，路径平滑可以通过不同的方式、不同的延伸、不同的路径点或延伸段进行，从而影响最终的路径结果。例如，在使用分层技术时，每个地形群的边界、入口和出口节点都必须是生成路径的一部分。这就限制了通过这些地图点进行路径平滑的可能性。这一事实也解释了为什么该算法没有获得比 HPT* 更优的路径成本（如最初预期的那样），因为 HPT* 也采用了分层策略，将搜索空间限制在由抽象路径扩展的地形簇内。反过来，标准 Theta* 算法在不考虑地形特征的情况下，与其他算法相比显示出更高的路径成本增加，大约增加了 1.117 个路径成本单位。当然，由于路径平滑中使用的视线技术只评估路径是否受阻，而不考虑平滑计算中的地形倾斜度，因此得出的路径成本要高于有地形倾斜度的 Theta* 算法。不过，分层 Theta* 版本，即 HPT* 与 Theta* 和带浮雕倾斜的 Theta* 版本相比，路径成本仍然相对较低。同样，从搜索空间的大小可以看出，尽管 HPT* 算法是一种分层算法，但它在搜索空间中也有局限性。总之，标准 Theta* 算法将地形图作为一个整体来探索，能够在不考虑地形信息的情况下平滑较大的地形区域，从而导致生成路径的路径成本较高。

与本文提出的基本方法相比，OHPA* 算法的路径成本也更高。虽然它们的搜索空间也仅限于地形集群节点，但这些算法并不进行路径平滑。因此，它们组成的节点-节点路径，其最终路径长度也会影响路径成本。在这种情况下，与拟议的 HPATheta* 相比，带有地形倾斜度的 OHPA* 所产生的路径成本增加了约 1.089 个单位。反过来，与基本方法相比，不带浮雕倾斜的 OHPA* 所产生的路径成本增加了约 1.104 个单位。如前所述，该算法寻求的是最短路径，但它没有考虑地形起伏信息。
在执行时间方面，拟议的 HPATheta* 算法落后于 OHPA* 算法（包含和不包含地形起伏倾斜度）和 HPT* 算法。这一结果在意料之中，因为 HPATheta* 算法不仅能计算由地形起伏产生的路径成本，还能在执行搜索时平滑路径。在地形 B 中，可以观察到长距离路径计算时间的增加远高于前面讨论过的地形 A 中类似路径计算时间的增加。增加的原因在于搜索过程中探索的节点数量，因为地形 B 的复杂性更高，因此分层表示结构的细化程度也更高。因此，响应时间与这些地形表示结构中已探索节点的数量成正比。不过，HPATheta* 算法即使在虚拟地形 B 中涉及较大距离的路径，也能在不到 1 秒的时间内返回路径结果。

与 HPT* 算法相比，HPATheta* 所需的计算时间延长了约 6.8%。至于两种版本的 OHPA* 算法（处理地形信息和不处理地形信息），基本算法的响应时间大约长 7 倍。需要强调的是，与标准的逐节点路径搜索相比，路径平滑执行过程需要额外的计算时间。如果考虑到浮雕倾斜信息，路径搜索过程就会变得相对耗时，从而导致响应时间比不执行平滑的有浮雕倾斜和无浮雕倾斜的 OHPA* 更长。不过，在计算寻路过程中考虑地形起伏信息进行平滑处理，比执行标准搜索，然后在平滑处理过程中执行考虑地形起伏倾角的后处理算法要好。考虑到所获得的计算时间值很低（路径距离为 20 千米时约为 50 毫秒），而且彼此非常接近，因此差异并不显著。

在地形 B 中，路径搜索中使用分层技术的重要性再次凸显。标准 Theta* 算法的执行时间比建议的基本方法多出约 3.61 毫秒。当使用带浮雕倾斜的 Theta* 算法时，执行时间比 HPATheta* 基本方法多出约 6.31 毫秒。

7.3. Pathfinding results with terrain ‘‘C’’

与其他地形相比，虚拟地形 C 有更多的节点被阻塞（40% 的叶节点被阻塞，占地图总面积的 21.82%）。在使用的三个虚拟地形中，地形 C 的地形不平整度较低。总体而言，该地形的山脉较少，而且位于地图中心区域，高度也不高。这与地形 A 不同，地形 A 的不平整区域位于地形边缘。地形 C 还有大量的湖泊和河流，因此在其虚拟表示中会产生阻塞节点。地形 C 的尺寸约为 33 km × 62 km，其结构中共有 676 300 个法线矢量，反映了地形的起伏倾斜。其中，24.59%的地形处于与目标智能体相关的地形倾斜范围内（5?至 35?）。

由于许多节点被河流和湖泊阻挡，地形 C 的搜索空间也很有限，甚至比地形 B 更有限。图 15 中突出显示了地形 C 的一部分，以说明在因河流而受阻的节点之间狭窄的自由空间中寻找路径的情况。尽管在地形 C 中观察到的算法之间的差异很小，但 HPATheta* 方法显示出了最佳的路径成本。不考虑地形特征的 HPT* 算法的结果排在第二位，与基本方法相比，路径成本增加了 1.017 个单位。鉴于地形 C 有许多阻塞节点和轻微的地形倾斜，搜索结果有一定的就近路径倾向，特别是在使用类似性质的算法时。与基本方法相比，OHPA* 算法的路径成本增加了约 1.065 个单位。这再次表明，由于 HPATheta* 和 HPT* 对分层技术的探索，路径平滑对最终路径成本的影响。如前所述，在具有微妙地形倾角的虚拟地形中，返回路径之间的差异主要是由于路径搜索算法所使用的技术而非地形倾角信息本身造成的。在分析分层算法的结果时，路径搜索结果的这种相似性更加明显，因为这些算法将搜索空间限制在所产生的抽象路径所选择的地形群上。然而，对于在搜索过程中无限制地探索虚拟地形图（无集群限制）的算法，在寻路结果中观察到了更大的差异。与基本方法相比，带浮雕倾斜的 Theta* 算法增加了约 1.030 个路径成本单位，而标准 Theta* 算法则增加了约 1.100 个路径成本单位；与不带浮雕倾斜的Theta* 算法相比，带浮雕倾斜的 Theta* 算法的路径成本增加了约 6.7%，这是测试的性质相似的算法之间观察到的最大差异。如前所述，自由探索虚拟地形图，不局限于某些地形集群区域，可使最终寻路结果产生更大差异。然而，在大规模虚拟地形中，使用分层搜索技术对于提高寻路的执行时间是至关重要的。

正如在其他测试过的虚拟地形中已经看到的那样，OHPA* 算法在有地形特征处理和无地形特征处理的版本中，执行时间比其他算法短得多。在这种情况下，基本算法（HPATheta* ）比两个版本的 OHPA* 算法（带浮雕倾斜和不带浮雕倾斜）慢约 7 倍。与 HPT* 算法相比，HPATheta* 算法的执行时间更长，这在意料之中，也在情理之中，因为该算法计算的是与地形起伏倾斜度相关的路径成本。需要指出的是，在 HPT* 算法的路径规划中，并没有考虑计算地形起伏倾斜度成本的步骤。执行时间最长的算法是处理地形信息的 Theta* ，与基本方法相比，响应时间约为 5.155 毫秒。最后，与拟议的 HPATheta* 算法相比，标准 Theta* 算法的响应时间增加了约 3.346 毫秒。

7.4. Discussion

为了扩大对本研究实验结果的评估范围，可以对以下几个方面进行分析：(i) 在所有地形中进行的测试结果，(ii) 本文所研究建议的分层寻路特性，(iii) 建议算法的效率和 (iv) 精度。

7.4.1. Cross analysis of the pathfinding results with the real-world terrain

通过这三种不同的测试场景，我们可以发现每种地形的特殊性是如何影响每种测试算法的寻路结果的。地形 B 和地形 C 在地形细化程度和地形阻塞方面有相似之处，其结果在路径成本和执行时间方面也有一定的相似性（成本方面分别为图 14A 和图 16A，计算时间方面分别为图 14B 和图 16B）。这两种地形结构都有很大的细化，生成的节点越来越小，越来越大（其中许多节点被阻塞，根据所代表河流的走向形成 “小巷”）。此外，地形 B 和地形 C 的网格簇以规则布局的形式表示，与 QuadTree 处于同一级别（即第 5 级）。根据测试算法得出的最佳路径成本，B 地形和 C 地形的结果相当，但在执行时间方面存在差异。

地形 A 的路径成本与其他地形的结果不同（图 12A）。地形 A 的路径成本值与路径距离值一致。正如之前所讨论的，这是因为地形 A 与地形 B 和地形 C 不同，地形 A 有少量陡峭的浮雕倾斜（接近 35?），并且由于地形特征，结构细化很少。这些结果还表明，分层平滑算法返回的路径成本较低。由于地形 A 的细化程度不高，也就是说，节点在表示结构中捕捉到的地形面积较大，此外还有细微的浮雕倾斜（绝大多数在 0 o 和 10 o 之间），因此路径平滑对结果路径的低成本起着根本性的作用。就每种算法在使用地形 A 时获得的最佳路径成本而言，它们的效率排序与使用其他地形进行测试时观察到的结果相同。这一寻路结果在所有测试场景中都是相同的。在性能方面，一般来说，与在其他地形下进行的测试相比，在地形 A 下执行的算法所需的处理时间要短得多（图 12B）。例如，对于 27 千米的距离，拟议的 HPATheta* 算法需要约 16 毫秒才能返回路径。在这种情况下，最耗时的算法是处理了地形特征的 Theta*。对于 27 公里的路程，该算法的执行时间约为 240 毫秒。在考虑这些长距离时，使用分层搜索方法的相关性再次凸显出来，从而提高了测试路径规划算法的性能。

如前所述，在地形 B 和 C 中，与测试算法返回的路径成本相关的效率顺序是相等的。不过，在使用不同算法时，路径计算时间的效率顺序存在差异（分别见图 14B 和图 16B）。在地形 C 中，与标准版本相比，带浮雕倾斜的 OHPA* 算法的执行时间更长。这是意料之中的，因为该算法采用了额外的成本计算步骤来计算地形起伏特征。在地形 B 中，观察到了相反的情况：基于地形的路径搜索算法与其标准版本相比，执行时间更短。不过，这一差异太小，小于 0.1 毫秒，因此不能视为相关。

与其他地形相比，在地形 C 中搜索相同距离路径所需的计算时间较长（图 16B）。在地形 C 中，拟议的 HPATheta* 算法搜索 27 千米距离的执行时间约为 200 毫秒，而在地形 B 中，相同距离的搜索时间约为 130 毫秒。

与地形 A 相比，地形 B 和地形 C 的搜索时间更长，这是意料之中的合理结果，因为这两个地形使用的表示结构更加精细。由于 B 和 C 地形更加复杂，搜索过程中需要探索的节点更多，这与路径规划算法的执行时间直接相关。在这些情况下，对地形特征进行处理的 Theta* 算法在所有情况下都获得了最长的计算时间，对 B 和 C 地形的响应时间分别达到约 820 毫秒和 1117 毫秒。

7.4.2. Analysis of the hierarchical pathfinding characteristics

实验中使用的寻路算法的选择基于以下问题： (i) 平滑化，因此选择了标准版本的 Theta* 算法，并对其进行了调整，以处理地形路径成本和加权视线的计算；(ii) 层次化，这也是选择 HPA* 算法（在本研究中使用 OHPA* 在线版本）和 HPT* 算法的原因–比较它们在应用地形路径成本和不应用地形路径成本时的性能–因为导航结构被划分为群组，所以它们可以处理较大的搜索空间。这项工作是对 Brondani 等人（2019）所做工作的扩展，其动机是 SIS-ASTROS 项目（SISASTROS，2014 年）正在开发的虚拟战术模拟系统的相同路径规划需求。虽然其他算法也能探索分层和平滑的路径规划，例如 N 层子目标图（Uras & Koenig, 2014）和跳点搜索（JPS）（Harabor & Grastien, 2011），但我们实验中使用的算法能更好地探索 SIS-ASTROS 模拟系统中已经实现的分层和不规则地形表示结构。

实验结果表明，使用分层方法进行路径规划对于获得更好的搜索性能非常重要。正如本文前面所讨论的，搜索空间仅限于 "抽象路径 "所发现的簇的维度，从而引导搜索并减少搜索 "具体路径 "时所探索的节点数量。实际上，具体路径是通过对表征结构更高层次的细化分析得到的。从实验结果中可以看出，在地形 A（地形复杂度较低）中，建议的算法（HPATheta*）计算出一条距离约为 27 千米的路径大约需要 16 毫秒，而不使用层次结构的算法（Theta*，带浮雕倾斜度）计算出一条通往同一对来源点和目的地点的路径则需要 240 毫秒。而 HPT* 算法在相同地形上的相同距离则需要约 17 毫秒，而其不使用层次细化的版本，即不使用浮雕倾斜的 Theta* 算法则需要 150 毫秒。在地形 B 中，层次结构的相关性也很明显，这主要是因为该地形的浮雕复杂度更高。要找到一条距离为 27 千米的路径，HPATheta* 算法大约需要 137 毫秒，而有浮雕倾斜的 Theta* 算法只需 896 毫秒就能返回一条路径。HPT* 算法及其非层次化版本，即不带地形倾斜的 Theta* 算法的执行时间分别约为 129 毫秒和 505 毫秒。在地形更为复杂的地形 C 中，HPATheta* 算法在 27 千米距离内的执行时间约为 200 毫秒，而带浮雕倾斜的 Theta* 算法在相同距离内寻找路径的执行时间约为 1,117 毫秒。此外，在相同距离上，不带浮雕倾斜的 HPT* 算法和 Theta* 算法的执行时间分别约为 200 毫秒和 725 毫秒。

正如第 3.1 节所分析的，使用分层方法的寻路算法与非分层方法的寻路算法相比，性能提升是显而易见的，尤其是在应用于大规模搜索空间时。地形信息的预处理也是有助于实现上述结果的一个方面。正如在 HPA* （Botea 等人，2004 年）中介绍的那样，在不使用层次结构的情况下比较 HPA* 和 A* 算法，寻路性能的提高是显而易见的，尤其是在大型搜索空间和具有许多特征的地形中。不使用层次结构的寻路算法可能比使用该技术的算法稍好的情况是，搜索问题非常简单，通常涉及源点和目标点之间非常小的距离。然而，在模拟大型地形时，有必要处理较难处理的情况，包括在不超过进行模拟所需的时间限制的情况下穿越地图的长度。

7.4.3. Efficiency analysis

为了证明寻路算法的效率，该算法必须达到预期目的，即以较低的成本获得结果路径，并在预定范围内提供执行时间。可以看出，所提出的算法在这些标准之间进行了相关的权衡：得到的路径成本和执行时间。在许多情况下，这两个方面是相互冲突的，因为要评估这些限制条件下的计算成本，就必须包含额外的路径搜索程序，这可能会增加执行时间。在所进行的实验中，根据第 7 节中介绍的实验方案，对所选算法的这些指标进行了收集和比较。低成本、平滑的路径可避免 "之 "字形行为，这对于开发算法的仿真系统以及许多需要进行此类地形计算的应用来说非常重要。此外，相对较短的执行时间也很重要，尤其是在仿真环境中，这一点将在第 7 节中说明。虽然实验结果并不表明所提出的算法（HPATheta* ）是所有测试算法中速度最快的算法，但就路径成本（这是实现本研究目标的关键因素）而言，该算法在所有测试地形中与其他算法相比取得了最好的结果。此外，即使是长距离路线，HPATheta* 算法的执行时间也低于规定的时间限制，从而保证了用户在模拟中的沉浸感（见第 7 节）。这表明 HPATheta* 算法即使在大规模地形中使用，也能在仿真时间限制内运行，从而实现了其目的。

7.4.4. Accuracy analysis

为了评估寻路算法的准确性，我们需要评估返回路径的成本。我们的目标是最大限度地降低成本，因为成本越低，地形倾斜度越小。然而，一条能避开所有陡峭地形坡度的路径可能会变得非常曲折。为了在模拟上实现更真实的智能体运动（避免 "之 "字形的智能体行为），建议算法的目标是为平滑的路径获取更低的成本。这意味着 HPATheta* 算法获得的最终路径成本并不会导致浮雕倾斜成本之和的最小值。实际上，该算法返回的是避免这种不理想之字形的最小倾斜成本总和。

带浮雕倾斜的 A* 算法返回的路径成本最优。不过，这种算法往往会产生蜿蜒曲折的路径。通过比较 HPATheta* 算法与带浮雕倾斜度的 A* 算法的路径成本，可以发现 HPATheta* 算法的路径成本非常接近最优成本。根据寻路算法所适用的地形配置，平滑也能有效降低路径成本。比较在地形 A 中获得的成本值，所提出的算法比带有浮雕倾斜度的 A* 算法成本更低，这是与目标相关的结果。这一结果与在地形表示和搜索过程中使用分层和不规则结构的方式有关。尽管取得了这一积极成果，但在测试中考虑地形 B 和 C 时，结果却不尽相同。这是因为在模拟这些真实世界地形的各种特征时，所使用的表示结构略有细化。

当所使用的地形中只有很少的地形特征可供模拟使用时，就会在表示结构中使用较大的节点（有些节点甚至有一个集群的大小）。这些节点最终代表了智能体移动时需要覆盖的大片地形。从这个意义上说，在计算路径时访问这些节点中心的具有浮雕倾斜度的 A* 的行为会导致不必要的之字形路线，从而增加智能体路线的最终成本。实际上，与平滑后的路径相比，它们最终要走更长的距离。在使用地形 A 时，这种影响会更大，因为地形 A 在 0 o 和 10 o 之间有轻微的起伏倾斜。在这种倾斜情况下，平滑过程并不会给生成的路径增加多少成本，这意味着最终成本要低于忠实地偏离这些倾斜的路径的成本，尽管要走更长的距离。根据丹尼尔等人（2010 年）的研究，如果考虑到路径的长度，Theta* 算法在网格上找到的路径比 A* 算法更短。根据该研究中的实验，99% 的情况下 Theta* 算法比 A* 算法在网格上获得的路径最小。在具有微妙地形倾斜和大型表示节点的地形中，最终成本主要表示的是行进距离，而不是地形倾斜造成的成本。对于这种地形 A，拟议算法的最终成本比 A* 算法加上地形起伏处理后的路径成本低 16%。

对于地形 B 和 C，由于其复杂性更高，特别是与所考虑的智能体相关的大量河流和浮雕倾斜度，它们的分层和不规则表示结构表现出更高的精细度，带有浮雕倾斜度的 A* 算法通过彻底偏离倾斜度返回最佳成本。在这种情况下，这些地形表示结构的节点并不大。因此，路径上的浮雕倾斜度对路径成本的影响相对于行驶距离而言会变得更大（这与地形 A 不同）。尽管如此，HPATheta* 算法与带有浮雕倾斜度的 A* 算法相比，成本变化较小，后者能返回最优路径成本。对于地形 B，HPATheta* 算法产生的路径成本增加了 6%。对于地形 C，则增加了约 7.5%。总之，建议的算法提出的路径成本接近于返回最优成本的算法。这样，它还避免了 "之 "字形行为，此外，与带有浮雕倾斜度的 A* 算法相比，运行时间也短得多。根据第 7.1-7.3 节的分析，与实验中测试的其他算法相比，该算法得出的路径成本最低。这也是路径质量的相关指标。

8. Final remarks

这项工作提出了一种寻路算法，用于处理基于真实世界地图构建的虚拟地形浮雕中的不平整问题，地形特征的处理反映在寻路的计算成本上。研究结果表明，在同一区域，相同的路径距离间隔，HPATheta* 算法的成本更低。

值得注意的是，这项研究解决了在不平坦的地形中搜索路径的问题，旨在促进插入大规模模拟虚拟环境中的不同类型智能体的安全移动。此外，该作品还介绍了如何使生成的路径更加逼真，这是以教育为目的的仿真系统的一个基本特征。这项研究通过对生成路径的平滑算法进行探索来实现。为此，路径计算使用了视线的概念，并对其进行了适当修改，以处理地形的浮雕倾斜。实际上，使用视线来处理涉及地形起伏倾斜的智能体移动限制信息，是一种在文献中仍未得到充分探讨的方法。尤其是在寻路过程中仅使用受阻节点信息时（通常在此过程中转换为路径权重），情况更是如此。此外，所提出的算法采用了分层搜索技术，将地形节点之间的路径预处理与虚拟地形表示结构的层次结构结合起来使用。这种技术优化了计算的执行时间。

针对提出的问题，通过与文献中的其他建议进行比较测试，对提出的路径规划解决方案进行了评估。通过这些测试，我们可以评估不同方案的优缺点，例如使用分层方法（OHPA* 和 HPT* ）所带来的性能提升，以及使用路径平滑技术（Theta* 和 HPT* ）的益处。通过所进行的实验，可以观察到 HPATheta* 算法成功地将不同寻路和地形表示技术的优势与使用和计算与目标智能体相关的地形特征信息结合在一起。研究还发现，无论模拟地形的复杂程度如何，提议的算法都能返回更高质量的路径。这意味着尽可能提供低成本的路径，包括浮雕倾斜度和覆盖距离，以及平滑路径。在性能方面，HPATheta* 算法也达到了 SIS-ASTROS 项目的研发预期。尽管在所有已执行的路径规划实验中，HPATheta* 算法的执行时间都不是最短的，但却接近最佳结果时间。在那些不是最佳时间的实验中，即使计算长路径距离（即大搜索空间），它也能满足所有实验中小于 1 秒的响应时间要求。

在未来的工作中，我们可以设想一种更加通用的方法，用于新型虚拟仿真的路径规划。这不仅是 SIS-ASTROS 项目的新发展，也是其他模拟培训和教学环境的新发展。由于这项工作仅限于有静态障碍物的场景，今后的工作可以扩展所提出的算法，以处理移动障碍物。尽管如此，仍有可能扩展本文讨论的分层和平滑技术，开发出一系列具有相似性的算法。这类算法将处理不同的现实智能体约束，更适合特定类型的大规模真实世界虚拟地形环境。