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

 基于三维栅格地图的移动机器人路径规划# ** 5 10 15 20 25 30 35 摘要：面向移动机器人路径规划问题，研究了基于三维栅格地图的路径规划方法。首先使用 装载三维激光扫描仪的移动机器人收集环境点云，将三维点云转换成为八叉树结构的三维栅 格地图，并扩展了 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*算法则不需要对地图具有认识。这些方法都是通过给位 置栅格一些可能的可通行性数值，当机器人移动到这些位置附近时，通过采集新的信息可以 得到这些位置的真实数值，并对地图进行更新。 理论上环境中如果存在可通过的路径，A*或者 D*算法总能找到这条路径，但是实际使 用时这些方法不考虑机器人实际尺寸，而是将机器人当做一个理想点，因此不能判断机器人 是否能真正通过某些区域。在这些规划算法的基础上，我们提出的方法一方面不需要对地图 -1-  具有先验认识，另一方面考虑了机器人实际尺寸，并在真实环境中进行了实际使用。 1 三维栅格地图创建 40 45 我们使用三维激光扫描仪获取环境的三维点云地图，然后将其转换成为八叉 树数据结构来构建三维栅格地图。八叉树（Octree）是一种基于树形层次的数据结构， 其定义是：若不为空树的话，树中任一节点的子节点恰好只会有八个或零个。八叉树充分利 用了形体在空上的相关性，因此，它所占用的存贮空间要比三维体素阵列的少。其主要优点 在于管理方便，有哪些信誉好的足球投注网站某一个小方块的时候，能很方便的使用二分法查找，当深度到一定层次 以后，基本可以拟合所有的三维模型。 (a) 三维空间结构  (b) 相应的八叉树数据结构 (a) The 3D spatial strcuture