基于改进蚁群算法移动机器人的路径规划.pdf

第 3 O卷第 1 2期 2 0 0 9年 l 2月 煤 矿 机 械 Co a l Mi n e Ma c hi n e r y Vo 1 ． 3 O No ． 1 2 De c ． 2 0 o 9 基于改进蚁群算 法移动机器人的路径规划木 刘军．刘广瑞 郑 州 大 学 机 械 工 程 学 院 ， 郑 州4 5 0 0 01 摘 要针对基本蚁群算法存在收敛速度慢 ， 计算周期长， 易死锁等问题 ， 提 出了蚂蚁回退、 蚂 蚁相遇、 带交叉点的路径交叉的改进算法。通过随机数 引入和状态转移概率的应用， 平衡 了各路径 信息素， 从而有效地避免陷入局部 最优 ， 使得算法在收敛速度和执行效率上得到有效提 高。 关键词 蚁群算法 ； 路径规划；死锁 ； 寻优 中图分类 号 T P 2 4文献标 志码 A 文章 编号 1 0 0 30 7 9 4 2 0 0 9 1 20 0 4 60 3 Pa t h Pl a n n i n g o f M o bi l e Ro bo t Ba s e d o n I m pr o v e d Ant Co l o ny Al g o r i t h m LI U J u n， LI U Gu a n gr u i S c h o o l o f Me c h a n i c a l E n g i n e e r i n g o f Z h e n g z h o u U n i v e r s i t y ， Z h e n g z h o u 4 5 0 0 0 1 ， C h i n a Abs t r a c t Ac c o r di n g t o t h e b a s i c a n t c o l o n y a l g o r i t h m f o r t h e e x i s t e n c e o f s l o w c o n v e r g e nc e ，c o mp u t i n g l o n g t e r m a n d e a s y t o d e a d l o c k a n d S O o n ，b a c k t o t h e a n t ，a n t s e n c o u n t e r wi t h c r o s s- p o i n t i mp r o v e me n t i n c r o s s - p a t h a l g o rit h m．Ra n d o m n u mb e r s t h r o u g h t h e i n t r o d u c t i o n a n d a p p l i c a t i o n o f s t a t e t r a n s i t i o n p r o b a bi l i t y ，ba l a n c e o f t h e p h e r o mo n e p a t h S O a s t o e f f e c t i v e l y a v o i d t h e l o c a l o p t i mu m， t h e a l g o rit h m i n c o n v e r g e n c e s p e e d a n d i mp l e me n t a t i o n o f e f f e c t i v e t o i n c r e a s e e ffi c i e n c y． Ke y wo r d s a n t c o l o n y a l g o rit h m；p a t h p l a n n i n g；d e a d b o h l o c k ；o p t i mi z a t i o n 0 引言 移 动 机 器人 的路 径 规 划 是 按 照 某 一 性 能 指 标 搜索一条从起点到 目标点的最优或次最优的无碰 撞路径。机器人路径规划的研究始于 2 O世纪 7 0年 代 ，目前国内外对这一问题 的研究仍然十分活跃 。 2 O世 纪 9 0年代 D o r i g o M最 早提出来蚁群优化算 法一蚂蚁系统 A S 并将其应用于解决计算机算法 学 中经典 的旅行 商 问题 T S P 。从 蚂蚁 系统开 始 ， 对 蚁 群算 法得 到 了不 断 的发 展 和完善 。 并 在 T S P以及 许多实际优化问题求解中进一步得到了验证 。本文 针对基本蚁群算法存在收敛速度慢 ，计算周期长 ， 易死锁等问题 ， 在算法上进行 了改进 ， 通过多次仿 真 试验 证 明 ， 改 进后 的算法 增 加 了新 路径 的生 成途 径 和提 高 了路 径生 成 速度 ， 从 而能 够 快 速得 到 较优 解 。 1 蚁群算 法的基 本原 理 1 环境建 模 环境模型表示是解决环境建模问题 的第 1步。 环境 建 模 的本 质 属 于 环境 特 征 提 取 与 知 识 表 示 方 法的范畴 ， 决定了系统如何存储 、 利用和获取知识 。 创建地图的 目的是供机器人进行路径规划 ． 因此地 图必须便于机器理解和计算 ， 而且当探测到新环境 信息时 ． 应该能够方便地添加到地图中。移动机器 人导 航领 域 常用 的环 境模 型分类 情 况 如 图 1所 示 ， 其 中尤 以几种 平面模 型更 为 常见 。其 中栅格 模 型在 机 器人 系 统 中得 到广 泛应 用 ， 是 目前 使 用 较 为成 功 的一种方 法 。 广-度量模型 广平面 模型一 环 境 模 型 一 鏖 藉 型 L三 维 模型一 L 可 视 化 模 型 图 1环 境 模 型分 类情 况 栅格模 型是一种应用非 常成功 的度量地 图构 建方法 ， 最早 由 E l f e s于 1 9 8 5年提 出 ． 其思想是把 移动机器人所处 的环境分成许多大小相等的栅格 ． 通过每个栅格被 障碍 占据或没有 占据 的概率值来 进行 空间状 态描 述 。 2 栅格 标识 的 2种方 法 ①直角坐标法 如图 2所示 ， 以栅格阵左上角 作为直角坐标 系坐标原点 ． 轴正方 向为水平 向 右 ， Y轴正方向为竖直 向下 ．坐标系的单位长度为 栅格区间的一个单位长度。某一栅格可用直角坐标 ， y 来标 识 。 公益性行业 农业 科研 专项 n y h y z x 0 7 0 0 5 2 5 I 46 ．．． 0 1 2 3 4 5 6 7 8 0 l 2 3 4 5 6 7 8 9 l O I 1 1 2 l 3 1 4 1 5 l 6 1 7 l 8 l 9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 8 0 Y 图 2栅 格 坐 标 与 序 号 的 关 系 耙 ～ L T J 第 3 0 卷第 1 2期 基于改进蚁群算法移动机器人的路径规划刘 军 ， 等 V o 1 ． 3 0 N o ． 1 2 ②序号法如图2 所示，从栅格阵左上角第 1 个栅格开始 ， 按从左到右， 从上到下的顺序 ， 给每一 个栅格一个序号 从 0开始计 ， 则序号 与栅格 块一 一对 应 。 2改进算 法 的描述 改进后机器人路径规划 的算法描述 为 在出发 点 放 置 m 只 蚂蚁 ，每只 蚂蚁 以所 在 点 为 圆心 ， 按事先规定的方法选择下一点 ， 按事先规定的方法 更新路径的信息素。如果有蚂蚁 n到达 目标点 ， 那 么 n到达 目标点 就耗 时最少 ，因此 此 次规 划 中 凡 得到的路径为最优路径 ， 故对 n所得路径进行全局 信息素更新 ， 并将此路径存储为 目前最优路径 。此 后 n从 鼬 出发以 为 目标节点依照上述方法 寻 优。如果蚂蚁得到了新的路径 ， 则将 当前最优路径 和新路径进行 比较 。 如果生成新路径 的时间少 于当 前最优路径 ，则 当前最优路径 由当前路径来代替 ， 与此同时对新 的当前最优路径进行全局信息更新。 如果在某一次全局信息素更新后 。 又生成新的 k条 路径时当前最优路径还没有被替换 ， 此时更新 当前 最优路径的全局信息素。反复循环 ， 直到达到设定 的约束条件或循环终止 的次数。 3改进算 法 的步骤 1 将含有 多个 障碍物 的地 图栅格化 ， 并赋 以 相应 的序号。初始化算法中的所有 变量 ， 设 置蚂蚁 总数 目m， 最大循环次数 ， 对任意两可达栅格 间 初始信息素 下 0 丁 0 为常数 ， 随机地设置起点 脚和 目标点 ， 将 m 只蚂蚁放 在起 点 踟 ， 并将 酗 加人到禁忌表 t a b u 中。 设置 踟 1d ， 为单程 目标节点 ∈{ 踟 ， 踟 } 。 2 启动所有蚂蚁 ， 以当前节点 蜀为中心 ， 比较 随机数 q与 q 。 的大小 ， 按式 1 或式 2 选择到下一 节点 f a r g m a x { n r [ 叼 】 q ≤g 0 ， ， 、 。 【 其 他 ，毕 器 式 中 蚂蚁 n所 选 鸶的节 点序 号 ， ∈ ； 随机 变量 口 叙述 方便 引入 的随机数 0 q 。 时 ， 计算 个点的概率 n ， 并选择节点 ． ，将 ． 加人禁忌表 t a b u 中。O ／ 和 分 别反映蚂蚁在运动过程 中积 累的信息 和启发信 息 在蚂蚁选择路径 中的相对重要性。 越大 ， 说明蚂蚁 选择以前走过路径 的可能性就越大 ， 越大 ， 说 明蚂 蚁选择局部最短路径的可能性就越大。 3 局部信息素更新。 当 k只蚂蚁将剩余节点都 选择完毕后按式 3 进行局部信息素更新 。用 1 _ p 表示路径上信息素消失程度 ，其浓度随着时间的推 移 逐渐 消失 T ／／ 斛 1 1 下 n p h r 3 其 中 A T 在 蚁 周 、 蚁 量 、 蚁 密 模 型 中 的求 法 不 同 ， 本 文取 △ 为常数， T m i △ 砖 Ⅳ眦则循环结束 ， 跳 出整个 循环 ， 输 出最 优路 径 ， 否则 ， 转到 步骤 2 。 4仿 真试 验 为了验证算法 的可行性 ，进行了大量的仿真试 验 ， 设置不同的栅格数 ， 生成起始点 ， 终点和障碍物 。 试验环境栅格数为 8 O的正方形区域 。取 2 0 0 ， 蚂 蚁 数 目 m 1 0 ， T O 1 ． 5 ， a 1 ． 0 ， ／ 3 1 ． 0 ， p 0 ． 1 ， 0 0 ． 1 ， Q 3 O ， q o O ． 9 。 基本蚁群算法和改进算法在相同的环 境下在执行步数和执行时间上进行 比较 ，仿真结果 见 图 3 。 由图 3可以看 出 ， 2种算法在 执行 步数上进行 了对 比分析 ．可 以明显 看 出改进 策 略的算 法对 路径 优化的性能有显著影 响。 改进算法在 5 0步左右收敛 到最优解 ，基本算法在 8 0步左右收敛到最优解 。2 第 3 0卷第 l 2期 2 0 0 9年 1 2月 煤 矿 机 械 Co a l Mi n e Ma c h i n e r y V0 1 ． 3 0 No ． 1 2 De c ． 2 o o 9 整体无心轴托辊管体旋压道次的试验研究 木 李 长 胜 。贺 红 艳 河南机 电高等专科学校 ， 河南 新 乡 4 5 3 0 0 2 摘 要 缩颈旋压工艺是制造无心轴托辊的最佳方法之一 在旋压成形过程中， 旋压道次的选 择对旋压后 管体零件的局部 变薄以及拉 裂等缺陷有重要影响。将普通车床 C 6 1 4 0改装成 P X 一 3旋 压设 备 ， 对外 径 1 o 8 mm， 壁厚 t 4 mm， 材 质为 2 0钢 的无 缝钢 管进行 缩 颈旋压 试验 ， 确定 了合理 的 旋压道 次 ， 完成 了托 辊 的缩颈 旋压成 形 。 关键 词 旋压 式无心 轴托辊 ；旋压 道 次 ；管体 ；试验研 究 中图分类 号 T D 5 2 8文 献标 志码 A 文章编 号 1 0 0 30 7 9 4 2 0 0 9 1 20 0 4 80 3 Ex p e r i m e nt St ud y o n Sp i nn i ng Tr a i l o f Pi p e i n I n t e g r a l M a n dr e l - - l e s s Ro l l e r LI Ch a n g s h e n g ， HE Ho n g y a n He n a n Me c h n i c a l a n d E l e c t r i c a l E n g i n e e r i n g C o l l e g e ，Xi n x i a n g 4 5 3 0 0 2，C h i n a Ab s t r a c t T h e j o u r n a l r e d u c t i o n s p i n n i n g t e c h n o l o g y i s t h e b e s t m e t h o d f o r m a k i n g ma n d r e l l e s s r o l l e r ． Th e s e l e c t i o n o f s p i n ni ng t r a i l h a s g r e a t e f f e c t s o n t h e p i p e i n t h e for mi n g p r o g r e s s ，a n d i t ma y l e a d t o de f e c t i v e s s u c h a s f r a c t u r e s ．La t he o f C61 4 0 i s mo d i fie d t o a s p e c i a l s p i n n i n g e q u i p me n t o f P X一 3．T he j o u r n a l s p i n n i n g e x p e r i m e n t s o n s e a ml e s s s t e e l p i p e w i t h o u t e r d i a me t e r 1 0 8 m m， t h i c k n e s s 4 mm a n d ma t e r i a l o f 20 a r e t e s t e d o n t he ma c hi n e ．Th e n t he ma n d r e l - l e s s r o l l e r i s fin i s h e d wi t h t h e r i g h t s e l e c t i o n o f s p i nn i n g t r a i l ． Ke y wor dss p i n n i n g ma n dr e l l e s s r o l l e r ；s p i n ni n g t r a i l ；p i p e；e x p e r i me n t s t u d y 1 试验装 置 托 辊是 带 式输 送 机 的主要 部 件 ， 随着带 式 输 送 机 广泛 应 用 于煤 炭 、 冶 金 、 矿 山 、 港 口 、 建 材 等 国 民 经济 各部 门 ， 托 辊 的用量 日益增 长 ， 越来 越 大 ， 课 题 河南省教育厅 2 0 0 6年 自然科学研究资助计划项 目 2 0 0 6 4 6 0 0 2 3 组研制的旋压式无心轴托辊是一种轴承安装在 整 体辊子两端旋压成形的半轴上。管端半轴成形依靠 塑 性 成 性 变 形 ， 金 属 纤 维 不 被 切 断 连 续完 整 ， 托辊 整体强度 高 ， 制造成本降低 2 0 ％， 安装及维修费用 比有心轴托辊降低 4 0 ％， 运转 能耗降低约 3 0 ％。降 低能源消耗 、 节约钢材 社会经济效益显著 。 具有推 ； - 、 l 、 l ＼ ＼ e ＼ 蛉e ； 蠕扮 石 ＼ I 、 分 石 ，’ 、 ； ＼ ． 、 蝣 蛤 石 蛉 石 ＼ ． 、 种算法相比， 改进算法采用了改进策略 ， 较优路径产 到较优解 ， 在算法 的早期就能较快地收敛 。使得算 生的途径较多 ， 所以较优解生成数 目和速度高于基 法在收敛速度和执行效率整体上得到提高。该算法 本算 法 ， 从 而加快 了 寻优效率 和 收敛速 度 。 在较复 杂 的环境 下也能 规划 出较优 的路径 。 K 螯 算 法 执 1步数 图 3算 法 寻 优 对 比 图 1 ． 改进算法 当前最优值 2 ． 基本蚁群算 法当前最优值 5结语 针对基本蚁群算法存在收敛速度慢 ， 计算 周期 长 ， 易死 锁 等问题 ， 本文 在算 法上 进 行 了改进 ， 通 过 多次仿真试验证明 ， 改进后的算法增加了新路径 的 生成途径和提高 了路径生成速度 ， 从而能够快速得 算法 [ J ] ． 华东理丁大学学报 ， 2 0 0 6 ， 3 2 8 7 9 9 9 9 9 ． [ 5 ] Z h a o D B ， Y i J Q ． L e c t u r e N o t e s i n C o m p u t e r S c i e n c e [ M] ． He i d e l b e r g S p r i n g e r B e r l i n． 2 0 0 6 2 2 2 2 3 1 ． [ 6 ] 牛新征 ， 佘望 ， 路纲 ， 等． 蚁群算法研究的新进展 和展望[ J ] ． 计算 机应用研究 ， 2 0 o 7， 2 4 4 l 2 一 l 3 ． 作者简介刘 1 9 8 3 一 ． 陕西榆林人， 硕士研究生， 主要研究方向 为机器人运动学 、 动力学与控制的研究 ． 电子信箱 l i u j u n 7 7 8 4 5 4 8 1 6 3 ． ．．． 4 8 收稿 日期 2 0 0 9 0 6 2 4