通信距离约束下异构水下爬游机器人任务分配

刘雅丽，高立娥，李 乐，郭利伟，刘卫东

(西北工业大学 航海学院，西安 710072)

0 引言

水下爬游机器人具有爬行与巡游两种运动模式，它可以帮助或替代人类完成一些难度较高、危险的水下作业任务[1]。由于单个爬游机器人存在携带资源有限、获取和处理信息能力有限等问题，导致其在执行复杂多样的任务时遇到挑战，因此爬游机器人集群为完成水下复杂作业提供了一种有效途径[2-4]。多机器人任务分配(MRTA,multi robot task allocation)问题是集群协同作业的关键之一[5-7]。在多爬游机器人系统中，各爬游机器人之间通过信息交互、相互合作的方式完成水下作业任务。

目前，用于MRTA问题的算法主要有群体智能优化算法、市场拍卖算法、神经网络算法等。市场拍卖算法较群体智能优化算法而言计算简单，能够得到全局最优分配结果，但鲁棒性弱且对系统配置要求较高。群体智能优化算法包括粒子群算法、蚁群算法、遗传算法等。文献[8]引入资源均衡函数，采用粒子群蚁群混合算法求解了异构多AUV任务分配中资源配置问题。文献[9]提出了一种基于自组织映射(SOM)神经网络的双竞争策略算法能够较好地实现水下机器人之间的任务分配。文献[10]为了满足实时系统的约束条件，提出了一种混合最大最小蚁群优化算法(H-MMAS)。将H-MMAS进行扩展，引入局部搜索启发式算法，改进了任务分配算法。由于蚁群算法具备正反馈特点，全局搜索性较好。针对任务分配问题，本文采用蚁群优化算法进行求解。但是多水下爬游机器人执行任务时也存在着一系列的问题，如机器人之间水下通信问题、协调合作机制等[11-12]。本文针对通信问题研究了异构爬游机器人在通信距离约束条件下的任务分配情况。

可靠高效通信是多水下爬游机器人顺利完成任务必不可少的条件。就目前而言，以声波为载体的水声通信是实现水下通信的主要形式。由于水介质吸收声信号的特性，导致水声信道带宽窄[13]。通信质量与距离不可兼得，而且海洋环境噪声影响严重，所以水声通信的传输距离具有一定的限制。当多水下机器人中所有个体构成的通信图为非连通时，机器人获得不完整的信息会影响水下机器人的任务完成进度。为了减小通信环境对水下爬游机器人执行任务效率的影响，所以需要多水下爬游机器人之间时刻保持通信。针对弱水下通信环境多AUV任务分配问题，文献[14]建立了基于可变时延的多AUV任务分配框架，提出了通信中断情况下机器人应采取的策略。文献[2]针对无人艇USV的能耗和通信范围的两个关键问题,提出了一种新的能量协调方案和任务优先排序方法，完成了多USV系统的任务分配问题。文献[15]研究了有限通信下多AUV编队控制，提出了领导者编队模式。领导者与每个AUV建立单向通信来维持编队形成，大大降低了通信能耗。文献[16]研究了强化学习下的多AUV轨迹规划。由于AUV-到达最后一个路径点时需要将其现场样本发送到一个接入点，因此AUV必须至少在一个接入点的通信范围内。在此通信、运动学等约束下实现了多AUV轨迹规划。文献[17]研究了通过AUV，UAV，USV之间协作完成水下目标搜索跟踪任务。文中要求UAV与USV、USV与AUV之间的距离小于要求范围。以上文献从不同角度研究了弱水下通信情况下集群任务规划问题，却未保证执行任务时多水下机器人通信图能够时刻保持连通的问题。文献[18]研究了通信距离、角度等约束情况下的多无人机目标分配。文献[19]针对通信范围有限的多分散机器人任务分配问题，提出了基于STST (single-traveling-salesman tour)的分布式算法和RBA(rendezvous-based algorithm)集中式方法在有限航程距离内访问所有目标位置而不需考虑机器人通信范围。文献[20]设计观察到同一目标的两个机器人之间可以进行相互通信。在有限通信情况下研究了一组移动机器人对多运动目标跟踪问题。上述文献研究了无人机与陆上机器人的通信问题。水下的通信环境较空中的通信环境差，以上文献研究方法在应用于水下机器人集群时受到挑战。本文则针对多水下爬游机器人执行任务时通信距离受限的情况，使用互通与单通两种方法研究了距离约束条件，而且解决了多水下机器人通信图不连通的问题。在任意时刻，任意一个爬游机器人都可以与其他爬游机器人进行通信从而保证整个集群获得全局信息，提高任务完成效率。

本文主要研究通信距离约束条件下异构多水下爬游机器人的任务分配问题。在通信距离、航程等约束条件下，将爬游机器人的总航行距离作为评价任务分配优劣的准则，采用蚁群算法进行优化求解，最终解决了异构多水下爬游机器人的任务分配问题。

1 任务分配问题数学模型

1.1 问题描述

异构多水下爬游机器人任务分配问题是指由N个异构爬游机器人执行M个不同的任务，通过决定各爬游机器人完成任务的特定序列实现所给定目标函数最小。异构多水下爬游机器人任务分配可以建模为一个四元组{CR，task，C，f}。CR={CR1，CR2，…,CRN}表示爬游机器人集合。每个爬游机器人包含其位置，速度，最长运动时间，最大航程等基本信息。task={task1，task2，…,taskM}表示任务集合。每个任务应包含其位置，完成任务所需时间，任务类型等基本参数。C表示约束条件集合。f表示任务分配系统的目标函数，本文所考虑的目标函数为爬游机器人在完成任务的前提下所航行总距离最小。

1.2 目标函数

任务分配方案需要通过指标进行评价，本文所建立的任务分配模型将水下爬游机器人完成任务需要的总航行距离作为评价指标。所建立的目标函数如下所示：

(1)

其中：D(CRi)表示爬游机器人i的航行距离。

1.3 约束条件

任务分配时，异构多水下爬游机器人被分配不同的任务，为了可以实现总体效能值最优，建立的约束条件如下：

1.3.1 通信距离约束

多水下爬游机器人通过水声通信获取彼此间的位置、执行任务情况等信息。由于水声通信固有特性，而且爬游机器人的通信设备能力有限，导致爬游机器人的通信能力具有一定的限制，水下爬游机器人的通信范围如图1所示。为了保证爬游机器人在执行任务过程中一直可以进行信息交互，使用单通和互通两种不同方式建立以下通信约束条件。

图1 爬游机器人通信范围

(2)

其中：R(i,j)表示水下机器人i与机器人j是否可以通信。R(i,j)=1表示机器人j在机器人i的通信距离范围内即机器人i可以向机器人j发送信息。R(i,j)则相反。rc(i)为机器人i的最大通信距离。D(i,j)表示爬游机器人i与机器人j之间的距离。

1)互通:

为了减小通信环境对水下爬游机器人工作效率的影响，需要爬游机器人之间可以时刻保持通信，所以建立互通通信约束条件来满足爬游机器人的通信需求。任意时刻任意两个爬游机器人之间的距离小于最大通信范围时可以相互通信。设定在k(k=1,2,…,K)时刻多水下爬游机器人中任意一个机器人j(j=1,2,…,N且j≠i)在机器人i(i=1,2,…,N)的通信范围内,此时两个机器人可以实现互通。

∀i,∀j(j≠i)，R(i,j,k)=1,i=(1,2,...,N),

j=(1,2,...,N),k=(1,2,...,K)

(3)

k=t/Δt

(4)

其中：t为机器人运行时间，Δt为时间步长。

2)单通:

虽然互通情况下通信距离约束条件可以满足爬游机器人之间时刻保持通信的要求，但是任意两个爬游机器人之间距离都小于最大通信距离的约束性较强，所以考虑建立单通情况下通信距离约束条件。单通约束条件要求在任意时刻任意一个爬游机器人可以与其他爬游机器人中任意一个爬游机器人进行通信即可。为了保证机器人之间顺利通信，在k时刻，至少有一个机器人j位于机器人i的通信范围内。建立相应表达式如下：

∀i,∃j(j≠i),R(i,j,k)=1,i=(1,2,...,N),

j=(1,2,...,N),k=(1,2,...,K)

(5)

3)非连通通信图:

由于单通下的距离约束条件中可能出现部分水下爬游机器人出现局部孤立的情况，本文采用遍历搜索方法解决此问题。根据搜索路径，遍历搜索方法包括深度优先搜索算法与广度优先搜索算法。本文所采用的广度优先搜索算法是以广度优先的方式遍历整个图，使用队列来实现搜索，从树的根节点开始，沿其宽度遍历所有节点。

任意时刻k，广度优先算法多水下爬游机器人非连通图检测流程包括如下步骤：

设定访问标志Vlog(i)=1时表示第i节点已被访问，Vlog(i)=0表示该节点未被访问。

step 1：假设初始状态所有顶点均未被访问Vlog(i)=0；

step 2：任意选取一个节点V作为搜索的起点，遍历节点V的所有相邻节点，并将未被访问过的相邻节点放入缓存队列中，将已访问过的节点放入结果队列中。

step 3：取出丢弃缓存队列中的首位节点并访问其相邻节点，将未被访问的节点放入缓存队列中，将已访问过的节点放入结果队列中。

step 4：循环步骤step 3，直至缓存队列为空。

Step 5：判断结果队列是否遍历所有节点。如果存在Vlog(i)=0，则k时刻通信图为非连通图，即此刻出现了局部机器人通信的情况。

1.3.2 执行任务能力约束

一个水下爬游机器人同时只能执行一个任务。

(6)

其中：x(i,j)为1则表示爬游机器人i执行第j个任务，0则相反。

1.3.3 航程约束

每个水下爬游机器人所携带的资源和续航能力有限，可以维系航行的最远距离有限。为了避免出现完成任务前能源耗尽的情况，建立如下的约束条件：

maxD_CR(i)≥

(7)

其中：D(CRi,task1)表示水下爬游机器人i到它所执行第一个任务的距离，D(taskj,taskj+1)表示爬游机器人i所执行任务中第j个任务与第j+1个任务的距离，tempi表示爬游机器人i所执行任务的个数，maxD_CR(i)表示水下爬游机器人i的最大航行距离。

1.3.4 时间约束

由于水下爬游机器人最大工作时间有限，所以要求机器人完成任务的时间不可以超出最大工作时间，建立如下的约束条件：

maxT_CR(i)≥

(8)

(9)

T(taskj,taskj+1)=

(10)

其中：T(CRi,task1)表示爬游机器人i到它所执行第一个任务并完成此任务所需时间，T(taskj,taskj+1)表示爬游机器人i从任务j到达并完成下一任务的时间，maxT_CR(i)表示第i个爬游机器人的最长工作时间，V_CR(i)表示爬游机器人i的航行速度，T_task(j)表示完成任务j所需时间。

1.3.5 能力约束

单个水下爬游机器人能力有限，所以不同类型的任务需要特定的爬游机器人来执行，如采样任务需要带有机械臂的爬游机器人来执行，监测任务则要求执行此任务的爬游机器人带有摄像头。TK=[TK1,TK2,TK3]表示任务类型。TK1,TK2,TK3分别表示采样任务、监测任务、测扫任务，如TK=[1 0 0]表示该任务为采样任务。VK=[VK1,VK2,VK3]表示机器人类型。VK1,VK2,VK3则分别表示爬游机器人是否有机械臂、摄像头、侧扫声呐，如VK=[1 0 0]表示机器人只带有机械臂。为了保证爬游机器人可以成功完成不同类型的任务，爬游机器人i能够执行任务j必须满足的约束条件如下：

TKtaskj(l)≤VKCRi(l)l=1,2,3

(11)

综合上述所建立的约束条件及目标函数，以实现总航程最短的多水下爬游机器人任务分配。

2 基于蚁群算法的异构爬游机器人任务分配方法

2.1 蚁群算法基本原理

蚁群算法是由意大利学者M.Dorigo初次提出，它是一种模拟蚂蚁寻觅食物的优化算法。自然界蚂蚁起初选择路径具有随机性，当寻找到食物之后会向环境中释放一种具有挥发性的信息素。它们根据其浓度来获得路径远近的信息，进行协作、交流，通过信息素挥发、增强，最终找到一条最短路径。简单而言，蚁群算法便是通过计算状态转移概率选择下一个转移节点，从而逐渐走到终点，经过一次次迭代、信息素更新，最终找到一条从起点到终点的最短路径。蚁群算法的两个关键步骤为计算状态转移概率和更新信息素。

状态转移概率的计算与信息素浓度和启发式信息有关。状态转移概率的表达式：

(12)

其中:pij表示蚂蚁从节点i转移到下一节点j的概率。allowed为未被访问过的节点集合。τij表示节点i到节点j的信息素浓度值。α为信息素启发因子，表示在蚂蚁经过的路径上留下的信息素受重视的程度。β为期望启发因子，表示在转移节点时蚂蚁遗留下来的启发信息的重要程度。ηij则为启发函数，在本文选择爬游机器人与任务的距离的倒数作为启发函数。

更新信息素：蚁群算法完成一次循环之后要更新信息素的值。信息素更新表达式如下：

τij(t+1)=(1-ρ)τij(t)+Δτij(t+1)

(13)

(14)

ρ∈(0,1)为信息素挥发系数，代表信息素挥发程度。Q为常量，Lk为第k只蚂蚁完成搜索路线长度。

2.2 算法实现

本文使用蚁群算法求解通信距离约束条件下的异构机器人任务分配问题的流程如下。

Step1：初始化{CR1,CR2,...,CRn}、{task1,task2,...,taskm}位置、速度等信息以及蚁群算法相关参数，如蚂蚁数K，最大迭代次数NC_max、信息素启发因子α、期望启发因子β等。

step 2：forNC=1 toNC_max

step 3：fork=1 to K

step 4：为蚂蚁k随机选取未执行的任务；

step 5：由公式(7)计算，采用轮盘赌法为蚂蚁k选择下一节点；

step 6：更新禁忌表，将已访问的节点加入禁忌表；

step 7：end

step 8：If 满足通信距离、航程等约束条件 then

step 9：记录该次循环的最优路径；

step 10：end

step 11：按照公式(8)，更新信息素；

step 12：end

step 13：输出历史目标函数值最小的任务分配结果。

3 仿真实验与分析

针对异构多水下爬游机器人的任务分配问题，设置爬游机器人个数为N=5，任务个数为M=9。具体参数如表1、表2所示。蚁群优化算法参数设置为：NC_max=100、K=30、α=4、β=7、ρ=0.5、Q=100。使用MATLAB软件和蚁群算法工具包分别针对不同通信范围情况下单通和互通两种通信距离约束方法进行仿真验证及分析。

表1 任务参数设置

表2 爬游机器人参数设置

3.1 仿真实验一

为了验证互通与单通两种通信距离约束方法，设定爬游机器人最大通信距离rc为[500,600,500,500,600]米。

3.1.1 互通情况仿真结果及分析

针对互通情况下的通信约束，本节对多水下爬游机器人任务分配问题仿真求解得到任务分配结果和相应目标函数变化情况如图2和图3所示。

图2 互通情况下任务分配结果

图3 目标函数值变化情况

由图2的分配结果可知爬游机器人在执行任务具有顺序。由于任务1、4、6均带有采样任务，所以需要带有机械臂的爬游机器人来执行。任务3、8为测扫任务，需要带有侧扫声呐设备的机器人来执行。最终分配结果为CR1执行任务9，CR2执行任务序列为5-1，CR3执行任务7,CR5执行任务序列为8-3-6-2-4。在满足能力约束条件以及目标函数最小的要求下，最终CR4并未分配任务。由图3可知，当算法循环迭代22次之后收敛，目标函数取到最小值。在图2的任务分配结果下，多水下爬游机器人完成任务的总航行距离达到最小，最小值为1 929 m。在此任务分配结果下，爬游机器人在执行任务过程中的每一刻都可以保证与其他的爬游机器人进行通信，且多爬游机器人所运动的距离最短。

3.1.2 单通情况仿真结果与分析

针对单通情况下的通信约束，本节对多水下爬游机器人任务分配问题仿真求解得到任务分配结果和相应目标函数变化情况如图4和图5所示。

图4 单通情况下任务分配结果

图5 目标函数值变化情况

图4表示最终分配结果为CR1执行任务序列为9-2，CR2执行任务序列为5-1，CR3执行任务7，CR5执行任务序列为8-3-6-4。在满足能力约束条件以及目标函数最小的要求下，最终CR4并未分配任务。由图5可知，当算法循环迭代5次之后收敛，目标函数取到最小值1 917米，算法收敛速度快。

本节仿真验证了单通和互通两种通信距离约束方法都可以保证异构多水下爬游机器人顺利完成水下作业任务，并实现总航行距离最短的目标。

3.2 仿真实验二

为了比较互通与单通两种通信距离约束方法，设定爬游机器人最大通信距离rc为[250,300,250,250,300]米。

3.2.1 互通情况仿真结果与分析

针对爬游机器人最大通信范围较小时互通情况下的通信距离约束，本节对多水下爬游机器人任务分配问题仿真结果为无解。

3.2.2 单通情况仿真结果与分析

针对爬游机器人最大通信范围较小的单通情况下通信距离约束，本节对多水下爬游机器人任务分配问题仿真求解得到任务分配结果和相应目标函数变化情况如图6和图7所示。

图6 单通情况下任务分配结果

图7 目标函数值变化情况

图6表示最终分配结果为CR1执行任务序列为9，CR2执行任务序列为6-4，CR3执行任务2，CR4执行任务7，CR5执行任务序列为8-3-5-1。由图7可知，当算法循环迭代14次之后收敛，目标函数取到最小值2 251米。

本节进行爬游机器人最大通信范围较小时单通和互通两种情况下仿真实验。通过两种不同通信距离约束下多水下爬游机器人任务分配仿真实验结果可知，由于互通通信距离约束条件的约束性更强，互通通信距离约束下的任务分配无解，无法顺利进行任务分配，但单通通信距离约束下爬游机器人却可以顺利完成水下作业任务，单通通信距离约束的方法适用性更广。

4 结束语

本文针对水下爬游机器人能源携带有限，而且水下通信难、通信距离有限的问题，研究了通信距离等约束条件下的多爬游机器人任务分配问题。为了保证多水下爬游机器人可以顺利执行任务，建立通信距离、航程等约束条件，以多爬游机器人总航行距离为目标，构建异构多水下爬游机器人任务分配模型，利用蚁群优化算法进行求解。仿真实验结果表明本文所研究模型和算法的有效性。下一步工作将分析研究水下爬游机器人集群任务分配时降低能耗问题。