基于改进遗传算法的移动机器人路径规划

２０１２年第２３期　ＳＣＩＥＮＣＥ＆ＴＥＣＨＮＯＬＯＧＹ　ＩＮＦＯＲＭＡＴＩＯＮ　ｏ科教前沿０　科技信息　

基于混沌遗传算法的机器人路径规划　

刘福　张殿富２　ｆ　１．武警工程大学研究生管理大队３８队陕西西安７１００８６；　２．武警工程大学通信与信息技术研究所陕西西安７１　００８６）　

【摘要】本文将混沌理论与遗传算法结合起来，提出了一种新的混沌遗传算法来解决机器人路径规划问题。首先，通过将障碍物进行“膨　化”处理以简化避障的运算，然后，将混沌优化的遍历性和随机性特点引入到遗传算法，防止和克服了进化过程中的早熟收敛情况。仿真试验表　明，在未知环境下本文设计的算法能够规划出更加优化的路径，并能实现安全避障。　【关键词】路径规划；遗传算法；混沌；避障　

０引言　路径规划是移动机器人导航的核心环节之一．它的目标是按一种　或几种性能指标（如运动路径最短、不与障碍物碰撞、用时最短、路径　平滑等）寻找搜索一条从起始状态到目标状态的最优或者近似最优的　无碰路径。根据环境信息的获取方式，路径规划可分为两种：基于模型　的全局路径规划和基于传感器的局部路径规划Ⅲ。局部路径规划因为　环境信息全部未知或部分未知．增大了寻找最优路径的难度１２１。近年　来．在机器人路径规划算法中．智能算法得到了很大的推广和应用。常　用的方法有人工势场法、模糊逻辑法、神经网络法、遗传算法等　。本文　将遗传算法与混沌算法结合起来，以遗传算法为基础，通过研究混沌　理论．利用混沌的随机性．在种群中加入扰动以避免遗传算法中的早　熟收敛现象．构成混沌遗传算法．在解决机器人在未知环境下的路径　规划问题中取得了较好的效果　１　问题描述与环境建模　设二维工作区域ｃ分布着多个障碍物０６ｓ．机器人Ｒｏｂ从起始点　ｓ要运行到终点Ｇ．路径规划的目标路径是从起点ｓ到终点Ｇ安全避　开障碍物所经过的一系列点的集合，并且保证路径最优。　本文假设所有的障碍物为凸形障碍物。为简化运算，可首先对障　碍物进行膨化处理。将移动机器人模型化为点状机器人．同时将工作　区域中障碍物．根据机器人的实际尺寸进行相应的膨化处理。处理过　程见图１。障碍物的半径膨化为　～　＋Ｒ　。其中，Ｒ　为机器人的　半径，Ｒ　为障碍物的半径。此时，机器人可看作一个质点。机器人能够　躲避动态障碍物就等同于这个质点能够避开经过膨化处理的动态障　碍物　

收稿日期：２０１９⁃１０⁃１５；修回日期：２０２０⁃０３⁃０２ 基金项目：国家重点研发计划资助项目（２０１８ＹＦＦ０２１４７０４）作者简介：赵明（１９９６⁃），女，山东青岛人，硕士研究生，主要研究方向为机器学习、深度学习、计算机视觉、多智能体、路径规划；郑泽宇（１９７６⁃），男，四川成都人，研究员，博士，主要研究方向为数据挖掘、复杂系统、时序列分析、风险预测；么庆丰（１９９５⁃），男，辽宁鞍山人，硕士研究生，主要研究方向为强化学习、多智能体、路径规划（ｙａｏｑｉｎｇｆｅｎｇ＠ｓｉａ．ｃｎ）；潘怡君（１９９２⁃），女，辽宁沈阳人，助理研究员，博士，主要研究方向为数据分析、机器学习、鲁棒主元分析；刘智（１９９４⁃），男，辽宁阜新人，博士研究生，主要研究方向为机器学习、深度学习、自然语言处理、自然语言理解、智能医疗、计算机视觉．基于改进人工势场法的移动机器人路径规划方法∗

赵　明１，２，３，郑泽宇１，２，３，么庆丰１，２，３，潘怡君１，２，刘　智１，２，３（１．中国科学院沈阳自动化研究所，沈阳１１００１６；２．中国科学院机器人与智能制造创新研究院，沈阳１１０１６９；３．中国科学院大学，北京１０００４９）摘　要：人工势场法是机器人局部路径规划常用算法，但是人工势场法中机器人会陷入局部稳定点的状况，基于此提出了域—人工势场法解决多目标点任务中局部稳定点问题。首先加入小范围强作用力的域势场，帮助机器人在陷入局部稳定点时通过域场逃离局部稳定点；其次为了域场范围难以确定的问题，进一步提出根据地图情况自动调整域场的大小的自适应域—人工势场法，解决不同地图情况局部稳定点的问题；最后加入域引导势场，对启发点进行域势场传递，解决复杂障碍下的局部稳定点问题。实验证明自适应域—人工势场法和域引导势场在解决多目标点和复杂障碍物局部稳定点问题的作用。关键词：路径规划；人工势场；人工智能；自适应０　引言随着机器人和人工智能理论的不断发展，自主式移动机器人技术日益成熟［１］，现已在工业、军事、医疗、服务等诸多领域得到广泛应用。与此同时，机器人所面临的任务也愈加复杂，所处环境由原来的单一机器人、静态环境转变为多机器人、动态环境。因此，近年来对复杂系统中机器人自主智能控制技术的研究得到了学术界和工业界的广泛关注，而路径规划及导航作为其中的关键性技术成为了目前机器人学的研究热点之一［２，３］。在复杂情况中的路径规划中需要多机器人协作，因为单个机器人无法完成某些需要协作的任务，必须依靠多个机器人才能完成。例如机器人搬运重物，对该类任务也许可以通过设计一个能力特强的机器人来完成，但从设计的复杂性和成本等方面考虑，这样的方案不如设计成多个功能简单的机器人来执行。并且对于可以分解的任务来说，多机器人可并行地完成不同的子任务，这比单个机器人完成所有的子任务所花时间少。这种情况下使用多机器人可提高工作效率，如多位置区域建图、固定区域探雷等均属于此类任务［４］。路径规划分类基于部分区域信息的局部路径规划和基于完整区域信息的全局路径规划，多机器人任务中需要较高灵活性和实时性，需要更多依靠局部路径规划，如人工势场法［５］、启发式Ａ∗算法［６］、模拟退火算法［７］、粒子群算法［８］等都是常见的局部路径规划算法。这些传统方法在单机器人中具有良好效果，但是在障碍物和机器人数量增多、多机器人需要协作合作的情况下难以保持算法的有效性，近年来引起国内外学者的广泛兴趣。Ｓｃｈｗａｇｅｒ等人［９］提出一种多机器人在具有大量未知信息的环境中的行为控制方法，使用贝叶斯过滤器帮助机器人进行在线控制。Ｚｈａｏ等人［４］提出使用模糊逻辑控制处理动态变化的环境，使用两种模糊控制器进行控制，一种用于避障，另一种用于目标定位。但是这些方法没有人工势场法结构简单、实用性强、路径平滑的优点。近年来有很多基于人工势场法改进的方法。胡小平等人［１０］加入了一个全局防止拥堵的防堵势场和防止碰撞的社群势场来平衡机器人移动与避障。张立阳等人［１１］提出结合模糊控制与人工势场法对斥力系数和引力系数根据环境调整来轨迹跟踪。仇国庆等人［１２］将多机器人与遗传算法结合，利用最优基因来调整机器人内在参数，并加入领航跟随法，保证队形的稳定性。本文对人工势场进行修改，加入了自适应的域势场，帮助机器人根据域势场快速到达目标点，避免陷入叠加势场带来的局部稳定点，改进后的算法能够提高机器人工作效率，避免停滞在环境中，最后使用域势场的域信息作为交流信号，加强多机器人的协作能力，提高路径规划的效率。１　人工势场法１􀆰１　人工势场法基本理论传统人工势场由两种势场叠加而成，将环境中的物体看做虚拟力场中的质点，目标点对机器人提供引力，形成引力势场；障碍物则提供斥力，形成斥力势场。障碍物处的势能较高，而目标点处的势能较低，在势场合力的驱动下，机器人沿着势函数从势能高的地方向势能低的方向运动，最终找到了一条可以到达目标点的无碰路径。目标点的作用吸引力覆盖整个地图，使机器人从地图的任意位置均可以感受到该目标点的作用力，而障碍物只对一定距离内的机器人产生排斥力，这是因为只有在距离障碍物很近时才需要进行障碍物的躲避。传统人工势场的引力势场函数为Ｕａｔｔ（ｑ）＝ｋａｔｔ×（ｑ－ｑｇ）２２（１）其中：Ｕａｔｔ（ｑ）为目标点在位置ｑ产生的引力场；ｋａｔｔ为目标点的引力系数，引力系数越大说明目标点具有更强的吸引力；ｑ为位置坐标；目标点所在坐标为ｑｇ，所以ｑｇ处势场为０，距离ｑｇ越远的地方具有更大的势场。引力由引力势场的负梯度计算可得Ｆａｔｔ（ｑ）＝－▽Ｕａｔｔ（ｑ）＝－ｋａｔｔ｜ｑ－ｑｇ｜（２）类似地，斥力势场函数为Ｕｒｅｐ（ｑ）＝１２ｋｒｅｐ１ｑ－ｑ０－１ｐ０æèçöø÷２ｑ－ｑ０≤ｐ００ｑ－ｑ０＞ｐ０ìîíïïïï（３）其中：Ｕｒｅｐ（ｑ）为障碍物在位置ｑ产生的斥力场；ｋｒｅｐ为障碍物的斥力系数，斥力系数越大说明障碍物周围具有更强的排斥力；ｑ－ｑ０为当前坐标与障碍物距离；障碍物的斥力场范围大小为ｐ０，超过该范围则机器人感受不到该障碍物的排斥力。使用斥力势场计算斥力：Ｆｒｅｐ（ｑ）＝－▽Ｕｒｅｐ（ｑ）＝１ｑ－ｑ０－１ｐ０æèçöø÷ｋｒｅｐ（ｑ－ｑ０）∂（ｑ－ｑ０）∂ｑ　ｑ－ｑ０≤ｐ００ｑ－ｑ０＞ｐ０ìîíïïïï（４）所以位置ｑ受到障碍物和目标点的势场的叠加，所受合力为Ｆｑ＝∑ｎｉ＝１Ｆａｔｔ（ｉ）＋∑ｍｊ＝１Ｆｒｅｐ（ｊ）（５）需要注意势场函数只受到障碍物和目标的叠加影响，而与机器人本身或者其他机器人无关，所以机器人仅仅通过当前位置的势场无法了解到其他机器人的情况。１􀆰２　环境地图的建立目前多机器人学习的路径规划技术尚处于理论研究阶段，大部分的研究成果都是基于栅格化地图的仿真实验。其主要原因有两点：ａ）目前多机器人路径规划算法鲁棒性和拓展性较差，不适用于实际系统；ｂ）栅格化地图实验能很好地反映算法效果，同时栅格法具有简单有效、易于实现等特点。机器人可以选择移动的方向如图１所示有上、下、左、右、左上、右上、右下、左下、原地不动等方向。栅格法将机器人工作环境用一系列相同大小的栅格进行表示，每个栅格具有两种状态，即占据状态和空闲状态。空闲状态为机器人可以移动和通过的区域，占据状态为机器人不能通过的区域。根据栅格法建立５０×５０的地图如图２所示。目标点和障碍物位置随机生成，目标点数量与机器人保持一致。图２中黑点（２１，２８）为目标点所在位置，２×２的灰色方块为障·６６·计算机应用研究２０２０年　碍物，障碍物与目标点不会重叠。基于人工势场下的地图热力如图３所示。图中越亮的地方代表势场越低，越暗的地方代表势场越高。所以障碍物和边界颜色很深，而目标点（２１，２８）旁边颜色最浅。

基于遗传算法的分拣机器人最优路径规划

文生平;陈端平

【摘 要】针对复杂的多约束条件下的机械手抓取几何体问题,通过分析将实际问题转换成旅行商问题求解.阐述了旅行商问题、遗传算法及其算法实现的过程,在充分考虑遗传算法和约束条件特点的情况下,提出将多约束条件变成约束矩阵的新方法,从而将多约束条件的路径规划问题转化成常规旅行商问题,有效简化了问题的复杂程度,充分利用遗传算法的搜索能力规划出最优抓取路径.软件仿真及实验结果表明,该算法能够取得比较理想的效果.

【期刊名称】《自动化与仪表》

【年(卷),期】2015(030)011

【总页数】4页(P6-8,30)

【关键词】路径规划;旅行商问题;遗传算法;约束矩阵

【作 者】文生平;陈端平

【作者单位】华南理工大学 聚合物新型成型装备国家工程研究中心 聚合物成型加工工程教育部重点实验室,广州510640;华南理工大学 聚合物新型成型装备国家工程研究中心 聚合物成型加工工程教育部重点实验室,广州510640

【正文语种】中 文

【中图分类】TP24

近年来，工业机器人技术发展迅速，广泛应用于工业生产的各个方面，具有较大的发展空间[1-2]。机器人抓取技术是指工业生产中实现不同物体的分拣，并且将其快速准确地放在指定位置。如果让工人长时间从事重复的分拣工作易产生疲劳且效率不高。因此，采用机器人完成分拣工作不仅可以提高工作效率和准确性，更能节省人力资源成本，增加工厂的效益。机器人分拣物体的路径优化问题是生产中常见的实际难题，如果路径设计不合理，将会增加系统的运行时间。分拣顺序优化是一个组合优化问题，而组合优化问题是一个复杂的问题，得到了广泛的研究[3-7]，但对并联机器人路径优化的研究还比较少。本文运用遗传算法对多约束条件的并联机器人分拣顺序进行了仿真研究并在贝加莱公司最新的Tripod机器人上进行实验，验证了该方法的有效性。

1 问题描述

Tripod机器人是贝加莱工业自动化有限公司和奥地利HTL Wels大学共同设计的四轴并行机器人，具有3个机械手臂。在3台相同电机的配合控制下，工具中心可以在X，Y，Z工作空间中进行平移运动，并通过一个步进电机实现旋转。

２　０　０　７年２月　沈阳理工大学学报　

第２　６卷第１期ＴＲＡＮＳＡＣＴＩＯＮＳ　ＯＦ　ＳＨＥＮＹＡＮＧ　ＬＩＧＯＮＧ　ＵＮＩＶＥＲＳＩＴＹ　Ｖｏ１．２　６　Ｎｏ　

Ｆｅｂ．　２　０　０　

文章编号：１００３—１２５１（２００７）０１—００１０—０３　

动态环境下自主式移动机器人的路径规划研究　

辜吟吟，刘砚菊，陈　亮　

（沈阳理工大学信息科学与工程学院，辽宁沈阳ｌ　１０１６８）　

摘要：首先建立了超声传感器预测模型，然后基于多传感器融合的方法获取准确的　

动态环境信息，最后在利用遗传算法进行路径规划的基础上，引入模拟退火算法，形成　

一种遗传模拟退火算法来寻求全局最优路径．仿真结果表明，该算法是正确和有效的．　

关键词：路径规划；遗传算法；模拟退火；数据融合　

中图分类号：ＴＰ２４２．６；ＴＰ２７３．５　文献标识码：Ａ　

Ａ　Ｐａｔｈ　Ｐｌａｎｎｉｎｇ　Ｓｔｕｄｙ　ｏｆ　Ａｕｔｏｎｏｍｏｕｓ　Ｍｏｂｉｌｅ　ＲＯｂｏｔ　

ｉｎ　Ｄｙｎａｍｉｃ　Ｅｎｖｉｒｏｎｍｅｎｔ　

ＧＵ　Ｙｉｎ—ｙｉｎ，ＬＩＵ　Ｙａｎ－ｊｕ，ＣＨＥＮ　Ｌｉａｎｇ　

（Ｓｈｅｎｙａｎｇ　Ｌｉｇｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ　１１０１６８，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｕｌｔｒａｓｏｎｉｃ　ｓｅｎｓｏｒ　ｐｒｅｄｉｃｔｉｖｅ　ｍｏｄｅｌ　ｉｓ　ｂｕｉｌｔ　ｆｉｒｓｔｌｙ．Ｔｈｅｎ　ｔｈｅ　ａｃｃｕｒａｔｅ　

ｄｙｎａｍｉｃ　ｅｎｖｉｒｏｎｍｅｎｔａｌ　ｄａｔａ　ｉｓ　ａｃｑｕｉｒｅｄ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｍｅｔｈｏｄ　ｏｆ　ｍｕｈｉｓｅｎｓｏｒ　ｆｕｓｉｎｇ．Ｆｉｎａｌｌｙ，　

ｏｎ　ｔｈｅ　ｂａｓｅｓ　ｏｆ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｂｙ　ｕｓｉｎｇ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ，ａ　ｇｅｎｅｔｉｃ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｐ－　ｐｒｏａｃｈ　ｉｓ　ｆｏｒｍｅｄ　ｂｙ　ｉｎｄｕｃｔｉｎｇ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｐｐｒｏａｃｈ　ｔｏ　ｓｅａｒｃｈ　ｔｈｅ　ｇｌｏｂａｌ　ｏｐｔｉｍａｌ