煤炭勘探及救援机器人最优路径规划研究.pdf

第 4 3卷 第 3期 2 0 1 7 年 3月 工矿 自 动化 I ndus t r y a nd M i ne Aut oma t i on Vo 1 ． 4 3 NO ． 3 M a r ． 2 O 1 7 ’ ．。 i实验研究 1 ⋯ f ．⋯ ◆ ． ． ◆ ’ 文 章 编号 1 6 7 1 2 5 1 X 2 0 1 7 0 3 0 0 2 4 0 6 DOI 1 0 ． 1 3 2 7 2 ／ j ． i s s n ． 1 6 7 1 - 2 5 1 x ． 2 0 1 7 ． 0 3 ． 0 0 6 李晓静 ， 余东满． 煤炭勘探及救援机器人最优路径规划研究I- J ] ． 工矿 自动化 ， 2 0 1 7 ， 4 3 3 2 4 2 9 ． 煤炭勘探及救援机器入最优路径规划研究 李 晓静 ， 余 东满 。 1 ． 河 南工业 职 业技 术学 院 机 械工程 学 院 ， 河 南 南 阳4 7 3 0 0 9 ； 2 ． 柔 性制 造河 南 省工程 实 验室 ，河南 南 阳4 7 3 0 0 9 摘 要 为 了解决 三 维环境 中的煤炭勘 探 及救 援机 器人 路 径规 划 问题 ， 提 出了一种基 于改进蚁 群 算 法的煤 炭勘 探及 救 援机 器人 最优 路径 规 划方 法 。利 用栅 格 法创 建 了三 维 空 间环境 模 型 ， 建 立 了煤炭 勘 探 及 救援 机 器人 的路 径 规 划 目标 函数 ； 通 过 引入新 的 启发 函数 因子 、 节点 随机 选择机 制 、 局 部 更 新 和 全局 更 新 相 结合 的 策略分 另 一l 对算 法的 节点 转移概 率设 计 、 节 点选择 策 略和信 息素 更新 策略 进行 了优 化 改进 。Ma t l a b仿 真 结 果 表明 ， 在三维空间环境模型 中， 传统蚁群算法和改进蚁群算法均能为煤炭勘探及救援机器人搜 索出一条最优 路径 ； 在不同任务要求下， 改进蚁群算法能有效缩短搜 索路径长度和降低路径搜 索时间， 且具有较 强的决策 能力 和较好 的 收敛 性 能 。 关键 词 煤炭 开采 ； 煤 炭勘 探 ； 救 援机 器人 ； 路 径 规 划 ；蚁群 算 法 中 图分 类 号 TD6 7 文献标 志 码 A 网络 出版 时间 2 0 1 7 0 2 2 8 1 6 4 7 网络 出版 地址 h t t p ／ ／ k n s ． c n k i ． n e t ／ k c ms ／ d e t a i l ／ 3 2 ． 1 6 2 7 ． T P ． 2 0 1 7 0 3 0 1 ． 1 5 1 4 ． 0 0 6 ． h t m1 Re s e a r c h o n t he o p t i ma l pa t h p l a nn i ng o f c o a l e x p l o r a t i o n a nd r e s c u e r o b ot LI Xi a o j i n g 一． YU Do n g ma n 1． Col l e g e of M e c h a ni c a l Engi n e e r i n g，H e na n Pol y t e c hni c I ns t i t ut e，Na n y a ng 4 73 0 0 9，Chi n a 2 ． He n a n En g i n e e r i n g L a b o r a t o r y o f F l e x i b l e Ma n u f a c t u r e ，Na n y a n g 4 7 3 0 0 9，Ch i n a Ab s t r a c t I n o r d e r t o s o l v e p a t h p l a n n i n g p r o b l e m o f c o a l e x p l o r a t i o n a n d r e s c u e r o b o t s i n t h r e e d i me n t i o n a l e n v i r o n me n t ，a n o p t i ma l p a t h p l a n n i n g me t h o d f o r c o a l e x p l o r a t i o n a n d r e s c u e r o b o t b a s e d o n i m p r o v e d a n t c ol o ny a l go r i t h m wa s p r op os e d．Thr e e d i m e n s i ona l s pa c e e n v i r on m e n t mode l i s e s t a bl i s he d b y u s i n g g r i d me t h o d，a n d p a t h p l a n n i n g o b j e c t i v e f u n c t i o n o f c o a l e x p l o r a t i o n a n d r e s c u e r o b o t i s e s t a b l i s he d．Nod e t r a ns i t i on pr ob a bi l i t y d e s i gn，n od e s e l e c t i on s t r a t e gy a nd phe r o m o ne up d a t e s t r a t e g y a r e o pt i m i z e d a n d i mpr o ve d by i n t r od uc i ng n e w he ur i s t i c f un c t i on f a c t or ，r a n do m s e l e c t i o n m e c h a ni s m o f no de a n d c o m bi n i ng s t r a t e g y of l oc a l up da t i ng a nd gl o ba l u pd a t i n g．M a t l a b s i m u l a t i o n r e s ul t s s h ow t ha t b ot h t he t r a d i t i o na l a nt c o l o ny a l g o r i t hm a nd t he i m p r ov e d a nt c o l o ny a l go r i t hm c a n f i nd a n o pt i m a l p a t h f o r t he c oa l e x pl o r a t i o n a n d r e s c ue r ob ot i n t he t hr e e d i me ns i o na l e n vi r o nme nt m o de 1 ． U n de r d i f f e r e nt t a s k r e q ui r e m e n t s，t he i m p r ov e d a n t c o l o ny a l go r i t h m c a n e f f e c t i v e l y s hor t e n t he l e n gt h o f s e a r c h p a t h a nd r e du c e t i m e o f pa t h s e a r c h，a n d ha s s t r on g de c i s i on ma ki n g a bi l i t y a nd g o od c o nv e r ge nc e p e r f o r m a n c e． Ke y wo r d s c o a l mi n i ng；c o a l e xp l o r a t i o n；r e s c ue r ob o t；pa t h p l a nn i ng；a nt c ol o ny a l g o r i t hm 收稿 日期 2 0 1 6 - 0 9 - 0 5 ； 修 回日期 2 0 1 7 一 O 1 1 5 ； 责任编辑 胡娴 。 基金项 目 河南省青年骨干教师资助计划项 目 2 0 1 2 GG J S - 2 4 8 。 作者简介 李 晓静 1 9 8 0 一 ， 女 ， 河南邓 州人 ， 实 验师 ， 主要研究 方向 为算法流程 、 公差 配合等 ， E ma i l h n p i l 1 2 6 ． c o rn。通 信作者 余东 满 1 9 7 7 一 ， 男 ， 河南邓州人 ， 副教授 ， 博士 ， 主要研究方 向为机构设计 、 仿真分析等 ， E ma i l y u d o n g ma n 1 2 6 ． c o rn。 2 0 1 7年第 3期 李晓静等 煤炭勘探及救援机器人最优路径规划研究 2 5 0 引言 煤炭资源勘探作为煤炭资源开采和煤炭工业建 设的基础和前提 ， 其勘探信息的准确与否将会对煤 炭 资源储 备 评估 和 国家煤 炭工 业建 设 布局设 计产 生 直接的影响口 ] 。因此 ， 在煤炭资源勘探过程中， 如何 获取 人无 法 到达 或不 适宜 到达 及无 人机 或其 他 智能 设备不易监测到的区域的详细地质信息是亟待解决 的难 题 。煤 炭勘探 及 救援 机器 人 的 出现 很好 地解 决 了这 一难 题 。煤炭 勘 探及 救援 机器 人是 一种 集计 算 机、 无线 网络通信、 图像处理 、 人工智能 、 机械设计、 机械 电子及仿生学等为一体 的智能机械移动装置 ， 其主要作用是利用 自身配置 的雷达传感器、 红外传 感器 、 C C D摄像机及其他智 能仪器装置 ， 代 替勘探 人员 进入 指定 工作 区域 ， 完 成 环境 侦查 、 煤炭 资 源勘 探和人员搜索救援等任务[ 2 ] 。在复杂多变的三维运 行环境中， 煤炭勘探及救援 机器人 如何在 已知起点 和 目标 点 的前 提下 ， 快 速 进入 指定 工作 区完 成 煤 炭 资源勘探和人员搜索任务 ， 涉及 到机器人三维空 间 路径 规划 问题 。针 对 三维 空 间路 径 规 划 问 题 ， 目前 常用的有效方法主要 有 A 算法[ 3 ] 、 遗传算法[ 4 ] 、 粒 子群算法嘲、 蝙蝠算法嘲及蚁群算法Ⅲ等。 蚁群算法是一种启 发式智 能群体仿 生优化算 法， 由于该算法具有较强的鲁棒性 、 优 良的分布式计 算机制 ， 所 以， 其在优化组 合 、 NP难题 、 二次分 配 、 机器人路径规划 、 车间调度及通信 网络路 由等领域 得到广 泛应用 。 。针 对煤 炭勘探 及救援 机 器人 三维空间路径规划 问题 ， 在传统蚁群算法基础上 ， 通 过 引入新 的启 发 函数 因子 对节 点转 移概 率 进行 了重 新设 计 ； 为 了增加 节点 选择 多 样性 、 增强 算 法全局 搜 索 能力 和改 善算 法 收 敛 性 能 ， 通 过 引 入 节 点 随机 选 择机制和信息素局部和全局相结合 的更新策略分别 对节 点 选 择 策 略 和 信 息 素 更 新 策 略 进 行 了 优 化 改进 。 1 问题 描述 及环 境 建模 1 ．1 问 题 描 述 环 境模 型是 研 究 路 径 规划 问题 的 基 础 和前 提 ， 因此 ， 在 对 煤炭 勘探 及 救 援 机 器 人 三 维 路 径 规划 问 题 进 行 研 究 前 ， 需 对 其 运 行 环 境 作 如 下 处 理 _ 1 ① 将煤 炭勘探 及 救 援 机 器 人 工作 环 境 简化 为 三 维 有限空间。② 机器人工作环境 中的障碍物可用 不 规 则 的多边 形 表 示 。③ 假 设 机 器 人 的 运行 速 度 恒 定 ， 忽 略其启动 、 转向和制动等操作 。④ 为便于仿 真， 将机器人视为一质点 ， 另外 ， 对环境 中的障碍物 也要 作适 当 的膨化 处 理 ， 并 允 许 机 器人 沿 着 障 碍 物 边 界 行走 。 1 ． 2环 境建模 针对 三 维 空 间环 境 模 型 ， 目前 常 用 的建 模 方 法 主要有栅格法 、 几何法和高程法。其 中， 几何法存在 所 需 数据存 储 数量 大且无 法对 环境 进行 有效 描述 等 缺陷； 高程法虽然能有效 降低数据存储空间和提高 建模速度 ， 但存在信息缺失的缺陷。基于此 ， 选用栅 格法创建煤炭勘探及救援机器人的三维空间运行环 境 模 型 ， 其 建模 思想 可 描 述 如下 [ 1 ① 根 据 现 实 环 境信息构建煤炭勘探及救援 机器人 的三维空 间模 型 ， 如 图 1所示 。② 将 三维 空 间模 型划 分 成二 维 平 面 。③ 选 用栅 格 法 将 二 维 平 面 分 割 成 多 个 大 小相 等的栅 格 ， 并 提 取 三维 路径 规 划所 需 网格 节 点。 ④ 根据现实环境信息 ， 连接三维空间模型各网格节 点， 即可得到所需的三维路径规划空间环境模型 ， 如 图 2所 示 。 只 要 D 图 1三维 空间模 型 图 2 三 维 路 径 规 划 空 I司环 境模 型 图 1中 0点 为三 维 空 间 坐标 原 点 ， 轴 为 经 度 方向， Y轴为纬度方向， z轴为海拔高度方 向。三维 地 图在 z轴 方 向的最 大长 度取 值 为 O A， y轴方 向 的 最 大长度 取 值 为 0 C， z轴 方 向 的 最 大 长 度 取 值 为 O 0 。采 用栅格 法 划分 二 维平 面 的 目的是 将 三维 空 间模 型离 散化 为一 系列 点 集 合 ， 为 后 续 采用 蚁 群 算 法进 行路 径搜 索提 供数 据支 持 。三维 路径规 划 空 间 环境 模 型 区域 跨 度 为 2 1 k m2 1 k m2 k m， 其 中 S ， S 。和 S 。表 示 煤 炭 勘探 及 救 援 机 器人 的起 始 位 2 6 工矿 自动 化 2 0 1 7年 第 4 3卷 置 ， 其 三维 空 间坐标 分别 为 1 ， 3 ， 6 0 0 ， 1 ， 9 ， 8 0 0 和 1 ， 1 7 ， 4 0 0 ， T ， T 2和 表 示 煤 炭 勘 探 及 救 援 机 器 人 的 目标 点 位 置 ， 其 空 间 坐 标 分 别 为 2 1 ， 1 0 ， 1 0 0 0 ， 2 1， 7 ， 1 2 0 0 和 2 1， 1 7 ， 1 2 0 0 。 1 ． 3 目标 函数 建 立 研 究 煤炭 勘探 及救 援机 器人 三维 空 间路 径规 划 问题的 目的是在 已知有障碍物存在的运行环境 中， 在 已知机 器人 起点 和 目标 点 位 置 的 前 提下 ， 以评 价 指标 最优 为 准则 ， 采用 特定 搜索 策 略 ， 为 机器 人规 划 出一 条从 起点 到 目标 点 的安 全 最 优 路 径 ， 并 确 保 机 器人能够沿着该优 化路径 ， 在较短的时间内快速完 成环境侦查 、 煤炭资源勘探和人员搜索救援等任务。 设节点 i ， J表示可行路段上 的 2个 端点， 建立煤炭 勘探 及救 援机 器人 的路径规 划 目标 函数 L一∑ ，J∈ z 一 z ， Y 。 1 L。 h 。 一d mi n { L ， k } 2 式 中 L为 机器 人 从 起 点 到 目标 点所 走 过 的 总 路 径 长度 ； z ， Y ， 2 和 ， Y ， 一f 分别为节点 i ， J的空 间几何 坐标 ； L 为机器 人 从起 点 到 目标 点 所 走 过的最短路径长度 ； L ， k 为蚂蚁 是在第 r n次路 径迭代搜索 中所走过的总路段长度。 2 最优 路 径规 划算 法设 计 2 ． 1启 发 函 数 因 子 设 计 启发函数因子是蚁群算法中节点转移概率的重 要组 成部 分 ， 它在某 种 程度 上会 对算 法 的收敛 性 能 、 稳 定 性及 全局 搜索 能力 产生 一定 的影 响 。在 传统 蚁 群算 法 中 ， 在 三维 空 间路径 规划 条件 下 ， 启发 函数 因 子一 般用 两 相邻 节 点 口 ， a 1 问 的空 间几 何 距 离 的倒数来表示 ， 如式 3 所示 。传统算法的启发函数 因子 只考 虑 了 当前 节 点 口和 下一 节 点 a 1的空 间 几何 关 系 ， 而 并 未考 虑 当前 节 点 n和 目标 节 点 e的 空 间几何 关 系 ， 因此 ， 采用 此启 发 函数 因子 对搜 索路 径 进行诱 导 时 ， 会 致 使 算 法 因缺 乏 目标性 而导 致 路 径搜索效率降低或路 径搜 索结果 出现偏差 ， 从而形 成局 部最 优解 或 无 效 解 。基 于此 ， 在 充 分考 虑 当前 节点 n 、 下 一 节 点 口 l 及 目标 节 点 P的 基 础 上 ， 通 过 引入安 全 因子 S ， 重 新 对 启 发 函数 因子 进 行 设 计 ， 具体 如 式 4 一 式 6 所示 [ 1 引。 1 一 一 1 z 计1一 z。 l Y 。 。 口 1 一 3 一 面 丽 4 D { 1 Ⅲ 一 ／ z 一X 一y 。 。 2 一 5 s 一 6 式 中 叩 Ⅲ， 为传统蚁群算法 的启发 函数因子 ； d 为 当前 节 点 n和下 一 节点 a 1间的空 间 几何 距离 ； ， ， ， l ， Y 十 1 ， Z a 1 和 ， Y ， 分 别 为 当前 节点 a 、 下 一 节点 a 1和 目标节 点 P的空 间 几 何 坐标 ； 为 重 新 设 计 的启 发 函 数 因子 ； D 为 当前节 点 口到 目标 节 点 的 空间几 何 距离 ； S 为节点选择安全 因素 ， 当选择节点不可到达时 ， 该值 可取 0 ， 其作用是促使蚂蚁在路径搜索 中选择安全 点 ， 并确保规划的路径尽可能远离障碍点 ； ， 。 ， 。 分别 为 d ， D 和 S 卅 的 相 对 重 要 程 度 因 子 ， ， 。 ， 。 ∈E o ， 1 ] ； N 为点 i ， J ， k 的可视 节点总 数 ； N 为可 视节 点 中不 可 到达节 点 总数 。 2 ． 2节 点转 移概 率设 计 节点转移概率是蚁群算法 的重要组成部分 ， 它 直接影响着蚂蚁在路径搜 索中节点 的选择概率 ， 也 影响着蚂蚁 的行进路线。为了使算法在路径搜索 中 更具指导性 和 目的性 ， 在传统节点转移概率计算公 式 式 7 的基础上 ， 通 过引入新 的启 发函数 因子， 对节点 转移 概 率进 行 了重新 设 计 ， 具体 如 式 8 所 示 。 P。 ， 1 ￡ 一 t 3 p ～ ㈩ J ∑[ r d ，升 ￡ ] [ ，升 ’⋯ 7 1 0 ， 其他 P 。 。 l ￡ 一 』 ～ ㈣ ∑ [ ] [ ⋯ ￡ ] ’ ⋯ 一 。 8 1 0 ， 其他 式中 P⋯ 为传统算法下蚂蚁 由节点 口转移到节点 n 1的 概率 ； P ⋯ 为 改 进 算 法 下 蚂蚁 由节 点 n转 移 到节 点 n 1的概 率 ； ． d 为 路 径 口 ， a 1 上 的 信息素量 ； a为信息素启发式因子 ； 卢为节点 间的期 望 启发 因子 ； W 为 蚂 蚁 下 一 步 可 选 择 的 可 达 节 点 集合。 2 ． 3节 点选择 策略 在 建 立 最 优 路径 的过 程 中 ， 蚂 蚁 必 须 不 断 地 从 相 邻节 点选 择 下一 节点 ， 因此 ， 为增 加 节点 选择 多 样 性和避免算法陷入局部最 优， 在采用概率选择路径 2 0 1 7年 第 3期 李 晓静 等 煤炭勘 探及 救援 机 器人 最优路 径 规 划研 究 2 7 节点 的基 础 上 ， 通 过 引 入 随 机 选 择 机 制 对 节 点 选 择 策略 进行 了改进 [ 1 ， 改 进后 的 节点选 择 公式 为 口 1一 f a r g ma x { [ 时1 ￡ ] [ ⋯ 1 ￡ ， q≤ q 。 一 一 【 一 ‘ n 1 ∈ w 式 中 q为[ O ， 1 ] 区间上 的一个 随机数 ； q 。为可调参 数 ， q 。 ∈[ o ， 1 ] ， 其作用是使节点选择更具倾向性 。 分 析式 9 可知 ， 当 q ≤ g 。 时 ， 可 达节 点 a 1可 直接由 a r g ma x [ r 口 ． d 1 ￡ ] [ ⋯ 1 ￡ ] } 确定 ； 当 q q 。时 ， 可达 节点 a 十1可 由节点 转 移 概 率 P ⋯ 和轮盘赌法联合确定。 2 ． 4信 息素 更新 策略 信息素浓度的强弱决定 了蚂蚁在搜索路径上节 点 的选 择 。为 了增 强算 法全 局搜 索 能力 和 改善算 法 收敛性能 ， 避免搜索路径 因信 息素浓度过高或过低 而致使算法出现停滞或早熟 问题 ， 通过 引入信息素 局部和全局相结合的更新策略对基本蚁群算法进行 了优化 改进 。 2 ． 4 ． 1 局部 信 息素 更新 局部信息素更新 目的是通过减少蚂蚁已访问节 点的信息素来增加未访问节点被访问的概率 ， 以此 增加节点选择多样性 ， 避 免蚂蚁在路径搜索 中收敛 到同一路径 。在三维路径搜索 中， 当蚂蚁 由节点 a 移动到节点 a1时 ， 需要完成一次局部信 息素更 新 ， 局部信息素更新规则为 r 珊 t 1 1一 ￡ r 稚 ￡ 盯o 1 0 式中 r 泓为点 i ， ， k 上 的信息 素值 ； ￡为信息素衰 减系数 ； 为初始信息素值 。 2 ． 4 ． 2 全局信息素更新 全 局信息素更新 目的是使算法 搜索更具指导 性 ， 且将蚂蚁搜索范围集中在最优解 附近， 以此增强 算法的全局搜索能力和改善算法的收敛性能。全局 信 息 素更新 只有在 所有 蚂 蚁完 成各 自的路径 搜 索后 才会执行 ， 全局信息素更新规则为 r 4 -1 一 1一 l D r 4- p Ar 0 k 1 1 △r 一 Q／ Lh 1 2 式中 ID为信息素挥发系数 ， P ∈[ 0 ，1 ] ； 1 一』 D 为信息 素持久性系数 ； A r 珊为信息素增量 ； Q为常数 ； L n 为 目前为止所有蚂蚁所能搜索到的全局最优路径 。 2 ． 5 算 法 实施 步骤 在 山区三维空 间环境模型 中， 利用改进蚁群算 法进行煤炭勘探及救援机器人三维路径规划的具体 实施 步 骤如 下 1 在 Ma t l a b平台上 ， 利用栅格法创建煤炭勘 探及 救 援机 器人 的 山 区 三维 空 间运 行 环 境模 型 ， 并 确定 机 器人在 环 境模 型 中的起 点和 目标 点位 置 。 2 初始化算 法参数 ， 分别设置蚂蚁的起 始点 S和 目标 点 T、 蚂蚁 数量 、 信 息 素挥发 系数 p 、 期望 启发因子 、 算法初始迭代次数 C和最 大迭代次数 c 等参数。 3 开 始搜 索 ， 根 据 节点 选择 策 略 ， 按 照不 同条 件约束 ， 确定蚂蚁的下一可行路径节点。 4 根 据局 部 信 息 素 更 新 方 程 ， 对 蚂蚁 刚访 问 节点的信息素进行局部更新 。 5 判断所有蚂蚁 的路径搜索任务是否完成 ， 若是 ， 则按照全局信息素更新方程， 对 目前为止所有 蚂蚁所能搜索 到的最优路径 的信息 素进行全局更 新 ； 否 则 ， 搜索 过程 转至 步骤 3 。 6 根据算法终止条件 C ≤C ， 判断算法搜索 过程是否结束 ， 若 cC ， 则算法路径搜索过程结 束 ， 输 出 最 优 路 径 ； 否 则 ， 算 法 搜 索 过 程 转 至 步骤 3 。 3仿 真 实验及 分 析 在如 图 2所 示 的环 境 模 型 下 ， 以安 全 避 障 和路 径最短为评价指标 ， 选用所设计 的改进蚁群算法作 为搜索策略 ， 在 Ma t l a b平台上对煤炭勘探及救援机 器人 三维 路 径 规 划 过 程 进 行 了仿 真 测 试 。在 测 试 前 ， 设置如下参数 蚂蚁起点坐标 s ， s 和 s 。 分别 为 1 ， 3 ， 6 0 0 ， 1 ， 9 ， 8 0 0 和 1 ， 1 7 ， 4 0 0 ； 蚂蚁 目标点 坐标 T1 ， 和 分 别 为 2 1 ， 1 0 ， 1 0 0 0 ， 2 1 ， 7 ， 1 2 0 0 和 2 1 ， 1 7 ， 1 2 0 0 ； 蚂 蚁 数 量 一 1 5 ； 算 法 初 始迭 代次 数 C一1 ； 最 大 迭 代 次 数 C m 一8 0 ； 信 息 素 挥发 系数 p 一0 ． 6 ； 常数 Q 1 5 0 。 为了便于对路径搜索过程和搜索结果进行观察 和分 析 ， 给 出了在 不 同任务 要求 下 ， 传 统蚁 群算 法和 改进 蚁群 算法 为煤 炭勘 探及 救援 机 器人规 划 的最短 路径 可视化 图， 如 图 3 ～ 图 5所示 。在 图 3 一图 5 中 ， 种群最佳适应度迭代曲线 主要用于评价算法在 路径搜索过程 中的决策能力和收敛性能， 其评估规 则是种群适应度取值大小与算法的决策能力和收敛 2 8 工矿 自动化 2 0 1 7年 第 4 3卷 性能成负相关 ， 即种群适应度值越小 ， 算法 的环境适 应能力和决策能力越强 ， 收敛性能越好 。 2 0 迭代次数 传统蚁群算法；一改进蚁群算法 ⋯传统蚁群算法；一改进蚁群算法 a 最短路径轨迹 b 种群 最佳适 应度 迭代曲线 图 3 煤炭勘探及 救援机器人从起点 s 到 目标 点 T1 的最短路 径可视化图 1 4 迭代次数 传统蚁群算法；一改进蚁群算法 一 一 一 传统蚁群算法；一改进蚁群算法 a 最 短路径 轨迹 b 种群最佳适应度迭代 曲线 图 4 煤 炭勘探及救援机器人从起 点 s z 到 目标 点 丁 2 的最短路径可视化 图 迭代次数 ⋯ 传统蚁群算法；一改进蚁群算法 一 传统蚁群算法；一改进蚁群算法 a 最短路径轨迹 b 种群最佳适应 度迭代 曲线 图 5 煤炭勘探及救援机 器人从起点 S 到 目标点 的最短路径 可视化图 2种算法 的路径 搜索 结果 见表 1 。由 图 3 一 图 5 算 法 在第 2 7 代 取 得 ， 且 改 进蚁 群算 法 的适 应 度最 佳 所示路径搜索结果 ， 综合表 1 数据分析可知 ， 在避障 值小于传统蚁群算法 ； 在 s 一 T 条件下 ， 传统蚁群 路径规划方面， 在山区三维空间环境模型 中， 传统蚁 算法的种群适应度最佳值在第 4 5代取得 ， 改进蚁群 群 算 法和 改进 蚁群 算法 均 能为煤 炭勘 探 及救 援机 器 算 法 在第 3 3代取 得 ， 且 改 进蚁 群 算法 的适 应 度最 佳 人搜索出一条最优路径， 且在不 同任务 即 s 一 T ， 值小于传统蚁群算法 ； 在 s 。 一 条件下 ， 传统蚁群 s 。 一 T 2 和 s 。 一T 3 要求下 ， 改进蚁群算法搜索的最 算法的种群适应度最佳值在第 3 3代取得 ， 改进蚁群 优路径长度小于传统蚁群算法。在种群最佳适应度 算法在第 1 9代取得 ， 且改进蚁群算法的适应度最佳 取值和收敛代数方面 ， 在 s 一 T 条件下， 传统蚁群 值小于传统蚁群算法 根据种群适应度取值大小与 算法的种群适应度最佳值在第 4 3 代取得 ， 改进蚁群 算法的决策能力和收敛性能成负相关 的特性可知 ， 晕 制枯葚 掣髓 錾 f 糌簿 2 0 1 7年 第 3期 李晓静 等 煤炭 勘探及 救援 机 器人 最优路 径规 划研 究 2 9 在 S 一 T ， S 。 一 丁 。和 S 。 一 条 件 下 ， 改 进 蚁 群 算 法 的种群 适应 能 力 、 决 策 能 力 以及 收敛 性 能 均 优 于 传统 蚁群 算法 。在程 序 运 行 时 间方 面 ， 在 3种 条 件 下 ， 传统蚁群算法耗时均大于改进蚁群算法 ， 表明改 进蚁群 算 法 的路 径搜 索 效 率 明显 高 于传 统 蚁 群 算 法 。 表 1 2种算法 的路径搜索结果 4结 语 针对煤 炭 勘探 及救 援机 器人 三维 空 间路径 规划 问题 ， 提出了一种基于改进蚁群算法 的三维路径规 划方法。利用栅 格法创建 了山区三 维空间环境模 型， 建立了煤炭勘探及救援机器人 的路径规划 目标 函数 ； 具体 介绍 了启 发 函数 因子设 计 、 节点 转移 概率 设计、 节点选择策略和信息素更新策略。Ma t l a b仿 真结果表明， 在 山区三维空间环境模型中， 传统蚁群 算法和改进蚁群算法均能为煤炭勘探及救援机器人 搜索出一条最优路径； 在不同任务要求下 ， 与传统蚁 群算法相 比， 改进蚁群算法能有效缩短搜索路径长 度和降低路径搜索时 间， 且在路径搜索中表现出较 强 的决 策 能力 和较好 的收敛 性能 。 参 考 文 献 1 2 [3] [4] DZ ／ T 0 2 1 5 -- 2 0 0 2煤 、 泥炭地 质勘 查规范E s ] ． 刘建 ， 葛世荣 ， 朱华 ， 等． 基 于多 目标优 化的矿 用救 援 机器 人动力匹配[ J ] ． 机械工程学报 ， 2 0 1 5 3 1 8 2 8 ． ZHAO J u n we i ， Z HAO J i a n j u n ． Pa t h p l a n n i n g o f mul t i UAVs c o nc e a l me nt a t t a c k b a s e d o n ne w A me t h o d[ C] ／ ／ S i x t h I n t e r n a t i o n a l C o n f e r e n c e o n I nt e l l i ge nt Huma n M a c h i n e Sy s t e ms an d Cyb e r n e t i c s， 2O1 4 ． W ANG Ho ngl un，LYU W e nt a o，YA0 Pe n g，e t a1 ． Th r e e d i me n s i o n a l p a t h p l a n n i n g f o r u n ma n n e d a e r i a l ve h i c l e b as e d o n i nt e r f e r e d f l ui d d yna m i c a l s ys t e m [ J ] ．C h i n e s e J o u r n a l o f A e r o n a u t i c s ，2 0 1 5 ，2 8 1 22 9 2 39 ． [5] Z E NG Ni a n y i n ，Z HA NG Ho n g ，CHE N Y a n p i n g ， e t a 1 ． Pa t h p l a n n i n g f o r i n t e l l i g e n t r o b o t b a s e d o n [6] [7 ] [ 8] [9 ] E l O ] [ 1 1 ] [ 1 2 ] [ 1 3 ] [ 1 4 ] [ 1 5 ] [ 1 6 ] s wi t c h i n g l o c a l e v o l u t i o n a r y P S O a l g o r i t h m [ J ] ． As s e mb l y Au t o ma t i o n ，2 0 1 6，3 6 2 1 2 O 一 1 2 6 ． W ANG G G， CHU H E，MI RJ ALI LI S ． Th r e e d i me n s i o n a l p a t h p l a n n i n g f o r UCAV u s i n g a n i mp r o v e d b a t a l g o r i t h m[ J ] ．Ae r o s p a c e S c i e n c e a n d Te c h n o l o g y，2 0 1 6，4 9 2 3 1 - 2 3 8 ． W ANG Ch a o，HE Cha ona n．Thr e e - di me n s i on a l p l a n n i n g o f a r r i v a l a n d d e p a r t u r e r o u t e n e t wo r k b a s e d o n i mp r o v e d a n t c o l o n y a l g o r i t h m[ J ] ．T r a n s a c t i o n o f N a n j i n g Un i v e r s i t y o f Ae r o n a u t i c s a n d A s t r o n a u t i c s ， 2 01 5，32 6 65 4 6 6 4． 段海滨． 蚁群算法原理及其应用 [ M] ． 北京 科学 出版 社 ， 2 0 0 5 ． 刘利强 ， 于 飞， 戴运桃． 基于蚁群算法 的水下潜器 三维 空间路 径 规 划 [ J ] ． 系 统 仿 真 学 报 ， 2 0 0 8 ， 2 0 1 4 3 71 2 3 71 6 ． XI AO Qi n k u n，WANG Yi ，GAO S o n g，e t a 1 ． 3 D p a t h p