有所谓
针对移动机器人导航技术的研究是移动机器人
研究领域的核心，而路径规划是机器人导航技术中的研究热点[1].机器人路径规划的目的是为机器人规划出一条从起始点至目标点的最优或近似最优的行走路径[2].目前，机器人路径规划的方法有多种，主要可分为全局路径规划和局部路径规划[3]，全局路径规划 主要包括：栅格法、可视图法和一些神经网络算法[4] 等，局部路径规划主要包括：人工势场法、蚁算法、
粒子算法、遗传算法和A*寻路算法等.而多任务目标点的机器人路径规划相较于单点目标的路径规划要更为复杂. 目前，在机器人路径规划的研究中，大多数是针对单任务目标这一情况，对于多任务目标的研究较少[5].蒲兴成等[2]将反向学习策略思想应用到粒子算
静态障碍物下的遍历多任务目标机器人路径规划
杨帆1，2，薛亚冲1，2，李靖1，
2
（1.河北工业大学电子信息工程学院，天津300400；2.河北工业大学天津市电子材料与器件重点实验室，天津300400）路面
Traversal multi-task target robot path planning under static obstacles
YANG Fan 1，2，XUE Ya-chong 1，2，
LI Jing 1，2（1.School of Electronics and Information Engineering ，
Hebei University of Technology ，Tianjin 300400，China ；2.Tianjin
Key Laboratory of Electronic Materials and Devices ，Hebei University of Technology ，Tianjin 300400，China ）
Abstract ：In view of the problem that the computional cost of PSO-GA algorithm is too high and the single algorithm can not
guide the robot traversing the multitask target to walk on the obstacle map袁a new traversing multitask targets path planning method combining the classification of PSO袁genetic algorithm and A *algorithm is proposed.In path planning袁the classification of PSO and genetic algorithm are used to
calculate the optimal sequence of task exe鄄cution in the first袁and second the A *algorithm is used to avoid obstacle walking according to the target execution order.This method applies the crossover and mutation operation in the genetic algorithm to the PSO algorithm to improve the global search ability and stability袁which effectively suppresses the PSO to be easily localized.Simu鄄lation results show that the algorithm can plan the better execution order of the task target袁and under the same
target situation袁compared with PSO-GA袁the number of iterations is reduced by about 25%袁and the planning time is reduced by about 10%.Key words ：static obstacles ；classification of PSO-GA ；crossover and mutation ；A *algorithm ；multitasking goals ；robot;
path planning
摘要：针对粒子-遗传算法存在计算成本过高并且单一算法不能解决有障碍物存在的地图上遍历多任务目标点
的移动机器人避障行走问题，提出一种分级粒子、遗传和A *算法相结合的遍历多任务路径规划新方法.规划时，首先使用分级粒子-遗传算法计算出执行任务的最优顺序，然后使用A *算法按照目标执行顺序进行无碰撞路径规划.该方法将遗传算法中的交叉、变异应用到粒子算法中，提高粒子算法的全局寻优能力和稳定性，并对粒子进行了等级划分，不同等级的粒子在下次迭代中采用不同的操
作.仿真实验证明：该算法能够规划出更优的任务目标执行顺序，并且同等目标情况下，相比于粒子-遗传算法，迭代次数降低约25%，规划时间降低约10%.
关键词：静态障碍物；分级粒子-遗传算法；交叉和变异；A *算法；多任务目标；机器人；路径规划中图分类号：
TP241.3；TP301.6文献标志码：A 文章编号：员远苑员原园圆源载（圆园18）
园4原园园65原07收稿日期：
2017-10-30基金项目：河北省自然科学基金项目（E2016202341）；河北省高等学校科学技术研究项目（BJ2014013）
通信作者：杨帆（1964—），男，教授，博士生导师，主要研究方向为图像处理、机器视觉与模式识别.E-mail ：
***************** 天津工业大学学报
允韵哉砸晕粤蕴韵云栽陨粤晕允陨晕孕韵蕴再栽耘悦匀晕陨悦哉晕陨灾耘砸杂陨栽再
第37卷第4期圆园18年8月
Vol.37No.4August 2018
DOI ：10.3969/j.issn.1671-024x.2018.04.012
. All Rights Reserved.
第37卷天津工业大学学报
法中，这种改进虽然一定程度上抑制了单个粒子的早熟现象，并且提高了算法收敛速度，但并没有有效解决粒子算法容易陷入局部最优的弊端，而且算法仿真中没有考虑目标点较多的情况.曹洁等[4]提出了一种改进蚁算法对捡球机器人进行多目标路径规划，将蚁算法中信息素强度Q设为动态，这种改进虽然解决了蚁算法可能出现的停滞现象，且提高了一定的求解精度，但改进后的算法还是容易陷入局部最优，且算法在进行路径规划时没有考虑到障碍物的存在，算法应用范围受到极大限制.针对这些问题，本文提出了一种基于粒子-遗传-A*算法的静态障碍物下的遍历多任务目标机器人路径规划.在进行路径规划时，首先使用粒子-遗传算法规划出最优目标点行走顺序，再使用A*算法进行避障行走.该算法将遗传算法中的交叉和变异操作应用到粒子算法中，显著提高了粒子算法的稳定性和寻优能力.
1算法理论基础
1.1栅格法
采用栅格法构建地图模型，栅格法在构建地图模型时，将障碍物区域即不可行走区域标为1，将自由区域即可行走区域标为0.所构建的地图模型详尽程度取决于划分的栅格大小[5].栅格越小，构建的地图模型越详细，但会占用较大的存储空间，并且会使得路径
规划计算量成指数增加，规划速度也会降低[6].栅格过大，会使得地图模型不够详尽，不能准确的描述出障碍区域和自由区域的信息，不利于有效路径的规划. 1.2A*算法
A*算法是一种启发式搜索算法，在进行路径规划时，A*算法会对将要进行搜索的点预估代价值，代价值预估函数为：
F（n）=G（n）+H（n）（1）式中：G（n）表示从其实节点到任意节点n的代价；H（n）表示从节点n到目标点的启发式评估代价.
改变G（n）和H（n）的代价值能够调节A*算法的搜索行为，当G（n）过大，H（n）过小时，A*算法扩展节点会增多，搜索速度会变慢，但能够规划出一条最优的行走路径；当G（n）过小，H（n）过大时，A*算法搜索速度很快，但不能保证规划出的路径为最优.A*算法有2个存储列表：OPEN（开启列表）和CLOSE（关闭列表），OPEN列表中存放等待检查方格，CLOSE列表中存放不需要检查的方格.
A*算法在栅格法构建的地图模型中进行路径规划时，机器人有8个可运动的方向[8]，分别为：前方、左方、右方、后方、左前、右前、左后、右后，如图1所示.图1中：A为起始方格；T为目标节点；灰区域为障碍物区域（在后文的仿真试验中设为蓝）；实线箭头为机器人最佳前进方向.
1.3粒子算法
粒子算法（particle swarm optimization，PSO）[7]最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于对鸟觅食行为的研究.在PSO中，每个优化问题的潜在解都可以想象成N维搜索空间上的一个点，称之为“粒子”（particle）[8]，所有的粒子都有一个被目标函数决定的适应值（fitness value），每个粒子还有一个速度决定它们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索[8].
粒子算法的速度和位置更新公式为：
V n+1
iD=w伊V n+1iD+C1伊琢（P n+1iD-X n+1iD）+
C2伊茁（P n+1iD-X n+1iD）（2）X n+1iD=X n+1iD+酌伊V n+1iD（3）式中：w为保持原来速度的系数，又称为惯性权重；n为迭代次数；D为粒子维度；C1是单个粒子历史最优值的权重系数；C2是所
有粒子体最优值的权重系数；琢、茁为区间[0，1]之间的随机数；酌为速度系数，设为1.
1.4分级粒子-遗传算法
湖南人文科技学院学报本文对普通粒子-遗传算法进行了改进，在其基础上对粒子进行了等级划分，分为：精英粒子、优等粒子、中等粒子和劣等粒子4个类别.其中精英粒子为单个粒子，是适应度值最优的粒子，本文中适应度值为距离总和，因此将适应度值最小的粒子设定为精英粒子；优等粒子由多个粒子组成，是除精英粒子外，适应度值较小的前几个粒子；劣等粒子由多个粒子构成，是适应度值较大的最后几个粒
图1A*算法规划示意图
Fig.1A*algorithm planning diagram
F1
1H1
F8
8H8
F2
G2H2
F3
G3H3
F7
7H7
F6
G6H6
F5
G5H5
F4
G4H4
66--
. All Rights Reserved.
第4
期子；其余适应度值处于中间位置的粒子全部设为中等粒子.精英粒子作为下次迭代中的父代粒子，不参与交叉和变异；优等粒子在下次迭代中不参与交叉操作，仅参与变异操作；中等粒子在下次迭代中既参与交叉操作，又参与变异操作；劣等粒子采取淘汰操作，即舍弃当前的劣等粒子，并重新初始化一批粒子加入到总粒子中，新初始化加入的粒子数目与被淘汰的粒子数目相同.
本文实验中，粒子总数目为50，在对粒子分级时，精英粒子个数设为1，优等粒子中粒子个数设为5，劣等粒子中粒子数设为10，中等粒子中粒子数设为34.
2
分级粒子-遗传算法结合A *算法进行路
径规划
在大多数情况下粒子算法相比遗传算法拥有更快的规划速度，但由于粒子的速度和位置更新信息依赖于当前搜索到的最优解，这就导致粒子算法在规划时容易陷入局部最优[10].而遗传算法具有交叉算
子和变异算子[11]，能够产生具有新的解集的种[12]，因
而在搜索最优解过程中不易陷入局部最优，使得算法
能够更好的收敛于最优解.因此，结合两种算法的优
点，在粒子算法中引入遗传算法的交叉和变异操作，以此来扩大粒子的多样性，增强粒子的全局随机搜索能力.
目前，遗传算法中交叉方法有：单点交叉、局部邻域交叉、多点交叉、均匀交叉等[13]，本文中采用随机多点交叉的方法，即交叉点的位置随机、数量随机，在对粒子进行变异操作时也采用随机多点变异的方法.这种交叉和变异操作增加了粒子的多样性，实验仿真证明，在处理复杂情况下的问题时，算法在全局搜索最优解能力和稳定性方面有显著提升.
分级粒子-遗传-A*算法进行机器人多任务目标路径规划主要包括3部分：淤构建地图模型；于寻最优行走路线；盂进行避障行走.其具体执行步骤如下：
（1）使用栅格法构建地图模型，如图2所示.栅格标号方式如图2（a ）所示，构建障碍物地图时，将障碍物所对应的标号保存在障碍物信息函数map_obsta原cle 中.考虑到机器人的安全和方便路径规划，对障碍物进行扩大处理，如图2（b ）所示，其中红区域为实际障碍物大小，蓝区域为扩大后的障碍物区域，障碍物扩大值为机器人的半径R .
（2）将目标点信息导入地图中（起始点也作为目
标点），计算任意2个目标点之间的曼哈顿距离，并将所得距离保存在矩阵target_d 中，target_d 为n 行n 列方阵，n 为目标数.target_d （i ，j ）=（X_target i -X_target j ）+（Y_target i -Y _target j ），i 屹j
（4）式中：X_target i 为目标点i 的横坐标；Y_target i 为目标点i 的纵坐标；X_target j 为目标点j 的横坐标；Y_target j 为目标点j 的纵坐标.
（3）计算种适应度值并记录当前全体最优和个体最优，适应度值函数fitness_d 表示在不存在障碍物情况下机器人遍历所有目标点后的经过的曼哈顿距离总和，单个粒子的适应度值fitness_d m 计算如公式（5）:
fitness_d m =target_d （m 1，n ）+target_d （m 2，n ）+…+
target_d （m n ，n ）（5）
irc式中：
m 1，m 2，…，m n 为1~n 之间的正整数，且m 1屹m 2屹…屹m n .
（4）对个体最优进行交叉和变异操作，记录求得
的新适应度值，并将求得的值与历史最优值进行比较，若当前最优小于历史最优，则替换历史最优，并删除交叉和变异操作中产生的相同元素；若当前最优大于历史最优，则保持历史最优不变.
（5）返回步骤（3）重新执行，若求出最优解或者迭代次数达到最大值，终止求解最优行走路线程序，并保存最优行走顺序.
（6）由于步骤（5）中求得的最优行走顺序是将起始点与目标点混合排序的，因此需要将起始点提取到行走路线第一位，且保持行走顺序不变.
（7）调用A*算法，并将map_obstacl e 中的障碍物信息导入到A*算法的CLOSE 列表中，然后以Start 点为机器人起始点，Target 为各个目标点，按照步骤（6）中行走顺序进行避障行走.进行避障行走时，H （n ）的值设为起始节点到当前节点的距离，G （n ）的值设为当前节点到目标节点的距离，即：
H （n ）=[（
X start -X node ）2+（Y start -Y node ）2
]姨（6）
（a ）栅格标号方式（b ）障碍物扩大处理
图2栅格法构建地图
Fig.2Build the map using grid method
R
212223242520191817161112131415109
8
76
1
234
5杨帆，等：静态障碍物下的遍历多任务目标机器人路径规划
67--
. All Rights Reserved.
第37卷
天津工业大学学报
G （n ）=[（
X node -X target ）2+（Y node -Y target ）2
]姨（7）
式中：
X start 表示起始节点横坐标；Y start 表示起始节点纵坐标；
X node 表示当前节点横坐标；Y node 表示当前坐标纵坐标；
X target 表示目标节点横坐标；Y target 表示目标节点纵坐标.
（8）为机器人规划出行走路程最短、安全无碰的行走路径，程序终止运行.
分级粒子-遗传-A *算法的路径规划流程图如
图3所示.
表1所示为粒子个数都为50，C 1=C 2=1时，
各算法在不同目标数下的求解情况.任务目标点数不同时算法规划对比如图4所示.图4（a ）和（b ）、（c ）和（d ）、（e ）和（f ）分别为任务目标数为5、15和30时的目标点位置分布及规划效果，图4中（a ）、（c ）、（e ）为粒子-遗传算法规划，图4中（b ）、（d ）、（f ）为粒子算法规划.
由图4和表1可以看出，当目标数量较少时，标准粒子算法和粒子-遗传算法得出相同的最优解，且标准粒子算法在规划时间上要优于粒子-遗传算法；当目标数量较多，目标点位置情况较复杂
时，标准粒子算法进行规划时，在迭代次数和时间上都远远高于粒子—遗传算法，且规划出的行走顺序不能保证为最优.目标数较少时，粒子-遗传算法与分级粒子-遗传算法规划效果差距不大，当目标数量为15时，在迭代次数上，分级粒子-遗传算法比粒子-遗传算法降低了25%，在规划时间上，降低了7.5%；当目标数量为30时，在迭代次数上，分级粒子-遗传算法比粒子-遗传算法降低了约26.2%，在规划时间上，降低了约11.1%.并且分级粒子-遗传算法得出的最终结果要优于粒子-遗传算法的结果.
分级粒子-遗传算法和粒子-遗传算法规划时最小适应度值变化如图5所示.
图5（a ）和（b ）分别为分级粒子-遗传算法和粒子-遗传算法在图4（d ）和（f ）中目标分布情
况下规划时的最小适应度值变化曲线.红曲线为分级粒子-遗传算法规划所得，蓝曲线为普通粒子-遗传算法规划所得.可以看出，分级粒子-遗传算法不论是在迭代次数还是规划结果上都优于普通粒子-遗传算法.
简单和复杂静态障碍物下的路径规划如图6所示.图6（a ）为简单静态障碍物下的遍历多目标机器人路径规划图，图6（b ）为复杂静态障碍物下的遍历多目标机器人路径规划图，图中障碍物以蓝实心栅格表示，各目标点与起始点之间的红连线为任务目标点的执行顺序，蓝连线为规划出的机器人行走路径.任务目标点个数为11，以标有Target 的绿方块表示；左下角标有Start 的绿方为起始点，坐标为
（3.5，1.5）.图6（c ）为在复杂静态障碍物下规划时适应度值随迭代次数的变化曲线，可以看出，当迭代次数约为27时，适应度值达到最小，为69.45，且当迭代次数增加时，适应度值保持不变，表明算法寻到了
图3分级粒子-遗传-A*算法路径规划流程Fig.3Classification of PSO-GA-A*-algorithm path
planning procedure
表13种算法规划对比
Tab.1Comparison of three algorithms
算法目标数量最短距离/m （5次取平均值）迭代次数（5次取平均值）程序运行时间/s （5次取平均值）5
42.37591
1.693182
1561.1318
232 1.96670330109.628515377.237629542.37591 1.9769341557.229644 2.369421
3095.1317421 2.712598分级粒子-遗传算法
542.3759
1
1.8236211557.229633
2.193485
3094.2228311 2.412049
粒子-遗传算法标准粒子算法
68--
第4期
1301201101009080706050
迭代次数500
450350300250200150100500
（a ）目标点数为15时，适应度值变化40026024022020018016014012010080
迭代次数
1000
9007006005004003002001000（b ）目标点数为30时，适应度值变化
800图5分级粒子-遗传算法和粒子-遗传算法规划时最小适应度值变化
Fig.5Minimum fitness value that calculated by hierarchical particle swarm genetic algorithm and particle
swarm genetic algorithm
最优解.
图6（b ）起始点与目标坐标位置矩阵为ST ，矩阵
第一行为各目标点的序号，第二行为目标点横坐标，
第三行为目标点纵坐标.图4任务目标点数不同时算法规划对比
Fig.4Comparison of algorithm planning in different task target points
（a ）任务目标点个数为5
（b ）任务目标点个数为5
X 轴/mhypermesh
X 轴/m
X 轴/m
（c ）任务目标点个数为15
X 轴/m
（d ）任务目标点个数为15
X 轴/m
（e ）任务目标点个数为30X 轴/m
（f ）任务目标点个数为30
ST =
1234567891011123.5 5.514.516.5 4.58.510.5 2.5 2.517.5 6.5 2.51.5 3.5 3.5 3.511.510.5
6.5
12.5
5.5
17.5
保师附小在线校园6.5
18.5
蓘
蓡
杨帆，等：静态障碍物下的遍历多任务目标机器人路径规划
69--
. All Rights Reserved.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议