在轨操控机器人拓邻域搜索三维路径规划

0 引 言

在轨操控机器人及在轨操控技术在未来大型航天装备建造、维护、升级过程中将扮演重要的角色。在任务过程中，机器人需要在复杂环境下自由移动，包括狭小空间的自由穿行，同时还需要保证移动和操控过程中与被操控对象的接触。因此，复杂环境下的三维全局路径规划成为实现移动和操控的前提和基础。

机器人路径规划一般包括空间环境建模和运动轨迹的生成、迭代与优化两部分。空间环境建模方法主要有两类：1)点云模型，即利用空间中离散的点云来描述空间环境的表面信息或者空间物体的坐标信息；2)地形几何模型，即利用正方形、矩形等规则形状或三角形、多边形等不规则形状作为模型单元构建空间环境模型。点云模型有较成熟的数据获取技术[1]，但一般用于物体表面信息的获取，其不能直观的表征物体的体积；以栅格地图为代表的地形几何模型又以二维模型为主，在地面路线规划上有着广泛的应用[2-3]。针对三维建模问题，文献[4-5]将点云数据转换成八叉树结构的三维栅格地图，用来描述空间被占据的情况。文献[6-7]则将多个二维栅格模型分层叠加，形成了三维高程模型。文献[8]在文献[6-7]基础上添加了悬浮障碍，以获取环境信息更为复杂的三维地图。但是，目前基于空间分层思想的建模方法无法解决复杂桁架结构或孔洞结构的环境建模和绕回路径规划问题。

在运动轨迹的生成、迭代与优化方面，国内外许多学者对此进行了大量的研究。目前，粒子群算法[9-10]、人工势场法[11]、A*算法[12]和蚁群算法[13-15]等是较为常用的三维空间路径规划算法。文献[9]采用粒子群算法针对自由漂浮空间机器人的关节角轨迹多项式插值系数进行优化，以实现机械臂关节角耗散能最小；文献[10]针对空间机械臂在轨迹规划过程中可能陷入局部最优的问题对粒子群算法进行了优化，同时将减小基座扰动和机械臂的运动时间作为优化指标的一部分，得到了满足减小基座姿态扰动及机械臂运动时间需求的空间机械臂轨迹。但是，以上两篇文献在规划的过程中都没有考虑空间环境障碍对机器人产生的约束。文献[11]针对采用人工势场法进行路径规划过程中的障碍可能会使路线陷入局部极值的问题，引入了一种细菌进化算法，得到了一种可以跳出局部极值的融合算法。但是，规划过程中未考虑环境特性，全局搜索步长相同，规划搜索效率仍有提升空间。文献[12]在二维栅格地图下基于地图的平面结构特征针对A*算法中参数和跳点规则进行了改进，提高了算法的效率并缩短了路径的长度。但是，转化到三维空间下之后会存在数据量级指数级增加的问题。文献[13-15]分别在不同的模型与工况下针对蚁群算法中的代价函数、信息素函数、概率选择函数等进行了改进，以达到适应不同任务的目的；文献[16-18]将不同的路径规划算法进行了仿真和对比，分析了各个算法在性能上的差异，三维空间中的路径规划问题得到了部分解决，但现有研究均未考虑到环境的空间结构特征并针对空间环境特性对算法进行改进，规划效率较低。

基于以上调研，本文开展了在轨操控机器人包含空间站桁架中穿行应用需求的三维全局路径规划问题研究。首先，采用三维单元栅格模型对桁架式空间站在轨操控空间环境以及机器人进行建模；其次，考虑穿行过程中的包络约束和操控过程中的附着要求，对三维栅格模型进行预处理，封闭不满足约束的空间，以减少路径搜索域提升路径搜索速度；再次，利用环境模型几何特征对搜索路径进行延拓，以调节搜索步长并利用拓邻域搜索的一群算法得到满足任务约束的最优或近似最优路径。最后通过仿真验证本文所提出算法的有效性。

1 空间环境和在轨操控机器人建模

1.1 环境模型

本文以国际空间站(International space station，ISS)为研究对象，对其结构特征进行提取并简化，并构建三维栅格地图环境模型。

在三维建模过程中，以空间站的对称轴作为栅格空间的方向坐标轴，综合考虑环境的复杂程度、在轨操控机器人的尺寸、任务需求等选取栅格单元的实际像素大小。本文选取了具有桁架结构特征的30×30×30栅格地图作为仿真的环境模型。对应的栅格地图如图1所示。

图1 ISS三维栅格模型
Fig.1 Three-dimensional raster model of the ISS

本文在算法验证和图形预处理过程中，将以图1中放大部分为例，具体的三视图如图2所示。

图2 三维栅格模型三视图(局部)
Fig.2 Three-view of three-dimensional raster model (part)

1.2 机器人模型

本文以某型空间操控机器人为研究对象，建立其刚球模型，即收缩状态下的最小外接球，以描述其在空间站桁架中穿行时的包络约束；选取空间操控机器人的自由操作空间描述操控任务的附着约束。

本文假定空间操控机器人刚球模型半径为rrb，其自由操作空间的半径为rfos。则在轨迹规划过程中同时满足包络约束和附着要求的几何约束可表示为：

rrb=rmin≤r≤rmax=rfos

(1)

其中:r为空间操控机器人刚球模型中心与障碍物的距离，rmin和rmax分别为满足要求情况下r的最大值和最小值。

2 预处理

由于r为空间操控机器人刚球模型中心与障碍物体的距离，可得：

r=po-prbc

(2)

式中：po为障碍的位置;prbc为刚球模型中心的位置。由式(1)(2)可以得到刚球模型中心位置的约束范围：

po-rfos≤prbc≤po-rrb

(3)

式(3)表明，机器人在运动过程中的刚球模型中心位置处于一个由障碍与自由操作空间半径和刚球模型半径共同决定的活动范围内。根据式(1)，将不满足该条件的空间进行封闭，由此得到约束下的机器人路径搜索可行域。

在三维路径规划过程中，机器人可搜索方向多，地图信息维度高，为避免搜索过程中数据爆炸，在运算前需要对这些包含地图属性信息的相关数据按照八叉树的规则进行储存和处理，具体如图3所示：

图3 数据预处理
Fig.3 Data preprocessing

该方法的具体处理规则如下：

1)将三维地图均匀切割分成八个部分，每次分割记为一次操作，一次操作在数据储存结构中占据一层；

2)选定分割后的子区域按照相同方法进行切割，直到最小分割单元满足路径规划最小像素单元精度要求；数据储存则按照切割次数分层，并依据其在每次分割中占据的位置进行编码、储存和调用。

3 蚁群算法

蚁群算法(Ant colony optimization, ACO)是仿效自然界中蚁群由巢穴出发的觅食行为，根据其在行走过程中分泌的信息素信息，获得最优路径的优化方法。ACO算法的原理主要是依据两个核心规则：可移动单元概率转移规则和信息素更新规则。

3.1 可移动单元概率转移规则

第k代的第m只蚂蚁从当前单元Pi移动到下一个单元Pj，首先需要确定下一步所有的可移动单元，并计算它们的转移概率，依据每个单元的概率从所有的可移动单元中随机选择一个作为下一个路径点。可移动单元转移概率如式(4)所示：

(4)

(5)

式中：表示第m只蚂蚁从Pi移动到Pj时的转移概率；τij(t)表示单元Pi到Pj的信息素浓度；ηij(t)表示单元Pi到Pj之间的启发式信息,取为单元Pi与Pj之间距离dij的倒数；α为信息启发因子；β为启发函数因子；Spm表示第m只蚂蚁在Pi单元处的下一步可移动单元集合。

4 信息素更新规则

在第m只蚂蚁从单元Pi移动到单元Pj之后，将对信息素浓度τij(t)进行更新，其目的是使蚂蚁已走过的信息素浓度减少，使后代蚂蚁有着选择其他路径的倾向，避免路径的解陷入局部最优。更新信息素浓度的公式如式(6)(7)所示：

(6)

(7)

式中：ρ(0<ρ<1)为信息素挥发系数;为第k代蚂蚁从单元Pi到单元Pj的信息素浓度增量;Q为信息素强度；Lk为第k代蚂蚁在本轮中搜索到的全局最优路径长度。

一般的，为了加快收敛速度，需要在转移概率之前对转移规则做预处理，如式(8)所示：

(8)

式中：参数q0(0<q0<1)为一个给定阈值，用以表征蚂蚁的探索能力，q(0<q<1)为一个随机生成的数。

为了表征算法的收敛速度，本文引入了收敛常数εk：

(9)

即第k代蚂蚁搜索到的最优路径长度Lk相较于初始路径长度Linit减少量Linit-Lk与算法稳定后路径长度Lsta相较于初始路径长度Linit减少量Linit-Lsta的比值，该值的取值范围为0≤εk≤1。相同代数条件下，εk越大，收敛速度越快；相同εk数值情况下，k值越小，算法收敛越快。

5 ACOBNCS算法

在三维空间的ACO算法中，蚂蚁的每一步可移动节点在无障碍情况下为26个，相较于二维空间无障碍情况的8个可移动节点要多，蚂蚁在选择路径的过程中，选择到最优路径的概率也相应的比二维空间要低，导致ACO算法规划的路径收敛性和平滑度较差。同时，三维空间下的信息素的数据规模也随着维度的增加而指数级增加，这个现象在大地图模型下变得更加明显，成为导致运算速度变慢的主要原因之一。针对上述问题，提出了一种基于空间约束的桁架式结构特殊节点搜索策略，在算法运行时，可以跳过某些桁架中大部分不需要计算的节点，仅计算桁架两端特殊的节点。

5.1 可移动单元集合搜索策略

假设蚂蚁的当前节点为Pi，下一步可移动单元集合为Spm，对于任意的Pj∈Spm，都满足以下的搜索规则：

1)Pi与Pj相邻或位于同一直线上。

2)Pj不为障碍且Pi与Pj之间也不存在障碍。

3)如果Pj与Pi不相邻，那么Pj在与Pi相连所在的直线上，且必与障碍相邻。

常规ACO算法在搜索时只考虑相邻的单元，并没有考虑到地图的特性，本文改进的第2)条规则与第3)条规则可以使当前节点所在轴线与障碍相邻的末端直接加入到可移动单元的集合当中去，直接跳过了该轴线上的搜索，即跳点。

ACOBNCS算法的搜索规则示意图如图4所示。图中倒立π字形斜纹单元为障碍单元，五角星单元为当前节点，竖条纹单元为ACO算法中下一步可以选择的所有单元的集合，即ACO算法搜索可行域，横条纹单元为ACOBNCS算法中在ACO搜索可行域基础上，额外拓展的搜索单元，即ACOBNCS附加可行域。与ACO算法的搜索策略相比，可以看出在搜索可移动单元时轴向方向增加了若干个备选的节点，可以很大程度上减少搜索迭代次数。搜索路径越长，效果就越明显。

图4 ACOBNCS示意图
Fig.4 Illustration of ACOBNCS

在桁架式结构中，有多个桁架相连的关节处，会成为在与节点相连桁架上的蚂蚁循迹过程中必经过的点，而在桁架两端关节之间的最优路径则是较为固定的。这些具有显著特征的节点就称为跳点。在某一区域的循迹过程中，如果蚂蚁需要经过这条桁架，那么必定会经过桁架两端的点，在其桁架上运动的路径就不需要进行重复运算。

ACOBNCS算法的算法流程如图5所示。

图5 ACOBNCS算法流程
Fig.5 Flowchart of ACOBNCS

6 仿真分析

本文利用Visual Studio 2019平台实现上述算法，计算机环境为Intel(R) Core(TM) i7-8700 CPU @ 3.20 GHz，内存32 GB，操作系统为Windows 10。分别对二维空间与三维空间下的ACO算法和ACOBNCS算法进行了对比仿真实验。实验中的蚁群算法相关参数见表1。

表1 算法参数设置
Table 1 Algorithm parameter setting

6.1 ACO算法二维地图与三维地图对比仿真

ACO算法在30×30的二维随机地图和30×30×30的三维地图仿真结果如图6所示。二维地图和三维地图仿真结果详细对比见表2。由其可知,随着每部迭代可移动节点数增加,迭代运算时间显著增加。

图6 二维随机地图仿真结果
Fig.6 Simulation results of 2D random map

表2 ACO算法两种维度地图下仿真数据对比
Table 2 Simulation of ACO on two different dimensional maps

图6和图7分别给出了30×30二维随机地图和30×30×30三维地图中最小路径长度随着迭代次数变化的曲线。在二维地图中，算法的收敛速度和稳定性较好。而在三维空间中，算法的收敛速度变慢，路径结果较差，存在较多转折点。随着维度的增加，算法中每一步的可移动节点数在无障碍情况下由8个变成了26个，依据概率选择公式得到最优路径的概率也随之变小，导致寻优路径的迭代次数变多。

图7 ACO算法最小路径长度变化曲线
Fig.7 Minimum path length curve of ACO

6.2 ACOBNCS算法三维地图仿真

ACOBNCS蚁群算法仿真结果如图8所示。

图8 ACOBNCS最小路径长度变化曲线
Fig.8 Minimum path length curve of ACOBNCS

图8和图9给出了利用ACOBNCS算进进行仿真的结果。与图7相比， ACOBNCS算法在迭代初期就有较大幅度收敛速度提升，在迭代57次时就达到了改进前最优路径的水平；最小路径长度缩短了29.23%；除此之外，迭代运算时间也大幅缩短，能在短时间内有效完成路径规划的任务。由表3可知，ACOBNCS算法较ACO算法性能上有大幅的提升。

图9 ACOBNCS仿真结果
Fig.9 Simulation results of ACOBNCS

表3 两种算法三维地图仿真数据对比
Table 3 Simulation results of two algorithms in 3D map

6.3 ACOBNCS算法有无跳点对比仿真

本文将ACOBNCS算法分别在有跳点和无跳点的情况下进行了20次重复试验，如图10和表4所示。从表4统计规律可以看出有跳点的ACOBNCS算法收敛速度有着明显的提升：收敛时的迭代次数平均减少了30.8次；k=100时的收敛常数ε100增加了0.1984；迭代运算的平均时间减少了3.65%，说明跳点规则可以有效的提升收敛速度；同时，ACOBNCS算法最小路径的平均长度较ACO方法增加了11.20%，说明ACOBNCS可能陷入局部最优。

表4 有无跳点的ACOBNCS算法重复试验仿真数据对比
Table 4 Simulation of the ACOBNCS with or without jump units

图10 ACOBNCS重复试验结果
Fig.10 Results of ACOBNCS repeat tests

6.4 ACOBNCS算法ISS栅格地图仿真

利用本文所提出的基于拓邻域搜索的在轨操控机器人三维路径规划算法，选定国际空间站上的某两点进行三维路径规划仿真，仿真结果如图11所示。

图11 ISS栅格模型上的路径规划结果
Fig.11 Path planning results on ISS 3D raster model

7 结 论

针对空间在轨操控机器人在桁架式空间站中三维空间路径规划时存在的问题，本文提出的拓邻域搜索蚁群算法可以满足在较短的时间内完成桁架间穿行且时刻与空间站保持接触的需求。本文采用三维栅格法建立了桁架式空间站障碍模型并建立机器人刚球中心可行域模型，对地图数据进行了预处理并基于邻域延拓思想改进了可移动单元的搜索策略，调节搜索步长以提高运算速度，能够有效的解决空间机器人执行在轨操控任务时的全局路径规划问题，提高了机器人路径规划的速度与全局搜索能力。