基于CVT和模拟退火的多机器人均匀部署

严李平，吴玉秀，张文忠

（安徽工业大学 电气与信息工程学院，安徽 马鞍山 243032）

0 引 言

在灾害救援搜索，大面积环境监测，临时网络动态构建等方面，多机器人在空间的扩展性上较单个机器人有明显的优势。本文针对上述问题，对机器人均匀部署覆盖的问题进行研究。

涉及到多机器人覆盖在模拟图形区域，面临了如何分割图形使得每个机器人的覆盖面积一致以及如何分配多机器人到分割的区域的问题。对于图形分割，基于生成元的Voronoi 图分割，由于生成元的不确定性，导致图形分割的不均匀，每个机器人覆盖的面积不均匀，无法满足多机器人对图形的模拟。文献[3]中提到一种基于萤火虫群优化的传感器部署方案，扩大了传感器的覆盖范围，但区域冗余的可能性很大。文献[4]研究了基于投标的优化算法，提高了覆盖率且减少了重叠覆盖，文献[5]中调整传感半径，使相邻的两两传感器之间的重复覆盖减少。文献[6]采用了沃罗诺伊-萤火虫群优化-K-means 算法提高了网络覆盖率。本文借助传感网络覆盖的思想，采用质心Voronoi 划分对模拟的图形来对图形的覆盖。对于多机器人多任务分配是指用一种方案把多个任务分给多个机器人，以达到总的任务执行方案时间最短、消耗最少、任务完成度最高等目的。本文所需要考虑问题是机器人行走的总路程最少，类似于TSP 问题。文献[8]提到一种改进蚁群遗传算法，提高了TSP 问题的效率。文献[9]和文献[10]提出针对旅行商问题的改进交叉算子遗传算法，收敛度有一定提升，提高了遗传算法的效率和高质量的解。鉴于本文的要求，一个机器人只需要去完成一个任务，故将问题转化为背包限制的旅行商问题。如今，一个机器人完成一个任务的任务分配问题用得最多的就是拍卖算法。单物品拍卖算法具有局部最优解的窘境，对于组合优化问题并不适用，可改进为组合拍卖，这是一个NP 难题。故本文使用模拟退火算法来解决多机器人多目标优化问题。

本文的目标是实现多机器人在某个图形区域来完成均匀部署，首先通过采用质心Voronoi 来完成对目标区域的划分，得到部署点的位置，然后采用模拟退火方法，对这些部署点进行分配，使得多机器人到达每个部署点的总路程最近。

1 目标的生成

机器人要完成某一区域中均匀部署，首先需对此区域进行均匀划分。该处采用质心Voronoi 方法，将待部署区域的划分为多个小区域，每个小区域的质心即为机器人的目标位置。

1.1 Voronoi 图

Voronoi 图是基于Delauany 三角对于空间限定区域采用节点中垂线相连接方法组成的区域划分。在一个平面随机散（（1，2，…，））个点，对相邻两个点做中垂线，即可获取多个多边形，并且形状可能存在不一，这样使得各多边形均存在一个点，多边形中任意一点到形成这个多边形的点距离最近。如图1所示。

图1 泰森多边形

对一个平面图形，有如下公式：

1.2 质心Voronoi 图

“形心沃罗诺伊镶嵌法”用于实现形心沃罗诺伊图的原理，在计算上非常有效。这些图将任意维空间中任意形状的区域细分成任意数量的几乎均匀的子体积。

给定一个区域⊆R和这个区域的密度函数，则这个区域的质心公式如下：

当个生成元与其每个重合时，这样的Voronoi 划分称为质心Voronoi 划分，如图2所示。

图2 质心Voronoi 图

2 模拟退火算法任务分配

多机器人任务分配问题主要有四种情况：

（1）单目标机器人：一个机器人只能到达一个目标点。

（2）多目标机器人：一个机器人有多个需要到达的目标点。

（3）单机器人目标：一个目标点只需要一个机器人到达。

（4）多机器人目标：一个目标点可以由多机器人到达。

此处主要研究单目标机器人，机器人数量和任务数一样多，即每个机器人有且仅有一个任务（目标）需要执行。

2.1 任务的描述

假设机器人数量个集合为={，，…，R}，任务数量也为个={，，…，T}，此处的任务可以描述为：将个目标唯一的分配给个机器人，即上述分配问题可以用元置换π：{1，2，…，}→{1，2，…，}来表示，定义置换矩阵：

定义→执行任务的代价矩阵：

其中：C为机器人R到任务点T的欧式距离。令：

任务分配目标函数定义为：

2.2 模拟退火算法

2.2.1 爬山法

爬山算法是一种模仿爬山的过程，首先任意指定一个点上山，然后附近选择一个点，若这个点得到结果更优，即选择这个点为下个点，这样结果向着更优方向移动，直到山顶。若有多个山峰，爬山算法步入局部最优解，根据初始点位置可得是否获取全局最优解。若初始点在全局最优解临近，这样就可以获得最优解。

2.2.2 模拟退火

为防止爬山法陷入全局最优，Kirkpatrick 等提出了模拟退火算法（SA）。此此算法由Metropolis 算法和退火过程两个部分组成。Metropolis 算法（即Metropolis 准则）是描述一种以概率来接受新解的方法，它可以使解脱离局部最优的困境，是一种非完全确定准则。利用退火在初始进行扩展搜索，预防进入局部最优；而到了后期则需要扩大局部搜索，方便更快获取最优解。对本文的问题求解基本过程如下：

（1）对目标函数随机生成一个初始解，计算初始解的函数值（）；

（2）在初始解的附近需要对目标函数随机生成一个解，计算解的函数值（）；

（3）将（）、（）两个函数值进行比较，若（）＜（），则将解赋值给解，然后重复（2）步骤；若（）≥（），那么将计算接受的概率，的计算公式如下：

然后生成一个[0，1]之间的随机数，如果＜，就将解赋值给解，然后重复（2）的步骤，否则，不将解赋值给解，重复（2）步骤。

上述（3）中，Δ为|（）-（）|，T为衰减函数，T=αT-1 其中为常数，可以取值为0.5～0.99，它的取值决定了降温过程。

2.2.3 模拟退火新解产生的规则

根据目标函数及约束条件，生成一个随机初始解，然后在初始解附近产生一个新解，产生新解的规则有以下三种；

交换法：随机生成两个交换点的位置，互换这两个位置上的点。例：

解：7 8 6 |3 2 |5 4 1

新解：7 8 6 5 2 3 4 1

移位法：随机生成三个点的位置、、，将到之间的点包括和位置上的点放置到位置点后，如下：

解：7 |8 6 |3 2 5 |4 1

新解：7 2 5 4 8 6 3 1

倒置法：随机生成两个点的位置，这两点的位置形成一个区间，将这个区间里的点顺序调换，例：

解：7 8 |6 3 2 |5 4 1

新解：7 8 5 2 3 6 4 1

3 目标生成及分配的伪代码

本文的图形划分采用的是质心Voronoi 划分，采用模拟退火算法对目标点进行分配，目标生成的伪代码为：

▲Procedures CVT： 伪代码Begin initialize n,sample_num,r[],dim_num;//生成元数量，随机种子数，r[]//储生成元位置，维度get(n,sample_num);//获取生成元的初始位置及种子的位置while(i ＜= iterate) do distance();//计算种子到各个生成元位置的距离find（）； //每个种子找到离自己最近距离的生成元for j = 1 to n do r1(1:dim_num,j)=r2(1:dim_num,j)/count(j);//计算新生成元位置end for Update generator locationr[];//更新生成元位置end while voronoi(x,y);//画出质心voronoi end目标分配的伪代码为：▲Procedures SA： 伪代码begin initialize Path0,Distance0,T;//初始路径,距离及初始温度while(t ＜= maxgen) do //maxgen 为外循环的次数for i = 1 to LK do //LK 为内循环的次数Path1=gen_new_path(Path0);//生成新路径Path1 Distance1 of Path1;//计算新路径距离if＜Distance1＜Distance0＞ //判断新路径与初始路径的距离Path0=Path1； //得到下代路径Distance0=Distance1；else以一定概率接受新路径;end if end for Update temperature T;//更新当前温度if (T＜0.0001) //终止条件判断break；end if end while end

4 实验仿真与结果

4.1 算法验证

为了验证本文提出的算法，给出3 种不规则图形的部署区域如图3所示。在Matlab 环境中，分别用不同数量的机器人数量对图3（a）（b）和（c）中的“L”“T”和“Star”-形进行部署仿真。

图3 部署区域

对图形进行质心Voronoi 划分得到所需要的目标点，即任务点。如图4所示。

图4 质心Voronoi 分割图

图4为不同图形，不同节点的质心Voronoi 分割图，图4（a）、4（b）、4（c）分别为10、50、100 个点在“L”-形中的质心Voronoi 分割图，图4（d）、4（e）、4（f）分别为10、50、100 个点在“T”-形中的质心Voronoi 分割图，图4（g）、4（h）、4（i）分别为20、50、100 个点在“Star”-形中的质心Voronoi 分割图，每个质心点的位置就是机器人目标点的位置，通过模拟退火算法对机器人的目标点进行分配，得到平面上的多机器人到目标点的总路径。目标分配如图5所示。

图5中为不同图形，不同目标节点的分配图，图5（a）、5（b）、5（c）分别为10、50、100 个机器人分配到“L”-形中位置的图，图5（d）、5（e）、5（f）分别为10、50、100 个机器人分配到“T”-形中位置的图，图5（g）、5（h）、5（i）分别为20、50、100 个机器人分配到“Star”-形中位置的图。

图5 目标分配图

4.2 算法对比

在同样的机器人初始位置下，在Matlab 2017b 中运用遗传算法、模拟退火算法、单物品拍卖算法对图形目标点进行分配，得到路径距离数据，对这些数据进行处理，然后在Origin 2018 中对处理后的数据进行多Y 轴画图，如图6所示。

图6 “L”形-多Y 轴图

从图6、图7、图8中可以看到，横轴为机器人的数量，纵轴为机器人的路径长度。图6是三种算法机器人到“L”-形下的路径长度对比，当机器人数量为10、35、50、75、100时，模拟退火所得的平均路径长度波动分别为0、±0.000 9、±0.004 4、±0.013 6、±0.030 8；遗传算法所得的平均路径长度波动分别为±0.345 1、±2.815 6、±6.640 2、±6.582 0、±11.061 6；单物品拍卖算法平均路径长度无变化。图7是三种算法机器人到“T”-形下的路径长度对比，当机器人数量为10、35、50、75、100 时，模拟退火所得的平均路径长度波动分别为0、±0.008 8、±0.002 6、±0.046 8、±0.066 9；遗传算法所得的平均路径长度波动分别为±0.189 6、±0.499 6、±1.945 2、±2.811 3、±4.024 1；单物品拍卖算法平均路径长度无变化。图8是三种算法机器人到“star”-形下的路径长度对比，由于机器人的最小数量随着图形复杂度变大而增多，所以“star”-形的机器人最小数量选取为20，当机器人数量为20、35、50、75、100时，模拟退火所得的平均路径长度波动分别为0、±0.060 5、±0.180 2、±0.426 9、±0.824 2；遗传算法所得的平均路径长度波动分别为±6.150 7、±6.247 4、±11.539 9、±27.796 3、±37.342 4；单物品拍卖算法平均路径长度无变化。

图7 “T”形-多Y 轴图

图8 “star”形-多Y 轴图

在Matlab 2017b 中运用遗传算法、模拟退火算法、单物品拍卖算法对不同数量的机器人进行目标分配，收敛时间如表1所示。

表1 三种算法收敛速度表

上述表1可以看出，再任何机器人数量下遗传算法的收敛时间都要比模拟退火的收敛时间长。在机器人数量较少时，拍卖算法的收敛时间比模拟退火的收敛时间都较快，随着机器人数量的增加，拍卖算法的收敛时间比模拟退火的收敛时间要慢很多。

由路径长度和收敛时间的对比可得出：在相同机器人数量，相同初始位置下的机器人分配到同一个图形下，模拟退火算法和单物品拍卖得到的总路径长度比遗传算法得到的总路径长度要稳定，几乎没有方差，模拟退火算法在上述三个方法中得到了最短的总路径长度且收敛时间较短，避免了单物品拍卖和遗传算法可能得不到全局最优解的缺陷，较稳定。

5 结 论

本文采用了质心Voronoi 图划分出了所模拟图形目标点的位置，对于多机器人多目标分配，本文给出了以最短总路径为目标，以每个机器人有且仅有一个任务需要执行为约束条件的模型，且使用了三种算法对多机器人进行目标分配，让其单机器人执行单任务。通过对上述算法进行验证和对比，验证了模拟退火算法在求路径最短问题的优越性。本文后续的研究将围绕机器人的轨迹规划、跟踪和机器人之间的冲突消解展开。