基于差分进化的多机器人路径规划

文章编号:1006-9348(2011)01-0010-04

计󰀁算󰀁机󰀁仿󰀁真

2011年1月󰀁󰀁

基于差分进化的多机器人路径规划

雷小宇,楼朴根,张婷婷,杨胜跃

1

1

1

2

(1.解放军理工大学,江苏南京211101;2.中南大学信息科学与工程学院,湖南长沙410075)

摘要:差分进化是一种新兴的、简单有效的智能优化方法。其具有较好的收敛性、鲁棒性和高效性。将差分进化引入到多机器人路径规划来,提出了一种基于差分进化的多机器人路径规划方法,并调整了进化的参数值。采用该方法加快了多机器人路径的规划速度,有效地克服了传统遗传算法速度慢,适应新环境差的缺点,最后给出了的仿真结果证明方法可行、有效。关键词:多机器人;路径规划;差分进化;遗传算法;控制参数中图分类号:TP391󰀁󰀁文献标识码:A

PathPlanningResearchforMulti-RobotBasedonDifferentialEvolution

LEIXiao-yu,LOUPu-gen,ZHANGTing-ting,YANGSheng-yue

(1.PLAUniversityofScienceandTechnology,NanjingJiangsu211101,China;

2.CollegeofInformationScienceandEngineering,CentralSouthUniversity,ChangshaHunan410075,China)ABSTRACT:DifferentialEvolutionisanove,lsimpleandeffectiveintelligentoptimizationapproach.Itis󰀁conver󰀁gent,robustnessandefficient.Anewapproachofpathplanningformulti-agentbasedDifferentialevolutionispres󰀁entedandmoreover,theparametersoftheevolutionareadjusted.Themethodacceleratesthemulti-robotpathplan󰀁ning,andeffectivelyovercomestheshortcomingthatthetraditionalgeneticalgorithmisslowinadaptingtothenewenvironmentoftheshortcomings.Finally,thesimulationresultsprovethatthemethodisfeasibleandeffective.KEYWORDS:Multi-robot;Pathplanning;Differentialevolution;Geneticalgorithm;Contorlparameter

1

1

1

2

1󰀁引言

分布式人工智能(DAI)成为近年来人工智能研究的一个重要分支,而DAI研究大致可以分为DPS(DistributedProblemSolving)和MAS(Multi-AgentSystem)两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发,将智能体概念应用于多机器人系统的研究中,将单个机器人视作一个能独立执行特定任务的智能体,并把这种多机器人系统称为󰀂多智能体机器人系统(MARS) 。因此,本文中多机器人系统等同于多智能体机器人系统。机器人的导航和路径规划是机器人运动的前提。单个机器人的路径规划是按照某一性能指标搜索一条从起始状态到目标状态的最优或近似最优的无碰路径。根据环境地理信息不同,路径规划可分为两种类型:!环境信息完全已知的离线全局路径规划;∀环境信息完全未知或部分未知,通过传感器对机器人的工作环境进行探测,以获取障碍物位置、形状和尺寸等信息的

在线局部路径规划。而多个机器人的路径规划侧重考虑整个系统的最优路径或近似最优,如系统总耗时间最少路径或是系统总路径最短等等。从目前国内外的研究来看规划多机器人路径时,更多地考虑的是多机器人之间的协调和合作式的路径规划。

目前国内外学者采用的研究方法主要有:可视图法、自由空间法、栅格法、Voronoi图法、人工势场、遗传算法、蚁群算法、免疫算法、神经网络、强化学习以及动态规划、最优控制算法、模糊控制[1-3]等。这些方法较好地解决了某些特定场合下的路径规划问题,但也呈现出规划效率不高,机器人之间协作性不强的弱点。

本文将差分进化进入到多机器人的路径规划中来、并调整控制参数,给出了仿真结果,并对下一步研究工作进行了探讨与展望。

2󰀁差分进化基本原理

基金项目:国家自然科学基金项目(60774023);湖南省自然科学基金

项目(06JJ50141);解放军理工大学理学院青年基金(QN-DZ-2009-03)

收稿日期:2010-10-28

由StornR和PriceK于1995年提出的差分进化(Differ󰀁entialEvolution,DE)算法[4-7]是以遗传算法为基础的一种随机并行直接搜索算法,具有记忆个体最优解和种群内信息共享的特点。该算法克服了遗传算法容易󰀂早熟 的缺陷,并

#10#拥有良好的鲁棒性,收敛性好、控制参数较少、可以动态跟踪当前的搜索情况调整其搜索策略、具有利用个体局部信息和群体全局信息指导算法进一步搜索的能力。DE的诸多优点和强大的全局寻优能力使得其在多个领域(如人工神经网络、电力系统、信号处理领域、生物学领域、机器人领域)得到了广泛的应用。

差分进化算法是将种群中任意两个个体的向量差加权后根据一定的规则加到第三个个体上从而获得新个体,若新生成的个体的目标函数值比种群中预先确定的一个个体的目标函数值小,则用新生成个体替代原种群与之相比较的个体,否则原个体保存到下一代。在实际问题时,该基本原理可以适当地进行扩展,例如,可以将多个向量差分加权后加到第三个向量上以获取新个体,也可引入当前种群中的最优个体以加速搜索等。在比较新旧个体目标函数值之前,可以对新个体与旧个体中某些位置上的解进行等位交换,类似于遗传算法中的交叉操作,从而提高差分进化算法的搜索能力。

差分进化过程包括变异(Mutation)、交叉(Crossover)和选择(Selection)三种基本操作。随机选择两个不同的个体矢量相减生成差分矢量,将差分矢量赋予权值之后加到第三个随机选择的个体矢量上,生成变异矢量,该操作称为变异。变异矢量与目标矢量进行参数混合,生成试验矢量,这一过程称之为交叉。如果试验矢量的适应度优于目标矢量的适应度,则用试验矢量取代目标矢量形成下一代,该操作称为选择。在每一代的进化过程中,每一个体矢量作为目标矢量一次。初始种群是在搜索空间随机生成的,且要求初始种群覆盖整个搜索空间。初始群体一般采用均匀分布的随机函数来产生,差分进化算法的具体操作如下。2.1󰀁变异操作

DE最基本的变异成分是父代的差分矢量,每个矢量对包括父代(第t代)群体中两个不同的个体(xrt1,xtr2),差分矢量定义为

Dr1,2,

G

u

t+1

ij,G

=

1

vt+ij,G,rand(j)£CR󰀁or󰀁j=randn(i)

xtij,G,rand(j)>CR󰀁and󰀁j&randn(i)

(3)

式(3)中rand(j)%[0,1]为均匀分布的随机数,j表示

[0,∋,D],为随机选择的维

第j个变量(基因);CR为交叉因子,通常的取值范围为[0,1],大小预先确定;randn(i)%

数变量索引,以保证试验矢量至少有一维变量由变异矢量贡献,否则试验矢量有可能与目标矢量相同而不能生成新个

1t+1

体。由式(1-3)可知,如果CR越大,则vt+i,G+1对ui,G+1的贡献11越多,当CR=1时,ut+=vt+,有利于局部搜索和加速收,G+1i,G+1i1+1t敛速率;如果CR越小,则xt+,G对uii,G+1的贡献越多,当CR=01t+1时,ut+,G+1=xi,G,有利于保持种群的多样性和全局搜索。由i

此可见,在保持种群多样性与收敛速率之间是矛盾的。2.3󰀁选择操作

DE采用󰀂贪婪 的搜索策略,经过变异与交叉操作后生

1tt+1成的试验个体ut+,G+1与xii,G进行竞争,只有当ui,G+1的适应度

较xti,G更优时就被选做新的一代,否则,直接将xti,G作为下一代。以最小化优化为例,选择操作的方程为:

x

t1+

,Gi

=

1+1tt

ut+,G+1,f(ui,G+1)(4)

2.4󰀁参数设置

在进化算法领域,参数多少及其设置的复杂性是衡量一个算法优劣的标准。要取得理想的进化结果,参数的选择至关重要。在DE算法中涉及到需要设置参数主要有:最大迭代次数G,种群个体数目N,变异因子F,交叉概率CR。迭代次数G依据具体问题而定,G越大最终结果越精确,也更接近实际目标,同时所耗费的计算时间更长。G群体所含个体数量N一般介于5*D与10*D之间(D为问题空间的维度),N越大,种群多样性越强,获得最优解概率越大,但是计算时间更长,一般取20-50。在DE算法中比较重要的两个参数是变异因子F和交叉概率CR,F控制种群的多样性和收敛性,一般在[0,1.2]之间取值,CR可控制个体参数的各维对交叉的参与程度,以及全局与局部搜索能力的平衡,一般取值在[0,1]之间。在文献[8]中Gamperle介绍了DE算法的参数设置,指出F小于一定的值V将导致算法不收敛,V依赖适应度函数和其他参数,F越大,算法更容易逃出局部极小点,更容易收敛到全局最优点,但是当F>1时,收敛速度将变慢;而CR越大,算法更容易收敛,但易发生早熟现象。所以,合理设置控制参数对很好运用DE算法非常关键,我们可以根据具体的路径规划问题进行相应的调整。

=xtr1,G-xtr2,

G

(1)

式(1)中r1和r2表示种群中两个不同个体的索引号。将差分矢量加到另一个随机选择的个体矢量上,就生成了变异矢量。对每一目标矢量x,变异操作为:

1ttt

vt+,G+1=xr1i,G+F∃(xr2,G-xr3,G)

t

i

(2)[0,1.

式(2)中r1,r2,r3%2]。

2.2󰀁交叉操作

[0,NP],为互不相同的整数,变异

因子F为控制差分向量的缩放因子,通常情况下F%

对于群体中目标矢量个体xi,tG,将与变异矢量进行交叉

1t

操作,产生试验个体ut+,G+1。为保证个体xi,G的进化,首先通i

3󰀁基于差分进化的多机器人路径规划

在复杂的静态环境中,结合DE算法的基本操作提出基于差分进化的多机器人路径规划的主要步骤:参数矢量构造、初始种群生成、变异扰动矢量合成、边界处理和目标函数构造。

过随机选择使得至少有一位由v哪位由x

t

,Gi

t+1

,G+1i

贡献,而对于其它位,可中哪位由v

t+1

,G+1i

利用一个交叉概率因子CR,决定u

t+1

,G+1i

贡献,

贡献,其交叉操作的方程为

#11#3.1󰀁参数矢量及初始群体的构造

同遗传算法一样,初始群体通常采用统一的概率分布来随机选择,第t代群体以S(t)来表示:S(t)=x1{t},∋,xn(t),其中n为种群规模;个体xi%Rd(i=1,∋,n)的参数矢量由实数分量构成,表示优化问题的一个可能解,其构成方式依据具体问题而定。据1.4中可知控制参数之一的交叉概率因子CR响着进化的效果,保持种群多样性和收敛速率是矛盾的,在有利于局部搜索和加速收敛速率与保持种群的多样性和全局搜索之间寻找到一个平衡点最为关键。而产生早熟收敛的根本原因是随迭代次数的增加,种群的多样性快速下降。为克服早熟现象和跳出局部最优解,在本文中提出了一种自适应交叉概率因子CR来调整进化的速度。

1+1t

CR随迭代次数的增加而由小变大,初始阶段xt+,G对ui,G+1的i

DE/randtobest/1

DE/best/2DE/rand/2

扰动矢量由一个差分向量与一个目标个体来生成

扰动矢量由两个差分向量与当前种群中的最优个体来生成

扰动矢量由两个差分向量与一个随机个体来生成

3.3󰀁交叉操作

同遗传算法一样,在DE算法中引入交叉操作以保持群体的多样性。第i代目标矢量xi,G与变异矢量Vi,G+1交叉操作,产生试验操作向量Ui,G+1。3.4󰀁选择操作(边界处理)

扰动矢量合成过程中计算出的矢量分量中可能超越实际问题取值范围,DE算法一般采取下面方法处理:

x

t1+,Gi

11

ut+,f(ui,t+G+)贡献越多,有利于提高全局搜索能力以及保持种群的多样

1t+1

性,而在后期则vt+,G+1对ui,G+1的贡献越多,从而加速算法的i

=(8)

收敛。

设CRmin为最小交叉概率,CRmax为最大交叉概率,I为当前迭代次数,Imax为最大迭代次数,有

CR=CRmin

I((CRmax-CRmin)

+

Imax

(5)

3.5󰀁目标函数

我们采用如下算式计算每个参数矢量x的目标函数值:

󰀁(x)=

2

2

)wf,)w

ii

i=1

i=1

i

=1(9)

式中wi系权值系数,分别决定着对路径长度、障碍规避能力两个因素的影响程度。

根据上述分析,基于差分进化的多机器人路径规划算法描述如下:

Step1:采用统一的概率分布随机选择的方法构造初始种群,第i代以

G(i)={x1(i),∋,xn(i)}来表示。其中,n为种群规模,个体参数

xk(i)=[xk.1,yk,1,∋,xk,m,yk,m]

Step2:变异操作,将差分变量加到另一个随机个体矢量上

Vi,G+1=Xr1,G+F*(Xr2,G-Xr3,G)

其中,r1,r2,r3%[0,NP],F为缩放因子.

Step3:交叉操作,将目标矢量xi,G与变异矢量Vi,G+!交叉操作,产生试验操作向量Ui,G+!,将Ui,G+!与xi,G竞争,优者进入下一代成为xi,G+1。

Step4:选择操作,在标准的DE算法中选择操作采用󰀂贪婪法 的搜索策略。

x

t1+

,Gi

1+1tt

ut+,G+1,f(ui,G+1)路径规划问题的个体参数矢量由以下2*M维实矢量构成:第m个个体(即第m条路径):

xm=[xm,ym,∋,xm,ym,∋,xm,ym]kk,1k,1k,jk,jk,Mk,M

(6)

明显地,节点数量增多,计算量也随之增大,势必影响进化速度。合理的节点个数应该使得进化过程的计算可以在合理时间范围内实现,同时不失去优良路径个体。本文依据障碍数量确定节点个数,根据大量仿真实验可知,节点个数应该取(O+1)~(O+3)之间,其中O是障碍个数,群体规模中矢量个数N一般取20*M。3.2󰀁变异扰动矢量合成

不同于遗传算法按照一定的概率对子代基因位点进行变异操作的方式,DE算法对第t代的每一个参数矢量xi(i=1,∋,n)通过下式的计算得到其对应的第t代扰动矢量(这里采用DE/rand/1模式):

1ttt

vt+,G+1=xr1i,G+F∃(xr2,G-xr3,G)

(7)

式中r1,r2,r3%F%

[0,n]是随机选取的互不相同的整数,

[0,1.2]为缩放因子。当然,还可以采用其它的扰动矢

=

量生成方法:如DE/best/1/bin,DE/rand/2,DE/randtobest/1等,如表1。

表1󰀁

形式DE/rand/1DE/best/1

DE的各种模式

含󰀁义

扰动矢量由一个差分向量与一个随机个体来生成

扰动矢量由一个差分向量与当前种群中的最优个体来生成

Step5:根据评价函数判断所得到的路径是否满足要求,不满足则转向Step2。

Step6:结束。

4󰀁算法仿真与结果分析

在窗口环境14cm(14cm中,取为机器人在多障碍物环境区域运动。最小交叉概率因子CRmin取0.3,最大交叉概率

#12#CRmax为0.9,缩放因子F取0.6。硬件DellOptiplex320PC和软件VisualC++7.0环境下仿真得到的结果如下:

5󰀁总结

采用差分进化算法求解路径规划问题,具有实现简单、优化效果好并有很好的鲁棒性等特点,仿真实验的结果表明该方法收敛速度快,稳定性好,适用于解决大范围、复杂障碍环境下多机器人运动路径规划问题。

当然,差分进化作为一种新兴的进化算法,其理论和应用正处于不断发展和完善的过程中,尽管算法拥有诸多的优点,但在许多方面有待深入研究,如差分进化的收敛性、收敛速度、鲁棒性方面的基础理论问题、控制参数的选取,初始种群的选择等都需要不断完善。但我们可以相信在多机器人路径规划中差分进化的应用必将会取得长足的发展。参考文献:

[1]󰀁GerhardWeiss.MultiagentSystems:AModernApproachtoDis󰀁

tributedModernApproachtoArtificialIntelligence[M].TheMITPress.Cambridge,Massachusetts,London,England,1999.121-161.

[2]󰀁蔡自兴,徐光祐.人工智能及其应用:研究生用书(第三版)

[M].北京:清华大学出版社,2004.124-198.

[3]󰀁张亚鸣,雷小宇,杨胜跃,樊晓平,瞿志华.多机器人路径规划

研究方法[J].计算机应用研究,2008,25(9):2566-2569.[4]󰀁RStorn,K.Price.Differentialevolution-asimpleandefficienta󰀁

daptiveschemeforglobaloptimizationovercontinuousspaces[J].TechnicalreportInternationalComputerScienceInstitute,Berkley,1995.

[5]󰀁KPrice.Differentialevolutionafastandsimplenumericaloptimi󰀁

zer[C].1996BiennialConferenceoftheNorthAmericanFuzzyInformationProcessingSociety,NewYork,1996.524-527.[6]󰀁SRainer,KPrice.Differentialevolution–asimpleandefficient

图1󰀁在简单障碍环境中的单个机器人路径规划

图2󰀁在复杂环境中的两个机器人路径规划heuristicforglobaloptimizationoverContinuousSpaces[J].JofGlobalOptimization,1997,11(4):341-359.

[7]󰀁云庆夏.进化算法[M].北京:冶金工业出版社,2000.2-21.[8]󰀁RGaemperle,SDMueller,PKoumoutsakos.Aparameterstudy

fordifferentialevolutionGmelaA,MastorakisNE:AdvancesinIn󰀁telligentSystems,FuzzySystems,EvolutionaryComputation[C].Newyork:WSEASPress,2002.293-298.

从仿真的结果可以得出,基于DE的路径规划算法具有良好的搜索能力和全局收敛能力。其搜索性能取决于算法全局探索和局部开发能力的平衡,而这在很大程度上依赖于算法的控制参数的选取,包括种群规模、缩放比例因子和交叉概率等,相对其他进化算法而言,DE所需调节的参数较少。DE和GA一样,都是基于群体智能理论的优化算法,通过群体内个体间的合作与竞争产生的群体智能指导优化搜索。

相比于传统的进化算法,DE算法具有更好的搜索性能,可以得到更优的目标函数值。同时,DE保留了基于种群的全局搜索策略,采用实数编码,简单的差分变异操作和一对一的竞争生存策略,降低了遗传操作的复杂性。而且,其特有的记忆能力使其可以动态跟踪当前的搜索情况,以调整其搜索策略,具有较强的全局收敛能力和鲁棒性,且不需要借助问题的特征信息,适于求解一些利用常规的数学规划方法所无法求解的复杂环境中的优化问题。

[作者简介]

雷小宇(1979-),男(汉族),湖南双峰人,讲师,主

要研究领域为:多智能体系统、无线网络、机器学习;

楼朴根(1982-),男(汉族),河南南阳人,讲师,主

要研究方向为:网络安全;

张婷婷(1978-),女(汉族),安徽邳州人,讲师,主

要研究领域为:网络测量;

杨胜跃(1969-),男(汉族),湖南人,教授,硕士生导师,主要研究

领域为:网络化系统控制,非线性控制、智能信息处理。

#13#