基于人工势场的多Agent路径规划方法研究

焦红艳

（河南科技学院,河南新乡453003）

基于人工势场的多Agent路径规划方法研究

焦红艳

（河南科技学院,河南新乡453003）

智能机器人自身运动路径的规划是其完成任务的基础.主要针对实际应用中常用的栅格法和人工势场法两种路径规划算法进行研究,针对多Agent运行的复杂陆地环境,利用栅格法构建环境模型,给出了一种基于人工势场法的路径规划方法.分析了势函数的选取方式,得出了参数选取的基本原则,并结合常用的冲突消解办法,使得规划出的路径更加平滑,效率更高.

多Agent；路径规划；栅格法；人工势场法；冲突消解

在Agent运动规划中较常用的方法有人工势场法、构型空间法、人工智能法以及各种启发式搜索方法等[1].其中人工势场法是在运动规划中引入了虚拟力场的概念对Agent的运动进行规划,Agent根据势场来确定它自身所受到的虚力,通过所受虚力来确定运动方向[2].本文采用栅格法建立环境模型,然后利用人工势场法进行路径规划,解决多Agent系统中的各种冲突.

1 用栅格法进行地形描述

在动态环境下,可能存在静态和动态两类障碍物,当不考虑这些障碍物存在的问题时,Agent就可以按照既定的路线前进,自然有些障碍物会和Agent相撞,有些则不会[3].利用人工势场法规划路径,为了避障,结果会导致运动路径变长,能源与时间损耗变大.

对于可能发生碰撞的障碍物,计算它对Agent所产生的斥力是非常必要的,对于安全的障碍物免于计算,从而达到优化算法和节约资源的目的[4].

1.1 地形的栅格化

地形的栅格化是指将Agent所处的实际的复杂环境用简单、规则的栅格表示出来.通常情况下,栅格地图中的栅格单元共有3种状态：①未知状态,表明该栅格单元离Agent较远,尚未被传感器探测到,目前属于未知区域；②占有状态,表明该栅格单元已经被障碍物占据；③空闲状态,表明该栅格单元归属于空闲区域,即Agent可以从该栅格通过.栅格法是一种非常流行的地形栅格化方法,其主要思想就是将环境划分为离散的栅格,并将栅格看作一个连通图,路径规划即是在这个连通图上利用相应的搜索算法搜索出无碰路径,路径是由栅格序号组成的,最后将序号转化为地图坐标即可.

1.2 信息编码

环境模型建立之后的信息编码是非常重要的一个环节,编码方式为：1表示障碍栅格,0表示自由栅格.计算机中以栅格序号为索引进行存储：

以序号为36的栅格为例,它的环境信息将存储在kj[36]的这个结构体数组元素中.

obs={z1,z2,z3…}为障碍栅格集合；qd表示起点,zd表示终点,这两点不属于obs.电子地图就可以通过栅格与数组的对应关系建立.之后的路径规划将在建立的电子地图的基础上进行.

2 用人工势场法进行路径规划

2.1 传统人工势场法所面临的问题

对于如图1所示的U型障碍物环境,Agent会因多处受力而震荡,对于狭窄通道也容易来回摆动,最终无法到达终点.另外,Agent本身也具有一定尺寸,当障碍物之间通道的尺寸本来就小于Agent的尺寸时,Agent自然也是无法通过此通道的.

图1 U型环境结构Fig.1 U environment structure

2.2 人工势场法的改进措施

经过长时间的实践与研究,研究人员发现,传统的人工势场法在路径规划时对于规则障碍物规划正常,但是对于不规则障碍物容易路径规划失败而发生碰撞.

本文实现了把选择策略加入到路径规划算法中,使Agent在每步动作之前就可以对下一步动作提前做出预判,以提高下一步动作的效率.也就是说我们期望通过此方法使得Agent可以付出最小的代价来规避障碍物从而到达目标点,这里所指的代价不仅仅包括速度,而且也包括规避障碍物的效率.

现将Agent自身的速度和加速度矢量分别引入到人工势场法中.则可推导出如下的公式

分析假如发生碰撞的情况下,要考虑当时临界点的情况：①如果障碍物的运动速度较大,则障碍物有可能在Agent的右侧与它发生碰撞；②如果障碍物的运动速度相对较小,则障碍物就有可能在Agent的左侧与它发生碰撞.

由此,可以通过计算得到ΔVx的两个临界值A和B.按照上述情况①和情况②所进行的分析,此时应该分别满足以下公式由公式（1）和（2）可以推出

Agent下一步行为的具体的判断方法如下：

（1）如果ΔVx介于A和B之间,则存在发生碰撞的可能,所以Agent需要做出规避的动作.但是因为障碍物对Agent来说,在速度上有优势,所以即使Agent做出了规避动作,仍有可能发生碰撞.

（2）如果ΔVx＞B,由于障碍物在x轴正方向的速度上存在巨大的优势,Agent无法从此方向避障,只能选择其反方向.

（3）如果ΔVx＜A,因为障碍物在x轴正方向上对Agent所存在的优势不足,使得Agent与障碍物不存在碰撞的可能,因此,在这种情况下,就可以利用传统的人工势场法来实现对障碍物的规避.

（4）如果障碍物与Agent之间的距离大于200（单位与Agent的半径单位相同）,因超出距离范围而无需考虑.

结合上面所论述的避碰原理,首先需要分析所要加的这个修正力的大小以及如何将这个修正力实现.可以看出,当Agent需要做出向右规避动作的时候,就需要给Agent施加一个指向x轴正方向的修正力,具体定义如下

这里的c是指与所增加修正力相关的一个参数.这里这个修正力的方向与ΔVx同向.最后所得到的合力的方向是原来人工势场的合力与后来增加的修正力的合力的方向.最后可以得出合力的定义

当Agent需要做出向左的规避动作时,就需要对Agent施加一个指向x轴负方向的修正力,从而使得Agent能够摆脱障碍物.可以看出,在传统的人工势场法中,障碍物对Agent的排斥力和目标点对Agent的吸引力的合力是使得Agent做出向右的规避动作.明显违背了规划路径要求最短的原则.此时,就需要Agent能够聪明地“分析”一下当前的局势,从而做出向左的规避动作.在这里仅仅需要Agent能够做出这个向左的规避动作,而不需要把当前障碍物和Agent的具体位置考虑进来,即可以不用考虑当前的障碍物i对Agent所产生的排斥力的大小.这个时侯,我们需要考虑的修正力的大小,就是目标物对Agent的引力和当前障碍物之外的其他障碍物对Agent的排斥力之和的合力,公式如下

根据上面的描述,在每个仿真周期开始时,就需要根据环境中的障碍物、目标物、Agent的位置以及Agent的速度矢量对Agent的下一步动作做出预判,这样就可以更好地消除无谓或者徒劳的避障.

经过采用上述方法对人工势场法所做的改进,问题的解决情况如下：

（l）局部最优问题的解决.当Agent所受障碍物合力为0时,通过上述的改进,使得Agent不断地更新自身位置与目标位置之间的距离,从而解决问题.

52.13 %（49/94）的学员希望固定时间进行课堂教学，39.36%（37/94）的学员希望以英语角形式进行学习，37.23%（35/94）的学员希望在科室业务学习中进行双语教学。

（2）狭窄通道中的摆动问题.遇到狭窄通道,将会适当地减小障碍物对Agent的影响系数,与此同时,增大目标点对Agent的影响系数.当然,减小和增大系数的数量级要是一致的,从而使得Agent可以安全地通过狭窄通道.

（3）多障碍物时斥力函数的调整.当遇到多障碍物的情况时,容易出现各个障碍物对Agent所产生的斥力方向不太一致的问题,如图2所示,目标点对Agent所产生的引力F引的大小方向与图3中一致,经过合力作用可以绕过障碍物而到达目标.

图2 传统人工势场法多障碍物路径规划失败情况Fig.2 The failures of traditional artificial potential field method more obstacles path planning

图3 改进人工势场法多障碍物路径规划成功情况Fig.3 The success of improved artificial potential field method more obstacles path planning

（4）障碍物之间的通道不足以让Agent通过.由于Agent本身是有一定尺寸的,当障碍物之间通道的尺寸小于Agent的尺寸时,Agent是无法从此通道通过的,所以为了避免这种情况的出现,通过将通道边缘向外扩展Agent一半尺寸,使得通道被视为障碍物而达到避障目的[5].

2.3 用人工势场法对多Agent进行实时路径规划

为了实现多个Agent的有效避碰,除了要考虑环境中的障碍物以外,还需要考虑到其他Agent的位置信息以及其他Agent对该Agent的斥力[6].本文在利用改进的人工势场法进行多Agent系统局部路径规划时,将人工势场法与冲突消解法结合在一起,并加入了Avoid-Agent行为,用于躲避其他Agent.

在Agent的路径规划过程中,如果没有出现冲突,则按人工势场法规划,一旦发生冲突,则按优先级法解决[7].具体规划方式如下.

（1）当两个Agent相遇时,有以下两种可能：

②两个Agent不在同一直线上,但如果检测到有冲突的可能,则低优先级减速避碰.

（2）如果有多个Agent的冲突需要消除,则执行如下步骤：

①如果Agent之间的距离小于某一个规定值,则表明进入冲突区；

②低优先级停止让行；

③如果不同优先级出现在同一线路,则低优先级避让高优先级[8].

上述冲突消解法是各种方法的综合应用[9].改进人工势场法的流程如图4所示.

图4 基于混合算法的路径规划流程Fig.4 Path planning based on hybrid algorithm flow chart

部分代码如下：

3 仿真实验

按照以上的规划策略进行仿真.假设Agent都是以不变的速度在前进,4个Agent首先各自按照传统的人工势场法所规划的最短路径运动,并且都是向各自的目标点处前进,如图5-a.当R1和R4进入彼此的安全半径后,利用改进的人工势场法进行局部避障,其余两个按原来的路径规划法,最终均安全抵达目的地,如图5-e所示.

图5 仿真实验Agent路径Fig.5 The simulation Agent path graph

对比加入了各种避碰策略的改进的人工势场法的路径仿真结果,路线平滑且高效.

4 小结

本文提出将栅格法和人工势场法相结合应用在Agent路径规划中的思路,针对多Agent的冲突问题,将传统人工势场法及栅格法与各种冲突消减法相结合,并加入Avoid-Agent行为等思想[10],使得多Agent的路径规划更加高效.实验证明该方法和理论正确有效.

[1]蔡自兴,徐光枯.人工智能及其应用[M].3版.北京：清华大学出版社,2004.

[2]赵锋.动态环境下移动机器人的路径规划[D].北京：北京工业大学,2003.

[3]张棋,杨宜民.基于改进人工势场法的足球机器人避碰控制[J].机器人,2002,24（1）：12-15.

[4]王肖青,王齐志.传统人工势场的改进[J].计算机技术与发展,2006（4）：96-99.

[5]王娟娟.机器人路径规划方法研究[D].淄博：山东理工大学,2010.

[6]贾润亮.多机器人系统路径规划研究[D].太原：太原理工大学,2008.

[7]王俊松,崔世钢,邴志刚,等.基于Multi-Agnet的多机器人控制技术[J].天津职业技术师范学院学报,2004,14（2）：4-7.

[8]王凡.基于Agent的多机器人路径规划的研究[D].武汉：武汉理工大学,2006.

[9]唐振民,赵春霞,杨静宇,等.基于动态规划思想的多机器人路径规划[J].南京理工大学学报,2003,27（5）：610-615.

[10]CHONG J O,ELMER G G.Growth oistances：new measures for object separation and penetration[J].IEEE Transaction on Roboties and Automation,1996,12（6）：888-903.

（责任编辑：卢奇）

Multi-Agent path planning method based on artificial potential field

JIAO Hongyan
（Henan Institute of Science and Technology,Xinxiang 453003,China）

Intelligent mobile robot motion path planning is the basis of fulfillment of its mandate.Two path planning algorithms,i.e.the grid method and the artificial potential field method was studied in this paper.According to the Multi-Agent complex dynamic environment,environmental model was made by the grid method.A path design method based on the artificial potential field,which is aimed at the complex environment of running the Multi-Agent,was presented using a model mad by grip method.The selection of the potential function was analyzed,and obtained parameters selected basic principles,a smoother,more efficient path planning was obtained by combined with the usual conflict resolution approach.

Multi-Agent；path planning；grid method；artificial potential field method；confilict resolution

TP391

A

1008-7516（2016）04-0056-06

10.3969/j.issn.1008-7516.2016.04.012

2016-05-27

焦红艳（1981―）,女,山西榆次人,硕士,讲师.主要从事计算机理论教学及研究.