多机器人路径规划方法研究
第21卷 第1期
文章编号:100325850(2008) 0120051203
电脑开发与应用(总53
) ・51・
多机器人路径规划方法研究
Study on M ulti -robots Pa th Plann i ng M ethod
贾润亮 安建成
(太原理工大学 太原 030024)
【摘 要】路径规划是当前多机器人系统研究的一个热点问题。在对已有方法研究的基础上, 提出一种全局路径规划和局部路径规划有效结合的新方法。仿真结果表明, 该方法能提高路径规划的效率, 使机器人具有良好的避碰能力, 较好地实现了多机器人的路径规划。
【关键词】多机器人, 路径规划, 遗传算法, 人工势场法
中图分类号:T P 39
文献标识码:A
ABSTRACT T he m u lti 2robo ts path p lann ing app roach is em erging as a key techno logy in the study of m u lti p le mob ile robo tics . Based on study of m u lti path p lann ing m ethods , th is paper p resen ts a new m ethod of global path p lann ing over recen t years
com b ined w ith local path p lann ing . T he experi m en t’sresu lt verifies the feasib ility and validity of the theo ry . KEYWOR D S m u lti 2robo ts , path p lann ing , genetic algo rithm , artificial po ten tial field
随着机器人技术的发展, 机器人的应用领域和范
围不断扩展, 机器人面临着越来越复杂的任务, 这些复杂的任务由单一机器人已难以胜任, 需要多个机器人通过协调与合作共同完成, 以比单个机器人更可靠任务。因此, 研究热点。, 决定了多机, 也是机器人实现智能化的关键技术。
下达给局部路径规。, , 规划出从当前点到某一子目标点的优选路径, 进行实时避碰。
程序框图如图1所示。
2. 1 基于遗传算法
1 多机器人路径规划
多机器人路径规划就是在同一工作空间中为每一个机器人找到一条路径, 并保证每一时刻机器人与机器人之间无碰撞, 机器人与环境之间无碰撞。
根据对环境的了解情况, 路径规划可以划分为两种类型:全局路径规划和局部路径规划。全局路径规划是根据先验地理环境信息, 找出从起始点到目标点的符合一定性能的可行或最优路径。局部路径规划是机器人在行走过程中, 通过传感器感知离机器人较近的障碍物信息和自身的状态信息, 在此基础上规划出一条一条无障碍、可通行的路径, 避开出现的未知障碍, 实现任务目标。
的全局路径规划算法设计遗传算法是模
仿生物的遗传、进化原理, 并引用随机统
计理论而形成的一类搜索算法。在求解过程中, 算法从一个初始变量群体开始, 逐代寻找问题的最优解, 直至满足收敛判据或预先设定的迭代次数为止。
①个体编码
个体表示机器人在其工作空间中的一条运动路径。在地面坐标系XO Y 中, 路径点序列的坐标是二维的。为了降低编码长度, 我们把起点和终点的连线等分, 在计算时只把路径点的纵坐标作为基因进行编码, 横坐标不变, 这样可以节省计算时间。
2 基于混合算法的多机器人路径规划
针对多机器人系统的特点, 我们提出一种基于混合算法的路径规划方法。利用遗传算法作全局规划, 给出一条从起点到终点的路径, 并产生一系列子目标点
3 2007209214收到, 2007211224改回
33 贾润亮, 男, 1974年生, 在读硕士, 研究方向:人工智能, 多机器人系统。
・52・(总54) ②初始化种群
多机器人路径规划方法研究
n -1
2008年
为了保证初始化的广泛性和全局最优性, 需要采用大范围初始化个体, 以使初始种群尽可能随机分布在搜索空间中的每一个区域。因此, 我们采用随机初始化方法。
③适应度函数
在考虑适应度函数时, 我们考虑以下因素:a 1可行性
W =
∑((y
1
i -1
(x i -1-x i ) -(y i -y i -1) (x i --y i )
x i -1) )
取其倒数作为路径光滑的适应度函数, 即
f 3=1 W 所以个体的适应度函数是:f =Αf 1+Βf 2+ςf
3
可行性是指机器人在所规划的路径中能够动态地避开障碍物。
设机器人从当前点P 0到P i (x i , y i )
需要的时间为
t i , 从P i -1(x i -1, y i -1) 到P i (x i , y i ) 所用的时间为T i -1,
则t i =t i -1+T i . -1, T i -1的表达式如下:
T i -1=
, Β, ς是比例常数。Α
④遗传算子策略a 1选择算子策略
选择操作是指从群体中选择优良的个体并淘汰劣质个体。采用精英选择法, 除了初始代种群外, 其余各代都把父代种群与子代个体群混合起来, 从中按一定
(x i -x i -1) +(y i -y i -1) v
2
2
其中, v 是移动机器人的当前速度。
设在时刻t i 第K 个障碍物的位置为O bk (x bk (ti ) ,
y bk (ti ) ) ,
x bk (t i ) =x bk (t 0) +v bx (t i ) y bk (t i ) bk 0) by (t i )
v bx , v by i X , 方向上的分
概率选择较优的个体。
b 1交叉算子策略
点概率进行交叉繁殖, 产生一对新的个体。
c 1变异算子策略
变异操作是以很小的概率随
机地改变群体中个体某些基因的值。先对穿越障碍物路段的中途
点以一定概率进行变异, 当路径中不存在穿越障碍物的点时, 再进行路径的优化。
⑤遗传算法操作据上所述, 遗传算法操作流程如图3所示。2. 2 基于人工势场法的局部路径规划算法设计
人工势场法把机器人在环境中的运动视为一种在抽象的人造受力场中的运动, 目标产生引力, 障碍物产生斥力, 最后通过求合力来控制机器人的运动。在多机器人路径规划中, 除了环境的障碍物以外, 还需要考虑其他机器人的位置信息以及其他机器人所产生的斥力。
2. 2. 1 势函数的确定
势场是对机器人运行环境的抽象描述
, 障碍物和目标点按某种规则(势函数) 产生一定的势场, 机器人在势场中具有一定的势能。势函数可分为斥力势函数和引力势函数。
①斥力势函数
在势场中, 由障碍物产生的势场对机器人产生斥力F rep , 并且距离越近, F rep 越大, 即机器人与障碍物越
量。
采用以下的适应度函数:
n
m
lk
k
lk
d (v co s Η′+v co s Η) ) ∑∑(G f 1=
l =1k =1n
m
∑∑l
l =1k =1
其中, G =
(x bk (t i ) -x i ) 2+(y bk (t i ) -y i ) 2, v 是机器
人在该路径的移动速度, v k 是障碍物在该路径的移动速度, Η′lk 是在第l 个路径点上机器人运动方向和机器人与第k 个障碍物之间连线的夹角, Ηlk 是在第l 个路
径点上障碍物运动方向和机器人与第k 个障碍物之间连线的夹角, n 为路径点的个数, m 为区内障碍物的总个数, d 为安全半径。
该适应度函数描述了每一条路径碰撞的可能性的大小。
b 1路径最短
路径的长度:
n -1
D =
∑
(x i +1-x i ) 2+(y i +1-y i ) 2
f 2=1 D
取其倒数作为判断路径最短的适应度函数, 即c 1光滑性
路径的光滑适应性:
第21卷 第1期电脑开发与应用(总55) ・53・
近, 机器人具有的势能越大, 反之越小。这种势场与距离成反比, 所以斥力势函数U rep 可以表示为:
K r Θ(X , X obs ) Θ≤Θm
() U rep X =
0Θ≥Θm 式中:K r 为斥力势场常量; X 为机器人位置向量;
X obs 为障碍物位置向量; Θ(X , X obs ) = X -X obs 为机器人与障碍物的最短距离; Θ。m 为斥力势场的作用范围当机器人与障碍物的距离大于Θm 时, 斥力势场对机器人的运动不再有影响。
斥力的方向背离障碍物。当Θ→0时, F rep →∞, 即当机器人与障碍物相碰时, 受到的斥力为无穷大。为了避免机器人与障碍物相碰, 可以设一个最小安全距离
→Θ。机器人受到的斥力F rep 可以Θ0, 当Θ0时, F rep →∞表示为:
F rep =
K r ×
此安全半径, 这时根据人工势场
法进行局部避障, R 1和R 4的轨迹发生弯曲, 直至离开彼此的安全半径。之后R 1, R 4以当前点为起点, 和最近的中间目标点重新用遗传策略进行规划, 机器人R 2, R 3则继续按照遗传算法规划的路径行进, 直至四个机器人均到达各自的目标点, 如图5(b ) 。
因此可以得出结论, 基于混合算法的路径规划效果良好, 满足多机器人系统对路径规划算法的要求。
(Θ(X , X
obs
) -Θ0) 0
2
-
2
(Θm -Θ0)
Θ≤Θm Θ≥Θm
4 结束语
,
目标的引力势函数U att 目标对机器人起吸引作用, , 小。, 此时机器人到达目标。
采用重力势函数以及由重力势函数产生的力作为引力势函数及目标的引力, 分别表示为:
U ott (X ) =K a ・Θ(X , X goal )
F att =K a
式中:K a 为引力势场常量; X
goal
为目标位置向量;
引力的方向指向目标点。
所以机器人所受的势场和力分别为:
U =U att +U rep
F =F att +F rep
图5 混合算法的仿真结果
法和改进的人工势场法的优点, 较好地实现了多机器人的路径规划。
参考文献
[1][2][3]
机器人在合力的作用下, 就可以避开障碍物到达终点。
2. 2. 2 人工势场法程序流程
改进的人工势场法执行流程如图4所示。
谭 民, 王 硕, 曹志强. 多机器人系统[M ]. 北京:清华大学出版社, 2005.
吴晓涛, 孙增沂. 用遗传算法进行路径规划[J ]. 清华大学学报(自然科学版) , 1995, 35(5) :14219.
李庆中, 顾伟康. 基于遗传算法的移动机器人动态避障路径规划方法[J ]. 模式识别与人工智能, 2002, 15
(2) :1602165.
3 仿真实验
实验中, 假定机器人是匀速前进的。四个机器人在一个10m ×10m 的区域内运动, 起点在区域的四个角, 目标点在起点所在角的对角处。确定种群规模50, 交叉概率0. 8, 变异概率0. 1,
避障半径Θ. 5, 最大0=1遗传代数2000。
四个机器人先各自按照遗传算法规划的最短路径前进, 如图5(a ) 。机器人R 1和R 4逐渐接近并进入彼
[4]Sun shudong , M o rris A S , Zlazala A . T rajecto ry
P lann ing of m u lti p le coo rdinati on robo ts u sing genetic . Robo tics , 1996, 14(2) :2272234. A lgo rithm
s [5]
Yong K Hw ang , M arendra A hu ja . A Po ten tial F ield A pp roach in Path P lann ing .
IEEE T ran sacti on s on
Robo tics and A u tom ati on , 1992, 8(1) :23232.