基于三维栅格地图的移动机器人路径规划.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：0.63M 资料格式：pdf 举报版权申诉

weixin_38734492-12145426-16359647577106900460.pdf-第1页.png

第1页 / 共7页

weixin_38734492-12145426-16359647577106900460.pdf-第2页.png

第2页 / 共7页

weixin_38734492-12145426-16359647577106900460.pdf-第3页.png

第3页 / 共7页

weixin_38734492-12145426-16359647577106900460.pdf-第4页.png

第4页 / 共7页

weixin_38734492-12145426-16359647577106900460.pdf-第5页.png

第5页 / 共7页

weixin_38734492-12145426-16359647577106900460.pdf-第6页.png

第6页 / 共7页

weixin_38734492-12145426-16359647577106900460.pdf-第7页.png

第7页 / 共7页

文本预览

中国科技论文在线基于三维栅格地图的移动机器人路径规划# http://www.paper.edu.cn 5 10 15 20 25 30 张彪，曹其新，王雯珊** （上海交通大学机器人研究所）摘要：面向移动机器人路径规划问题，研究了基于三维栅格地图的路径规划方法。首先使用装载三维激光扫描仪的移动机器人收集环境点云，将三维点云转换成为八叉树结构的三维栅格地图，并扩展了 D*算法使之考虑机器人尺寸，并检测每一状态是否与环境发横碰撞，最终直接生成机器人运动轨迹。实验中创建了有多个障碍物的环境三维栅格地图，并生成了两条可行路径，验证了该方法的可靠性和实用性。关键词：机械电子工程；路径规划；三维栅格地图；移动机器人；三维点云中图分类号：TP24 Mobile Robot Path Planning Based on 3D Grid Map ZHANG Biao, CAO Qixin, WANG Wenshan (Research Institute of Robotics, Shanghai Jiao Tong University) Abstract: To tackle with mobile robot path planning problem, we utilized 3D grid map based planning method. Firstly we collect point cloud using mobile robot equipped with 3D LRF, then we transform 3D point cloud into octree data structure, getting 3D grid map. We developed D* algorithm to take mobile robots size into consideration, which will generate 3D trajectory of mobile robot directly. In experiments we construct the 3D grid map of multi-obstacle environment, and generalize two different path which validated the reliability and practicality of this system. Key words: mechanical and electronic engineering;path planning; 3D grid map; mobile robot; 3D point cloud 0 引言机器人路径规划是机器人研究领域的一个重要分支，机器人需要利用符号性环境模型，从一个位置到达目标位置，同时避开环境中某些特定区域，生成一个可执行的运动序列或运动轨迹。机器人地图包括几何地图、点云地图、拓扑地图和栅格地图等，其中栅格地图将环境分解成一系列具有二值信息的网格单元，栅格的大小决定了环境信息存储量的大小，适当调整既可以降低存储消耗，又保留了环境的空间结构，吸引了国内外多位学者进行了研究和应用[1][3-4]。栅格地图下的路径规划算法有 A*算法[2]，它通过引入试探检索法来降低了 Dijkstra’s 算法[5]的计算消耗，但是 A*算法需要对地图有一些先验认识，Anthony Stentz 和 Sven Koenig 所提出的 D*及简化 D*算法则不需要对地图具有认识。这些方法都是通过给位置栅格一些可能的可通行性数值，当机器人移动到这些位置附近时，通过采集新的信息可以得到这些位置的真实数值，并对地图进行更新。 35 理论上环境中如果存在可通过的路径，A*或者 D*算法总能找到这条路径，但是实际使用时这些方法不考虑机器人实际尺寸，而是将机器人当做一个理想点，因此不能判断机器人是否能真正通过某些区域。在这些规划算法的基础上，我们提出的方法一方面不需要对地图基金项目：国家自然科学基金委(No. 61273331)、教育部博士点基金(No.20090073110037)和教育部重大项目培育资金项目(No.708035)资助。作者简介：张彪，男，研究生，主要研究方向为三维点云数据分析与感知、环境建模与地图创建通信联系人：曹其新，男，教授，博士生导师。研究领域：机器视觉与模式识别、智能机器人与模块化技术、智能维护与物联网技术. E-mail: qxcao@sjtu.edu.cn - 1 -

中国科技论文在线 http://www.paper.edu.cn 具有先验认识，另一方面考虑了机器人实际尺寸，并在真实环境中进行了实际使用。 1 三维栅格地图创建 40 我们使用三维激光扫描仪获取环境的三维点云地图，然后将其转换成为八叉树数据结构来构建三维栅格地图。八叉树（Octree）是一种基于树形层次的数据结构，其定义是：若不为空树的话，树中任一节点的子节点恰好只会有八个或零个。八叉树充分利用了形体在空上的相关性，因此，它所占用的存贮空间要比三维体素阵列的少。其主要优点在于管理方便，搜索某一个小方块的时候，能很方便的使用二分法查找，当深度到一定层次以后，基本可以拟合所有的三维模型。 45 50 55 60 (a) 三维空间结构 (b) 相应的八叉树数据结构 (a) The 3D spatial strcuture (b) The corresponding octree structure 图1 八叉树存储示例 Fig.1 Example of an octree [7] 图 1 所示为一个利用八叉树存储空间被占据情况的实例，（a）中被占据的方格用黑色表示，没有被占据的用白色表示，相应的八叉树可以用（b）表示。如果每个节点用 2 位存储，那么空间被占据情况可以用一个 6 比特的八叉树来存储。将点云数据转换成八叉树结构的三维栅格地图，一方面可以大大节省内存空间，另一方面也便于后续路径规划过程中进行碰撞检测和空间可行性分析。如图 2 所示，左侧为原始点云地图，大小为 12MB，右侧为栅格大小 5cm 的栅格地图，大小为 246KB。转换为八叉树结构在不损失空间结构的同时节省了存储空间，提高了计算速度，有助于移动机器人实时感知环境并智能决策。 (a) 三维点云地图 (b) 三维栅格地图 (a) 3D point cloud map (b) The corresponding 3D grid map 图2 三维点云转换成三维栅格 Fig.2 Transform 3D point cloud into 3D grids - 2 -

中国科技论文在线 2 路径规划算法 http://www.paper.edu.cn , ( = )ESG 我们使用上文中描述的三维栅格地图来表示环境信息，路径规划方法来源于简化 D*算代表了栅格地图，其中 S 是一系列表示机器人可能位置的栅格， Succ ⊆ 表示栅法，首先，假设而 E 表示这些过渡位置的边界。函数 ( )s adj d 则表示栅格 s 前面的栅格。当给定一个初始栅格格 s 的后续栅格，而 ed ⊆ Pr sstart ∈ ，和目标栅格 s goal ∈ , 路径规划算法应该能生成一条最短的路径，估计函数 S ( )sg 记录了从初始状态到每一个其他状态 s 的消耗. 定义为栅格 s 的邻域， ( ) s ( ) s S S S (1) 来估计到达目标位置的路径消耗，并减少那些 ( 's ssc , 用来存储从状态 s 变为状态 0 min ⎧ ⎨ ⎩ = ( ) sg ( ) ) ssc ,' 同时，我们使用快速检索函数 ( ssh , ( ) sg ' ' Pr ∈ + ( ) s ( ed s 不必要（没有朝向目标点）的计算。函数 ) 的消耗，显然， ( ssh , goal ( ssh ,' ≤ ( , ssc ( ( )' ssh ssc , , 开始时我们将所有的 S 和 ) + s ∈ 和 ( )sh )' goal ) s = sif start otherwise ) goal 0 < ) ∞≤ 满足三角不等式 ' goal (2) 都设为 0 并且将 ( )sv 否可通行等信息对于机器人而言都是未知的。开始搜索时， s ∈ 设为 false, 即所有的栅格是 ( 并且 s 设置为 sg start ( adj s 和 . 如果栅格 s 没有设为 CLOSED，就将其加入 OPEN 序列，OPEN 序列存储着 CLOSED，即不需要再次到达该栅格。对于所有的栅格 ( ssh , 机器人需要达到的栅格并通过 ( )sk 函数来排序： ) 0= ) 我们计算 ( )sg start goal ) = + ( ) sg ( ) sk ( )sk 数值最低的栅格被排在 OPEN 序列的顶端，当栅格 goal (3) s ∈ 的被放入 OPEN 序列后，序列顶部的栅格 s 被弹出并且状态被设为 CLOSED。对 OPEN 序列排列完成后，我们将 ( )sk 数值最低的栅格弹出，继续进行搜索。这一过程一直持续直到 goal s 被标记，如果 s 到达 goal OPEN 序列为空，则表明没有合适的路径，否则表明已经找到从 start s 的路径。 start adj ( s ) ( ssh , ) 65 70 75 80 85 - 3 -

中国科技论文在线 http://www.paper.edu.cn 90 图 3 路径规划算法流程示例 Fig.3 An example of path planning 综上，动态 A*算法描述如下： 1.假设未知栅格位置具有较高的通行性，用采集到的点云数据更新地图。 2.选择一个目标位置周围最接近的一个可通行栅格。 3.移动到该位置，并用采集到的新数据更新地图并回到步骤 2。 4.如果选择了目标栅格，则生成初始位置到终点的路径。 95 3 考虑机器人尺寸的路径规划理想算法中我们将机器人看做一个点没有尺寸，实际试验中我们还要考虑机器人大小，即设置机器人的包围盒尺寸，不考虑过细的形状信息，一方面简化计算，另一方面提高了安全系数。机器人及其三维模型如图 4 所示，其大小在 40×40×60(cm)范围内。 100 105 (a) 实际移动机器人 (b) 机器人三维模型 (a) Mobile robot platform (b) 3D model of mobile robot 图 4 移动机器人及其三维模型 Fig.4 Mobile robot and its 3D model 移动机器人主要有三个状态需要考虑：尺寸，转向和停止。机器人尺寸大小可以用来判断精致情况下是否与环境发生碰撞，机器人运动时要判断其旋转和停止时是否具有足够的空 - 4 -

中国科技论文在线 http://www.paper.edu.cn 间，考虑这些因素的路径规划算法如下所述： 1. 在八叉树的邻域内遍历可通行的网格。 2. 检测第一步中的网格处是否有足够的容纳机器人的空间，如果可以，转至步骤 3，否 110 则转至步骤 4。 3. 检测是否具有足够的空间来进行旋转，当前位置不能旋转的话放弃当前网格并回到步骤 1，否则转至步骤 4。 4.检测是否具有足够的空间是机器人停止在当前网格，不能的话放弃当前网格并回到步 115 骤 1，否则转至步骤 5。 5.移动到之前找到的网格，如果该网格是目标网格，则转至步骤 6，否则回到步骤 1。 6.生成从初始网格到达目标网格的路径。 4 实验结果与分析实际环境如图三维点云数据收集由三维激光扫描仪完成，激光测距为 SICK 公司的 120 LMS200 型，平面收集点数最大为 750，角度最小分辨率为 0.25°，旋转平台带动激光测距系统旋转以收集三维点云数据。移动机器人处理器为酷睿 2GHz，内存 2GB。真实场景如图 5 左侧所示，点云地图如图 2 左侧所示，生成的三维地图如图 5 右侧所示，我们分别设置了六个不同障碍物，障碍物的大小、高低和形状均不相同，实际和三维地图中的障碍物分别与左图和右图的标号相对应。各种障碍物在地图上都有清晰的表示，包括形状 125 和位置，这能对于机器人有效地避免碰撞，绕开各种障碍物探测远距离的环境信息具有重要意义。 130 (a) 实际实验场景 (b) 三维栅格地图 (a) The environment of experiment (b) The corresponding 3D grid map 图 5 实际场景与三维栅格地图 Fig.5 Real scene and 3D grid map - 5 -

中国科技论文在线 http://www.paper.edu.cn 图 6 三维栅格地图中的起点与终点 Fig.6 The start position and destination in 3D grid map 将点云地图转换成为三维栅格地图后，我们给定一个初始位置和终止位置，使用移动机器人进行路径规划，导入足球机器人模型并进行路径规划。起始位置和终止位置在环境中的位置如图 6 所示，机器人需要绕开环境中的多个障碍物才能最终到达终点。最终规划的路径见如图 7，机器人搜索出两条可行路径，分别从左侧和右侧绕开重要障碍物 3。移动机器人的运动轨迹而清晰地从图中得到，这对于机器人避免与环境碰撞，保证运动的安全性具有重要意义。 (a) 规划路径1 (b) 规划路径2 (a) The first planned path (b) The second planned path 图 7 三维栅格地图中的路径 Fig.7 The possible paths in 3D grid map 5 结论针对移动机器人路径规划问题，我们研究了基于三维栅格地图的路径规划，栅格地图一方面可以降低内存消耗，另一方面方便进行碰撞检测，有利于快速进行空间可行性分析，基于栅格地图，我们扩展了 D*算法，使其不需要对地图有先验认识的基础上考虑实际机器人尺寸，在规划路径的同时生成机器人运动轨迹。实际实验中设置了多个障碍物，生成了相应的三维栅格地图，并在此基础上规划处两条路径，验证了这种方法的有效性和实用性。 - 6 - 135 140 145 150

中国科技论文在线 http://www.paper.edu.cn 155 [参考文献] (References) [1] Antariksha Bhaduri. A mobile robot path planning using genetic artificial immune network algorithm [ C ]// World Congress on Nature & Biologically Inspired Computing. New Delhi, India: [s. n. ] , 2009: 1536-1539. [2] Hart, P.; Nilsson, N.; and Rafael, B.. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE trans. Sys. Sci. and Cyb. 4, 100-107 (1968) [3] Jiajun Gu; Qixin Cao, Path planning for mobile robot in a 2.5-dimensional grid-based map[J] , The Industrial Robot vol. 38, no. 3 (2011), p. 315 [4] Giesbrecht J.Global path planning for unmanned ground vehicles[R].Defence R&D Canada-Suffield.Technical Memorandum DRDC Suffield TM 2004-272,December,2004. [5] E. Dijkstra. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1, 269-271 (1959). [6] Jiajun Gu, Qixin Cao, Path planning using hybrid grid representation on rough terrain[J] , Industrial Robot, 2009 , Vol.36, No.5 pp497-502 [7] K. M. Wurm, A. Hornung, M. Bennewitz, C. Stachniss, and W. Burgard. OctoMap: A probabilistic, flexible, and compact 3D map representation for robotic system[C]s. In Proc. of the ICRA 2010. Anchorage, AK, USA, May 2010. [8] D. Comanicu, P. Meer: Mean shift: A robust approach toward feature space analysis[J]. IEEE Trans. Pattern Anal. Machine Intell., 24, 603-619, May 2002. 160 165 170 - 7 -

分享到：

赞收藏

资料库

基于三维栅格地图的移动机器人路径规划.pdf

相关推荐

开发技术

热门标签

最新资料