大数据支持下考虑障碍避让的机器人路径规划

张立铭

(佳木斯大学信息电子技术学院，黑龙江 佳木斯 154007)

1 引言

考虑障碍避让的机器人路径规划是指在具有障碍物的环境中快速、有效地搜索到一条从出发点到目标点的最短路径，并且在移动过程中机器人能够绕开所有障碍物抵达目标点[1]。在已知环境下，离线全局规划能够将这些问题完美的解决，同时还可以对机器人的部分性能进行优化。但是，在大多数的实际应用中，机器人的运行环境是未知的，依靠机器人自身仅能够探测到局部环境信息[2]。因此，在机器人移动过程中，需要借助障碍物感知及避障路径规划实现机器人的安全、高效移动。

目前，在机器人路径规划领域，已有学者提出了一些相对成熟的方法，如文献[3]中提出了一种基于改进传统人工势场法的机器人避障和路径规划方法。针对传统人工势场法存在的全景最大收敛问题，利用改进传统斥力函数优化传统的人工势场法，使得机器人在未达到目标点时的斥力函数小于机器人受到的引力函数，从而保障机器人顺利到达终点。然而该方法由于缺乏对路径的有效优化，导致机器人避障效果并不理想。文献[4]中提出了一种基于改进蚁群算法的移动机器人路径规划方法。该方法首先借助于栅格法的时效性对机器人运行环境进行模拟，并标记其中的每一个栅格，在此基础上使蚁群从初始栅格移动到目标栅格，实现初始路径搜索。基于此，以提高蚁群个体搜索的目的性及路径规划的时效性为目的，构造新的启发函数，通过挥发因子的自适应变化保证蚁群个体在全面地搜索路径的同时可以快速收敛，从而实现机器人路径规划。

针对传统方法中存在的最优路径规划效果差、规划时效性差的问题，本研究在大数据支持下提出了一种考虑障碍避让的机器人路径规划方法。该方法通过模拟蚂蚁觅食的过程来规划机器人的基础路径，并通过滚动窗口来优化机器人行进路径，进而规划出最优路径。仿真证明该方法在存在障碍物的情况下能够快速、高效规划出最优行进路径。

2 方法设计

2.1 问题描述

对于任意需要考虑障碍避让的二维地形，可将其中的障碍物表示成已知信息。路径规划的目的是为了使机器人经过起点gbegin，安全的避开场景中的各障碍物，然后沿着一条最短的路径到达终点gend。

假设机器人Rob在二维平面中的有限运动区域AS的半径为R，移动速度为vR，环境搜索与路径规划所需的时间可以忽略不计[5]。移动区域内部设有有限障碍物Db1，Db2，…，Dbq。

假设保证机器人能够自由运动的活动范围为[0，r]，在AS中组建系统的直角坐标系，依靠AS左下角来替代坐标零点，以X轴描述水平方向运动，以Y轴描述竖直方向运动，那么则存在AS在X，Y方向的最大值分别是xmax和ymax。以r为步长，分别对X、Y进行分割处理，从而组成一系列栅格，每行的栅格数为Nx=xmax/r，每列的栅格数是Ny=ymax/r。基于此，能够在AS边界补以障碍栅格，其中Dbi(i=1，2，…，q)可占一个或多个栅格。在一个栅格没有填满的情况下，也可将其算作一个栅格。该分化策略从使用开始就将现实环境转换成二维环境，机器人依靠规划完的路径可畅通无阻的抵达目标点。

假设g∈AS代表随机栅格，A={g1，g2，…，gm}代表AS内g的集合，H={h1，h2，…，hm}代表障碍栅格集，gm和hm都存在确准的位置，可描述为g(x，y){x=row，y=col}，其中，row代表g所处的行号，col代表g所处的列号。

令C={1，2，…，i，…，m}代表栅格序号集，根据上述设定，gi∈A的位置(xi，yi)和序号i∈C可以形成互为映射关系[6]，序号i的位置可以通过下列公式评定

(1)

其中，int 代表舍余取整计算，mod 代表求余计算。

将Rob在AS内的坐标描述为p，每一个p在AS都存在确准的位置(px，py)，t时刻Rob的坐标可描述为(px(t)，py(t))。

规划路径的起始坐标gbegin∈A，终止点坐标gend∈A为随机坐标，其它约束条件为begin，end∈C，end≠begin，gbegin与障碍物的距离

2.2 基于蚁群算法的路径规划

2.2.1 算法原理及参数定义

蚂蚁在搜索食物的过程中能够在所经过的路径上留下信息素，其它蚂蚁在搜索食物时能够探测到信息素的存在，并依靠信息素引导自己的运动轨迹[7]。通常，蚂蚁倾向于向着信息素密度较高的坐标移动。因此，大量蚂蚁组成的集体觅食行为代表了一种信息的正反馈现象，路径越短，那么该路径上的蚂蚁就越多，且存留的信息素程度就会越大，那么之后的蚂蚁就会有更大的几率继续选择该路径进行觅食，蚁群算法即模拟蚂蚁觅食行为的一种方法。

为了适应复杂的地形、提高搜索效率，利用两个蚂蚁集合共2m只蚂蚁共同完成对最优路径的搜索。其中，蚂蚁集合ant1的m只蚂蚁以gbegin代表蚁穴坐标，以gend代表事物源，蚂蚁集合ant2的m只蚂蚁则以gend代表蚁穴坐标，以gbegin代表食物源。两组蚂蚁相向搜索，共同完成路径规划。首先约定定义域：

1)anti={1，2，…，k，…，m}代表一种蚂蚁集合内每一种蚂蚁的集合(i=1，2)，k∈anti代表单独的蚂蚁，m代表第i蚂蚁集合的蚂蚁总量，τij(t)代表蚂蚁在t时刻残留在栅格gi、gj连线内的信息量。

2)如果g∈A且g∉H，则g代表可行节点，每一种可行节点集合能够被描述成可行域[8]，将其记作FS。如果g∈A且g∈H，那么将g描述成禁入节点，每一种禁入节点的集合叫做禁入域，将其记作NFS。

很明显，FS=A∩(H)c，NFS=A∩H，其中，上标c代表补集。

3)假设蚂蚁k随机时刻所在的坐标代表L，每一个L在AS都存在确准的位置(Lx，Ly)，k在ti时刻位于某栅格处的坐标为(Lx(ti)，Ly(ti))，简记成Li或L(ti)，如果其与g(x，y)∈A的位置相同，那么能够将Li和gi看作等价，将其描述成Li～gi。

4)随机栅格之间的尺寸指两栅格之间的连线尺寸，将其描述为d(gi，gj)或d(Li，Lj)，i，j∈C。通过运算式(2)，如果存在d(gi，gj)，满足|j-i|=1或|j-i|=Nx，则d(gi，gj)表示在AS内的两栅格之间的连线边。

d(gi，gh)=(xi-xj)2+(yi-yj)2

(2)

5)将BR描述为gi的邻域在gi坐标处的视野域[9]。

6)假设在t时刻，k所处的BR可行域中存在tabuk={L(t0)，L(t1)，…，L(ti)}，则其可代表k经t0至ti时刻已经过的栅格坐标集合。同时，tabuk也可看作为第k只蚂蚁已经通过目标位置的集合，其随着蚂蚁的移动情况进行实时调节，凭借蚁群算法的原理，这些位置就不允许再次行走，因此，将tabuk描述成禁忌表。

tabuk内任意两个坐标点在AS内的连线叫做P0至Pe的通道，将其描述成path(P0，Pe)，也可以通过path(P0，Pe)代表这条通道内的节点集合，通道的尺寸能够通过l进行表示，该尺寸由式(3)进行计算。

(3)

8)假设k1∈ant1，k2∈ant2，k1从gbegin开始，k2从gend开始。通过t个时刻，k1，k2的坐标分别是Pk1，Pk2，如果存在|d(Pk1，Pk2)|≤1，那么两只蚂蚁将会相遇，该条件就会别描述成|d(Pk1，Pk2)|≤1。

2.2.2 算法流程设计

假如机器人Rob在时刻ti位于gi坐标，那么下一步需要经过的栅格则是BR里的任一可行点[10]。因此，蚂蚁从当前节点gi选取下一个节点时，只需要在BR里挑选gj即可。具体流程如下：

1)起始化：把m只蚂蚁放在出发点gbegin处，同时拟定至禁忌表tabuk，使τij(0)=0。

2)以当前节点gi∈FS当做中心，i∈C，凭借两个集合蚂蚁的相向趋近原理与最近邻居选择策略挑选下一节点gj[11]，并移动至下一个节点gj。此时，同时存在gj∈tabuk，gj∉tabuk，节点挑选过程如下：

如果gi∉BR(gbegin)，则可凭借下式挑选下一个节点，那么gj∉tabuk。

(4)

2.3 确定局部子目标

在局部规划内，因不能够判定全局目标Pgoal是否处于机器人的滚动窗口里，因此需要挑选局部规划的子目标，从而将其描述为Pgoal在滚动窗口里的映射。

假设在t时刻，Rob的滚动窗口是Win(PR(t))，如果Pgoal∈Win(PR(t))，那么取Psub(t)=Pgoal。反之则使用启发式函数f(P)=g(P)+h(P)来选取使f(P)最小的窗口边界点P作为子目标Psub(t)。

2.4 场景预测

假设Z代表t时刻的滚动窗口里能够所搜到的障碍物集合，设定Rob在某刻t会依据规划路径FS(PRPf)从出发点PR移动到目标点Pf。tp表示机器人移动到目标位置所需的时间，其也可以被称作为预测时域[12]，O表示机器人移动路径在滚动窗口DW内t时间段种所覆盖的范围，则t时刻在滚动窗口里预测的可行域为

(5)

即可用WFD(t)表示考虑障碍避让的机器人路径规划结果。

与此同时，针对不同的避让问题，需要进行二次预测，即依据已知的信息设定对应的路径规划方法。机器人移动的每一步都需凭借局部规划算法在窗口里预测的可行域内规划出可行路径，同时依靠路径完成定向移动。

3 仿真证明

为检验大数据支持下考虑障碍避让的机器人路径规划方法的应用性能，设计如下仿真加以验证。仿真在MATLAB 9.1环境下完成。为有效突出本文方法的规划效果，将传统的基于改进传统人工势场法的机器人避障和路径规划方法、基于改进蚁群算法的移动机器人路径规划方法作为对比，共同完成仿真验证。

测试范围为250m×250m，障碍物分布情况如图1所示，机器人移动起点为(0，0)，终点为(250，250)。

图1 预设障碍物分布图

根据图1，分别利用本文方法、基于改进传统人工势场法的规划方法、基于改进蚁群算法的规划方法规划机器人避障路线。不同方法下机器人运行路线如图2所示。

图2 不同方法规划路径图

根据图2可知，应用本文方法后，机器人的移动路径准确避开了各障碍物所在位置。应用基于改进传统人工势场法的规划方法后，机器人虽也能有效躲避障碍物，但运行路径明显长于本文方法。而应用基于改进蚁群算法的规划方法后，机器人对小规模障碍物的识别和躲避效果不好，难以及时避障。由此可以证明本文方法能够保证机器人对障碍物进行准确感知，避障路径规划合理。

为进一验证本文方法的工作效率，统计对比不同路径规划方法下障碍物信息传输用时，结果如表1所示。

表1 障碍物信息传输用时对比(ms)

分析表1可知，随着实验次数的不断增加，不同路径规划方法的障碍物信息传输用时也在不断变化。两种对比方法的障碍物信息传输用时均在2000ms以上，相比之下，本文方法的障碍物信息传输用时最低，维持在1500ms上下，证明本文方法能够快速实现对障碍物信息的感知与传输，为障碍物避让和路线规划奠定了基础。

4 结束语

为使机器人在未知且存在障碍的环境内可以成功的规划最优避障路径，本文利用大数据技术设计了考虑障碍避让的机器人路径规划方法，并通过仿真证明了该方法能够有效规划出最优避障路径，且规划效率高，表明该方法具有较强的实用性能。