描述

上一篇文章混合A*算法详解（一）路径搜索

路径损失函数使用Voroni势能图

根据之前的文章分析，决定A*路径长度的有两点：路径长度和距离障碍物远近。Voroni图用于权衡这两者。之前我在记录二维点云的阿尔法形状算法时简单介绍过维诺图，链接在这里。
阿尔法形状算法与2D点云的C++实现

维诺图可以将每个障碍物作为一个多边形的中心。障碍物与障碍物之间，被等分的线段分割开，使得整个环境构成了一张维诺图。它有如下几个性质：
1.每个多边形中只有一个节点；
2.相邻多边形中的节点到达他们公共边的距离相等；
3.多边形内的点距离其中心，比距离其他多边形的中心都要近

论文在维诺图的基础上提出了维诺势能（Voroni Field）。它的公式如下：

(,)pv(x,y)代表节点在某一位置的势能，α代表下降速率，dO?代表节点到最近障碍物的距离，dV?代表节点到维诺图多边形边的距离。dOmax?代表势能值的最大有效范围。根据该势能会生成一个维诺图（the Generalized Voronoi Diagram，GVD）

该势能有以下几个特点：

1.超出势能值范围的势能都为0；
2.势能值(,)?[0,1]pV?(x,y)?[0,1]，且在(,)(x,y)范围内是连续的；
3.只有在障碍物内部才会达到最大值；
4.在GVD的边上达到最小值。

Voronoi场相对于传统势场的关键优势在于，势能值是根据总可用导航间隙按比例缩放的。因此，即使很窄的开口仍然是可导航的，这在标准势场中并不总是如此。在传统势场中，障碍物周围的场值通常被设置为无穷大，这意味着车辆无法穿越这些区域。相比之下，Voronoi场根据可用的导航间隙来调整势能值，这意味着即使在狭窄的空间内，车辆也可以找到可穿越的路径。

论文给出了几张图，如下：

图a显示了一个模拟停车场对应的Voroni势能图，图b是其对应的GVD图。注意到障碍物之间的狭窄空隙没有被势能阻挡，在他们之间总会有一条=0pV?=0的势能为0路径。图c显示了一个反例，当势能公式为(,)=(+(,))?1p(x,y)=α(α+dO?(x,y))?1时，障碍物之间仍然有比较高的势能。

下图显示了一个真实停车场的维诺地图中的一条驾驶轨迹。

点击混合A*算法详解（二）路径平滑——古月居可查看全文