近年来, 随着人工智能的发展, 多智能体系统(multi-agent system, MAS)作为其重要分支, 得到了广泛关注。由于多智能系统具有自治性、分布性、适应性、协作性、鲁棒性、灵活的扩展性等特点, 被广泛应用于无人机编队、传感器网络、协同监控等领域, 为大规模的复杂现实问题提供了更具效率的解决方案^[1-2]。灾难救援作为多智能体系统应用的典型代表, 具有救援规模庞大, 灾难现场路况复杂、次生灾害可能再次发生等诸多问题。因此, 用人工方式进行救援, 面临不确定性大、危险性高等难题。为了减少救援损失, 克服救援困难, 用智能体代替人工进行灾难救援已成为人们的共识。并且已有科研人员将单个机器人智能体应用在地震灾后救援和日本福岛核电站泄漏灾害中^[3]。由于灾后救援时间宝贵, 约束条件繁多, 单个智能体已不能完全满足救援要求。因此, 如何利用多智能体系统进行救灾便成为人们研究的主要课题。

灾难救援中的多智能体任务分配是主要的研究热点。对此, 国内外已经进行了大量研究, 并获得了一定的研究成果。其中, 文献[4]构建一种加权协作模型, 用以指导智能体选择合适的同伴进行协作救援。文献[5]使用一种改进的遗传算法, 将各智能体的任务集抽象成树状模型, 每次对最优解的任务进行选择, 保证关键任务得到优先解决。文献[6]采用基于合同网的拍卖模型, 智能体发现呼救信号时, 开辟拍卖市场, 发出招标, 其他智能体便进行投标, 中标后开始执行救援任务。使用拍卖算法, 能保证救援任务由一个或多个不同类型的最优智能体执行, 有利于智能体之间的任务协作。但灾难现场情况多变, 若通讯受阻, 时间紧急, 拍卖算法不仅用时长, 而且需要在招标者和投标者之间进行二次确认, 对远距离通信有较高要求, 往往容易发生信息丢失, 不利于救援的快速进行。

针对上述灾难救援中, 多智能体任务分配极其依赖通信、短时间搜救范围小的不足, 本文提出了一种基于ISODATA聚类分区的多智能任务分配策略, 将智能体优先分配到各自负责的区域完成救援任务, 降低通信要求, 扩大搜救范围, 以此提升救援的整体效果。

1 基于分区的多智能体任务分配策略1.1 聚类

聚类是将给定的规模巨大的一批数据, 通过一定的方法划分为聚类的过程。相似度较高的数据对象会聚集到同一聚类中, 而不同聚类之间的数据对象相似度很低。由于聚类方法简单有效, 已被广泛应用于数字图像处理、文本分析、多目标检测等领域。灾难救援过程中, 城市由不同的大大小小的建筑物组成, 每个建筑物占据一定面积, 拥有其中心点, 因此可以将建筑物抽象为二维地图的坐标点, 采用基于距离大小的相似性评价, 进行聚类划分, 将邻近的建筑物划分到同一分区中。

1.2 ISODATA聚类算法描述

ISODATA算法是一种无监督分类机器学习方法。和传统的K-means算法相比, ISODATA算法克服了K-means算法的不足, 不需要人为地指定聚类结果K的数值。它通过设置阈值参数、动态地进行类的合并或分裂, 自动调节聚类K的数目, 以迭代操作将样本数据划分为较为理想的聚类结果^[7]。ISODATA算法的流程如图 1所示。其中K表示预期聚类的数目, N_C表示当前形成的聚类数目。

1.3 ISODATA算法具体步骤

针对传统K-means聚类算法中的K值需要人为设定的不足, ISODATA算法通过调节阈值参数, 合理地进行聚类的合并分离, 进而形成合适的K值。同时, ISODATA算法聚类过程中的初始中心是随机选取, 对于大规模的地图数据, 初始中心的不同会造成不同的聚类结果, 同时也会影响聚类时间, 因此也需要确定初始聚类中心。改进的ISODATA算法的流程如下:

输入N个样本数据X{x_i∈R²|i=1, 2, 3, …, N}

Step1  自适应地选取N_C个初始聚类中心:

① 计算样本数据间的平均距离D, 根据交叉检验法则, 设定两个阈值参数, T₁=1.5D, T₂=3D;

② 在样本中, 任取一个点作为圆心O, 以T₁、T₂为半径作圆, 大圆内的数据分为一组, 同时将小圆内的数据从样本中剔除, 以此迭代地选择圆心O, 得到多个样本聚类。

③ 迭代完成后, 将会生成n个聚类, 并且可能出现重叠情况, 任意选择一个聚类S_j, 将其中心作为第一个聚类中心z₁, 接着选择离最远的聚类z₂, 继续选择离z₁、z₂最远的聚类中心z₃, 以此类推, 可选出N_C个初始聚类中心, 并将此值作为期望得到的聚类数目K。

Step2  设置相应阈值参数, 其中类内最小数据值是θ_N, 聚类间的最小距离为θ_C, 聚类中数据按距离分布的标准差为θ_S, 每次合并过程中最大聚类对数为L, 最大迭代次数为I。

Step3  计算每个样本数据到聚类中心的距离, 将样本分配给距离最近的聚类S_j, 即其距离为

(3)

Step4  若聚类S_j中的样本数目小于θ_N, 则该聚类不成立, N_C减1, 重新聚类;

Step5  计算聚类后的各项参数:

重新计算聚类中心

(4)

计算聚类内样本数据到聚类中心的平均距离

(5)

计算所有样本数据到相应中心的总平均距离

(6)

Step6  停止分裂和合并运算

① 若此次迭代数等于迭代次数阈值, 则转至Step7, 并将θ_C置0;

② 若N_c≤K/2, 即聚类数目过少, 则转至Step7;

③ 若N_c≥2K, 即聚类数目过多, 则转至Step9;

④ 若K/2≤N_c≤2K, 且当此次迭代是偶数次时, 转至Step9, 否则转至Step7;

Step7  根据距离值计算聚类中样本数据的标准差向量:σ_j=(σ_1j, σ_2j, …, σ_πj)^T, 其中向量分量为

(7)

式中, i代表样本特征向量的维数, j代表聚类的数目。并得到σ_j中的最大分量σ_jmax;

Step8  若σ_jmax大于θ_S, 并且满足以下条件之一:

① 且N_j>2(θ_N+1), 即聚类S_j中的样本数量比阈值高出一倍;

② N_c≤K/2;

则将z_j分裂成2个聚类, 且σ_jmax加1。2个新的聚类中心分别是在原z_j中相应于σ_jmax的分量加上和减去kσ_jmax, 其他分量不变, 其中0 < k≤1, 迭代次数加1, 并转至Step1。

Step9  计算聚类中心之间的距离

(8)

Step10  比较D_ij与θ_C, 并按递增顺序将D_ij < θ_C的值排列, 即得到数据{D_i1j1, D_i2j2, …, D_iLjL};

Step11  将相应的2类N_C和N_C进行合并, 并计算新的聚类中心, 且N_C减1。

(9)

Step12  若等于迭代阈值Ⅰ或者结果收敛, 即不再有合并分裂操作且聚类中心不再改变, 则算法结束。否则, 转至Step1, 且迭代次数加1, 继续聚类操作。

ISODATA算法克服了K-means算法K值的缺陷, 并且通过适当改进, 自适应地选择了初始聚类中心和阈值参数, 聚类速度更快, 聚类结果更合理, 因此, 本文采用基于ISODATA算法的多智能体任务分配策略。

1.4 基于ISODATA算法的多智能体任务分配

在灾难救援中, 救援任务由具有特定功能的智能体完成, 例如工兵负责清理障碍物, 医生负责救治伤员等。救援智能体需要对整个城市进行遍历搜救, 结合ISODATA算法, 设置阈值参数, 式中P为建筑物总数目, n为不同功能智能体队伍的平均数, L=20, I=10, θ_C设定为Step2所形成的聚类中心差值的平均值, θ_S设定为城市建筑与Step2形成的聚类中心的距离的总和S除以城市建筑的总数量。对不同功能的智能体计算其到每个聚类中心的距离D_j=min{||x-z_i||, i=1, 2, 3, …, N_c}, 将一队智能体分配到距离最近的聚类中去, 若该分区已经分配了同类智能体, 则将智能体分向次近的分区, 以此类推, 直到城市区域完全分配。分配完成后, 各队智能体使用A^*算法等最短路径搜索算法让智能体队伍快速移动到分区中心开始执行任务。若所有分区分配完成后, 还剩有智能体队伍, 则这些智能体队伍成为空闲智能体, 在城市中随机遍历开展救援任务, 同时随时响应其他智能体队伍的协助请求。

2 仿真实验2.1 仿真环境介绍

由于在实际环境中进行灾难发生后的多智能体任务分配研究有一定难度, 因此本文采用机器人救援仿真系统^[8](robo cup rescue simulation system, RCRSS), 一种通过计算机模拟发生地震后, 城市建筑物倒塌, 市民被废墟掩埋, 道路被障碍物阻塞, 城市发生火灾, 通信被破坏等真实灾难情况, 并通过警察智能体、消防智能体和救护智能体3类具有特殊功能的智能体进行灾难搜索、救援行动的灾难救援平台进行仿真实验。

图 2所示是一幅最基本的仿真测试地图。图中深灰色的多边形是建筑物、浅灰色的多边形是城市道路、道路上的黑色物体是道路障碍物、实心圆分别代表消防智能体、救护智能体、警察智能体。其中消防智能体负责灭火、警察智能体负责清理道路障碍物、救护智能体负责救治伤员、避难所负责接收伤员、补给能量。

测试地图中不同深浅的方块表示在燃烧或燃烧之后的建筑物。和真实世界一样, 建筑物在燃烧过程中有着不同的等级, 浇灭建筑物也会给其带来不同破坏。并且随着建筑物的燃烧, 温度会不断升高, 火势会向四周不断蔓延。不同深浅建筑物的具体含义如表 1所示。

2.2 实验

1) 针对ISODADA算法自适应性特点, 本文以RoboCup救援仿真平台的测试地图为例, 对建筑物进行了聚类操作, 样本数据为地图实际数据, 最后实验效果如图 2所示。

从测试地图中可以看出, 建筑物被分成了2个聚类。由实验效果可知, ISODATA算法自适应的选择了初始中心和期望聚类数目, 形成了2个合理的分区, 分区类的建筑物数量基本一致, 具有很好的自适应性。

2) RoboCup救援仿真平台中, 道路障碍物遍布整个城市, 警察智能体负责打通道路, 在越短时间内疏通城市道路, 越能给其它救援队伍创造救援时机, 因此警察智能体的任务分配是重中之重。实验以Kobe2013仿真环境为实验地图, 在自主编码的NPUbase代码上, 控制单一变量, 只存在15个警察智能体, 使用原未分区策略、K-means分区策略, 和ISODATA分区策略重复20次实验取每隔10周期的平均值, 警察智能体的清障效率对比如图 3所示。

实验中, 实际参数设定为, K=5, 11, 20, 警察智能体数量=15, L=5, θ_N=53, 即θ_N等于总建筑数除以警察智能体数量。

由图 3可知, 在仿真过程中, 原未分区分配任务的警察Agent清障效率始终低于基于分区的任务分配, 并且在最终清理掉的障碍物比例上远远低于2种基于分区的任务分配策略, 由此可见分区策略的有效性。在K-means算法中, 当K小于11时, 分区过大, 警察智能体之间的远距离通信障碍没有消除, 空闲智能体没有得到有效利用, 障碍物清理存在盲区。而当K大于11时, 分区过小, 警察智能体数量不足, 移动耗费大, 部分建筑群没有分配警察智能体, 障碍物清理不完全。而当K等于11时, 恰好将警察智能体分配到数量较为合理的建筑群中, 清理最高效。而使用ISODATA算法时, 虽并未手动指定K值, 但聚类的效果和K-means算法K值取11时大体一致, 因此可见使用ISODATA算法通过自主地合并或分离的建筑点形成了合理的聚类个数, 自适应性优于K-means算法。

3) 为了说明使用ISODATA算法的分区任务分配策略对整体救援效果的促进作用, 本文在原NPUbase策略上, 控制其他变量一致, 对警察智能体增加了基于ISODATA算法的分区任务分配策略, 并在Kobe2013仿真环境下进行了如图 4所示的实验对比。

在图 4中, 可以直观的看到使用基于ISODATA算法分区的任务分配策略烧毁的黑色建筑物明显少于未分区的原NPUbase策略, 控制住了火势的迅速蔓延。对比图 4a)和图 4b)可知, 后者的警察智能体在仿真环境中分布更广, 更分散, 将仿真环境中广泛分布道路障碍物清理得更干净, 保证了消防智能体能迅速并且畅通无阻地到达火灾现场进行火势的控制, 救护智能体能顺利进行伤员的救治, 促进了整体的救援仿真效果。

3 结论

针对在灾难救援过程中, 多智能体任务分配存在的问题, 本文提出了一种基于ISODATA聚类分区算法的优化方法, 通过分析总结传统聚类方法的不足, 使用ISODATA算法, 使之能自适应地计算初始聚类中心、期望聚类数目和重要的阈值参数, 控制其进行合理的分离和合并, 并对多智能体进行了静态、动态相结合的任务分配。实验结果表明, 该方法有效提升了仿真救援的效果, 对多智能体的任务分配有一定的推动作用。