群体机器人同步问题的分布式协同控制及优化

杨 茂，李成凤，田彦涛，2

(1.吉林大学通信工程学院，吉林长春 130025;2.吉林大学工程仿生教育部重点实验室，吉林长春 130025)

群体机器人同步问题的分布式协同控制及优化

杨 茂1，李成凤1，田彦涛1，2

(1.吉林大学通信工程学院，吉林长春 130025;2.吉林大学工程仿生教育部重点实验室，吉林长春 130025)

主要研究群体机器人系统协同适应性，通过局部信息交互下的分布式控制实现群体对复杂环境的适应.以同步现象为研究对象，结合虚拟力、最近邻居原则以及环境因素，提出了一种可以解释该现象的分布式控制器.并证明该控制器能够使所有的群体成员在误差允许的范围内收敛到一个共同速度，其优点是仅需要局部信息就能够实现稳定的群体行为.此外，在上述分布式控制器设计的基础上进行了参数优化，利用粒子群优化算法实现能量消耗最少的目标.通过仿真实验验证了控制器及算法的可行性和有效性.

群体机器人;同步;协同控制;分布式控制器;粒子群优化算法

在众多生物群体中，如编队迁徙的鸟群、结队巡游的鱼群、协同工作的蚁群、聚集而生的细菌菌落等，不存在协调者来协调大量自主个体，但整个系统却呈现协调有序的状态.这使生物群体在觅食生存、逃避天敌等方面获得单独个体难以实现的优势，完成复杂、有一定目的或功能的活动［1］.群体机器人学受社会性昆虫及群居动物群体行为的启发，主要研究如何使大量相对简单的机器人通过局部交互，涌现出智能群体行为.如何制定一定的规则，从系统论与控制学的观点出发解释这些现象，并对控制器参数进行优化，可能对相关工程应用有潜在效益.

1986年C.W.Reynolds在文献［2］中建立了一个协调运动的行为模型.他将模拟的通用实体命名为“boids”，并且他的工作开启了计算机图形学中一个名为“人工生命”的新的研究课题.文献［3］中Vicsek等人提出了基于最近邻居原则的仿真模型，仿真结果表明所有粒子的速度能够收敛到一个共同的值.尽管是分别提出的，但Vicsek模型是boids模型的一个特例.为了从数学上证明Vicsek的结果，Jadbabaie等人［4］提出了离散的运动学模型和依据最近邻居原则的分布式控制器.他们使用了一些源自代数图论的概念证明所有个体速度的收敛性，在他们后续的工作中［5－7］，对于固定的和动态的群体拓扑结构提出了一个连续的动态模型和一个分布式控制器.控制器包括基于最近邻居的状态的航向和速度调节成分，通过代数图论和不连续稳定性理论，证明控制器能够引导所有机器人的航向收敛到一个公共值，并且所有的速度收敛到相同的值.Gazi和Passino［8］提出了群体成员的一个连续的一阶运动学模型，并且运用虚拟作用的观点提出用于分析n维空间中群体集聚的分布式控制器.文献［8］表明个体能够在有限的时间内形成内聚群体，并且其中也得到了群体大小的一个明确约束.文献［9］中一类更广泛的虚拟力函数是文献［8］结论的扩展.在其后续工作中［10－12］，使用相同的方法证明了在某种特定环境中群体聚集行为的存在性.Liu等人［12］利用一个二阶动力学模型来研究在某种具有噪声的特定环境下的稳定的群体觅食行为.然而，文献［8－13］提出的所有控制器要求每个机器人知道所有其他机器人的状态，这对于自然生物是不可能的.文献［14］中Reif和Wang首先提出了超大规模机器人系统(very large scale robotic system)的概念，并提出一种使用人工势场(artificial potential field)作为控制律的分布式控制方案.但是以上控制方法仅限于全局交互机制或者是无环境信息反馈的情况，且均未考虑控制器性能参数的优化问题.本文针对群体机器人系统在复杂环境下的同步问题，利用邻接矩阵的方法，设计了基于局部信息交互的分布式控制器，并进行了群体稳定性分析，证明了该控制器无论是在切换拓扑还是固定拓扑关系下都能够使得系统中的所有个体在环境信息反馈下实现同步.同时还对控制器进行了参数优化，以实现能量优化的目标.

1 分布式协同控制

1.1 群体机器人系统的协同适应性

群体机器人系统是一类特殊的多机器人系统，其特殊性体现在如下几方面:首先，在控制方式方面，多机器人系统可以是集中控制也可以是分布式控制，而群体机器人系统一定是分布式控制;其次，在系统规模方面，多机器人系统一般个体数量较少，而群体机器人系统数量很多;再次，在个体能力方面，多机器人系统中的个体一般较为复杂，而群体机器人系统的个体相对简单;最后也是最重要的，在通信机制方面，多机器人系统一般是全局通信，而群体机器人系统是以局部通信为主要特征.以上特征决定了群体机器人系统具有鲁棒性、可扩展性和适应性等特点.

本文首次提出了群体机器人系统的协同适应性的概念.

定义复杂动态环境中，机器人如何通过个体与个体之间以及个体与环境之间的交互，优化控制策略并调整自身行为，以适应环境和任务的动态变化的特性叫做群体机器人系统的协同适应性.

具体地从数学上可以描述为:

设群体机器人系统中有N个机器人，r为机器人邻居半径;令ε(i，t)为第i个机器人在时间t时刻的局部环境状态(i=1，2，…，N); ξ(i，t)为第i个机器人在时间t时刻其他邻居机器人反馈的状态信息;ω为满足运动及环境约束的机器人动作集合;η(t)对应t时刻的群体行为;E(η)表示对于群体行为的性能评估;V为群体机器人系统集体任务性能标准.则群体机器人系统为

协同适应性的目的是max(E)(或min(E)).

同步问题是群体机器人系统的研究中的经典问题之一，是多机器人利用分布式感知能力通过控制器的作用最终达到速度(包含速率与方向)一致，该控制器通常是分布式控制器.而在实体机器人中，机器人通常依靠电池提供能量，其运行往往受限于电池容量，因此如何有效地使用有限的电池能量，对提高机器人的续航能力至关重要.这对于大量个体能量消耗问题尤为突出，因此，将优化技术应用群体机器人中是具有理论意义和实际工程价值的.

1.2 群体模型

考虑在n维空间中运动的机器人群体，假设个体同时运动并视为质点，个体之间无通信延迟.对个体建模如下:

式中:i=1，2，…，N，xi∈Rn、vi∈Rn、mi和ui分别是机器人i的位置、速度、质量和控制输入.假设没有扰动力作用在个体上，且mi已知.显然，式(1)为典型的拉格朗日动态模型.

1.3 局部信息交互机制与机器人环境感知

如果满足‖xi－xj‖≤d0，称2个不同机器人i和j(i≠j)为彼此的邻居，其中d0是给定的正数，通常由机器人的通信范围决定.i≜{j:‖xi－xj‖≤d0，j≠i，j=1，2，…，N}代表机器人i所有邻居的集合.

可见，机器人的邻域结构是运动空间中分布的圆，半径等于机器人的通信半径，见图1.若机器人的通信距离与运动空间相比足够大，局部信息交互将会演化为全局交互.

图1 机器人的邻域结构Fig.1 Robots’neighborhood

为简化群体速度收敛的证明，本文运用代数图论中邻接矩阵来代表机器人的邻居.对于机器人数目为N的群体，定义邻接矩阵A=［aij］N×N，其中

假设群体在具有特定势能函数ρ(x)的环境中运动，并且此函数具有有限斜率，即ρ(x)在xi的梯度(ρ(x))已知，通过在生物系统中的观察可以证明此假设是正确的.

1.4 控制器设计及稳定性分析

对每个机器人提出分布式控制器如下:

式中:kp、kv和kr是给定的正常数，g:Rn→Rn代表个体之间的吸引排斥函数.

函数g(·)的类型为

式中:ga:R+→R+代表吸引项的大小，gr:R+→R+代表排斥项的大小.以向量y为例，所以实际的吸引、排斥分别是－yga‖y‖和ygr‖y‖，假设g(·)满足下列条件:

1)g(·)是一个在相反方向运动的吸引排斥项的奇函数，也就是，g(y)=－g(－y).

2)存在惟一的距离δ使得ga(δ)=gr(δ).此外，

3)存在相应的函数Ja:R+→R+和Jr:R+→R+，使得▽yJa(‖y‖)=yga‖y‖，▽yJr(‖y‖)=ygr‖y‖.

假设条件1)、2)、3)是由 Gazi和 Passino介绍的［15］.本文考虑吸引排斥函数由线性吸引项和有界排斥项组成:

式中:a、b是给定的正常数.

假设群体在对每个机器人产生相同作用的一致性环境中运动，即ρ(x)= ▽xjρ(x)，∀i≠j，从而有 －

并且定义误差状态为=xi－=vi－，则有

定理对于如式(1)所示的群体机器人系统数学模型，若吸引排斥函数如式(4)所示，那么当t→∞时，vi→¯，所有个体将收敛到一个超球()={x:‖x－‖≤δ})，式中:

因为对任意矩阵S=ST＞0和向量x，有λmin(S)xT·x≤xTx≤xTSx≤λmax(S)xTx，其中 λmin(S)和λmax(S)分别代表S的最小和最大的特征值.并由式(2)定义的邻接矩阵AN×N得

式中:d=max{‖xi－xj‖|i=1，2，…，N;j=1，2，…，N}.所以对于一致性环境有

推论群体同步收敛所需时间可估计，即

从上述函数中计算出时间:

注意上述证明是在没有任何关于群体拓扑结构的特定条件下进行的，即无论拓扑结构是固定的还是变化的，该分布式控制器都能够实现稳定的群体同步运动.

2优化

2.1 粒子群优化算法

PSO算法随机地初始化为目标函数的一个解群体，群体中的每个个体称为一个粒子.每个粒子模仿鸟类的觅食行为，通过跟踪2个“极值”来实现在搜索空间寻找最优解的目的:一个是每个粒子当前已搜索到的最优位置(适应度最大)，称为个体极值Pbest;另一个是整个粒子群当前已搜索到的最优位置，称为全局极值Gbest.PSO算法可描述如下:假设在D维搜索空间有m个粒子，粒子i在搜索空间的位置用向量Xi=［xi1xi2…xiD］T表示，其个体极值记为Pi=［pi1pi2…piD］T，而全局极值记为Pg=［pg1pg2…pgD］T.在迭代过程中，粒子i以速度v在搜索空间飞行.每个粒子的飞行速度及位置按下式进行修正:

式中:c1、c2为正常数，称为加速因子，通常取c1=c2=2.0;r1，r2为［0，1］之间的随机数;w为惯性因子.在迭代过程中，粒子的速度向量被限制在［－Vmax，Vmax］范围内，以降低例子飞出搜索空间的概率;而粒子的位置向量被限制在［Xmin，Xman］范围内.

2.2 优化问题描述

3 仿真实验与结果分析

3.1 稳定的群体同步仿真实验结果与分析

在仿真中，假设所有群体成员同构并且质量已知.本文选择设计常数为kp=3.5，kv=2.3，kr=2.0，d0=10.随机给定机器人的初始速度，在［－10，10］内随机给定初始位置.在下述图形中星形和圆形分别代表机器人的初始位置和最终位置.

图2和图3分别显示机器人个数为10个的群体在二维空间中的运动轨迹和速度收敛曲线，可以看出群体中所有机器人收敛到一个相同的速度，并且它们的间隔几乎保持为常数，实现了稳定的群体同步行为.

图2 二维空间中机器人的运动轨迹(N=10)Fig.2 Robots’trajectories in 2－D environment(N=10)

图3 二维空间中机器人的速度(N=10)Fig.3 Robots’velocity in 2－D environment(N=10)

图4和图5分别显示机器人个数为100的群体在二维空间中的运动轨迹和速度曲线，群体的速度仍收敛，机器人间的间距仍基本恒定.此外，图2和图4所具有的环境信息不同，即初始化的环境梯度方向相反，因此机器人的运动方向也相反.

图4 二维空间中机器人的运动轨迹(N=100)Fig.4 Robots’trajectories in 2－D environment(N=100)

图5 二维空间中机器人的速度(N=100)Fig.5 Robots’velocity in 3－D environment(N=100)

图6 三维空间中机器人的运动轨迹(N=15)Fig.6 Robots’trajectories in 3－D environment(N=15)

图7 三维空间中机器人的速度(N=15)Fig.7 Robots’velocity in 3－D environment(N=15)

图6和图7分别是群体机器人(数量为15个)在三维空间中的运动轨迹和速度变化曲线，同样，群体仍然能够达到速度收敛和保持恒定间距的目的.

表1是群体机器人系统中每个个体运动角度随时间变化情况(即协同适应性中的性能评价指标)，可知随时间的推移每个个体的角度最终趋于一致.

表1 二维空间中机器人运动的角度随时间的变化Table 1 Robots’angle experimental results with time in 2-D environment (°)

通过上述仿真结果及分析，可见群体机器人的运动不仅不受群体中个体数量的限制，且能根据环境信息的变化自动调整运动方向和速度大小，实现了稳定的群体同步行为.

3.2 能量优化的仿真实验

在机器人运动过程中，利用粒子群优化算法对控制器的性能参数k=［kpkvkr］进行优化，达到能量消耗最小的目的.

图8表示参数k取不同值时，群体所消耗的能量的对比.可见，控制器的性能参数能够影响系统消耗能量的大小，进而可以对控制器的性能参数进行优化，达到能量消耗最小的目的.图9显示粒子对k值的寻优过程，可以看出，利用粒子群优化算法能够使控制器的性能参数k经过一段时间的调整达到了最优值.

图8 优化前不同参数对应能量曲线对比Fig.8 Comparisons of energy for different parameters before optimization

图9 k最优值的变化曲线Fig.9 Optimal k values with the iteration of PSO

图10显示相应的优化后的群体同步行为所消耗的能量，与图8所示优化前的能量相比，减小了3个数量级，得到了很好的优化效果.

图10 优化后能量消耗曲线Fig.10 Curve of energy consumption after optimization

4 结束语

本文提出了群体机器人系统的协同适应性的概念，针对于同步现象，在充分考虑环境信息及机器人之间的局部信息交互的前提下，设计了群体机器人系统的分布式控制以实现稳定的同步运动，并对于完成时间进行了估计.利用粒子群优化算法来优化控制器中的相应参数，进而解决同步过程中的能量优化问题，仿真结果证明了方法的有效性.进一步的工作包括对于动态环境下的控制器设计;提出通用性强的吸引排斥函数，实现将时间、能量等相结合的综合优化目标，从而得到更为理想的效果.

［1］胡中功，李静.群智能算法的研究进展［J］.自动化技术与应用，2008，27(2):13－15.

HU Zhonggong，LI Jing.The progress of swarm intelligence algorithms［J］.Techniques of Automation and Application，2008，27(2):13－15.

［2］REYNOLDS C W.Flocks，birds，and schools:a distributed behavioral model［C］//Proceedings of ACM Computer Graphics(SIGGRAPH’87).New York，USA:ACM，1987:25－34.

［3］VICSEK T，CZIROK A，Ben－JACOB E，COHEN I，SHOCHET O.Novel type of phase transition in a system of self－driven particles［J］.Physical Reviews Letter，1995，75(6):1226－1229.

［4］JADBABIE A，LIN J，MORSE A S.Coordination of groups of mobile autonomous agents using nearest neighborhood rules［J］.IEEE Transaction on Automatic Control，2003，48(6):988－1001.

［5］TANNER H G，JABABAIE A，PAPPAS G J.Flocking in fixed and switching networks［J］.IEEE Transaction on Automatic Control，2007，52(5):863－868.

［6］TANNER H G，JABABAIE A，PAPPAS G J.Stable flocking of mobile agent，part I:fixed topology［C］//Proceedings of Conference on Decision Control.Maui，HI，USA，2003:2010－2015.

［7］TANNER H G，JABABAIE A，PAPPAS G J.Stable flocking of mobile agent，part II:dynamic topology［C］//Proceedings of Conference on Decision Control.Maui，Hawaii，2003:2016－2021.

［8］GAZI V，PASSINO K M.Stability analysis of swarms［J］.IEEE Transaction on Automatic Control，2003，48:692－697.

［9］GAZI V，PASSINO K M.A class of attraction/repulsion functions for stable swarm aggregations［C］//Proceedings of Conference on Decision Control.Los Vegas，USA，2002:2842－2847.

［10］GAZI V，PASSINO K M.Stability analysis of swarms in an environment with an attractant/repellent profile［C］//Proceedings of American Control Conference.Anchorage，USA，2002:1819－1824.

［11］GAZI V，PASSINO K M.Stability analysis of social foraging swarms:combined effects of attractant/repellent profiles［C］//Proceedings of Conference on Decision Control.Las Vegas，USA，2002:114－123.

［12］GAZI V，PASSINO K M.Stability analysis of social foraging swarm［J］.IEEE Transaction on Systems，Man，and Cybernetics－Part B:Cybernetics，2004，34(1):539－557.

［13］LIU Yanfei，PASSINO K M.Stable social foraging swarms in a noisy environment［J］.IEEE Transaction on Automatic Control，2004，49(1):30－44.

［14］REIF J H，WANG Hongyan.Social potential fields:a distributed behavioral control for autonomous robots［J］.Robotics and Autonomous Systems，1999，27:171－194.

杨 茂，男，1982年生，博士研究生，主要研究方向为群体机器人系统、强化学习.

李成凤，女，1986年生，硕士研究生，主要研究方向为群体机器人系统、分布式优化.

田彦涛，男，1958年生，教授、博士生导师、博士.吉林大学自动化研究所所长，兼任中国自动化学会理事、中国自动化学会机器人专业委员会常务委员、吉林省自动化学会理事长、吉林省通信学会副理事长、吉林省电机工程学会常务理事，中科院沈阳自动化研究所先进制造技术实验室学术委员会委员，中国自动化学会《机器人》学报编委、《吉林大学学报(信息科学版)》副主编.主要研究方向为复杂系统建模、优化与控制、分布式智能系统与网络控制.近五年，完成国家“863”计划项目1项、国家自然科学基金项目1项、吉林省科技发展计划项目3项、国家“863”计划智能机器人网点实验室基金项目1项;目前负责承担国家“863”计划项目和国家自然科学基金项目等国家级科研项目3项、吉林省科技发展计划重点项目3项.曾被评为国家机械部“优秀科技青年”、机械部和教育部跨世纪学科带头人，2004年评为吉林省拔尖创新人才.发表学术论文70余篇，其中被SCI、EI、ISTP 检索36篇.

Distributed coadaptive control and optimization of swarm robot synchronization

YANG Mao1，LI Cheng－feng1，TIAN Yan－tao1，2

(1.School of Communication Engineering，Jilin University，Changchun 130025，China;2.Key Laboratory of Bionic Engineering(Jilin University)，Ministry of Education，Changchun 130025，China)

Co－adaptive control mechanisms for swarm robot systems were investigated to see if swarms could adapt to complex environments by using distributed control with local information exchange.The phenomenon of synchronization was studied，and on that basis a decentralized controller was proposed.It combined the ideas of a virtual force，the nearest neighborhood law，and environmental factors.It was proven that this controller can enable all swarm members to converge to a common velocity with bounded errors，whether the swarm topology is fixed or dynamic.The advantage of this controller is that it just needs local information to provide stable group behavior.In addition，parameters were optimized on the basis of the proposed controller to achieve the goal of minimum energy consumption.To deal with particle swarm optimization algorithms(PSO)easily falling into local optimums and having low accuracy，an improved algorithm was put forward.This was used to solve the energy optimization problem.Simulation results are included that verified the controller and algorithm.

swarm robot;synchronization;cooperative control;distributed controller;PSO algorithms

TP18

A

1673－4785(2010)03－0247－07

10.3969/j.issn.1673－4785.2010.03.007

2009－11－12.

国家自然科学基金资助项目(60675057);吉林大学研究生创新基金资助项目(20091020).

田彦涛.E－mail:tianyt@jlu.edu.cn.

book=3,ebook=27