基于蚁群算法的清扫机器人路径规划设计

周冬冬;金诚谦;倪有亮

【摘 要】在国内外对蚁群算法理论研究与工程应用的基础上,采用蚁群算法对清扫机器人进行路径规划设计.通过分析蚁群算法原理,并结合家庭中清扫时清扫机器人所遇到的障碍物,通过环境建模实现清扫机器人的路径规划.清扫机器人硬件采用模块化的设计,将清扫机器人分成行走模块、清扫与吸尘模块、传感器模块.进行系统的综合调试.试验结果表明清扫机器人清扫面积重复率小于6％,避障成功率为93％,达到了工程精度的要求.

【期刊名称】《南京工程学院学报（自然科学版）》 【年(卷),期】2018(016)003 【总页数】5页(P34-38)

【关键词】清扫机器人;模块化设计;蚁群算法;路径规划 【作 者】周冬冬;金诚谦;倪有亮

【作者单位】南京工程学院,江苏 南京211167;农业部南京农业机械化研究所,江苏 南京210014;农业部南京农业机械化研究所,江苏 南京210014;山东理工大学,山东 淄博255000;农业部南京农业机械化研究所,江苏 南京210014 【正文语种】中 文 【中图分类】TP24

蚁群算法是20世纪90年代提出的一种新的进化计算方法[1],具有分布式计算、无

中心控制和分布式个体之间间接通信的特征.最早蚁群算法是蚂蚁系统，研究者们根据不同的改进策略对蚂蚁系统进行改进，开发了不同版本的蚁群算法,并成功地应用于优化领域.

目前蚁群算法理论研究主要集中在蚁群算法参数设置、蚁群算法改进、蚁群算法收敛性及工作机制探索、蚁群算法与其他算法融合等方面[2].文献[3]将遗传算法与蚁群算法融合，优化了蚁群算法中的参数和信息素，并将其运用于移动机器人路径规划中，取得较好的结果；文献[4]对蚁群系统信息素更新机制进行研究，增强每次迭代中找到最优路径蚂蚁的重要性，对其找到的路径增加额外的信息素，以此来提高路径规划的效率；文献[5]用蚁群算法对地下水监测网络的设计进行优化；文献[6]运用蚁群算法解决约束潮流问题,试验结果表明蚁群算法具有较高的可靠性和优化能力.文献[7]将蚁群算法运用于物流系统AGV路径规划,试验结果表明蚁群算法在路径规划上具有较好的路径搜索效率与可靠性；文献[8]运用蚁群算法进行移动机器人的路径规划，试验结果表明蚁群算法具有较好的稳定性与可靠性；文献[9-11]采用改进蚁群算法来实现清扫机器人全局路径规划，通过状态转移来选择蚂蚁下一步访问的地点，利用信息素局部更新规则更新路径上的信息素，在遍历所有地点后根据信息素全局更新规则对所有路径上的信息素进行更新.硬件系统由红外传感器、单片机、稳压电路、复位电路、显示电路与驱动电路组成，实现清扫机器人前进、后退、左右转、清扫与吸尘的功能.通过传感器模块检测机器人周围环境(是否有障碍物以及与障碍物之间的距离)，并经过传感器处理电路将数据传送到单片机上,单片机通过蚁群算法分析数据,进而将分析结果采用PWM波的形式来驱动电机，实现机器人的路径规划. 1 蚁群算法 (a) (b)

(c)图1 蚁群算法原理图

采用蚁群算法来实现路径规划，基本原理如图1所示.蚂蚁在寻找最优路径的过程中,经过蚂蚁群体的共同行为寻找到最优的路径[12].在寻找路径的过程中,蚂蚁会在其经过的路径上留下一定量的信息元素(很好地避免了对同一地方进行多次清扫),之后的蚂蚁会根据这些路径上所留下的信息元素的强弱选择合适的路径.当走到一个从未经过的路口时,会随机选择释放信息元素,信息元素的多少与路径的长短成负相关[13-15].随着时间的推移,较短路径上的信息元素将会不断增加,而其他较长路径上的信息元素则会慢慢减少甚至消失,最终蚁群会寻找到一条最优路径[16]. 图2 基于家庭障碍物的栅格图

假设清扫机器人的工作空间是一个二维区域，且在该区域内分布着大小不同的障碍物,这些障碍物的位置、大小已知,在清扫机器人进行路径规划过程中,障碍物位置固定不变.设清扫机器人以相同的单位清扫面积R移动,则以R为单位对工作空间进行划分，可得到清扫空间的栅格图.根据家庭障碍物的摆放情况将所有栅格分为空白栅格、障碍栅格，若某障碍物在一个栅格内，则视该栅格为障碍栅格；若某障碍物超出了一个栅格但在两个栅格内，则视该障碍物所占据的两个格栅为障碍栅格，其它以此类推.若一个栅格内没有障碍物，则视该栅格为空白栅格.栅格划分与设定后的清扫机器人工作空间如图2所示. 2 蚁群算法路径规划的实现

在清扫机器人清扫空间内，按从左到右、从上到下的顺序,依次标记栅格序号1,2,3,…,n,序号与栅格坐标系标号一一对应，Q={1,2,3,…,n}为栅格序号集.根据对应关系可知，f(0,0)的序号为1,f(1,0)序号为2,直至f(9,9)的序号为100.路径规划初始位置为序号0、目标位置为序号100.

1) 设蚁群中有k只蚂蚁，将其放置在出发点(序号为1的点f(0,0))处,同时将f(0,0)与序号1添加到禁忌表(tbauk)中；设最大步数为max；寻优步数计数器step初

始值为0,用数组C[*]来存储当前最优路径并初始化；N为当前时刻蚁群所得到的路径数目.

2) 将蚂蚁所在当前节点f作为中心,根据式(1)或式(2)选择要前进的节点： (1) (2)

式中:J为蚂蚁k所选f的节点序号；W为随机变量G在n步时，k由节点i转移到节点j的概率；b为期望启发因子(初始取5);a为信息启发因子(初始取0.5);Sij为机器人从栅格i转移到j的信息元素.逐渐减小信息启发因子a与期望启发因子b并进行不断的迭代,直到找到最优的匹配参数使得路径最短.

3) 对局部信息素进行更新.当k只蚂蚁全部完成后续节点的选择后按照公式 (3)

进行局部信息素更新(α为信息素挥发因子).

4) 对蚂蚁状态进行判断.若fm=fmax,即蚂蚁m达到终点,则在禁忌表中生成一条新的路径Lnew,同时如果为第一条路径,那么将其存入C[*]中,记为Lfirst并对全局信息元素更新,N=1. (4)

5) 如果Lnew不是第一条到达终点的路径,那么比较该路径与当前路径哪个最优,如果小于当前路径,那么就用该路径代替当前路径作为最优路径,同时对全局信息元素进行更新,N加1.如果当N>k,即最优路径数目大于蚂蚁数,那么N=0.并清空禁忌表. 6) 寻优步数计数器step加1,如果蚂蚁行走步数达到最大步数max(大于83)且最

小步数为83(即完成全局路径),则路径规划停止,输出最优路径,否则跳转步骤2)继续执行.

3 清扫机器人系统设计

根据清扫机器人的功能需求,其控制系统应满足:1) 实现清扫机器人前进、后退、左右转；2) 实现清扫机器人的主动避障与全局路径规划；3) 实现自动清扫与吸尘. 图3 硬件系统结构图

图3为清扫机器人硬件系统设计构架.

本文采用模块化的设计理念，根据清扫机器人所要实现的自动避障、自动清扫与吸尘功能，将其分为行走模块、清扫与吸尘模块、传感器模块.各个电路模块采用软件protel绘制原理图并制作出PCB板.硬件系统原理图如图4所示行走模块:由4个行走步进电机组成，通过protel设计驱动电路(如图5所示)来实现电机驱动，控制电机实现清扫机器人前进、后退、向左、向右的功能.行走模块:由4个行走步进电机组成，通过protel设计驱动电路(如图5所示)来实现电机驱动，控制电机实现清扫机器人前进、后退、向左、向右的功能. 图4 硬件系统原理图

清扫与吸尘模块:由吸尘直流电机、吸尘机构、毛刷直流电机、扫刷组成，电机由单片机直接供电，不需要进行电机调速.

传感器模块:由红外传感器实现电路的避障,红外传感器受外界环境(如光线强度等)影响较小,它由一对红外线发射与接收管组成.发射管发出红外线(固定频率),如果前方有障碍物,那么红外线就会反射,如果接受管接受到反射回来的光线,那么红外传感器就会收到信号，同时会把信号(一个低电平信号)由接口发送到单片机，传感模块的电路原理图如图6所示. 图5 驱动电路原理图

图6 传感器模块电路原理图 4 系统调试

在试验场地对软硬件系统进行整体调试,进行了15组试验.模拟家庭环境障碍物的摆放位置与栅格图见图2，栅格总数为100个,其中障碍物栅格为17个,自由栅格为83个.清扫机器人在完成清扫任务的过程中较为成功地实现障碍物的规避，清扫面积重复率小于6%,清扫结果如表1所示.

表1 试验结果试验序号是否成功避障行走栅格数试验序号是否成功避障行走栅格数试验序号是否成功避障行走栅格数1成功856成功8611成功852成功877成功8312成功843成功838成功8313成功844成功849成功8514成功855失败7910成功8415成功86 5 结语

采用蚁群算法进行清扫机器人路径规划,运用栅格法对清扫机器人的工作环境信息进行描述，采用状态转移规则、局部信息素更新规则、全局信息素更新规则实现了最优的路径搜索;将搜索到的每一条路径保存到矩阵中，从而实现了机器人全局路径的覆盖.根据蚂蚁移动的步长，设置最大与最小步长，从而实现了面积清扫的重复率小于6%.

基于蚁群算法的清扫机器人系统采用蚁群算法实现机器人路径规划与主动避障;硬件由行走模块、清扫与吸尘模块、传感器模块组成,并进行软硬件综合调试试验;试验结果表明，改进期望因子与启发因子的蚁群算法实现了清扫机器人93%的避障成功率. 参考文献:

【相关文献】

[1] 叶兆莉，袁明新，程帅，等.移动机器人的一种烟花爆炸式新免疫规划算法[J].计算机仿真，2013，30(3)：323-326，375

[2] 徐晓晴，朱庆保.动态环境下基于多人工鱼群算法和避碰规则库的机器人路径规划[J].电子学报，2012，40(8)：1694-1700.

[3] 姚正华，任子晖，陈艳娜.基于分段自适应鱼群算法的煤矿救援机器人路径规划[J].矿山机械，2014，42(6)：107-111.

[4] 徐翔，梁瑞仕，杨会志.基于改进遗传算法的智能体路径规划仿真[J].计算机仿真，2014，31(6)：357-361.

[5] 孙波，陈卫东，席裕庚.基于粒子群优化算法的移动机器人全局路径规划[J].控制与决策，2005，20(9)：1052-1055，1060.

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

[7] 刘彬，陈特放，张仁津.动态和未知环境中基于改进粒子群优化的路径规划[J].计算机应用研究，2014，31(6)：1673-1676.

[8] 朱会杰，王新晴，张红涛，等.一种基于监工机制的改进蚁群算法[J].解放军理工大学学报：自然科学版，2014，15(2)：165-170.

[9] 柏继云，李士勇.基于agent的蚁群觅食行为建模及在机器人路径规划问题中的应用[J].计算机应用研究，2014，31(1):47-54.

[10] 潘杰，王雪松，程玉虎.基于改进蚁群算法的移动机器人路径规划[J].中国矿业大学学报，2012，41(1):108-113.

[11] 赵娟平，高宪文，符秀辉，改进蚁群优化算法求解移动机器人路径规划问题[J].南京理工大学学报，2011，35(5):637-641.

[12] 朱庆保，张玉兰.基于栅格法的机器人路径规划蚁群算法[J].机器人，2005，27(2):132-136. [13] 段海滨.蚁群算法原理及应用[M].北京:科学出版社，2005:100.

[14] 王沛栋，冯祖洪，黄新.一种改进的机器人路径规划蚁群算法[J].机器人，2008，30(6):554-560.

[15] 康冰，王曦辉，刘富.基于改进蚁群算法的搜索机器人路径规划[J].吉林大学学报(工学版),2014，44(4):1063-1068.

[16] 孙纯哲，林巨广，楼赣菲，等.凹形障碍全局路径规划的双蚁群完全交叉算法[J].农业机械学报，2008，39(7):149-153.