杨岱川,文成林

(杭州电子科技大学系统科学与控制工程研究所，浙江 杭州 310018)

基于蚁群和改进PRM算法的多目标点路径规划

杨岱川,文成林

(杭州电子科技大学系统科学与控制工程研究所，浙江 杭州 310018)

针对移动机器人最短路径问题，设计了一种包含了蚁群算法和改进PRM算法的融合算法.首先，根据实际地图建立了栅格化地图模型，并将地图模型用瘦化方法优化，然后，用蚁群算法排出其优先级，用改进的PRM算法进行路径规划，最后，给出了基于实际地图多目标点的仿真路径以及与同类算法的结果对比，改进算法比Bug2算法和D*算法快约2 s，验证了蚁群算法和改进PRM算法融合的有效性.

移动机器人；蚁群算法；概率地图算法；路径规划

0 引 言

移动机器人的路径规划在工业和民用领域得到了广泛的应用，例如扫地机器人[1]、旋翼快递飞行器以及采摘机器人[2]等，而各方面相关研究也在不断推进.目前大多数算法研究的是二维平面的两点间路径规划问题[3]，如A*算法[4]、Dijkstra算法[5]和粒子群算法[6]等.单独使用一种算法虽然能够解决实际地图上的路径规划问题，但是对于多任务点问题难以胜任.为此，本文提出采用蚁群算法对多目标点执行顺序进行规划.结合地图优化方法和改进的概率地图算法(Probabilistic Roadmap Method，PRM)对带有实际地图障碍物的多个目标点进行先后排序和路径搜寻，较好地解决了目前存在的移动处理器响应速度慢和不能一次规划多个目标点路径的问题.

1 实际地图建立

机器人导航中地图的表示方法大致有特征地图[7]、拓扑地图[8]和栅格地图[9].本文地图建模时使用的是栅格地图.栅格地图把整个地图化为一个一个的栅格，并分别指出每个栅格是否被障碍物占据，形成了一个连通图，通过指定起始栅格和目标栅格，利用搜索算法进行路径搜索.这种方法应用广泛，有较强的鲁棒性，由于其离散化的设计，地图也便于维护.

1.1 任务与地图建模

1.2 地图优化

在传统的PRM方法中存在狭窄通路(narrow passage)问题，其根本原因是PRM方法产生的随机采样点在空间上的分布不够均匀，在狭窄区域或在转角的分布点连线较少甚至没有，导致明明存在的通路却不能在运算中被规划出来.

针对该问题，普遍采用的解决方法有MLDP[10]、桥测试[11]等，本文使用障碍物合理瘦化的方法来解决.根据实际障碍物轮廓进行等比例收缩，从而扩大通路面积，同时把机器人看做为栅格地图上的一个点.

图1 某高校校园实际地图与栅格模型

地图的优化也是一个“预计算”的过程，只要工作区域的地图不变，优化后的地图可以保留到下次再使用，所以对于栅格地图的瘦化过程所花费的时间并不计入总规划时间.

2 蚁群算法与改进PRM算法结合

2.1 蚁群算法与路径点排序

蚁群算法[13]是从蚂蚁在觅食过程中寻找路径的方法中得到启示.本文使用的是基于Ant-Cycle模型的算法，有

(1)

蚁群算法在众多路径点中选出一条不重复经过的连线，并且以尽量缩短路径总长度为优化目标.每两个路径点之间的距离为

(2)

本文所求的运动路线为

(3)

2.2PRM算法改进

概率地图算法PRM通过随机采样进行碰撞检测，并获取所需要的障碍物或自由空间信息，再进行路径规划.

普通PRM算法要想得到更好的结果，直接增加Ga中采样点的数量，让更多的点落入狭窄通路即可.配合前面所说的障碍物瘦化方法，在一定程度上进一步解决了狭窄通路问题.但采样点增多，运算量也会成指数级增长，这对大地图上依靠增多采样点来保证算法的可靠性提出了极高的计算性能要求.本文提出一种邻域半径r可动态变化的改进方法，代替了由最近k个节点或者固定半径r连接构建网络的方法，更好地解决了这个问题.

动态变化的邻域半径r指的是在地图大小一定时，r并不是地图边长的固定倍数，而是随采样点数目的变化而变化.具体的算法改进为

(4)

3 仿真实验

3.1 不同参数仿真结果

以南大门到图书馆为例，在地图中采用原始PRM算法和不同半径r及采样点数目的RPM算法仿真50次对比，得到结果如表1所示.

表1 不同参数设置的PRM算法结果

从表1中可以看出，采样点的增减对算法复杂度的影响效果最显著.通常的PRM算法在采样点增多一倍的情况下复杂度增加到近4倍，但是对邻域半径进行缩短处理后，复杂度随之降低.对上述结果进行分析与拟合，得出新的半径公式

r=0.015 05E-0.207 6V+39.15

(5)

表示针对图1(c)的PRM算法中边的数目与顶点和邻域半径的关系.

3.2 结果分析与其他方法对比

在复杂度差不多的情况下，边的数量越多，效果越好，所以本文的优化目标就是在复杂度可以接受的情况下得到Emax.如表2所示，采样点150、邻域半径22的情况是相对优秀的参数，相比之下，采样点200、邻域半径12与之复杂度相近，但是边数更少.同时也通过画图验证分析，图2中灰色为障碍物(建筑，水池等)，黑色点为采样点，灰色大圆点为要路过的采样点，灰色粗线条为规划出的路径.在目前绝大多数的研究主要针对的都是两点间的寻路，故针对从[42;5]南大门到[51;70]图书馆进行了50次两点间的寻路仿真及算法对比，如表2所示.

表2 代表性的参数结果

从表2的代表性统计数据上看出，改进PRM路径网络明显比另外两种基于PRM的算法对地图的覆盖全面.由此可以说明，采用动态变化邻域半径的改进PRM算法可以渐进达到最优参数，从而保证运算量合理的情况下有最优的规划，表现了改进方法的优越性.同时还比较了文献[12]中的两种常用算法：类D*算法与bug2算法.虽然这两种方法的路径更好，但是从用时看出算法的复杂度比新的改进算法高很多.并且类D*算法与bug2算法无法一次完成下一节中四点快递目标点的规划，而是需要至少3次运行，这样更增加了运算时间.

3.3 实际地图仿真

本文1.1节中提到地图上有4个目标点：[42;5]南大门、[51;70]图书馆、[95;98]北一门、[70;40]第三教学楼，要求机器人走过4个点，并且寻求一条最短的路径.首先使用蚁群算法规划先后顺序为南大门→第三教学楼→北一门→图书馆，之后再运行改进的PRM算法寻找路径，得到最终路径如图2所示.

图2 最终路径规划

图2(a)-(d)依次展示的是从南大门到第三教学楼，再到北一门，然后到图书馆，最后回到南大门的路径.这些路径并非十分光滑、平直，但是合理可行.

4 结束语

针对多目标点寻路问题，本文给出了一种基于蚁群算法和PRM算法的改进路径规划方法，将大多数规划方法的两点规划扩展到多点规划.改进算法针对栅格化的地图模型，进行了障碍物瘦化，成功找出合适路径，并缩减了运算时间，提高了反应速度.针对当前移动机器人领域发展趋势，多机器人的任务目标分配和动态地图上的路径规划均可作为进一步的研究方向.

[1]张健,陈立伟,郭玉骄,等.自动清扫机器人研究[J].中国高新技术企业,2015(10):10-11.

[2]黄玲,胡蔚蔚.基于改进蚁群算法的果蔬采摘机器人三维路径规划[J].农机化研究,2016(9):38-42.

[3]史恩秀,陈敏敏,李俊,等.基于蚁群算法的移动机器人全局路径规划方法研究[J].农业机械学报,2014,45(6):53-57.

[4]林巍凌.引入导航网格的室内路径规划算法[J].测绘科学,2016,41(2):39-43.

[5]裴小兵,贾定芳.基于模拟退火算法的城市物流多目标配送车辆路径优化研究[J].数学的实践与认识,2016(2):105-113.

[6]张万绪,张向兰,李莹.基于改进粒子群算法的智能机器入路径规划[J].计算机应用,2014,34(2):510-513.

[7]朱建国,高峻峣,李科杰,等.室内未知环境下移动机器人特征地图创建研究[J].计算机测量与控制,2011,19(12):3044-3046.

[8]苏丽颖,宋华磊.基于激光传感器构建环境拓扑地图[J].传感器与微系统,2012,31(9):64-66.

[9]杨兴,张亚.基于改进栅格模型的移动机器人路径规划研究[J].农家科技旬刊,2016(3):416.

[11]HSU D, JIANG T, REIF J, et al. The bridge test for sampling narrow passages with probabilistic roadmap planners[C]//Robotics and Automation, 2003. Proceedings. ICRA'03. IEEE International Conference on. IEEE, 2003,3:4420-4426.

[12]CORKE P. Robotics, Vision and Control[M]. Berlin:Springer, 2011:91-97.

[13]COLORNI A, DORIGO M, MANIEZZO V, et al. Ant system for job-shop scheduling[J]. Operations Research Statistics & Computer Science, 1994,34(1):39-53.

Multiple Targets Robot Path Planning Based on Ant Colony and Improved Probabilistic Road Map

YANG Daichuan, WEN Chenglin

(InstituteofSystemScienceandControlEngineering,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Aiming at shortest path of robot path planning, this paper designs an ant colony algorithm(ACA) combine with improved probabilistic road map(PRM) method of moving robots in real map, which need to pass by several work points and back to starting point in a shortest way. Firstly, building a model of grid of work space and diminish it, then work out a priority level of work points, next using improved PRM method to plan a path, and finally gives the results of simulation based on real map, and results compared with other algorithm to show the reliability of this fusion algorithm. Improved algorithm is faster than Bug2 and D*method for 2 seconds, which proved the effectiveness of it.

moving robot; ant colony; probabilistic road map; path planning

10.13954/j.cnki.hdu.2017.03.013

2016-10-14

国家自然科学基金资助项目(61304186;U1304615)

杨岱川(1992-)，男，四川乐山人，硕士研究生，机器人学.通信作者：文成林教授，E-mail：wencl@hdu.edu.cn.

TP24

A

1001-9146(2017)03-0063-05