基于栅格法的机器人路径规划快速搜索随机树算法

基于栅格搜索树的路径规划李淑霞【期刊名称】《河南科学》【年(卷),期】2013(000)005【摘要】将栅格法和搜索树结合在一起，提出一种新的路径规划方法——栅格搜索法。

首先利用栅格法建立环境模型，构建搜索树，在搜索树中采用从叶节点到根节点的回溯搜索方法寻找路径规划，最后用MATLAB仿真。

结果表明，该方法能找到从起点到终点的最优路径，验证了该方法的有效性。

% Combining the grid with search tree method together,the author proposes a new path planning method-grid search method. Firstly,this paper uses grid method to establish an environmental model,builds the search tree, and uses backtrack search method to find the leaf node to the root node path planning in search tree. Then the simulation of this method is carried out by MATLAB. The results show that this method can find the better path from starting point to target point,which verifies that this method is effective.【总页数】3页(P605-607)【作者】李淑霞【作者单位】河南工业职业技术学院计算机工程系，河南南阳 473000【正文语种】中文【中图分类】TP24【相关文献】1.基于改进Morphin搜索树的局部路径规划算法 [J], 张毅;杜凡宇;罗元2.基于正六边形栅格JPS算法的智能体路径规划 [J], 王文明;杜佳璐3.基于IAPF与多层Morphin搜索树的移动机器人路径规划 [J], 王伟;陈跃东;陈孟元4.基于拓扑栅格建模的AGV路径规划算法优化 [J], 徐晗;金隼;罗磊;刘顺5.栅格环境下基于开阔视野蚁群的机器人路径规划 [J], 刘智飞;刘冬冬因版权原因，仅展示原文概要，查看原文内容请购买。

15.以下哪种算法在路径规划中通常用于处理动态环境？（）
A. A*算法
B. D*算法
C. Floyd算法
D. Bresenham算法
16.在路径规划中，以下哪种数据结构用于存储已访问的节点？（）
A.开放列表
B.关闭列表
C.路径列表
D.邻接矩阵
17.关于工业机器人的路径规划，以下哪个描述是错误的？（）
B. Dijkstra算法
C. D*算法
D. RRT算法
13.关于路径规划中的碰撞检测，以下哪种方法计算量相对较小？（）
A.精确碰撞检测
B.粗略碰撞检测
C.迭代最近点法（ICP）
D.点到线段距离计算
14.以下哪项不是路径平滑处理的目的？（）
A.降低路径长度
B.减少运动时间
C.减少能量消耗
D.增加路径上的拐点
3.用于评估路径规划算法性能的指标通常包括路径长度、规划时间和______。
4.在路径规划中，为了减少计算量，常用的空间划分技术有四叉树和______。
5.机器人路径规划中的碰撞检测可以通过______和基于几何的碰撞检测两种方法实现。
6.路径平滑处理的目的是为了减少路径的拐点，提高路径的______和可执行性。
A. A*算法
B. Dijkstra算法
C. Floyd算法
D. Bresenham算法
2.下列哪种算法不属于路径规划中的启发式搜索算法？（）
A. A*算法
B. D*算法
C. IDA*算法
D. Breadth First Search算法
3.在A*算法中，H(n)代表什么？（）
A.从起始点到当前点的代价
4.在工业机器人路径规划中，如何处理动态障碍物？请提出一种算法或策略，并解释其工作原理和有效性。

（ ３） （
，
） （ｉ＝０ １ ２ ．．．）， 为 ｔ 时 刻 第 ｉ 个 动 态 障碍
物在环境坐标中的位置坐标。
（
，
） （ｉ＝０ １ ２ ．．．）， 为 ｔ 时 刻 第 ｉ 个 静 态 障 碍 物
在环境坐标中的位置坐标。
（ ４） （ ｘ（ｔ）， ｙ（ｔ）， θ（ｔ）） 为 ｔ 时 刻 机 器 人 在 环 境 坐 标 中 的 位 姿，如
本文将栅格法与模拟退火法结合， 采用栅格法表示环境信 息， 利用模拟退火法进行局部路径规划使路径跳出局部极小 点， 到达目标位置。
２ 栅格法和模拟退火法的基本思想
栅格 法 是由 Ｗ．Ｅ．Ｈｏｗｄｅｎ 在 １９６８ 年 提出 的．在 进 行 路 径 规 划时采以栅格（ｇｒｉｄ） 为单位表示环境 信 息，在处 理 障 碍物 的 边 界 时，避免了复杂的计算。 可以看出栅格的大小直接影响着规划 时间的长短和精度，栅格划分越小，障碍物的表示会越精确，但同 时 会 占 用 大 量 的 存 储 空 间 ，算 法 的 搜 索 范 围 将 按 指 数 增 加 。栅 格 的划分太大，规划的路径会很不精确．
您的论文得到两院院士关注 文章编号：１００８－ ０５７０（２００７）０２－ ２－ ０２４７－ ０２
机器人技术
基于栅格法－ 模拟退火法的机器人路径规划
Ｒｏ ｂ ｏ ｔ Ｐａ ｔｈ Ｐｌａ ｎ ｎ ｉｎ ｇ Ｂａ ｓ ｅ ｄ ｏ ｎ Ｇｒｉｄ Ｍｅ ｔｈ ｏ ｄ ｗ ｉｔｈ Ｓ ｉｍ ｕ ｌａ ｔｅ ｄ Ａｎ ｎ ｅ ａ ｌｉｎ ｇ
栅格按一定的规则编号， 本文采用如图二所视的编号方法（图中
术 Ｓ 点为机器人起始点，Ｅ 点为目标点）。
创
ｒｉｊ＝
其中 ， ｔ 为 控制 参 数 ， Δｆ＝ｆｊ－ ｆｉ 为新 解 与 旧解 之 间 的目 标 函 数 差， ｆｉ 是已知解， ｆｊ 是新产生的解．

基于栅格法的机器人路径规划
王娟娟;曹凯
【期刊名称】《农业装备与车辆工程》
【年(卷),期】2009(000)004
【摘要】阐述了基于栅格法的机器人路径规划算法问题.首先通过将不完全可行栅格归于完全可行栅格,在粗略划分整个工作环境的情况下,采用概率搜索方法,先获得一条次优最短路径,然后在此基础上,将不完全可行栅格还原到原工作环境,剔除无效栅格后,通过将栅格长度等比递减的策略,最终获得一条所需精度下的最短无碰撞路径.
【总页数】4页(P14-17)
【作者】王娟娟;曹凯
【作者单位】山东理工大学交通与车辆工程学院,山东,淄博,255049;山东理工大学交通与车辆工程学院,山东,淄博,255049
【正文语种】中文
【中图分类】TP242.6
【相关文献】
1.基于改进势场栅格法的清洁机器人路径规划算法研究 [J], 梁嘉俊;曾碧;何元烈
2.基于栅格法的机器人路径规划快速搜索随机树算法 [J], 国海涛;朱庆保;徐守江
3.非结构化环境中基于栅格法环境建模的移动机器人路径规划 [J], 刘晓磊;蒋林;金祖飞;郭晨
4.基于栅格法的移动机器人路径规划研究 [J], 鲁庆
5.基于栅格法-模拟退火法的机器人路径规划 [J], 郑秀敏;顾大鹏;刘相术
因版权原因，仅展示原文概要，查看原文内容请购买。

专利名称：基于栅格地图的机器人全覆盖路径规划方法、装置及设备
专利类型：发明专利
发明人：林雅云,黄骏,周晓军,陶明,孙赛,李骊,王行,盛赞,李朔,杨淼
申请号：CN201910294129.0
申请日：20190412
公开号：CN109947114A
公开日：
20190628
专利内容由知识产权出版社提供
摘要：本发明公开了一种基于栅格地图的机器人全覆盖路径规划方法、装置及设备，首先将整个环境地图分解成若干个简单的相邻子区域，然后遍历各子区域，在高覆盖率的同时重复率也很低。

另外，在遍历的过程中，根据定位信息和地图障碍物信息实时改变行走状态，具有简单灵活、易实施的优点。

并且，机器人在清扫区域时，其主要行驶方向直接影响了路径的转折次数。

本发明使用区域的主方向作为机器人遍历清扫路径的主要行驶方向，这样可以极大地减少路径的转折次数，从而提高遍历的效率。

申请人：南京华捷艾米软件科技有限公司
地址：210012 江苏省南京市雨花台区软件大道118号新华汇B3栋8楼
国籍：CN
更多信息请下载全文后查看。

2009，45（32）移动机器人路径规划是指在有障碍物的工作环境中，寻找一条从起始点到终止点的较优的运动路径，使机器人在运动过程中能安全地绕过所有的障碍物，且所走的路径较短。

目前，对于静态环境下路径规划问题的研究已经取得较多成果，主要是用一次性全局规划来得到一条自起点到终点的安全路径，并且采用算法对路径进行优化，如遗传算法、神经网络和蚂蚁算法等[1-3]，这些算法都可以很好地实施路径规划，但存在着搜索空间大、算法复杂、效率不高等问题。

针对环境中同时存在已知静态障碍物和未知动态障碍物的情况，采用全局路径规划和局部避碰规划相结合的思想，为动态环境下的机器人路径规划的研究方法提供一种新手段。

1总体思路总体解决思路包括全局路径规划和局部避碰规划两部分。

全局路径规划根据全局感知模块提供的静态障碍物信息，采用RRT算法，确定出一条未考虑未知动态障碍物的初始全局化路径；接着，机器人按全局优化得到的路径行走，并通过传感器不断探测滚动窗口内动态障碍物的运动信息，根据对动态环境运动轨迹的预测，判断是否会发生碰撞并采取相应的避障策略，从而到达目的地且保证路径较优。

2环境描述设机器人的工作空间为二维平面上的有限平面区域AS，其中分布着有限个已知静态障碍物b1，b2，…，bn（考虑AS为任意形状，因此，可在AS边界补以障碍物栅格，将其补为正方形或长方形）和有限个未知静态障碍物。

路径规划的目的是使机器人由起点Gbegin安全避障地沿一条较短路径到达终点Gend。

为使问题简化，该文所指的动态环境只是针对未知动态障碍物做匀速直线运动的简单情况，更复杂的情况有待于今后进一步研究。

在AS中，以AS的左上角为坐标原点0，以横向为X轴，以纵向为Y轴，建立系统直角坐标系。

假设机器人在水平方向上的行走步长为δ，并且AS在X、Y方向的最大值分别为Xmax和Y max。

以δ为步长形成一个栅格，则每行的栅格数N x=X max/δ。

其中，bi（i=1，2，…，n）占一个或多个栅格，当不满一个栅格时算一个栅格。

ｏ ｂ ｔＢａ ｅ ｎ Ｇ ｒｄ Ｍ ｅｈｏ ｆＲｏ ｏ ｓ ｄ ｏ ｉ ｔ ｄ
Ｇｕ ａ ａ ， ｈ ｎ ｂ ｏ ＸｕＳ ｏ ｊ ｎ ｏ Ｈ ｉ ｏ Ｚ ｕＱｉ ｅ ｔ ｓａｄＣ ｍ ｕｅ ｃ ｎｅ Ｎ ｎｉｇＮ ｒ ｌ ｎｖｒｔ，Ｎ ｎｉｇ １０ ７ ｈｎ ） Ｓ ｈｏ ｏ ｔ ｍａｃ ｎ ｏ ｐ ｔｒ ｉ ｃ ， ａｊ ｏｍａ Ｕ ｉｅｓｙ ａｊ ０ ９ ，Ｃ ｉａ ｈ ｉ Ｓｅ ｎ ｉ ｎ ２
Ｖ １７Ｎ ． ｏ． ｏ ２
Ｊ ｎ．０ ７ ｕ ２０
基 于 栅 格 法 的 机 器 人 路 径 规 划 快 速 搜 索 随 机 树 算 法
国海 涛 ， 庆 保 ， 守江 朱 徐
（ 南京师范大学 数学 与计算机科学学院 ， 江苏 南 京 ２０ ９ ） １０ ７
［ 摘要 ］ 针对复杂环境下的机器人路径规划问题， 提出了一种全新的基于栅格法的机器人路径规划快速搜索随机树算
维普资讯
第７ 卷第 ２ 期
２０ ０ ７年 ６月
南京师 范大 学学 报（ 工程技术版 ）
ＪＵ Ｎ ＬＯ Ａ Ｊ ＧＮ Ｒ Ａ ＮＶ Ｒ Ｉ （ Ｎ ＩＥ ＲＮ Ｎ Ｅ Ｈ Ｏ Ｏ ＹＥ ＩＩＮ Ｏ Ｒ Ａ ＦＮ ＮＩ Ｏ Ｍ ＬＵ ＩＥ Ｓ Ｙ Ｅ ＧＮ Ｅ ＩＧＡ ＤＴ Ｃ Ｎ Ｌ Ｇ ＤＴＯ ） Ｎ Ｔ
法． 以机器人 出发点为随机树的根节点 ， 通过扩展 ， 渐增加 叶节 点直至随机树 的叶节点 中包 含了 目标点． 出发点 到 目标 逐 从 点之间 的一条 以随机树的边组成的路径就是 目标路径 ． 研究表 明在 同样 的环境下与遗传算法 、 算法 相 比该方法能 在更 短 Ａ
的时 间内找到更优的路径． 仿真实验也表明 ， 即使在随机 生成 的复杂环境下 ， 利用该算法也可 以快速规划出一条全 局优化路

一种基于环境栅格地图的多机器人路径规划方法
陈晓娥;苏理
【期刊名称】《机械科学与技术》
【年(卷),期】2009(028)010
【摘要】利用多机器人系统实现对已知环境区域的全覆盖路径规划.提出了一种基于环境栅格地图的路径规划及路径优化算法.首先建立已知环境的矩形化栅格地图,用分区算法实现地图建模.然后在分区内采用广义VORONOI图(GVG)和中轴实现机器人运行的路径规划;最后利用拓扑图、加权值的深度优先搜索算法和Dijkstra 算法优化所得到的机器人运行路径最终得出了机器人在分区内优化运行路径.机器人沿着路径即可实现对已知环境区域的全覆盖,并且使得机器人的运行路径最短.对于环境内存在的任意形状的障碍物,此算法均可适用.仿真结果验证了该算法在多机器人路径规划中的可行性和有效性.
【总页数】5页(P1335-1339)
【作者】陈晓娥;苏理
【作者单位】陕西纺织服装职业技术学院,咸阳,712000;西安微电子技术研究所,西安,710054
【正文语种】中文
【中图分类】TP24
【相关文献】
1.一种变栅格地图的巡检机器人路径规划方法研究 [J], 彭刚;沈宇
2.基于栅格地图环境的机器人路径规划算法 [J], 刘琳琳
3.一种多机器人栅格地图拼接方法的研究 [J], 李雅梅; 张瑞; 吕猛
4.基于栅格地图的环境建模在清扫机器人路径规划中的应用 [J], 周欣沅;张玲;马永帅
5.基于SURF特征的多机器人栅格地图拼接方法 [J], 唐宏伟;孙炜;杨凯;林安平;吕云峰;程熙
因版权原因，仅展示原文概要，查看原文内容请购买。

10. if dis[Xnew , xgoal] < u
11.
Return T ；
算法在第 1~2 行初始化随机树，满足最大迭代次数
下，进入循环。
第 3~7 行产生新节点，RANDOM 函数在空闲区域
中生成随机节点 Xrand 。 NEAREST 函数利用欧式距 离选择树节点中离 Xrand 最近的节点 Xnear 。若 Xnear 与 Xrand 的连线上存在障碍物，则判断条件终止当前循环， 进入新一轮循环。 NEW_STATE 函数从 Xnear 与 Xrand 的连线方向上扩展固定步长 u ，得到新节点 Xnew 。节 点扩展过程如图 1 所示。
基金项目：国家自然科学基金（No.71371058，No.61363026）。 作者简介：陈秋莲（1974—），女，博士，副教授，研究领域为优化计算与 CAD；蒋环宇（1995—），男，硕士研究生，研究领域为路径规
划与算法优化，E-mail：597650532@；郑以君（1994—），男，硕士研究生，研究领域为路径规划与算法优化。 收稿日期：2019-05-07 修回日期：2019-06-21 文章编号：1002-8331（2019）16-0010-08 CNKI 网络出版：2019-06-28, /kcms/detail/11.2127.TP.20190626.1751.022.html
第 8~9 行将生成的新节点与新边添加至随机树。 第 10~11 行给出算法终止条件。若新节点与目标 点的欧式距离小于固定步长或者已经抵达目标点，则返 回随机树 T 。若达到最大迭代次数 K ，终止算法并退出。 返回随机树后，标记目标点与循环遍历得到的父节 点，直到树根节点被标记。此时，算法从随机树中找到 一条由标记节点连接的起点至目标点间无碰撞的可行 路径。

机器人路径规划算法中的快速搜索技巧优化自动路径规划是机器人技术领域的重要研究方向之一。

路径规划算法的效率直接影响着机器人在现实环境中的运动能力和实时响应能力。

为了提高机器人路径规划算法的搜索效率，研究者们一直在寻求各种优化技巧。

本文将介绍几种快速搜索技巧，以优化机器人路径规划算法的性能。

一、启发式搜索算法启发式搜索算法是一种基于问题域知识的搜索方法，它通过引入启发式函数来指导搜索过程，从而提高搜索效率。

在机器人路径规划中，常用的启发式搜索算法包括A*算法和D*算法。

1. A*算法A*算法是一种基于启发式函数的有界最优搜索算法。

它利用启发式函数估计当前节点到目标节点的代价，通过综合考虑当前节点的实际代价和启发式函数的估计值，选择最有可能导致最优解的节点进行扩展。

A*算法的核心在于启发式函数的设计，一个合理的启发式函数可以大幅提高搜索效率。

2. D*算法D*算法是一种基于增量搜索的路径规划算法。

它通过动态地修正节点的代价值，使得在搜索过程中只需要重新计算受影响的节点，从而减少算法的计算量。

D*算法在实时应用场景中具有一定的优势，特别适用于环境动态变化的情况。

二、剪枝技巧剪枝技巧是指通过排除无效的搜索空间来减少搜索的范围，从而提高搜索效率。

在机器人路径规划中，常用的剪枝技巧包括：1. 空间剪枝空间剪枝是指根据问题设置的域知识，排除一些明显不可能存在路径的区域，从而减少搜索空间。

例如，在机器人移动中，一些障碍物的位置是固定的，可以将这些区域排除在搜索范围之外，从而减少搜索的次数。

2. 时间剪枝时间剪枝是指通过设置时间限制来控制搜索的深度，从而减少搜索的次数。

例如，在实时应用中，可以根据机器人的运行速度和任务的紧急程度，设置一个合理的时间限制，当搜索时间超过限制时，及时返回当前最优解，避免无谓的搜索。

三、并行计算技术并行计算技术是指将搜索任务分成多个子任务，并行地进行计算，从而加速搜索过程。

在机器人路径规划中，常用的并行计算技术包括：1. 分布式计算分布式计算是指将搜索任务分发到多个计算节点上进行计算，然后将计算结果进行合并。

基于栅格模型的机器人路径规划快速算法
周郭许;唐西林
【期刊名称】《计算机工程与应用》
【年(卷),期】2006(42)21
【摘要】机器人路径规划算法通常要求是实时的,遗传算法和蚁群算法应用于机器人路径规划时性能并不突出.论文提出的基于栅格的快速算法,简单实用,且计算速度快、占用存贮空间少.实验结果表明,在同等规模下,该算法求解时间仅为蚁群算法求解时间的大约0.025%,算法在更大的数据集上也取得了成功.同时该算法还是一个高效的迷宫最短路的搜索算法.
【总页数】3页(P197-199)
【作者】周郭许;唐西林
【作者单位】华南理工大学数学科学学院,广州,510640;华南理工大学数学科学学院,广州,510640
【正文语种】中文
【中图分类】TP24
【相关文献】
1.基于栅格法的机器人路径规划快速搜索随机树算法 [J], 国海涛;朱庆保;徐守江
2.基于栅格模型机器人路径规划的量子蚁群算法 [J], 张晨;游晓明
3.基于栅格模型机器人路径规划的改进蚁群算法 [J], 王沛栋;冯祖洪
4.一种基于栅格模型的机器人路径规划算法 [J], 吴锋;杨宜民
5.基于栅格模型与改进蚁群算法的机器人路径规划研究 [J], 王影; 梁凯; 于攀; 刘麒
因版权原因，仅展示原文概要，查看原文内容请购买。

关 键 词 ：移动 机 器人 ；路除 、 插入算子达到路径 规划 中避 障的要求 。 虽然仿
真 结 果 较 为 优 异 ， 是其 实 现过 程 也 是 较 为 复 杂 。 此 但 在
机 器 人 路 径 规 划 技 术 是 机 器 人 学 研 究 领 域 的一 个 重 要 分 支 ．它 是 研 究 机 器 人 控 制 系 统 和导 航 技 术 的基
基础上 ． 本文提 出了一种基 于栅格模 型的新 算法 ． 通过 引入参考方 向和移动 因子等概念 ．有 针对 性地实现 了 可控的路径搜 索 ． 高了对最优路径 的搜索效率。 提 仿真 实验结果表 明．基于栅格模 型的新算法具有较 好的实
时 性 和 适 应性
本环节 之一。 它要求机器人在有 障碍物 的环境 中 ． 依据 某个 或某些性能指标 （ 例如最少能量 消耗 、 短行走路 最 径． 最短行走时 间等 ） 在其工作空间 中寻找一 条从起始 状态 到 目标状态 的最 优或近似最优路径 ．使 机器人在
分 配 发 送来 的 目标 位 置 和 机 器 人 当 前 位 置 的连 线 确 立 作 为 机器 人 行 走 的参 考 方 向。 定 义 １ 机 器 人 当前 位 置 与 目标 位 置 连 线 所 确 定
三
一
／
种基于栅 格模 型 的机器人路径规划算 法
吴 锋 ． 杨宜 民
（ 东 工 业 大 学 自动 化 学 院 ， 州 ５ ０ ９ ） 广 广 １０ ０
摘
要 ：在 移 动 机 器 人 路 径 规 划 ｆ题 的 研 究 中 ，针 对 现 有 算 法 效 率 较低 以及 实现 过程 复 杂 的 问 题 。 ＂ ｌ
样 环境 所 更 新 ． 境 坐 标 是 绝 对 地 表 示 环 境 ． 在 一 定 环 并 的 实 时 区 域 、 定 时 间 内保 持 坐 标 原 点 的 固定 ， 在 此 一 但 局 部 区 域 内完 成 了移 动 后 ．再 基 于 目前 行 驶 点 和 下 个 目标 点 重 新 建 立 机 器 人 的环 境 地 图 栅 格 法 就 是 在 世

际 应 用 中 ，主 要 面 临 的 问 题 是 种 群 多 样 性 不 足 导 致
的 种 群 过 早 收 敛 问 题 ，这 是 普 遍 现 象 ，前述文献算
法都从不同角度进行了有效解决[8,9],获 得 了 一 定
效果。
本文研宄思路是利用多种群并行进化方式，通
过 设 置 有 效 的 种 群 融 合 控 制 手 段 ，实 现 对 种 群 进 化 多 样 性 的 有 效 控 制 。同 时 ，结 合 粒 子 群 优 化 算 法 中
化
舛 ) (2)
②
机 器 人 信 号 接 收 阈 值 响 应 模 型 。机 器 人 所
能 接 收 到 的 目 标 对 象 的 信 号 越 强 ，表 示 该 机 器 人 可
参 与 对 象 搜 索 的 几 率 越 高 。利 用 迭 代 优 化 过 程 可 实
现 对 机 器 人 目 标 搜 索 过 程 的 任 务 进 行 有 效 分 配 ，具
i 引言
近 年 来 ，智 能 优 化 算 法 得 到 快 速 发 展 ，粒子群 优 化 （particle swarm optimization, P S O )算法是常 用的仿生优化算法，具 有优 异 的 优 化 性 能 >2]。同 经 典 的 遗 传 算 法 、差 分 进 化 相 比 ，采用粒子群优化 算 法 进 行 机 器 人 路 径 规 划 具 有 一 定 优 势 ，其粒子的 运动过程与机器人路径规划过程更为接近，具有先
体过程如图1 所示。
图 2 路径规划栅格模型 Fig. 2 Path planning grid model
第6 期
刘晓林等：考 虑 LIM栅格模型的MPMVPSO机器人路径规划算法
•1257 •

基于随机树节点的变电站机器人全覆盖巡检路径优化设计研究作者：郑磊，王楠，李金鑫，廖海，董泽强来源：《粘接》2023年第12期摘要：常规的机器人巡检路径规划方法通常以最短规划时长作为目标，通过结合机器人的工作性能，对目标函数进行约束，通过求取最优解实现路径规划。

但由于忽略了机器人工作视野的限制，导致规划效果不佳。

对此，针对变电站机器人，提出基于快速搜索随机树的全覆盖巡检路径规划方法。

首先，利用栅格法对巡检区域进行环境建模，并计算局部滚动窗口，获得机器人的最佳工作视野范围。

然后，将目标采样阈值设定为一个动态变量，计算随机树节点的路径代价，通过将双向搜索与迭代的方式，实现随机树节点扩展，从而搜索到最优路径规划结果。

在实验中，对该方法的规划效果进行检验，结果表明，在可以完成巡检任务的前提下，采用该方法规划的巡检路径较短，可以提高机器人巡检的效率。

关键词：快速搜索随机树；变电站机器人；巡检路径；路径规划中图分类号：TP399；TM743文献标志码：A文章编号：1001-5922（2023）12-0169-05Research on the optimal design of substation robot full coverage inspection path based on random tree nodesZHENG Lei，WANG Nan，LI Jinxin，LIAO Hai，DONG Zeqiang（Zunyi Power Supply Bureau of Guizhou Power Grid Co.，Ltd.，Zunyi 563100，Guizhou China）Abstract：The conventional robot inspection path planning method usually takes the shortest planning time as the goal，constrains the objective function by combining the working performance of the robot，and achieves path planning by finding the optimal solution.However，due to the neglect of the limitations of the robo t’s working field of view，the planning effect is not satisfied.In this regard，a full coverage inspection path planning method based on fast search random trees was proposed for substation robots.Firstly，the grid method was used to model the environment of the inspection area，and the local rolling window was calculated to obtain the best working field of view of the robot.Then，the target sampling threshold was set as a dynamic variable to calculate the path cost of the random tree nodes，and the random tree nodes were expanded by bidirectional search and iteration，so as to search for the optimal path planning results.In the experiment，the planning effect of this method was tested，and the results showed that，under the premise of completing the inspection task，the inspection path planned by this method was shorter，which can improve the efficiency of robot inspection.Key words：quickly search for random trees;substation robots;inspection path;path planning變电站机器人巡检系统作为一种先进的解决方案，能够实现变电站设备的实时监控和定期巡检，提高了电力系统的稳定性和可靠性。

第24卷第2期 哈　尔　滨　工　程　大　学　学　报 V ol.24№.2 2003年4月 Journal of Harbin Engineering University Apr.2003基于势场栅格法的机器人全局路径规划王醒策,张汝波,顾国昌(哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨150001)摘　要:综合势场法和栅格法的优点,提出了一个新的全局路径规划方法———势场栅格法.算法在避免局部最优点和降低计算量方面,有着良好的效果;并且可以自动确定栅格粒度.最后,文章分析了影响算法精度的因素,仿真试验表明此算法有良好的可行性和有效性.关键词:势场栅格法;全局路径规划;智能机器人中图分类号:TP24　文献标识码:A　文章编号:1006-7043(2003)02-0170-05Potential grid based global path planning for robotsWANG X ing2ce,ZHANG Ru2bo,G U G uo2chang(School of C omputer Science and T echnology,Harbin Engineering University,Harbin150001,China)Abstract:The potential way is combined with the grid way to form a new potential grid way,which is very effective in reducing com putational w ork and av oiding local minima,and can automatically create grids.The factors having in2 fluence on the accuracy of calculation are analyzed and the feasibility and the validity of the mehtod proposed is veri2 fied through simulation.K ey w ords:potential grid method;global path planning;intelligent robot 全局路径规划技术是智能机器人领域中的核心问题之一,也是机器人学中研究人工智能的一个重要方面.解决全局路径规划问题的基本的方法有:几何法[1]、单元分解法[2]、人工势场法[3]和数学分析法等.全局路径规划方法的一般步骤为:1)划分状态空间;2)形成包含状态空间信息的搜索空间;3)在形成的搜索空间上应用各种搜索策略进行搜索.势场的方法是由K hatib[4]最先提出的.他把机械手或者是移动机器人在环境中的运动视为在一种抽象的人造受力场中运动:目标点对机器人产生引力,障碍物对机器人产生斥力,最后根据合力来确定机器人的运动.应用势场法规划出来的路径一般是比较平滑并且安全,但是这种方法存在局部最优点问题(local minima).为了解决这个问题,许多的学者进行了研究:如Rim on[5], Shahid[6]和K hosla[7]等等.他们期望通过建立统一的势能函数来解决这一问题.但这就要求障碍物最好是规则的,否则算法的计算量将很大,有时甚至是无法计算的.栅格法是由W.E.H owden在1968年提出的.他在进行路径规划时采用了栅格(grid)表示地图,在处理障碍物的边界时,避免了复杂的计算.可以看出,栅格粒度越小,障碍物的表示会越精确,但同时会占用大量的存储空间,算法的搜索范围将按指数增加.栅格的粒度太大,规划的路径会很不精确.所以栅格粒度大小的确定,是栅格法中的主要问题.本文针对多机器人编队任务的需要,综合了栅格法和势场法的优点,提出一种新的方法,势场栅格法.一般全局路径规划主要是为了满足单机器人的需要,这里针对多机器人的编队任务,考虑到路径安全性和可靠性要比路径长短重要得多,所以采用势场法.为了降低势场法的计算量,应用栅格法表示地图.针对势场法和栅格法的自身的缺陷,在整个的路径规划的算法中进行了相应的改进.算法的特点有以下几个:收稿日期:2002-05-27.作者简介:王醒策(1977-),女,博士研究生.研究方向为智能控制,路径规划,多机器人协调. 1)系统根据地图中障碍物的疏密自主决定栅格粒度.因为系统规划出的路径还要依靠势场的作用,所以即使栅格粒度较大时,也能规划出比较好的路径.2)由于应用栅格的方法,在计算整个的地图中的函数势时就只要计算栅格点的时函数,根本地解决了传统势场法的大计算量问题.整个的算法中只计算最近障碍物对机器人的排斥,终点对机器人的吸引是由启发函数来完成的,避免了局部最优点问题.1　基于势场栅格法的路径规划算法应用势场栅格法来规划路径的过程:在平面内,首先系统根据地图中障碍物的疏密来决定栅格的粒度;然后求出每一个栅格中心点的势能值;经过g函数变换后,再利用A3搜索,综合栅格的g 函数结果与栅格与终点的距离,通过启发函数的运算,得到一条自始至终的路径.1.1　栅格粒度的确定系统会根据地图中障碍物疏密来决定栅格粒度的大小.在得到地图之后,首先计算地图中所有障碍物面积和.凸多边形以某一顶点进行三角剖分,椭圆和其它的不规则图形则按照能够对它们进行最小覆盖的长方形进行计算.然后根据障碍物的面积在整个地图中所占的比例来决定地图中的栅格粒度.栅格粒度大小生成方法:1)在地图中任选一个障碍物.2)判断此障碍物是否为凸多边形?3)如果是,则以某一个顶点为起始点,把多边形划分为多个互不相交的三角形.4)如果不是,则找出这个障碍物所有顶点中的x max,y max,x min,y min,然后分别以(x min,y min)和(x max,y max)为对角顶点绘制一个长方形;以长方形某一顶点为起始点,把长方形划分为两个不相交的三角形.5)按照公式S=12×a×b×sinα,计算各三角形的面积.其中a,b是以剖分顶点为顶点的三角形的两边,α是a,b所夹的角度.6)地图中还有没计算的障碍物吗?如果有,则转1).7)计算障碍物的面积和S ob=∑l∈ΩS l,Ω是整个障碍物集合,l是Ω中的一个元素.8)计算栅格粒度:计算l temp=S obS总×l max,得到l=l temp,if l temp>l min;l min,其他.(1)式中:l max是定义的栅格的最大边长,l min是栅格的最小边长,l是最终的栅格边长.9)算法结束.图1给出了不同形状障碍物的剖分结果.图1　不同形状障碍物的剖分Fig.1　The triangulating of different obstacles1.2　势场的构造传统势场法里势场构造是应用引力与斥力共同对机器人产生作用.表示为U art=U o+U g.(2)式中:U art表示总势场,U o表示斥力场,U g表示引力场.势场中的力表示为F art=F g+F o.(3)式中:F g是引力,F o是斥力,F art是合力.其中F g=-grad(U g)=-5U g5x i+5U g5y j+5U g5z k,(4)F o=-grad(U o)=-5U o5x i+5U o5y j+5U o5z k,(5) 可能会有F art=0,因为引力和斥力共同对机器人作用,当目标点对机器人的引力等于障碍物对其产生的斥力的时候,算法会产生局部极小点,需要引入其它的量对机器人进行控制.而在这个算法中,障碍物产生的斥力场构造出整个势场,表示栅格的安全程度.路径终点对障碍物的吸引体现在启发函数中路径预测长度上.机器人行走的方向由启发函数来决定,而非引力和斥力来决定.由于没有力的矢量计算,从根本上解决了局部最优点的问题.・171・第2期 王醒策,等:基于势场栅格法的机器人全局路径规划在算法中先计算势能值,应用g 函数对势能值变换构造出势场.这里势能值定义为栅格中心点到最近障碍物的距离,表示此栅格点的危险程度.利用扫描法计算每一个栅格势能值.具体方法为:1)地图中选择一个栅格;2)初始化圆的半径r =r 0;3)以栅格中心点n 为圆心,以r 为半径画圆;4)判断圆与障碍物是否相交;5)如果相交,则返回栅格中心点的势能的值为D (n )=r -l p ;6)如果不相交,则r =r +l p ,转3);7)地图中是否还有没有计算的栅格?若是,则转1);8)算法结束.这里r 0是圆半径的初始值,l p 是等势圈的半径差.由图2可以看到,在某栅格中心点a 处,进行等势波样扩张,直到等势圈与障碍物相交.图2　栅格中的势能值的选取Fig.2　The potential value of the grid栅格的势能值就是栅格与离其最近的障碍物的距离.这是因为对栅格的安全影响最大的是距栅格最近的障碍物.D (n )=min p ∈Ωdis (n ,p ).(6)式中:n 是某栅格,Ω是整个的障碍物集合,p 是Ω集合中元素,dis (n ,p )是n 到p 经过扫描法计算出来的距离.计算好地图中的各个栅格节点势能值之后,进行g 函数变换,g 函数为g (n )=100×exp (-D (n )/40).(7)式中:D (n )是势场中栅格n 的势能值.当栅格n 距障碍物的距离越大,则它的g 函数将越小.函数变换使势能与栅格中点与路径终点的距离在大致相等的数量级上,可以共同对节点的选择起作用.地图的势场,表示为不同栅格节点的g 函数值.总势场为U art =U o ={g (n )|g (n )=100×exp (-D (n )/40),n ∈Ψ}(8)式中:Ψ是地图中所有栅格中心点的集合.图4是地图3由此算法产生的势场三维图.图3　一幅地图Fig.3　Amap图4　地图3的势场三维图Fig.4　The 32D map of the figure 3′s potential field1.3　全局路径的栅格节点的选取全局路径节点的选取是应用A 3算法进行相邻节点搜索.具体的过程是:在图中的a 栅格的周围有8个栅格.算法按照启发函数,在栅格a 周围的8个栅格中寻找一个启发函数值最小的栅格(例如栅格2).然后,把a 标注为已走过的栅格,画出从此栅格到新寻找到的栅格2之间的路径.然后以栅格2为母节点,重复这一过程.如图5所示.启发函数:f (n )=g (n )+h (n ),n =1…8.(9)式中:n 是a 周围的8个栅格节点中的某一个,g (n )是n 节点的g 函数,h (n )是n 节点到路径终点的估计距离,表示为n 节点到路径终点的欧氏距离.・271・哈　尔　滨　工　程　大　学　学　报 第24卷图5　全局路径的节点的选取Fig.5　The node selection of global pathh (n )=(x n -x end )2+(y n -y end )2.(10)式中:(x n ,y n )是n 栅格的中心点坐标,(x end ,y end )是规划的路径终点的坐标.k 为被选中的下一个栅格节点.k =min 8n =1(f (n )).(11) 当某一个栅格中心点与障碍物的距离越大,与终点的距离越短,那么整个的启发函数的值将越小,此栅格将更容易被选中.这样就可以保证在每次进行栅格选取的时候,选择一个相对于其它的栅格距离障碍物最远而距离终点最近的栅格节点.1.4　路径的回溯方法当利用栅格法来进行全局路径规划的时候,必然会讨论路径的节点回溯问题.首先来介绍一下路径的回溯问题.如图6所示,路径选择图中的B 栅格后,根据启发函数的计算,可以得到下一个栅格为栅格A ,可以看到在A 栅格除了B 栅格之外,不与任何节点连通,这样路径会进入死胡同.但是即使出现这种情况,整个地图可能依然存在着从起点到终点的路径.因此要进行回溯操作.在这种情况下,把A 栅格打上危险标记,然后回溯到B 栅格,重新利用启发函数寻找节点的计算.在新一次的计算中,根据危险标记滤掉A 栅格,以免引起上述的情况.图6　路径节点的回溯Fig.6　The backup of the path node在算法中,栅格需要在两种情况下打标记.一种情况是B 栅格进入A 栅格之后,为了防止路径的循环、交叉和跳跃,为B 栅格打上标记,使得A 栅格在下一次选择时,不再考虑B 栅格.另一种情况就是在回溯时,B 栅格进入A 栅格之后,发现A 栅格不连通之后,为A 栅格打上标记,并解开B 栅格由于第一种情况所打的标记.这两种标记中,第一种标记是表示路径所经过的栅格;另一种标记是表示栅格的连通性.在这里定义栅格的结构类型时,用两种不同的布尔量来实现两种标记的区别.typedef struct{……bool m -liantong ;//栅格中路径经过的标记bool m -around[8];//此栅格与其周围的栅格的连通情况……};1.5　算法的总结最后来总结一下整个的算法:step 1:初始化算法;step 2:对地图进行预处理.根据障碍物在地图中的密度,生成栅格;step 3:应用扫描法和g 函数计算地图势场;step 4:设机器人的起始节点所在栅格为当前的路径搜索栅格.判断当前栅格是否为路径的终点,是则转step8;step 5:根据公式(9),利用A 3算法进行路径下一节点的搜索;step 6:下一个栅格是否为路径终点?是则转step8;step 7:计算的路径节点需要回溯?若是则采用回溯算法,否则把搜索到的栅格当作当前栅格,返回step5;step 8:算法结束;2　仿真试验以及结果分析根据以上介绍的算法,在P Ⅲ800机器上,应用VC6.0编制仿真试验环境下,进行了相应的仿真试验.经过多次实验得到l max =40,l min =5,r 0=l p =5.图7和8是在不同环境中的规划的结果.图7因为障碍物稀疏,从路径的折点就可以看出栅格粒度较大,而图8中栅格粒度较小.经过多次实验验证,・371・第2期 王醒策,等:基于势场栅格法的机器人全局路径规划此全局路径规划算法有很高的安全性,可以满足多机器人编队的任务的需要.同时算法具有很好的扩展性,对于三维地图中的全局路径规划也同样适用.并且对机器人局部路径规划也有一定的借鉴作用.图7　在稀疏环境下的全局路径规划结果Fig.7　The planning result in the map with sparseobstacles图8　在障碍物密集的时候的路径规划结果Fig.8　The planning result in the map with dense obstacles 由于在地图采用了栅格表示法,所以在经过扫描法计算出势场后,路径规划的速度会很快,算法的实时性较强.整个算法的精度与栅格的粒度的大小l 和扫描法中每一层等势圈之间的半径差值l p 有关.在这两方面选取恰当的系数,系统就可以规划出较好的路径.3　结束语势场法由于结构简单、易于实现,所以在路径规划中被广泛的采用.但是势场法存在着大计算空间和局部最优点问题.针对势场法的这些缺点,应用栅格法与势场法的结合,降低势场法的计算复杂度;应用障碍物构造势场,避免了局部最优点的问题.此算法在三维空间中的路径规划也同样有效,是一种安全、可靠和高效的算法.参考文献:[1]JANET J A.The essential visibility graph :an approach toglobal m otion planning for autonom ous m obile robots[A].Proc of IEEE Int C on f on R obotics and Automation [C].Nag oya ,Japan ,1995.[2]LAZ ANO 2PEREZ.S patial planning :a con figuration space ap 2proach[J ].IEEE T ransaction on C omputers ,1983,32(2):108-119.[3]Y OSHIFURMI KIT AM URA.32D path planning in a dynamic environment using an octree and an artificial potential field [A].IROS ’95II[C].Pittsburgh ,US A ,1995.[4]K H ATI B O.Real 2time obstacle av oidance for manipulators and m obile robots[A].IEEE Int C on f on R obotics and Automation [C].S t 2Louis ,Miss ouri ,1985.[5]RI M ON E.Exact robot navigation using artificial potentialfunctions [J ].IEEE T ransactions on R obotics and Automa 2tion ,1992,8(5):501-518.[6]SH AHI DI R.SH AY M AN M.M obile robot navigation usingpotential functions[A ].IEEE Int C on f on R obotics and Au 2tomation[C].New Y ork ,1991.[7]KI M Jin 2oh ,K H OS LA P.Real 2time obstacle av oidance using harm onic potential function [A ].IEEE Int C on f on R obotics and Automation[C].Sacremento ,C A ,1991.[8]王田苗,张　钹.基于环境势场法的感知-动作行为研究[J ].计算机学报,1993(2):89-96.[9]张汝波,熊列彬.基于势场法的路径规划[J ].现代科技译丛,1996(2):26-29.[10]张汝波,张国印,顾国昌.基于势场法的水下机器人全局路径规划的研究[J ].黑龙江自动化技术与应用,1996(4):30-33.[责任编辑:刘玉明]・471・哈　尔　滨　工　程　大　学　学　报 第24卷。