摘要：针对未知环境下的群体机器人形成聚集动态队形的问题，提出k-means聚类算法，将该算法与基于行为的控制相结合，使群体机器人形成聚集队形，减少机器人在聚集位置的抖动问题。引入四种适应度函数，提高机器人对未知环境的反应速度。个体机器人可根据局部感知自主产生队形控制向量。仿真实验表明了队形控制策略的可行性与有效性。
关键词：群体机器人 k-means聚类算法 聚集队形 行为控制
1引言
在自然界的众多群体中，如蜜蜂，鸟群、鱼群等不存在一个协调者来协调大量自主的个体，但他们在运动时普遍存在着编队行为，即他们形成某一集合形状或者在运动过程中保持一种相对不变的位置关系，从而使得这些动物能够联合起来更加有效地发现、围捕猎物和抵御捕食者，这对于它们的生存和繁衍具有重要的生物学意义[1]。人们受到自然界中生物的启发：如果群体机器人在执行任务的过程中保持某种队形，可以发挥较大的作用，其中聚集队形控制问题受到广泛的关注。
许多现有的机器人运动规划方法在某种程度上有一点相同，即机器人的运动都是通过对任务环境的完整或部分描述来规划并执行[2]，但是仍然未解决的问题是，当一群机器人无法得到环境信息，或者得到这些信息的代价太高时，如何使机器人朝着目的地进行的过程中，既遵守一定的队形约束，又要适应当前工作环境的约束的控制技术。
目前队形控制方法主要有基于行为法、基于leader的队形控制方法、虚拟结构法等[3]。这些方法侧重于使机器人严格的保持某种特定的几何形状，涉及的机器人数量通常较少，当机器人数量发生变化时需要对队形控制方法做出改进。
本文主要研究聚集队形控制策略，目的在于实现群体机器人系统在保持某一队形的前提下，对未知环境做出快速响应，且不限制机器人个体的位置。本文利用k-means聚类算法及四类适应度函数，实现了对大规模群体机器人的聚集队形控制，在奔向聚类中心的过程中避免机器人之间的碰撞，并且快速聚集形成队形完成任务。
2行为控制策略
在基于行为的控制中，基于行为的结构建立了机器人传感器与执行器的直接联系，实现了对未知环境的快速响应。群体机器人中每个机器人都装配有一圈等间隔分布的传感器，每个传感器都能够在其临域内探测是否有其他机器人存在，使机器人能够从局部环境中得到外部激励。每个机器人都有一个内建的强化学习（RL）机制，当遇到激励时，机器人首先从N个对象中选出k个对象作为聚类中心，并开始向中心移动。在机器人之间的相互作用下，机器人基于其行为权重向量的概率分布选择行为，每一个机器人在一个给定的时间内，其实际的步长依赖于最大的移动步长和最大的自由移动步长，而最大的自由移动步长由一个所选择方向上的最大的无冲突位移决定。在执行该行为之后，行为权重向量再进行函数更新。K-means聚类算法将产生一系列的空间位置，然后在四类适应度函数的作用下，评价这些位置，并且选择高适应度的位置来进行下一步进化。
3k-means聚类算法
k-means聚类就是将数据对象分组成为多个类或簇，在同一簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。在群体机器人控制中，机器人可以看做为基本粒子。首先从N个机器人对象中任意选取K个对象作为初始聚类中心，而对于所剩下的其他对象，根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类[4]。然后，再计算每个所获新机器人聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下：
2 （1）
其中系数E为群体机器人中所有对象的均方差之和；p代表对象的空间中的一个点；mi为机器人聚类Ci的均值（p和mi均是多维的）。
基于以上的工作过程，在群体机器人聚集运动所使用的标准K-means算法流程如下所述：
（1）随机初始化机器人Nc聚类的中心向量；
（2）对于每个向量，计算出机器人所属于的聚类类别对第j个聚类机器人中心点的距离；
（2）
（3）重新计算各个机器人聚类的中心向量；
（3）
（4）直到满足停止条件，否则跳转到2。
其中系数Nd代表输入维数，即每个向量的参数个数；No代表向量的个数；Nc代表群体机器人聚类中心点的个数——聚类堆数；Cj代表聚类j的数据向量子集。
通过（1）式产生标准测度函数开始收敛时，所有机器人与聚类中心的距离获得最小值。首先保证聚类中心的稳定，其次保证群体机器人各个聚类本身尽可能的紧凑，而各聚类之间尽可能是分开的。K-means算法的计算复杂度为O（nkt）,因而在处理群体机器人复杂问题是相对具有可扩展性的。这里n为对象个数，k为聚类个数，而t为循环次数。通常有K《n和t《n。
4聚集队形控制
本文中群体机器人保持近似圆形的聚集队形聚向目标区域，同时保证群体机器人中个体不相互碰撞，聚集队形控制策略中引入四类适应度函数。分别为contact、surround、chase、focus。
1）contact:发现目标行为，每个机器人都能够发现至少一个分部在空间中的机器人，适应度函数计算在时间t时机器人i与最近的机器人j之间的平均距离。MR与MW表示机器人i与机器人j的总数。函数dist计算机器人i与机器人j之间的距离。
（4）
（5）
2）surround：包围目标行为，每个机器人将至少被三个机器人包围，适应度函数计算在时间t时，机器人i与最近的k个机器人j之间的平均距离。函数 k计算k个最小距离。
（6）
（7）
3）chase：追击目标行为：每个机器人i朝着机器人j的位置移动，其中（d,k）表示机器人i在时间t移动的步长。
（8）
4）focus：聚焦目标行为，每个机器人着眼于学习一些具体的反应行为时，已达到至少发现一个分散在空间中的机器人。这里的 对应于在时间t内最常遇到的激励。 计算各个激励的行为权重之和。函数std计算权重和的标准差。
（9）
在聚集队形控制中，分布在空间的机器人稳定的处在一个分散式的空间分布的任务配置下，个体机器人通过选择最大权重的行为反应,确定他们的移动是有效地。聚类算法可以保证机器人之间有效地聚集，并且尽可能的保持一定距离[5]。目标机器人可以为机器人的搜索行为提供各种激励，因而很容易改进机器人个体的行为学习，在这种情形下,机器人的聚集行为具有良好的鲁棒性。
5仿真实验分析
个体机器人聚集队形控制算法的流程如下：
（1）感知局部环境。
（2）如果达到目标区域则终止，否则继续执行。
（3）用k-means算法确定聚集中心；计算contact产生的向量；计算surround产生的向量；计算chase产生的向量；计算与感知到的每个机器人之间的聚集向量，计算focus产生的向量；计算由外部激励产生的向量加权和。
（4）根据加权和设置机器人的转向角度及速度并执行。
（5）转到（1）。
根据个体机器人聚集队形控制算法流程可知，该算法计算量主要由步骤（3）决定，在步骤（3）中contact函数、surround函数、chase函数都与机器人总体个数N有关，因此个体机器人聚集控制与总体机器人个数有关。可见群体机器人数量与聚集队形控制策略的计算量间呈线性递增关系。
仿真实验将matlab7.10作为基础实验平台，如图所示为聚类运动的仿真全过程，图（1）为群体机器人以相当混乱的方式分布在空间中，首先随机分布在空间中的机器人随机确定一个聚类中心，并对聚类中心的外部激励快速做出响应，并朝该方向积极运动，再重新计算每个聚类的新质心，直到准则函数会聚。在机器人的聚类中心发生变化后，机器人可以立即奔向心的目标。这些分布式的机器人需要经过25次迭代以上才能隐现出一个有效的适应度函数的群体行为。随着集体运动策略的进化，机器人轨迹的运动逐渐变得光滑。迭代121次以后，机器人之间的协作开始明显，在聚类中心附近可以明显的看到机器人的聚集。225次之后，可以注意到机器人群体在目标位置附近产生了一个盘旋的运动。这是因为在许多所选择的高适应度个体中，合力排斥的方向可能并不直接指向目标位置。虽然有少量的震荡，但450次之后群体机器人适应度达到了新的高度，最终聚集为近似圆形的队形（见附图）。
（a）t=0秒 （b）t=25秒 （c）t=121秒
（d）t=225秒 （e）t=310秒 （f）t=450秒
附图 群体机器人适应度
5结束语
本文以群体机器人系统为背景，基于行为的控制为基础，结合K-means算法，实现群体机器人在未知、复杂环境中聚集队形的形成和保持。为了能够有效地完成聚集队形控制，防止机器人之间的相互碰撞，快速对外部激励做出反应。本文引入了四种行为函数：发现目标行为函数、包围目标行为函数、追击目标行为函数、聚焦目标行为函数。仿真实验说明了队形控制策略的有效性。
聚集队形采取分布式控制策略，每个机器人根据自己的局部感知生成自主策略，因此该控制策略具有良好的可扩展性，聚集队形控制策略具广泛的应用前景。在军事上合理的队形结构可以代替士兵执行恶劣，危险环境下的军事任务。在航空航天领域，群体机器人保持队形可以对未知区域进行探索，降低昂贵的费用。
作者简介
杨萍 女 博士/教授，长期致力于CAD/CAM、虚拟设计、机器人等方面的研究。
参考文献
[1]刘衍民.牛奔等.多目标优化问题的粒子群算法仿真研究[J].计算机应用研究，2011,2（28）：458-461.
[2]靳小龙，张世武.多智能体模型与实验[M].清华大学出版社，2003.
[3]谭民，王硕.多机器人系统[M].清华大学出版社，2005.
[4]段晓东，王存睿.粒子群算法及其应用[M].沈阳：辽宁大学出版社，2007.
[5]杨永明，田彦涛.基于社会势场的群体机器人聚集队形控制[J].系统仿真学报，2009,21(4):1106-1110.
[6]张奇丽，周亚丽.移动机器人运动规划的粒子群优化算法[J].北京信息科技大学学报，2009，4（24）：12—16.
[7]阳春华，莫志励.基于改进粒子群优化算法的约束多目标优化[J].计算机工程，2010，36（20）:203-207.
[8]John H R, Hongyan W. Social Potential Fields: A Distributed Behavioral Control for autonomous robots [J].Robotics and Autonomous Systems (S0921-8890),1999, 27(3):171-194.
[9]Balch T, Arkin R C. Behavior-based Formation Control for Multi-robot Teams [J].IEEE .Transactions on Robotics and Automation (S1552-3098), 1998, 14(6):1-15.
共0条 [查看全部] 网友评论