路径规划

路径规划方法的核心是从一个顶点开始搜索图，并探索相邻的节点，直到到达目的节点，通常是为了找到最便宜的路径。虽然图形搜索方法，如广度优先搜索，能够在足够的时间内找到一条路线，但其他“探索”图形的方法往往会更快到达目的地。一个类比是一个人走过一个房间；与其事先检查每一条可能的路线，人们通常会朝着目的地的方向走，并且仅仅偏离路径以避免障碍物，并且使偏离尽可能小。

路径规划的两个主要问题是(1)找到图中两个节点之间的路径；(2)最短路径问题——寻找最优最短路径。广度优先和深度优先搜索等基本算法通过用尽所有可能性来解决第一个问题；从给定节点开始，它们遍历所有潜在路径，直到到达目的节点。这些算法运行的时间复杂度是O(|V|+|E|)，或者线性时间复杂度，其中V是顶点的数量，E 是顶点之间的边的数量。

更复杂的问题是找到最佳路径。在这种情况下，穷举的方法被称为贝尔曼-福特算法，它产生的时间复杂性为 O(|V||E|)，或二次时间。然而，没有必要检查所有可能的路径来找到最佳路径。像A*和戴克斯特拉算法这样的算法从战略上消除路径，要么通过启发式算法，要么通过动态编程。通过消除不可能的路径，这些算法可以实现低至O (|E |log(|V |))的时间复杂度。^[1]

上述算法是在没有预处理的情况下对图形进行操作的最佳通用算法之一。然而，在实际的旅行路线系统中，可以通过对图进行预处理以获得更好性能的算法来获得更好的时间复杂度。^[2]其中一种算法是收缩层次结构。

1.1 戴克斯特拉算法

基于图的寻路算法的一个常见例子是戴克斯特拉算法。该算法从一个开始节点和一组“开放”的候选节点开始。在每个步骤中，检查开放集合中距离起点最低的节点。该节点被标记为“关闭”，并且如果尚未检查，则与其相邻的所有节点都被添加到打开的集合中。重复该过程，直到找到到达目的地的路径。因为首先检查距离最低的节点，所以第一次找到目的地时，到达目的地的路径将是最短的路径。^[3]

如果有负边缘权重，戴克斯特拉算法就失败了。在节点A、B和C形成边AB = 3、AC = 4和BC = 2，从A到C的最优路径花费1，从A到B的最优路径花费2。迪杰斯特拉算法从A开始将首先检查B，因为那是最近的。它将为它分配3的成本，并将其标记为关闭，这意味着它的成本永远不会被重新评估。因此，迪克斯特拉不能评估负边缘权重。然而，由于在许多实际应用中，永远不会有负边缘权重，戴克斯特拉算法在很大程度上适用于路径规划的目的。

1.2 A*算法

A*是游戏中常用的戴克斯特拉算法的变体。A*为每个打开的节点分配一个权重，该权重等于该节点的边的权重加上该节点和终点之间的近似距离。该近似距离由启发式算法找到，代表该节点和末端之间的最小可能距离。一旦找到初始路径，这允许它消除更长的路径。如果在起点和终点之间有一条长度为x的路径，并且节点和终点之间的最小距离大于x，则不需要检查该节点。^[4]

A*使用这种启发式方法来改善相对于戴克斯特拉算法的行为。当启发式算法评估为0时，A*相当于戴克斯特拉算法。随着启发式估计的增加和接近真实距离，A*继续寻找最佳路径，但是运行得更快(通过检查更少的节点)。当启发式算法的值恰好是真实距离时，A*检查最少的节点。(然而，编写总是计算真实距离的启发式函数通常是不切实际的。)随着启发式算法值的增加，A*检查的节点越来越少，但不再保证最优路径。在许多应用中(例如视频游戏)，这是可以接受的，甚至是理想的，以便保持算法快速运行。

1.3 样本算法

对于基于图块的地图，这是一个相当简单且易于理解的路径查找算法。首先，你有一张地图，一个起点坐标和一个终点坐标。地图会是这样的， X 作为墙， S 作为开始， O 成为终点 _ 作为开放空间，沿着顶部和右侧边缘的数字是列号和行号:

  1 2 3 4 5 6 7 8
X X X X X X X X X X X X X X
X _ _ _ X X _ X _ X
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X _ X _ _ X _ _ _ X 4
X _ _ _ X X _ X _ X
X _ X _ _ X _ X _ X 6
X _ X _ _ _ X _ X _ 7
X _ _ O _ X _ _ X 8
X X X X X X X X X X X X X X

首先，创建一个坐标列表，我们将把它用作队列。队列将用一个坐标初始化，即结束坐标。每个坐标还将附加一个计数器变量(其目的将很快变得明显)。因此，队列以((3，8，0)开头。

然后，遍历队列中的每个元素，包括在算法过程中添加到末尾的元素，并对每个元素执行以下操作:

1. 创建四个相邻单元格的列表，当前元素的计数器变量为+ 1(在我们的示例中，四个单元格是((2，8，1)、(3，7，1)、(4，8，1)、(3，9，1))
2. 检查每个列表中的所有单元格是否存在以下两种情况:
   1. 如果单元格是墙，将其从列表中删除
   2. 如果主列表中有一个元素具有相同的坐标和小于或等于的计数器，将其从单元格列表中删除
3. 将列表中剩余的所有单元格添加到主列表的末尾
4. 转到列表中的下一项

因此，在第一轮之后，元素列表如下:(3，8，0)，(2，8，1)，(4，8，1))

• 2轮后:((3，8，0)，(2，8，1)，(4，8，1)，(1，8，2)，(4，7，2))
• 3轮后: (...(1，7，3)，(4，6，3)，(5，7，3))
• 4轮后: (...(1，6，4)，(3，6，4)，(6，7，4))
• 5轮后: (...(1，5，5)，(3，5，5)，(6，6，5)，(6，8，5))
• 6轮后: (...(1，4，6)，(2，5，6)，(3，4，6)，(6，5，6)，(7，8，6))
• 7轮后: (...(1，3，7))–问题解决，结束算法的这一阶段–请注意，如果有多个单元在追逐相同的目标(如在许多游戏中一样–算法的完成到开始的方法旨在使这更容易)，您可以继续，直到整个地图被占用，所有单元都达到或达到设定的计数器限制

现在，将计数器映射到地图上，得到这个:

  1 2 3 4 5 6 7 8
X X X X X X X X X X X X X X
X _ _ _ X X _ X _ X
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
x6x 6x _ _ _ x4
X 5 6 5 X X 6 X _ X 5
X 4 X 4 3 X 5 X _ X 6
X 3 X 2 3 4 X _ X 7
X 2 1 0 1 X 5 6 _ X 8
X X X X X X X X X X X X X X

现在，从S (7)开始，转到附近数量最少的单元格(未选中的单元格不能移动到)。追踪的路径是(1，3，7)-(1，4，6)-(1，5，5)-(1，6，4)-(1，7，3)-(1，8，2)-(2，8，1)-(3，8，0)。如果两个数字相等(例如，如果S为(2，5))，选择一个随机方向——长度相同。算法现在完成了。

克里斯·克劳福德在1982年描述了他是如何“花费大量时间”试图解决在坦克游戏中电脑的坦克被困在U型湖的陆地上的问题。“在浪费了大量精力之后，我发现了一个更好的解决方案：从地图上删除U形湖泊，”他说。^[5]

2.1 分层路径查找

这个想法最早是由电子游戏产业提出的，他需要用较少的CPU时间在大地图上进行规划。使用抽象和试探法的概念由来已久，最早是以抽象条带的名字提出的^[6]，用于在逻辑游戏的状态空间中高效搜索。^[7] 一种类似的技术是导航网格(navmesh)，它用于游戏中的几何规划，而多模式运输规划则用于多个运输车辆的旅行推销员问题。

地图被分成几组。在高层，规划集群之间的路径。找到计划后，将在较低级别的集群中规划第二条路径。^[8]也就是说，规划分两步进行，即在原始空间中进行有指导的局部搜索。优点是，节点数量更少，算法性能非常好。缺点是，分层路径规划器很难实现。^[9]

例子

地图的大小为3000x2000像素。在像素基础上规划路径需要很长时间。即使是高效的算法也需要计算许多可能的图表。原因是，这样的地图将包含600万像素，探索几何空间的可能性是无穷无尽的。分层路径规划器的第一步是将地图分成更小的子地图。每个集群的大小为300x200像素。集群总数为10x10=100。在新创建的图中，节点数量很少，可以在100个集群之间导航，但不能在详细地图中导航。如果在高级图中找到有效路径，下一步是规划每个集群中的路径。子映射有300x200像素，普通的A*路径规划器可以轻松处理。

• A*搜寻算法
• 戴克斯特拉算法，A*搜寻算法的一个特例
• D*一系列增量启发式搜索算法，用于解决约束随时间变化或代理首次规划路径时不完全知道的问题
• 任意角度路径规划算法，一系列用于规划路径的算法，这些算法不限于沿着搜索图中的边缘移动，旨在能够呈现任意角度，从而找到更短、更直的路径

多代理路径规划是在不相互冲突的情况下，为多个代理找到从其当前位置到其目标位置的路径，同时优化成本函数，例如所有代理的路径长度之和。这是路径规划的综合。许多多智能体路径规划算法都是从A*推广而来的，或者是基于归约到其他研究得很好的问题，如整数线性规划。^[10] 然而，这种算法通常是不完整的；换句话说，没有被证明在多项式时间内可解。不同种类的算法通过使用已知的导航模式(如交通流)或问题空间的拓扑结构来牺牲性能的最优性。^[11]