多路口环境下RRT的最优路径规划
发布时间：2021-09-09 20:05
针对于多路口环境下RRT的搜索时间长,搜索范围广和路径不平整的问题。提出一种基于路标引导和增长采样区域的混合策略来引导RRT算法向目标搜索。将对地图做预处理,处理掉较小的障碍物,尽可能保存大障碍物,得到预处理地图;在新地图上路口区域设置路标点,路标点的可视区域的组合要覆盖整个地图,根据其在新地图上的连通区域,通过寻找出一组从起点到终点的最优路标点组合,以相邻两路标之间构建移动增长采样区域来引导RRT算法快速向目标搜索;用树枝修剪和二次贝塞尔曲线拟合生成光滑路径。通过仿真实验验证了算法的有效性、合理性和正确性。
【文章来源】：计算机工程与应用. 2020,56(19)北大核心CSCD
【文章页数】：6 页
【部分图文】：
路标点设立
本文所采用的地图是全局栅格地图，地图中存在不同大小的障碍物，增加路口区域的复杂性，在随机搜索树搜索时，很难有明确的方向引导，而且多个障碍会影响机器人对方向的判断，因此本文将用过滤的地图和路标来寻找随机搜索树扩展的引导方向。过滤掉较小障碍物方便更好地在路标间寻找连通方向，如图1所示，文献[11]提出将图形中的不同物体分类。本文根据地图判断每个像素是否与其他像素的八领域内连接，如果连接则把他们归为一类，否则就贴上另外的标签，最后将过滤掉标签个数小于某一个值的类别[11-12]。保存标签数量多的部分（即障碍物大的部分）。对于函数Get New Map，首先输入二值化的地图map，初始化一个同等大小且像素值全为0的newmap(line1～2），通过遍历map行列，找到第一个在map单元值为1且newmap值为0的单元，并将newmap的对等位置赋予标签startlabel，再根据函数findconnectlabel不断更新newmap(line3～10），最后输出newmap。对于函数findconnectlabel，首先找出该位置在newmap和map对应位置的各自相应的八邻域内值（line2），对于该单元八邻域的值，在newmap上的值为0且在map上为1时，则赋予newmap相应位置的label，同时对八邻域的单元做函数findconnectlabel的递归（line3～7），最后更新完newmap。
通过上一步的处理，得到一系列最优路标点集合。当在两个路标间采样时，参数μ为随机采样区域宽度放大系数，Collision Check Time为碰撞检测次数，Δμ为增加采样区域的范围。当搜索树在两路标之间搜索的时候，如果初始构建的采样区域不能找到解或碰撞检测次数达到一个值时，区域将根据Δμ进行放大。如果工作空间存在从起始点到目标点的可行路径，放大的区域将覆盖整个地图，最终可以找到一条可行路径，也从侧面验证基于增长采样区域RRT算法的概率完备性。如图5显示了RRT根据增长区域扩展的方式。2.3.2 合理性采样策略
【参考文献】：
期刊论文
[1]室内外一体化最优路径分析算法实现[J]. 张文元,丁京祯,杨丽娜,杨翔宇. 计算机工程与应用. 2018(18)
[2]路网环境下的最近邻查询技术[J]. 鲍金玲,王斌,杨晓春,朱怀杰. 软件学报. 2018(03)
[3]一种车联网环境下的城市车辆协同选路方法[J]. 吴黎兵,范静,聂雷,崔建群,邹逸飞. 计算机学报. 2017(07)
[4]节点约束型最短路径的分层Dijkstra算法[J]. 康文雄,许耀钊. 华南理工大学学报(自然科学版). 2017(01)
[5]斜尖针穿刺软组织建模及针尖轨迹预测[J]. 杜海艳,张永德,赵燕江,姜金刚,贾小红. 仪器仪表学报. 2015(08)
[6]动态不确定环境下多目标路径规划方法[J]. 魏唯,欧阳丹彤,吕帅,冯宇轩. 计算机学报. 2011(05)
[7]卫星时变拓扑网络最短路径算法研究[J]. 张涛,柳重堪,张军. 计算机学报. 2006(03)
本文编号：3392703
【文章来源】：计算机工程与应用. 2020,56(19)北大核心CSCD
【文章页数】：6 页
【部分图文】：
路标点设立
本文所采用的地图是全局栅格地图，地图中存在不同大小的障碍物，增加路口区域的复杂性，在随机搜索树搜索时，很难有明确的方向引导，而且多个障碍会影响机器人对方向的判断，因此本文将用过滤的地图和路标来寻找随机搜索树扩展的引导方向。过滤掉较小障碍物方便更好地在路标间寻找连通方向，如图1所示，文献[11]提出将图形中的不同物体分类。本文根据地图判断每个像素是否与其他像素的八领域内连接，如果连接则把他们归为一类，否则就贴上另外的标签，最后将过滤掉标签个数小于某一个值的类别[11-12]。保存标签数量多的部分（即障碍物大的部分）。对于函数Get New Map，首先输入二值化的地图map，初始化一个同等大小且像素值全为0的newmap(line1～2），通过遍历map行列，找到第一个在map单元值为1且newmap值为0的单元，并将newmap的对等位置赋予标签startlabel，再根据函数findconnectlabel不断更新newmap(line3～10），最后输出newmap。对于函数findconnectlabel，首先找出该位置在newmap和map对应位置的各自相应的八邻域内值（line2），对于该单元八邻域的值，在newmap上的值为0且在map上为1时，则赋予newmap相应位置的label，同时对八邻域的单元做函数findconnectlabel的递归（line3～7），最后更新完newmap。
通过上一步的处理，得到一系列最优路标点集合。当在两个路标间采样时，参数μ为随机采样区域宽度放大系数，Collision Check Time为碰撞检测次数，Δμ为增加采样区域的范围。当搜索树在两路标之间搜索的时候，如果初始构建的采样区域不能找到解或碰撞检测次数达到一个值时，区域将根据Δμ进行放大。如果工作空间存在从起始点到目标点的可行路径，放大的区域将覆盖整个地图，最终可以找到一条可行路径，也从侧面验证基于增长采样区域RRT算法的概率完备性。如图5显示了RRT根据增长区域扩展的方式。2.3.2 合理性采样策略
【参考文献】：
期刊论文
[1]室内外一体化最优路径分析算法实现[J]. 张文元,丁京祯,杨丽娜,杨翔宇. 计算机工程与应用. 2018(18)
[2]路网环境下的最近邻查询技术[J]. 鲍金玲,王斌,杨晓春,朱怀杰. 软件学报. 2018(03)
[3]一种车联网环境下的城市车辆协同选路方法[J]. 吴黎兵,范静,聂雷,崔建群,邹逸飞. 计算机学报. 2017(07)
[4]节点约束型最短路径的分层Dijkstra算法[J]. 康文雄,许耀钊. 华南理工大学学报(自然科学版). 2017(01)
[5]斜尖针穿刺软组织建模及针尖轨迹预测[J]. 杜海艳,张永德,赵燕江,姜金刚,贾小红. 仪器仪表学报. 2015(08)
[6]动态不确定环境下多目标路径规划方法[J]. 魏唯,欧阳丹彤,吕帅,冯宇轩. 计算机学报. 2011(05)
[7]卫星时变拓扑网络最短路径算法研究[J]. 张涛,柳重堪,张军. 计算机学报. 2006(03)
本文编号：3392703
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3392703.html
