深度解析使用位场算法实现路径规划

qiaoweiyiyi

近年来无人机在各类潜在民用领域获得了广泛的研究，然而现有的机器人导航仍然需要发展在各种场景下高效应用的技术。一个研究热点与关键点就在于感知与避障。对于无人机的自主决策与控制，研究者们提出了几种规划与导航算法。这篇文章旨在对于无人机的路径规划算法深入研究，并且解释了势场算法的原理。实验中的测试样例场景有助于理解时间复杂度是如何随着维度变化和提供的系统空间而变化的。

引言

在过去几年中，用机器人来减轻人类工作已经成为一个新兴的研究领域。从移动机器人在陆地上以及水下的军事用途，到在餐馆里为顾客烹饪食物，机器人已经成为减少人类工作负担的新兴领域。然而，无人驾驶处理的一个主要问题是路径规划和障碍物检测，同时最小化输入值并获得最优结果。最近某些研究工作已经解决了这个问题，关于如何通过使用不同的技术创建障碍分布模型，以及当我们在真实世界系统中做一些假设，如何能够获得期望的结果。

位场算法是用于这类问题的最基本和最传统的算法之一。本文将根据所使用的文献来源和实验结果简要介绍不同的算法如何可用于路径规划的，以及位场算法如何帮助我们进行障碍物检测。

不同路径算法的比较研究

最近一些科学家一直在研究路径规划优化问题和障碍物检测问题。很多算法都可以通过不同方式使用、操纵，并进行无人机的路径规划。下面是算法族及其特征的概述：

1.位场

·在实际应用中很难实现

·窄通道性能差

·动态环境下的性能差

·容易陷入局部极小情况

·处理对称障碍的问题

2.Floyd–Warshall

·它是具有最优子结构的动态规划的子集。

·它可以在基于网格的地图中得到最优答案

·相较于Dijkstra和Belman-Ford算法有更好的性能

·能够解决困难的路径规划问题

·由于计算复杂度高，不建议在板上实现

3. Genetic Algorithm

·高效的启发式方法。

·计算时间和算法复杂度很大程度依赖于算法的实现。

·最近该算法与学习过程的结合导致一个非常有前途的在线应用[I]

4．A*算法

·它可以为最优路径搜索提供一种通用的启发式方法

·它可以潜在地搜索地图的巨大区域。

·该算法最坏的情况是考虑图中所有的节点和边。

·解决时间将受益于静态环境

· 基于场景，可能导致最优或接近最优解

5. 动态编程

·通过分解成成问题的集合来解决一个复杂的问题

·它需要存储器来保存由迭代生成的所有解决方案

·计算时间随着问题规模的增大而增加。

·解决方案在实现的基础上保证了最优答案

使用的术语

位场算法已被用于传统机器人的障碍检测和路径规划。在学习这个算法时，有几个术语必须定义以使解释更简单。为了有效地解释算法，下面是对本文中使用的术语的简要总结：

·世界空间需存在车辆。

·配置是包含定义车辆的位置状态所需的参数的向量，该参数通常由无人机的三个位置坐标和三个方向坐标组成。

·障碍空间是障碍物所占据的物理空间。

·自由空间是不被障碍物占据的物理空间。

·在物理空间中，路径是曲线，以跟踪车辆。

·路径规划确定了一个路径，该路径从当前状态（也被称为初始状态）到最终状态（也被称为目标状态）的路径。

·局部目标是指无人机试图实现从初始状态向目标状态过渡的中间目标。这涉及到求解多个子问题以获得一般总体问题的解。总体目标是找到导航无人机到全球目标的路径或轨迹。

什么是位场，它是如何工作的？

位场是服从拉普拉斯方程的任何物理场。位场一些常见例子包括：电场、磁场和引力场。位场算法利用人工位场对机器人在一定空间内进行调节。为了方便起见，我们考虑把一个空间划分成网格的障碍物和目标节点。

▲二维空间中产生的位场

该算法利用潜在的位场函数将人工势场分配给世界上的每个点，位场函数将在后面进一步描述。机器人模拟从最高势能点到最低势能点。这里，目标节点具有最低的势能，而起始节点具有最大的势能。因此，我们可以说，无人机从最低势能点移动到最高势能点。

产生的潜在场：

在该系统中产生两种人工位场：

吸引场和排斥场。

▲三维空间中的障碍物检测

目标节点表现出有吸引力的场，而系统中的障碍物产生排斥场。

斥力α  1 /从机器人到障碍物的距离。

因此，在图的每个点处产生的总力是：

U总 =U吸引力+U排斥力

吸引力

下面的函数可以用来生成目标节点产生的力。这里，x、y是起始节点的坐标，（xgoal，ygoal）是目标节点的坐标，C是常数。

斥力

在这个系统总产生了两种排斥力：

1. 边界排斥力

这种力在整个系统中保持均匀，因此不影响计算；这种力是用来保持机器人远离边界的。下面的方程式可以用来寻找边界所表现出的排斥力：

其中，gi是表示凸区域边界的线性函数，δ是一个小值的常数，S是边界面段的数目。

2．障碍物的排斥力：

障碍物的斥力可以通过下面给出的公式来计算。这里，pmax是最高的势能，（x0，y0）是障碍物的中心的坐标，I是障碍物的侧面长度：

因此，环境的合力是：

P= P0+Pgoal

其中，

P0= max {pi}

局部极小陷阱

位场算法面临的一个挑战是局部极小陷阱问题。当所有人造力（吸引力和排斥力）相互抵消时，例如下面这些情景：当障碍物恰好位于无人机与目标之间，或当障碍物紧密间隔时。有几种方法可以克服这个问题[II]。我们这里使用的解决方案是在局部极小区域中添加了一个假想的障碍物来驱除行进物体。

▲系统中的全局和局部极小

算法的伪代码：

▲潜航区域无人机路径规划的位场算法

算法的时间复杂度

位场算法需要评估配置空间中的力和算法的复杂度，常常是O（M^ D），其中M是计算空间中节点总数，D是空间的维数。该算法在机器人路径规划中的成功应用。

算法的结果与分析

考虑下面网格中的障碍物（黄色物体）和目标节点（蓝色物体）

▲带障碍物和空格的网格

用给定公式计算边界排斥力：

其中：

由3个障碍物推算的排斥力是：

如上图所示，我们计算了这个世界每个物体的中心坐标的g（x,y）。

因此，由每个障碍物产生的势能Pi为：

通过增加吸引力和排斥力计算的合力为：

因此，世界上每个物体的势能是：

上图中的箭头代表跟随机器人的路径。这里，我们所得到的路径是最短可能路径，而忽略了路径中的障碍。解决上述网格所需的时间为O（M^ 2）。

通过镶嵌过程，将整个区域划分为单元。在路径规划计算中考虑的唯一点是每个单元的中心。无人机仅限于从一个单元的中心到连接到无人机当前占据的单元的中心。虚拟对象被用来避免在区域中的局部极小陷阱。

总结

通过对位场算法的仿真研究，我们发现该算法具有合理的时间解，但它克服局部极小陷阱的性能差，且得到的不是最优结果。不同的场景可能产生不同的结果，因为算法难以在真实世界场景中执行。从结果可以清楚地看出，最优和计算时间要求之间存在折衷。在实际操作中，算法的选择需要基于运算要求的运算时间和最优性的平衡

参考文献

B. M. Sathyaraj, L. C. Jain, A. Finn and S. Drake, Multiple UAVs pathplanning algorithms: A comparative study, Fuzzy Optimization and Decision Making 7(3) (2008) 257–267.

[ii]N. Ernest, D. Carroll, C. Schumacher, M. Clark, K. Cohen and G. Lee, Genetic fuzzy based artificial intelligence for unmanned combat aerial vehicle control in simulated air combat missions, J. Def. Manag. 6(144) (2016) 2167–0374

[iii]N. Ahuja and J.-H. Chuang, Shape representation using a generalized potential field model, IEEE Trans. Pattern Anal. Mach. Intelli. 19(2) (1997) 169–176

Bibliography

Y. K. Hwang and N. Ahuja, A potential field approach to path planning, IEEE Trans. Robot. Autom. 8(1) (1992) 23–32.

Y. Koren and J. Borenstein, Potential field methods and their inherent limitations for mobile robot navigation, in Robotics and Automation,1991. Proc, 1991 IEEE Int. Conf. (IEEE, 1991), pp. 1398–1404.

Radmanesh, Mohammadreza & Kumar, Manish & H. Guentert, Paul & Sarim, Mohammad. (2018). Overview of Path Planning and Obstacle Avoidance Algorithms for UAVs: A Comparative Study. Unmanned Systems. 6. 1–24

Y. Koren and J. Borenstein, Potential field methods and their inherent limitations for mobile robot navigation, in Robotics and Automation, 1991. Proc, 1991 IEEE Int. Conf. (IEEE, 1991), pp. 1398– 1404. M. G. Park and M. C. Lee, A new technique to escape local minimum in artificial potential field based path planning, KSME Int. J. 17(12) (2003) 1876–1885.

G. Faria, R. A. F. Romero, E. Prestes and M. A. P. Idiart, Comparing harmonic functions and potential fields in the trajectory control of mobile robots, in Robotics, Automation and Mechatronics, 2004 IEEE Conf., Vol. 2 (IEEE, 2004), pp. 762–767

本文转载自AI研习社