《基于三维栅格地图的移动机器人路径规划.doc》由会员分享，可在线阅读，更多相关《基于三维栅格地图的移动机器人路径规划.doc（7页珍藏版）》请在三一办公上搜索。
1、精品论文基于三维栅格地图的移动机器人路径规划张彪，曹其新，王雯珊（上海交通大学机器人研究所）5摘要：面向移动机器人路径规划问题，研究了基于三维栅格地图的路径规划方法。首先使用装载三维激光扫描仪的移动机器人收集环境点云，将三维点云转换成为八叉树结构的三维栅 格地图，并扩展了 D*算法使之考虑机器人尺寸，并检测每一状态是否与环境发横碰撞，最 终直接生成机器人运动轨迹。实验中创建了有多个障碍物的环境三维栅格地图，并生成了两 条可行路径，验证了该方法的可靠性和实用性。10关键词：机械电子工程；路径规划；三维栅格地图；移动机器人；三维点云中图分类号：TP24Mobile Robot Path Plann
2、ing Based on 3D Grid MapZHANG Biao, CAO Qixin, WANG Wenshan15(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 L
3、RF, then we transform3D 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. In20experiments we construct the 3D grid map of multi-obstacle environment, and ge
4、neralize 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; 3Dpoint cloud0引言25机器人路径规划是机器人研究领域的一个重要分支，机器人需要利用符号性环境模型， 从一个位置到达目标位置，同时避开环境中某些特定区域，生成一个可执行的运动序列或运 动轨迹。机器人地图包括几何地图、点云地
5、图、拓扑地图和栅格地图等，其中栅格地图将环 境分解成一系列具有二值信息的网格单元，栅格的大小决定了环境信息存储量的大小，适当 调整既可以降低存储消耗，又保留了环境的空间结构，吸引了国内外多位学者进行了研究和30应用13-4。栅格地图下的路径规划算法有 A*算法2，它通过引入试探检索法来降低了 Dijkstras 算法5的计算消耗，但是 A*算法需要对地图有一些先验认识，Anthony Stentz 和 Sven Koenig 所提出的 D*及简化 D*算法则不需要对地图具有认识。这些方法都是通过给位 置栅格一些可能的可通行性数值，当机器人移动到这些位置附近时，通过采集新的信息可以 得到这些位置
6、的真实数值，并对地图进行更新。35理论上环境中如果存在可通过的路径，A*或者 D*算法总能找到这条路径，但是实际使 用时这些方法不考虑机器人实际尺寸，而是将机器人当做一个理想点，因此不能判断机器人 是否能真正通过某些区域。在这些规划算法的基础上，我们提出的方法一方面不需要对地图基金项目：国家自然科学基金委(No. 61273331)、教育部博士点基金(No.20090073110037)和教育部重大项目 培育资金项目(No.708035)资助。 作者简介：张彪，男，研究生，主要研究方向为三维点云数据分析与感知、环境建模与地图创建 通信联系人：曹其新，男，教授，博士生导师。研究领域：机器视觉与模
7、式识别、智能机器人与模块化技 术、智能维护与物联网技术. E-mail: qxcao- 7 -具有先验认识，另一方面考虑了机器人实际尺寸，并在真实环境中进行了实际使用。1三维栅格地图创建40我们使用三维激光扫描仪获取环境的三维点云地图，然后将其转换成为八叉 树数据结构来构建三维栅格地图。八叉树（Octree）是一种基于树形层次的数据结构， 其定义是：若不为空树的话，树中任一节点的子节点恰好只会有八个或零个。八叉树充分利 用了形体在空上的相关性，因此，它所占用的存贮空间要比三维体素阵列的少。其主要优点 在于管理方便，搜索某一个小方块的时候，能很方便的使用二分法查找，当深度到一定层次45以后，基本
8、可以拟合所有的三维模型。(a) 三维空间结构(b) 相应的八叉树数据结构(a) The 3D spatial strcuture(b) The corresponding octree structure50图1八叉树存储示例Fig.1Example of an octree 7图 1 所示为一个利用八叉树存储空间被占据情况的实例，（a）中被占据的方格用黑色表示，没有被占据的用白色表示，相应的八叉树可以用（b）表示。如果每个节点用 2 位存 储，那么空间被占据情况可以用一个 6 比特的八叉树来存储。将点云数据转换成八叉树结构55的三维栅格地图，一方面可以大大节省内存空间，另一方面也便于后续路径
9、规划过程中进行 碰撞检测和空间可行性分析。如图 2 所示，左侧为原始点云地图，大小为 12MB，右侧为栅 格大小 5cm 的栅格地图，大小为 246KB。转换为八叉树结构在不损失空间结构的同时节省 了存储空间，提高了计算速度，有助于移动机器人实时感知环境并智能决策。60(a) 三维点云地图 (b) 三维栅格地图(a) 3D point cloud map (b) The corresponding 3D grid map图2 三维点云转换成三维栅格Fig.2 Transform 3D point cloud into 3D grids2路径规划算法65我们使用上文中描述的三维栅格地图来表示环境
10、信息，路径规划方法来源于简化 D*算法，首先，假设G = (S , E )代表了栅格地图，其中 S 是一系列表示机器人可能位置的栅格，而 E 表示这些过渡位置的边界。函数 adj(s)定义为栅格 s 的邻域，Succ(s ) S表示栅格 s 的后续栅格，而 Pr ed (s) Sd 则表示栅格 s 前面的栅格。当给定一个初始栅格s start S，和目标栅格 s goal S , 路径规划算法应该能生成一条最短的路径，估计函数70g (s )记录了从初始状态到每一个其他状态 s 的消耗.0g (s) = if s = sstart(1)min s Pr ed (s ) (g (s) + c(s
11、 , s )同时，我们使用快速检索函数 h(s, sotherwise)来估计到达目标位置的路径消耗，并减少那些goal不必要（没有朝向目标点）的计算。函数 0 c(s, s) 用来存储从状态 s 变为状态 s)的消耗，显然， h(s, sgoal 和c(s, s)满足三角不等式h(s, s75goal) h(s , sgoal) + c(s, s)(2)开始时我们将所有的 s S 和 h(s )都设为 0 并且将 v(s )设为 false, 即所有的栅格是否可通行等信息对于机器人而言都是未知的。开始搜索时，g(sstart ) = 0 并且 s 设置为CLOSED，即不需要再次到达该栅格。
12、对于所有的栅格s adj (s)start我们计算g (s ) 和h(s, sgoal). 如果栅格 s 没有设为 CLOSED，就将其加入 OPEN 序列，OPEN 序列存储着80机器人需要达到的栅格并通过 k (s ) 函数来排序 ：k (s ) = g (s ) + h(s, s)goal(3)k (s ) 数值最低的栅格被排在 OPEN 序列的顶端，当栅格 s adj (sstart)的被放入 OPEN序列后，序列顶部的栅格 s 被弹出并且状态被设为 CLOSED。对 OPEN 序列排列完成后，我goal们将 k (s ) 数值最低的栅格弹出，继续进行搜索。这一过程一直持续直到 s 被
13、标记，如果85OPEN 序列为空，则表明没有合适的路径，否则表明已经找到从 s start 到达 s goal 的路径。图 3 路径规划算法流程示例Fig.3An example of path planning9095100105综上，动态 A*算法描述如下：1.假设未知栅格位置具有较高的通行性，用采集到的点云数据更新地图。2.选择一个目标位置周围最接近的一个可通行栅格。3.移动到该位置，并用采集到的新数据更新地图并回到步骤 2。4.如果选择了目标栅格，则生成初始位置到终点的路径。3考虑机器人尺寸的路径规划理想算法中我们将机器人看做一个点没有尺寸，实际试验中我们还要考虑机器人大小， 即设置机
14、器人的包围盒尺寸，不考虑过细的形状信息，一方面简化计算，另一方面提高了安 全系数。机器人及其三维模型如图 4 所示，其大小在 404060(cm)范围内。(a) 实际移动机器人 (b) 机器人三维模型(a) Mobile robot platform (b) 3D model of mobile robot图 4 移动机器人及其三维模型Fig.4 Mobile robot and its 3D model移动机器人主要有三个状态需要考虑：尺寸，转向和停止。机器人尺寸大小可以用来判 断精致情况下是否与环境发生碰撞，机器人运动时要判断其旋转和停止时是否具有足够的空110115120125130间，
15、考虑这些因素的路径规划算法如下所述：1. 在八叉树的邻域内遍历可通行的网格。2. 检测第一步中的网格处是否有足够的容纳机器人的空间，如果可以，转至步骤 3，否 则转至步骤 4。3. 检测是否具有足够的空间来进行旋转，当前位置不能旋转的话放弃当前网格并回到 步骤 1，否则转至步骤 4。4.检测是否具有足够的空间是机器人停止在当前网格，不能的话放弃当前网格并回到步 骤 1，否则转至步骤 5。5.移动到之前找到的网格，如果该网格是目标网格，则转至步骤 6，否则回到步骤 1。6.生成从初始网格到达目标网格的路径。4实验结果与分析实际环境如图三维点云数据收集由三维激光扫描仪完成，激光测距为 SICK 公
16、司的 LMS200 型，平面收集点数最大为 750，角度最小分辨率为 0.25，旋转平台带动激光测距系 统旋转以收集三维点云数据。移动机器人处理器为酷睿 2GHz，内存 2GB。真实场景如图 5 左侧所示，点云地图如图 2 左侧所示，生成的三维地图如图 5 右侧所示， 我们分别设置了六个不同障碍物，障碍物的大小、高低和形状均不相同，实际和三维地图中 的障碍物分别与左图和右图的标号相对应。各种障碍物在地图上都有清晰的表示，包括形状 和位置，这能对于机器人有效地避免碰撞，绕开各种障碍物探测远距离的环境信息具有重要 意义。(a) 实际实验场景 (b) 三维栅格地图(a) The environmen
17、t of experiment (b) The corresponding 3D grid map图 5 实际场景与三维栅格地图Fig.5 Real scene and 3D grid map135图 6 三维栅格地图中的起点与终点Fig.6 The start position and destination in 3D grid map140将点云地图转换成为三维栅格地图后，我们给定一个初始位置和终止位置，使用移动机器人进行路径规划，导入足球机器人模型并进行路径规划。起始位置和终止位置在环境中的 位置如图 6 所示，机器人需要绕开环境中的多个障碍物才能最终到达终点。最终规划的路径 见如图
18、7，机器人搜索出两条可行路径，分别从左侧和右侧绕开重要障碍物 3。移动机器人 的运动轨迹而清晰地从图中得到，这对于机器人避免与环境碰撞，保证运动的安全性具有重 要意义。1455结论(a) 规划路径1 (b) 规划路径2(a) The first planned path (b) The second planned path图 7 三维栅格地图中的路径Fig.7 The possible paths in 3D grid map150针对移动机器人路径规划问题，我们研究了基于三维栅格地图的路径规划，栅格地图一 方面可以降低内存消耗，另一方面方便进行碰撞检测，有利于快速进行空间可行性分析，基 于
19、栅格地图，我们扩展了 D*算法，使其不需要对地图有先验认识的基础上考虑实际机器人 尺寸，在规划路径的同时生成机器人运动轨迹。实际实验中设置了多个障碍物，生成了相应 的三维栅格地图，并在此基础上规划处两条路径，验证了这种方法的有效性和实用性。155参考文献 (References)1601651701 Antariksha Bhaduri. A mobile robot path planning using genetic artificial immune network algorithm C / World Congress on Nature & Biologically Inspir
20、ed 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 pathsJ. 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-base
21、d mapJ , The IndustrialRobot vol. 38, no. 3 (2011), p. 3154 Giesbrecht J.Global path planning for unmanned ground vehiclesR.Defence R&D Canada-Suffield.TechnicalMemorandum DRDC Suffield TM 2004-272,December,2004.5 E. Dijkstra. A note on two problems in connexion with graphsJ. Numerische Mathematik,
22、1, 269-271 (1959). 6 Jiajun Gu, Qixin Cao, Path planning using hybrid grid representation on rough terrainJ , Industrial Robot,2009 , Vol.36, No.5 pp497-5027 K. M. Wurm, A. Hornung, M. Bennewitz, C. Stachniss, and W. Burgard. OctoMap: A probabilistic, flexible, and compact 3D map representation for robotic systemCs. In Proc. of the ICRA 2010. Anchorage, AK, USA, May 2010.8 D. Comanicu, P. Meer: Mean shift: A robust approach toward feature space analysisJ. IEEE Trans. PatternAnal. Machine Intell., 24, 603-619, May 2002.
