全局未知环境下智能群体群集运动与避障控制 4页

第30卷第9期系统工程与电子技术Vol.30No.92008年9月SystemsEngineeringandElectronicsSep.2008文章编号:10012506X(2008)0921744204全局未知环境下智能群体群集运动与避障控制王冬梅,方华京(华中科技大学控制科学与工程系,湖北武汉430074)摘要:研究了在全局环境未知且存在静态障碍物的情况下,智能群体的群集运动控制问题。模型在人工势能结合速度一致策略的基础上,利用了滚动窗口的方法实时产生虚拟领航者引导群体向目标位置运行;并利用极限环方法解决了群体避障问题。基于滚动窗口方法构造的虚拟领航者,充分地利用了实时测得的局部环境信息,具有自适应性;极限环方法避障使得群体能够平滑地绕过障碍物,克服了传统人工势场法避障的局部最小问题。关键词:群集运动;虚拟领航者;滚动窗口法;极限环中图分类号:TP242.6文献标志码:AFlockingwithobstacleavoidanceoftheintelligentswarminglobalunknownenvironmentWANGDong2mei,FANGHua2jing(Dept.ofControlScienceandEngineering,HuazhongUniv.ofScienceandTechnology,Wuhan430074,China)Abstract:Theflockingwithobstacleavoidanceinglobalunknownenvironmentisstudied.Basedonthestrategyofcombiningartificalpotentialwithvelocityconsensus,theswarmisnavigatedtogoalbyvirtualleaderwhichisproducedwithrollingwindowmethod,andtheobstacleavoidanceissolvedbythelimit2cyclemethod.Virtualleaderproducedbytherollingwindowmethodutilizesfullylocalinformation,whichhasself2adaptabili2ty,andthelimit2cyclemethodmakestheswarmavoidobstaclessmoothly,andgoesoverlocalminimumintradi2tionalartificialpotentialfield.Keywords:flockingmotion;virtualleader;rollingwindowmethod;limit2cycle采用改进的人工势场函数导航方法实现了静态障碍物环境0引言[425]下具有动态拓扑结构的群集运动控制,克服了局部最小近年来,模仿自然界动物聚集行为(如:鸟、鱼、蚂蚁、蜜问题,但忽略了障碍物的尺寸大小,只考虑点状障碍物。蜂等以群体的方式觅食或者迁徙的行为)研究智能群体协Magnus等研究了一阶离散系统的群集运动与避碰控制,结调控制问题引起了研究人员的极大关注。1987年Reyn2合人工势场函数导航和Voronoi图法实现了障碍物环境下[6]olds最早提出了模仿动物聚集行为的计算机模型,它由三的群集运动控制;通过生成Voronoi图建立无碰撞路径条基本规则构成:避免碰撞(separation);尽量靠拢(cohe2网络,利用导航函数表达个体移动路径的权值,使群体最终[1]以最优且安全的路径到达目的地;该方法优点适合于任意sion);保持速度一致(alignment)。当前关于群集运动的研究工作也大都是建立在这三条规则的基础之上,我们称形状的障碍物。之为Reynolds模型。本文采用人工势能结合速度一致的策略研究了具有二Reynolds模型仅考虑了无障碍物环境下的群体内部个次积分特性的智能群体的群集运动与避碰控制。文中利用体间避碰与聚集问题,但在实际应用中避开环境障碍物是智能个体实时测得的局部环境信息,以滚动方式实时产生必须面对的问题。鉴于此,OlfatiSaber,Tanner等将基本虚拟领航者引导群体绕开环境障碍物,奔向目标;在滚动的无障碍物的群集运动控制扩展到静态障碍物空间研究了群每一步,以智能个体当前位置为中心的、以个体可以探测到集运动及避碰控制问题。OlfatiSaber采用虚拟个体的方的最大距离r为半径的窗口作为滚动窗口。当滚动窗口内法实现避碰与聚集,用虚拟领导者(·型个体)引领群体避无环境障碍物时,则以目标在滚动窗口内的投影为虚拟领开环境障碍物,其中β型个体和·型个体用来模拟环境障航者;当滚动窗口内发现障碍物时,则利用极限环方法产生[223]碍物,障碍物限制为具有凸形或墙形的表面。Tanner虚拟领航者。人工势能结合速度一致的策略使得群体内部收稿日期:2007210225;修回日期:2007212226。基金项目:国家自然科学基金资助课题(60574088)作者简介:王冬梅(19742),女,博士研究生,主要研究方向为多智能体。E2mail:wdmyou@126.com©1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net\n第9期王冬梅等:全局未知环境下智能群体群集运动与避障控制·1745·个体间不发生碰撞,且以稳定的距离和速度运行;以滚动的标运动时,通过分析障碍物的位置和大小,调节极限环的半方式产生虚拟领航者,以极限环的方法避障,保证了群体充径,采取顺时针或者逆时针方向运动实现避障。该方法柔分地利用局部信息安全地到达目标位置。性地避开障碍物,克服了人工势场法的局部最小问题。3.1极限环基本原理1协调控制策略极限环是一条相轨迹,由于非线性系统会出现自振荡,在障碍物空间的群集运动仍是一种基于势场原理的运相应的相平面上就会出现一条孤立的封闭曲线,曲线附近动,其作用主要包括两部分:一部分是群体内部个体间的相的相轨迹都渐近地趋向这条封闭的曲线,或者从这条封闭互作用;另一部分是个体与周围环境间的相互作用,即障碍的曲线离开,这条特殊的相轨迹就是极限环。对于二阶非物对个体的阻碍作用与目标对个体的吸引作用。线性方程组:本文采取人工势能结合速度一致的策略实现了群体内Ûx222)1=x2+x1(d-x1-x2部个体间的相互作用,使群体内部个体间避碰、聚集且速度Ûx222)(1)2=-x1+x2(d-x1-x2协调一致;并且引入虚拟领航者实现了个体与周围环境间平衡点在原点处。当d=1时系统的轨迹如图1所示。的相互作用,使群体避开障碍物向目标运行。控制律由三部分组成:ui=u1i+u2i+u3i,i=1,2,⋯,N式中,u1i,u2i,用于实现群体内部个体间的相互作用;u1i控制个体间距离,实现群体内部的避碰与聚集且使整体势能最小;u2i调整个体的速度,使得群体的速度协调一致;u3i用于实现群体与周围环境间的相互作用;通过引入虚拟领航者实现导航与避碰,使群体避开障碍物向目标运行。2基于滚动窗口方法确定虚拟领航者滚动窗口方法是国内学者席裕庚等借鉴预测控制中的滚动优化原理提出的动态不确定环境下基于滚动窗口的移[728]图1方程轨迹动机器人路径规划方法。其基本思想是在全局环境未知情况下,利用机器人实时测得的局部环境信息,周期性地在d=1环内的初始点的轨迹向外旋转,环外的初始点刷新窗口信息,以滚动方式进行在线规划。本文借鉴滚动的轨迹向内旋转,最终均趋向于极限环d=1。窗口的思想,根据个体周围的局部信息以及个体的通讯能3.2基于极限环避障力确定一个滚动窗口;在保证避开障碍物和更接近目标的基于极限环避障具体方法是以障碍物的圆心为平衡前提下,在滚动窗口内实时产生虚拟领航者引导群体运行。点,以障碍物的半径与安全阈值的和为可变障碍物的半径考虑由N个个体组成的群体,群体的的起点为S,终点R生成如方程(1)形式的二阶非线性方程;根据该方程连续为G,要求群体以群集的方式从起始点安全地到达终点。实时产生导航轨迹,生成虚拟领航者引导个体沿着障碍物工作环境中分布着有限个静态障碍物,个体以点状描述,障边界处避开障碍物。碍物经过处理以圆形来表示。任一时刻以个体当前位置为定义1(可变障碍物):是指以障碍物位置为圆心,障[9]圆心,探测范围r为半径的圆形区域内的环境信息,该圆形碍物的半径与安全阈值的和为可变半径R的障碍物。可区域称为滚动窗口。个体对全局信息未知,只能根据滚动变半径R是指满足个体和障碍物避免碰撞的极限环的窗口内的信息进行决策。半径。根据滚动规划原理虚拟领航者产生过程如下。障碍物的位置为(xo,yo),半径为RO,安全阈值为δ,则(1)初始化群体的初始状态与目标位置;二阶非线性方程为222(2)根据个体的当前位置、通讯能力确定滚动窗口,并XÛ=±Y+X(R-X-Y)222对窗口内的环境进行刷新;ÛY=ºX+Y(R-X-Y)(2)(3)若当前的滚动窗口内不存在障碍物,取个体当前其中(X,Y)相对于障碍物的坐标值:位置和目标位置的连线与滚动窗口边界的交点作为虚拟领X=x-xo,Y=y-yo;R=RO+δ航者,该虚拟领航者为全局目标在滚动窗口内的映射,称为当滚动窗口内存在障碍物时,避障算法如下:局部目标。(1)连接个体和目标点,作直线L:ax+by+c=0;(4)若当前的滚动窗口内存在障碍物,则利用极限环(2)判断障碍物是否在连线L上,若障碍物不在L上,方法产生虚拟领航者。则以全局目标点在滚动窗口边界的投影作为虚拟领航者;(3)若障碍物在L上,则将障碍物坐标(xo,yo)代入直3基于极限环的智能群体群集控制算法2线L中,判断轨迹的时针方向;若abx+by+bc>0,则障碍目前,对于单个个体避障问题的研究已经非常成熟,其物在目标点和个体连线L的上方,按顺时针方向运动;反之2中最具有代表性的是人工势场法,但易产生局部最小问题。若abx+by+bc<0,则障碍物在直线L的下方,按逆时针本文利用了二阶非线性函数的极限环特征,在个体趋向目方向运动。©1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net\n·1746·系统工程与电子技术第30卷(4)选取适当的积分时间,求解方程组(2)的解作为虚式中,B为结构系数,确定群体最终个体间的间距;A为势能场拟领航者,引导个体绕开障碍物。方程组(2)正负号的选择调整系数。由于对应个体避障的时针方向。顺时针时,方程组第一个系数9Uij9Uij9pij9Uij9Uijpij=-pji,===-取上侧的符号;逆时针时,方程组第一个系数取下侧的9pij9pij9pi9pi9pjΔΔΔ符号。pijUij=piUij=-pjUij23.3基于极限环的智能群体群集控制算法Δ2AB2A则当‖pij‖0(3)1TW=∑[Ui+qiqi]式中,Ni表示i个体的邻居集,Ni>{j∶‖pij‖≤r}A{1,2,2i=1⋯,N},r表示个体的通讯作用能力;c1,c2,c3为常数;Uij为式中,Ui>(N-|Ni)Ur+c1∑Uij(‖pij‖)+2c3UiL为群j∈N势能函数,是关于个体i与个体j之间的相对距离‖piij‖体的总势能,Ur为个体间距离‖pij‖>r时的势能,的非负、可微函数。Uij应满足以下条件:Uij=Ur。(1)当‖pij‖→0时,Uij(‖pij‖)→∞;(2)当个体i与个体j之间的相对距离‖pij‖达到一函数W是连续的,但在‖pij‖=r处非平滑,故当00时,集合Ω={(pi,qi)|W≤C}是闭集。由图G定值时,Uij取得唯一最小值。(3)Uij在pij=r附近单调递增。的连通性可知,当0r连通性使得节点i与j的最大长度为N,因此‖pij‖≤UijΔT时,Uij=Ur为常量,pijUij=0,即超出距离r个体间没有相互(CN)。同样当0c1,c2,使得避障具有最-c1∑PΔ1U1j-c2∑(q1-qj)-c3PΔ1U1L高的优先权,如图3所示群体分为左右两组柔性地避开障j∈Nj∈N11碍物;但当障碍物不在个体向目标运行的方向上,没有阻碍K[u]=K…个体向目标运行时,群体仍作自由空间中的群集运动,并最ΔΔ-c1PUNj-c2(qN-qj)-c3PUNL∑N∑N终以群集的方式聚集在目标位置。仿真结果证明了该算法j∈Nj∈NNN的有效性。由于9PUi(r)=<,运用微分包含理论,则iN·ΔΔ5结束语W˜0时WÛ<0,W单调递减。ioralmodel[J].ComputerGraphics,1987,21(4),25234.运用非平滑的LaSalle不变集原理,初始条件属于Ω系[2]Olfati2SaberR,MurrayRM.Flockingwithobstacleavoidance:统的Filipov轨迹将收敛到区域S={q|qi-qj=0}内的一个cooperationswithlimitedcommunicationinmobilenetworks子集。因此智能群体的渐进地进入稳态,最终速度趋向一[C]∥IEEEConferenceonDecisionandControl,2003.致,各个体间的相对距离保持不变,使群体的总势能达到[3]Olfati-SaberR.Flockingwithobstacleavoidance[R].Techni2最小。calReport,CaliforniaInstituteofTechnology,ControlandDynamicalSystems,Pasadena,California,2003.4仿真分析[4]TannerHG.Flockingwithobstacleavoidanceinswitchingnet2worksofinterconnectedvehicles[C]∥IEEEInternationalCon2本文取5个个体在Matlab环境下进行仿真,在保证群ferenceRoboticsandAutomation,NewOrleansLA,2004:体对应的连接图G为连通的前提下,个体的初始位置可随300623011.机产生,为了便于分析选取个体初始位置分别为:(4,12),(6,10),(8,8),(10,6),(12,5);个体的初始速度随机选取[5]RimonE,KoditschekD.Exactrobotnavigationusingartificialpotentialfunctions[J].IEEETrans.onRoboticsandAutoma2任意的方向,大小在(0,1)的范围内。图中障碍物分别分布tion,1992,8(5):5012518.在(25,25),(50,65),(80,95),(115,80)处,大小分别为:7,[6]LindheM,;grenP,JohanssonKH.Flockingwithobstaclea29,12,12。终点位置坐标为(160,150)。个体之间相互作用的参数为:a=2,L=5,r=3,c1=1,c2=3,c3=5,δ=0.5。voidance:anewdistributedcoordinationalgorithmbasedon该仿真成功模拟了群体绕过障碍物的过程,如图3所示。Voronoipartitions[J].RoboticsandAutomation,2005:178521790.[7]张纯刚,席裕庚.全局环境未知时基于滚动窗口的机器人路径规划[J].中国科学(E)辑,2001.31(2):51258.[8]席裕庚,张纯刚.一类动态不确定环境下机器人的滚动路径规划[J].自动化学报,2002,28(2):1612175[9]KimDH,KimJH.Areal2timelimit2cyclenavigationmethodforfastmobilerobotanditsapplicationtorobotsoccer[J].Ro2boticsandAutonomousSystems,2003,42(1):17230.[10]BradPaden,ShankarSastry.Acalculusforcomputingfilipov’sdifferentialinclusionwithapplicationtothevariablestructurecontrolofrobotmanipulators[J].IEEETrans.onCircuits图3群体的运行轨迹andSystems,1987,CAS234(1):73282.在未遇到障碍物时,所有个体的动态窗口内均无障碍[11]DanielShevitz,BradPaden.Lyapunovstabilitytheoryofnons2物,群体以自由空间中的群集运动方式迅速聚集。进入到moothsystems[J].IEEETrans.onAutomaticControl,1994,障碍区后,个体的动态窗口内出现障碍物,当障碍物阻碍着39(9):191021914.©1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net