英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料

---

移动机器人路径规划的离散人工势场方法

A.Lazarowska *

lowast;波兰格丁尼亚格丁尼亚海事大学船舶自动化系（电子邮件：a.lazarowska@we.umg.edu.pl）.

摘要：本文介绍了一种用于自主移动机器人的路径规划方法，称为离散人工势场算法（DAPF）。该方法不同于目前应用的类似的路径规划方法，例如经典的APF方法，该方法采用吸引和排斥势场函数或波前算法。方该法的新颖性和独创性在于离散势场的构建，在算法的路径长度和运行时间方面考虑动态障碍并获得有效解决方案。DAPF算法能够在静态和动态环境中为移动机器人找到无碰撞的路径。本文还提出了路径优化算法（POA）。其目的是修改无碰撞路径，以获得更平滑，更短的路径。DAPF算法几乎实时运行，因此该方法可以在实际应用中使用。通过在MATLAB环境中的仿真以及使用四轮差动驱动的移动机器人的实际实验对算法进行了评估。将结果与基于蚁群优化的启发式方法进行了比较，证明了该方法的可行性和有效性。

1.介绍

自主导航是一个动态发展的研究领域。其原因是电子和自动化技术的发展。人工智能和计算智能领域的发展，以及相对容易和低成本地实现和测试新解决方案的可能性，导致科学界对这一研究领域相关的话题的兴趣日益浓厚。定位方法、遥感、路径规划、目标跟踪、障碍物映射、避免碰撞和路径跟踪是与自主机器人导航相关的一些主题。在上述所有主题中都可以看到快速发展。

自主导航领域的主题之一是路径规划。移动机器人的路径规划问题可以在两种常见的环境中考虑：静态和动态环境。静态环境是仅发生固定障碍物的区域，而在动态环境中，固定障碍物和移动障碍物均可发生。

由于导航工作空间的不同，路径规划方法的一种不同分类是将其划分为在已知和未知环境中应用的方法。 为解决可获得机器人周围环境的完整信息的已知环境的路径规划问题而开发的方法称为离线方法。在这种解决方案中，路径是在机器人开始移动之前计算的。另一种方法称为在线路径规划。在机器人的进近中，路径的计算是在机器人运动过程中逐步进行的，因为有关环境的信息是不完整的，并且在运动过程中会检测到障碍物。

路径规划方法也可以根据应用的优化方法进行分类，其中可以区分确定性算法、启发式算法和混合算法。在有关这一主题的文献中也可以找到精确和人工智能方法的分类。确定性方法的特征在于，使用相同的输入数据为每次计算运行返回相同的输出。精确算法是一种总是返回最优解的算法。当精确方法太慢或无法找到精确解时，启发式算法会在合理的时间内返回近似解。人工智能方法通过模仿人思维的某些功能或自然界中存在的智能行为来解决该问题。一些人工智能和启发式方法的局限性在于对于相同的输入数据缺乏对相同输入数据的解的可重复性。这是由于它们的工作原理，其中应用了基于概率的机制。路径规划中的一个相对较新的趋势是使用混合方法，将两种或两种以上的优化方法结合起来寻找路径。这样做的原因是要获得比单独使用方法更好的结果，并且利用每种方法的优势，通过与另一种方法结合使用来补偿特定方法的局限性。

路径规划方法用于许多不同应用领域的移动机器人的自主导航系统中，例如家用机器人、工业运输机器人、水下、地面和空中飞行器。

为了强调所提出方法的新颖性，分析了现有的类似路径规划方法，例如Qureshi和Ayaz（2016）提出的基于势函数的快速探索随机树星（P-RRT *）方法。Montiel等人提出的细菌势场算法。（2015年），Ni等人提出的虚拟力场算法。（2014年），由Kovacs等人开发的人工势场算法。（2016）和混合方法，结合使用人工免疫系统和Mingxin等人介绍的蚁群算法。（2010年）。有关不同路径规划方法的详细调查可以在Mac等人的文章中找到。 （2016）和Galceran和Carreras（2013）。

对不同路径规划方法的分析表明，某些方法可以处理简单的场景，但无法解决特定的复杂环境，而有些方法则缺乏可重复性或计算时间相对较长。目前的现状分析证实了在提出的科学问题范围内需要进一步研究。

本文介绍了一种新的移动机器人路径规划方法，该方法用于避免环境中发生固定和移动障碍。进行研究的主要目的是开发一种有效的方法，该方法可以近实时运行，并为不同的导航环境提供解决方案，因此适合在各种应用中使用。通过仿真试验和实际环境中的实验研究，确定了所提出的解决方案。

本文的主要贡献是：

bull;提出了一种新颖的搜索算法DAPF算法，作为在复杂静态和动态环境下具有接近实时操作能力的自主移动机器人的路径规划方法，可用于实际应用；

bull;为了改善无碰撞路径的平滑度和长度，引入了路径优化算法（POA）；

bull;提出了一种新颖的考虑动态障碍的方法；

bull;给出了仿真结果和实际实验结果，以验证DAPF算法的可行性；

本文的其余部分安排如下。在下一节中，将定义移动机器人路径规划问题。方法描述部分包含环境表示、路径规划算法和路径优化方法的说明，在此基础上，进行了仿真和实际实验研究。最后一部分是结论和未来的研究方向。

2.问题定义

移动机器人路径规划问题是解决从机器人的起始位置和目标位置之间寻找无碰撞路径的问题。机器人的路径是一条无碰撞的路径，它使机器人能够在起始位置和目标位置之间移动而不与任何障碍物相交。

机器人工作空间是一个二维工作空间W = R²，包含一个障碍区域O sub; W。该机器人被定义为A sub; W。然后将该工作空间转换为配置空间C。该配置空间包含障碍区域C_obs和可用空间C_free。它定义为C = C_free Cobs。配置空间的示例如图1所示。

图1.配置空间

图2.离散的配空间

障碍区域C_obs sube; C可以定义为C_obs = {qisin;C | A(q)cap;O ne; 0}，其中q isin;C是机器人A的配置，其中q =（xt，yt，theta;）; x和y是机器人位置的坐标，theta;是机器人方向LaValle（2006）。

可用空间C_free定义为C_free = C C_obs。q_S isin;C_free是初始机器人配置，q_G isin;C_free是目标机器人配置。

因此，可以将移动机器人路径规划问题定义为以下问题：找到路径p：[0，1] → C_free，使得p(0)= q_S且p(1)= q_G，其中将移动机器人视为配置空间中的质点。

为了解决上述问题，需要对连续配置空间进行分解。细胞分解法就是为了这个目的而使用的。离散配置空间的示例如图2所示。

3.方法说明

为了解决静态和动态环境下的移动机器人路径规划问题，提出了一种基于人工势场（APF）思想的移动机器人路径规划方法。APF中的概念是为离散配置空间定制的，并进行了调整，以实现快速有效的求解器。由于上述原因，新方法是离散人工势场（DAPF）启发算法。

3.1环境描述

将机器人导航环境建模为一个离散的二维构形空间。它是由n x m个单元组成的2D网格，其中n是水平单元（行）的数量，m是垂直单元（列）的数量，包括起始单元、目标单元、自由单元和被障碍物占据的单元。单元可能会被静态和动态障碍物占据。 考虑到移动机器人和障碍物的运动参数，计算动态障碍物所占据的单元的位置。首先检查机器人方向和障碍物方向之间的交点。如果检测到交叉点，则确定障碍物的位置。计算移动机器人将在交点处的时刻。然后，在该时刻确定障碍物的位置。

图3.具有标记单元的离散配置空间

3.2权重分配

权重分配是根据以下规则实现的：

bull;目标单元格G标记为值0；

bull;被障碍物占据的单元用一个值标记infin;；

bull;起始单元S标记为（n-1）x 10；

bull;根据方程式（1），用数值标记其他自由单元，其中x和y是单元坐标；

具有标记单元的配置空间的示例如图3所示。图4展示了具有权重分配的配置空间。

图4.一个离散的配置空间，其中单元已分配了权重

3.3 DAPF算法

算法1 DAPF算法

1：程序DAPF

2：建立离散的配置空间

3：初始化n，m，开始单元格（S），目标单元格（G）

4：标记被障碍物占据的单元格

5：根据等式（1）为单元分配权重

6：当前单元格=起始单元格

7：当当前单元格不等于目标单元格时

8：N当前单元格相邻单元格的集合

9：选择下一个单元格=分钟（相邻单元格N）

10：保存当前路径

11：为下一个单元格分配值

12：当前单元格=下一个单元格

13：结束

14：路径优化

15：路径的L长度

16：返回无碰撞路径

17：结束程序

DAPF算法的伪代码由算法1给出。从每个步骤中的起始单元开始，从相邻单元中选择权重最低的下一个单元。相邻的单元格是当前单元格周围的单元格，如图5所示。在那之后，下一个单元格成为当前单元格，并为其分配值infin;。应用此机制是为了防止在路径中生成环路。上述过程一直持续到到达目标单元为止。由DAPF算法计算出的无碰撞路径的示例如图6所示（用红色箭头标记）。

图5带有相邻单元格的当前单元格

图6 DAPF计算的无碰撞路径

图7.无冲突的优化路径

3.4路径优化

修改无碰撞路径以获得较短的路径。路径优化算法的伪代码如算法2所示。它的工作原理是基于迭代消除属于无碰撞路径的不必要单元，直到不能消除更多单元为止。如果连接单元k-1和单元k 1的路径跳过单元k不与障碍物相交，则单元k被消除。

路径像元是构成移动机器人路径上转折点的单元总数，min_-cells是构成无碰撞路径的最小单元数，i是当前考虑的节点（单元中心），p₁ =（x_i ，y_i）和p2 =（x_i 2，y_i 2）是检查连接可能性的节点，obs_-num是障碍总数，obs是当前考虑的障碍，j是当前考虑的障碍节点，p3 =（x_j，y_j）和p4 =（x_j 1，y_j 1）是当前考虑的障碍物边缘的节点，obs节点是形成当前考虑的障碍物边界的节点总数。如果当前考虑的节点之间的连接是可能的，则connect变量等于1，如果导致与障碍物相交，则等于0。

优化算法使用两个线段相交的验证。一个线段是障碍物的边缘，第二个线段将属于无碰撞路径的两个单元连接起来，以检查是否存在连接。 图7给出了优化的无碰撞路径的示例（由绿色箭头标记）。

算法2路径优化算法POA 1: procedure POA

2: i = 1

3: connect = 1

4: while path cells is greater than min cells do

5: obs = 1

6: connect nodes i and i 2 (p1 with p2)

7: while obs is less than or equal to obs num do

8: j = 1

9: while j is less than or equal to obs nodes

do

10: connect nodes j and j 1 (p3 with p4)

11: check (p1,p2) and (p3,p4) intersection

12: if (p1,p2) does not intersect 剩余内容已隐藏，支付完成后下载完整资料 资料编号：[239235]，资料为PDF文档或Word文档，PDF文档可免费转换为Word