无人驾驶智能车三维环境建模与地图构建
|
摘要
近年来关于无人驾驶车研究的发展十分迅速,尤其是国内外举办的一系列赛事,更有效推动了无人驾驶车智能性和实用性的快速发展。在该研究领域,针对室外非结构化三维场景的环境建模与三维地图构建是研究的核心与重点。针对三维环境的有效表述,不但有助于无人车实现可靠的自主运动规划,同时也保证其在线构建的三维环境地图能真实准确反映复杂室外场景。
无人驾驶车要实现可靠的实时运动规划,必须利用三维环境建模方法进行实时局部地图构建。本文借鉴经典高程图方法,设计了一个实时更新的队列来构建局部高程栅格地图,并基于高程地图数据进行障碍物聚类和可行方向角生成,从而指导无人车的自主运动规划。为了克服基于多源二维激光数据进行三维环境实时建模时由动态障碍物产生的“拖尾”现象,研究中利用动态障碍物在线跟踪结果,在局部地图中实时剔除动态障碍物前一时刻的干扰数据,从而保证了实时构建地图数据的真实性与有效性。
在获取大范围三维环境数据后,为了实现对三维环境的有效建模与数字化,本文提出了一种快速栅格划分方法。该方法借鉴经典八叉树空间划分思想,依据场景规模优化了划分策略,加快了大范围场景的划分过程。通过保留划分过程中空间栅格26邻域关系以及父子栅格关系,构建相应的数据结构,并提出大范围场景数字化显示策略,从而保证了大范围场景数字化显示较为优化的效果。
为了验证本文所提方法的有效性和实用性,基于本实验室自主研发的无人驾驶车平台,在大连理工大学校园不同场景进行了一系列的实验。实验结果及相关数据分析表明,实时构建的局部高程地图能保证无人车自主运动规划可靠进行,而利用在线采集的多源激光测距数据所构建的三维环境地图则能有效完成大范围校园场景的数字化。
With the help of a series of unmanned ground vehicle (UGV) competitions, the development of the technology in UGV has grown rapidly in recent years, which also makes the practical application of UGV be a reality. In this field, 3D environment modeling and mapping are essential tasks for UGV in unstructured outdoor scenes. In order to complete reliable UGV's motion planning autonomously, an effective approach for 3D environment modeling is prerequisite to perform online 3D mapping, which can represent the real outdoor environment accurately.
To guarantee reliable real-time motion planning for UGV, a local map building algorithm has to be presented by using the result of 3D environment modeling. In our work, a data structure of queue is updated in real-time to complete local elevation map building on the basis of the classic elevation map. Moreover, the results of obstacles clustering and direction angle generating are used to guide UGV's autonomous motion planning. In order to overcome the phenomenon of "the trails of moving objects" caused by limited 2D laser scanning data, the results of the dynamic targets'online tracking are integrated into local map building, which can eliminate the trails in real-time and generate the local map in a more accurate and practical way.
To meet the demand of dealing with complex computation caused by large scale environment, a fast voxelization algorithm is proposed for 3D environment modeling and mapping. This algorithm can automatically search partition strategy which divides the 3D range data into unified blocks represent as voxels. Since the 26-neighourhood and parent-child-relationship models are constructed in the proposed voxelization algorithm, it makes large-scale environment digitalization much easier to be accomplished in a more efficient way.
To test the proposed approaches'validity and practicability, a number of experiments are conducted in our campus on the UGV platform developed by our laboratory. The experiment results and corresponding data analysis show that our real-time elevation map is effective for guiding UGV motion planning. Furthermore, the result of large-scale 3D scene mapping based on multiple 2D laser scanners can accomplish DUT campus digitalization effectively.
无人驾驶车要实现可靠的实时运动规划,必须利用三维环境建模方法进行实时局部地图构建。本文借鉴经典高程图方法,设计了一个实时更新的队列来构建局部高程栅格地图,并基于高程地图数据进行障碍物聚类和可行方向角生成,从而指导无人车的自主运动规划。为了克服基于多源二维激光数据进行三维环境实时建模时由动态障碍物产生的“拖尾”现象,研究中利用动态障碍物在线跟踪结果,在局部地图中实时剔除动态障碍物前一时刻的干扰数据,从而保证了实时构建地图数据的真实性与有效性。
在获取大范围三维环境数据后,为了实现对三维环境的有效建模与数字化,本文提出了一种快速栅格划分方法。该方法借鉴经典八叉树空间划分思想,依据场景规模优化了划分策略,加快了大范围场景的划分过程。通过保留划分过程中空间栅格26邻域关系以及父子栅格关系,构建相应的数据结构,并提出大范围场景数字化显示策略,从而保证了大范围场景数字化显示较为优化的效果。
为了验证本文所提方法的有效性和实用性,基于本实验室自主研发的无人驾驶车平台,在大连理工大学校园不同场景进行了一系列的实验。实验结果及相关数据分析表明,实时构建的局部高程地图能保证无人车自主运动规划可靠进行,而利用在线采集的多源激光测距数据所构建的三维环境地图则能有效完成大范围校园场景的数字化。
With the help of a series of unmanned ground vehicle (UGV) competitions, the development of the technology in UGV has grown rapidly in recent years, which also makes the practical application of UGV be a reality. In this field, 3D environment modeling and mapping are essential tasks for UGV in unstructured outdoor scenes. In order to complete reliable UGV's motion planning autonomously, an effective approach for 3D environment modeling is prerequisite to perform online 3D mapping, which can represent the real outdoor environment accurately.
To guarantee reliable real-time motion planning for UGV, a local map building algorithm has to be presented by using the result of 3D environment modeling. In our work, a data structure of queue is updated in real-time to complete local elevation map building on the basis of the classic elevation map. Moreover, the results of obstacles clustering and direction angle generating are used to guide UGV's autonomous motion planning. In order to overcome the phenomenon of "the trails of moving objects" caused by limited 2D laser scanning data, the results of the dynamic targets'online tracking are integrated into local map building, which can eliminate the trails in real-time and generate the local map in a more accurate and practical way.
To meet the demand of dealing with complex computation caused by large scale environment, a fast voxelization algorithm is proposed for 3D environment modeling and mapping. This algorithm can automatically search partition strategy which divides the 3D range data into unified blocks represent as voxels. Since the 26-neighourhood and parent-child-relationship models are constructed in the proposed voxelization algorithm, it makes large-scale environment digitalization much easier to be accomplished in a more efficient way.
To test the proposed approaches'validity and practicability, a number of experiments are conducted in our campus on the UGV platform developed by our laboratory. The experiment results and corresponding data analysis show that our real-time elevation map is effective for guiding UGV motion planning. Furthermore, the result of large-scale 3D scene mapping based on multiple 2D laser scanners can accomplish DUT campus digitalization effectively.
引文
[1]Urmson C, Anhalt J, Clark M, et al. High speed navigation of unrehearsed terrain:Red Teamtechnology for Grand Challenge 2004 [M]. Tech. Rep. CMU-RI-TR-04-37. Robotics Institute, Carnegie Mellon University. Pittsburgh, PA,2004.
[2]Thrun S, Montemerlo M, Dahlkamp H, et al. Stanley:The robot that won the DARPA Grand Challenge [J]. Journal of Field Robotics,2006,23(9):661-692.
[3]Stavens D, Thrun S. A Self-Supervised Terrain Roughness Estimator for Off-Road Autonomous Driving [C]. Conference on Uncertainty in Al (UAI), Cambridge, MA, USA, July 13-16 2006.
[4]Montemerlo M, Thrun S, Dahlkamp H, et al. Winning the DARPA Grand Challenge with an Al robot [C]. In Proceedings of the AAAI National Conference on Artificial Intelligence, Boston, MA,2006.
[5]Urmson C, Anhalt J, Bartz D, et al. A robust approach to high-speed navigation for unrehearsed desert terrain [J]. Journal of Field Robotics.2006,23(8):467-508.
[6]Urmson C, Anhalt J, Bae H, et al. Autonomous driving in urban environments:Boss and the urban challenge [J]. Journal of Field Robotics Special Issue on the 2007 DARPA Urban Challenge, Part I,2008,25(1):425-466.
[7]Baker C R, Dolan J M. Traffic Interaction in the Urban Challenge:Putting Boss on its Best Behavior [C], in Proceedings of the 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems. Nice, France, September 22-26 2008.
[8]Montemerlo M, Becker J, Bhat S, et al. Junior:The Stanford entry in the Urban Challenge[J]. Journal of Field Robotics,2008,25(9):569-597.
[9]Dolgov D, Thrun S. Autonomous driving in semi-structured environments:Mapping and planning [C]. Proceedings of the 2009 IEEE International Conference on Robotics and Automation (ICRA-09), Kobe, Japan.2009.
[10]Bacha A, Bauman C, Faruque R, et al. Odin:Team VictorTango's entry in the DARPA Urban Challenge [J]. Journal of Field Robotics,2008,25(1):467-492.
[11]Leonard J, How J, Teller S, et al. A Perception-Driven Autonomous Urban Vehicle [J]. Journal of Field Robotics,2008,25(1):727-774.
[12]Nature Photonics, Vol.4, July 2010
[13]Bares J, Hebert M, Kanade T, et al. Ambler:An autonomous rover for planetary exploration [J]. IEEE Computer Society Press,1989,22(6):18-22.
[14]Hebert M, Caillas C, Krotkov E, et al. Terrain mapping for a roving planetary explorer [C]. Proceedings of ICRA 1989, pages 997-1002,1989.
[15]Pfaff P, Triebel R, Burgard W. An efficient extension to elevation maps for outdoor terrain mapping and loop closing [C]. IJRR,26,2007
[16]Triebel R, Pfaff P, Burgard W. Multi-level surface maps for outdoor terrain mapping and loop closing [C]. In Proc. of the International Conference on Intelligent Robots and Systems (IROS),2006.
[17]Pervolz K, Nuchter A, Surmann H, Hertzberg J. Automatic reconstruction of colored 3d-models [C]. In Proc. Robotic,2004.
[18]Wurm K M, Hornung A, Bennewitz, M, et al. OctoMap:A probabilistic, flexible, and compact 3D map representation for robotic systems [C]. In:Workshop on Best Practice in 3D Perception and Modeling for Mobile Manipulation, IEEE Intl. Conf. on Robotics and Automation (2010)
[19]Hadsell R, Bagnell J A, Huber D, Hebert M. Accurate roughterrain estimation with space-carving kernels [C]. In Proceedings of Robotics:Science and Systems, Seattle, USA, June 2009
[20]Ryde J, Hu H S.3D mapping with multi-resolution occupied voxellists [C]. Autonomous Robots, pp.1-17,2010.
[21]马志奇,杨宏文,胡卫东,等.一种新的基于邻接矩阵的拓扑排序算法[J].计算机应用,2007,27(9)：2307-2309
[22]Krishna K, Murty M N. Genetic k-means algorithm [J]. IEEE Trans System, Man and Cybern-B, 1999,29 (3):433-439
[23]Haralick R M, Shapiro L G. Image segmentation techniques [J]. Computer Vision, Graphics, and Image Processing,1985,29(1):100-132.
[24]Cormen T H, Leiserson C E, Rivest R L. Introduction To Algorithms [M]. MIT Press and McGrawHill.1989.
[25]Atwah M M. Computing the Convex Hull on the Associative Model [D], Masters Thesis. Kent State University 1994.
[26]Sundaresan A, Chellappa R. Multi-camera Tracking of Articulated Human Motion Using Shape and Motion Cues [J]. IEEE Transactions on Image Processing,2009,18:2114-2126.
[27]Abhyankar A. Efficient Multi-Target Human Motion Tracking [C]. International Association of Computer Science and Information Technology, Spring Conference,2009
[28]孔金生,瞿弦.车辆导航中的交互多模卡尔曼滤波跟踪方法[J].计算机工程与应用,2009,45(14)：198-200.
[29]Moravec H. Robot spatial perception by stereoscopic vision and 3D evidence grids [M]. Tech. Rep. CMU-RI-TR-96-34, Robotics Institute, Pittsburgh, PA, September 1996.
[30]Roth-Tabak y, Jain r, Building an environment model using depth information [J]. Computer, Jun 1989,22(6):85-90
[31]Schnabel R, Klein R. Octree Based Point Cloud Data Compression [C]. In Proceedings of the Eurographics Symposium on Point Based Graphics,2006:15-23.
[32]吴晓军,刘伟军,王天然.基于八义树的三维网格模型体素化方法[J],工程图学学报,2005,4：15-22.
[33]Meagher D. Geometric modeling using octree encoding [J]. Computer Graphics and Image Processing,1982,19(2):129-147.
[34]Payeur P, Hebert P, Laurendeau D, Gosselin C. Probabilistic octree modeling of a 3D dynamic environment [C]. in Proc. of the IEEE Int. Conf. on Robotics & Automation (ICRA), 1997.
[35]Gallup D, Frahm J M, Pollefeys M. Piecewise planar and non-planar stereo for urban scene reconstruction [C]. Proceedings of the 23rd CVPR. June 2010.
[36]Surmann H, Nuchter A, Hertzberg J. An autonomous mobile robot with a 3D laser range finder for 3D exploration and digitalization of indoor environments [J]. Robotics and Autonomous Systems.2003,45:181-198.
[37]Besl P, McKay N. A method for registration of 3D shapes [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence. February 1992,14(2):239-256.
[38]Labatut P, Pons J P, keriven R. Efficient multi-view reconstruction of large-scale scenes using interest points, delaunay triangulation and graph cuts [C]. Proceedings of the 11th ICCV. October 2007.
[39]Sequeira V, Ng E K, Goncalves J, Hogg D. Automated 3D reconstruction of interiors with multiple scan-views [C]. Proceedings of SPIE, Electronic Imaging'99. January 1999.
[40]Allen P, Stamos I, Gueorguiev A, Gold E, Blaer P. Automated site modelling in urban environments [C]. Proceedings of the Third International Conference on 3D Digital Imaging and Modeling. May 2001.
[41]Thrun S, Burgard W, Fox D. A real-time algorithm for mobile robot mapping with applications to multi-robot and 3D mapping [C]. Proceedings of ICRA. April 2000.
[42]Surmann H, Lingemann K, Nuchter A, Hertzberg J. A 3D laser range finder for autonomous mobile robots [C]. Proceedings of the 32nd International Symposium on Robotics. April 2001.
[43]Sappa A, Restrepo-Specht A, Devy M. Range image registration by using an edge-based representation [C]. Proceedings of the Ninth International Symposium on Intelligent Robotic Systems. July 2001.
[44]Nuchter A, Lingemann K, Hertzberg J, Surmann H.6D SLAM-3D mapping outdoor environments [J]. Field Robotics.2007,24(8/9):699-722.
[45]Cole D, Newman P. Using laser range data for 3D SLAM in outdoor environments [C]. Proceedings of the 2006 ICRA. May 2006.
[2]Thrun S, Montemerlo M, Dahlkamp H, et al. Stanley:The robot that won the DARPA Grand Challenge [J]. Journal of Field Robotics,2006,23(9):661-692.
[3]Stavens D, Thrun S. A Self-Supervised Terrain Roughness Estimator for Off-Road Autonomous Driving [C]. Conference on Uncertainty in Al (UAI), Cambridge, MA, USA, July 13-16 2006.
[4]Montemerlo M, Thrun S, Dahlkamp H, et al. Winning the DARPA Grand Challenge with an Al robot [C]. In Proceedings of the AAAI National Conference on Artificial Intelligence, Boston, MA,2006.
[5]Urmson C, Anhalt J, Bartz D, et al. A robust approach to high-speed navigation for unrehearsed desert terrain [J]. Journal of Field Robotics.2006,23(8):467-508.
[6]Urmson C, Anhalt J, Bae H, et al. Autonomous driving in urban environments:Boss and the urban challenge [J]. Journal of Field Robotics Special Issue on the 2007 DARPA Urban Challenge, Part I,2008,25(1):425-466.
[7]Baker C R, Dolan J M. Traffic Interaction in the Urban Challenge:Putting Boss on its Best Behavior [C], in Proceedings of the 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems. Nice, France, September 22-26 2008.
[8]Montemerlo M, Becker J, Bhat S, et al. Junior:The Stanford entry in the Urban Challenge[J]. Journal of Field Robotics,2008,25(9):569-597.
[9]Dolgov D, Thrun S. Autonomous driving in semi-structured environments:Mapping and planning [C]. Proceedings of the 2009 IEEE International Conference on Robotics and Automation (ICRA-09), Kobe, Japan.2009.
[10]Bacha A, Bauman C, Faruque R, et al. Odin:Team VictorTango's entry in the DARPA Urban Challenge [J]. Journal of Field Robotics,2008,25(1):467-492.
[11]Leonard J, How J, Teller S, et al. A Perception-Driven Autonomous Urban Vehicle [J]. Journal of Field Robotics,2008,25(1):727-774.
[12]Nature Photonics, Vol.4, July 2010
[13]Bares J, Hebert M, Kanade T, et al. Ambler:An autonomous rover for planetary exploration [J]. IEEE Computer Society Press,1989,22(6):18-22.
[14]Hebert M, Caillas C, Krotkov E, et al. Terrain mapping for a roving planetary explorer [C]. Proceedings of ICRA 1989, pages 997-1002,1989.
[15]Pfaff P, Triebel R, Burgard W. An efficient extension to elevation maps for outdoor terrain mapping and loop closing [C]. IJRR,26,2007
[16]Triebel R, Pfaff P, Burgard W. Multi-level surface maps for outdoor terrain mapping and loop closing [C]. In Proc. of the International Conference on Intelligent Robots and Systems (IROS),2006.
[17]Pervolz K, Nuchter A, Surmann H, Hertzberg J. Automatic reconstruction of colored 3d-models [C]. In Proc. Robotic,2004.
[18]Wurm K M, Hornung A, Bennewitz, M, et al. OctoMap:A probabilistic, flexible, and compact 3D map representation for robotic systems [C]. In:Workshop on Best Practice in 3D Perception and Modeling for Mobile Manipulation, IEEE Intl. Conf. on Robotics and Automation (2010)
[19]Hadsell R, Bagnell J A, Huber D, Hebert M. Accurate roughterrain estimation with space-carving kernels [C]. In Proceedings of Robotics:Science and Systems, Seattle, USA, June 2009
[20]Ryde J, Hu H S.3D mapping with multi-resolution occupied voxellists [C]. Autonomous Robots, pp.1-17,2010.
[21]马志奇,杨宏文,胡卫东,等.一种新的基于邻接矩阵的拓扑排序算法[J].计算机应用,2007,27(9)：2307-2309
[22]Krishna K, Murty M N. Genetic k-means algorithm [J]. IEEE Trans System, Man and Cybern-B, 1999,29 (3):433-439
[23]Haralick R M, Shapiro L G. Image segmentation techniques [J]. Computer Vision, Graphics, and Image Processing,1985,29(1):100-132.
[24]Cormen T H, Leiserson C E, Rivest R L. Introduction To Algorithms [M]. MIT Press and McGrawHill.1989.
[25]Atwah M M. Computing the Convex Hull on the Associative Model [D], Masters Thesis. Kent State University 1994.
[26]Sundaresan A, Chellappa R. Multi-camera Tracking of Articulated Human Motion Using Shape and Motion Cues [J]. IEEE Transactions on Image Processing,2009,18:2114-2126.
[27]Abhyankar A. Efficient Multi-Target Human Motion Tracking [C]. International Association of Computer Science and Information Technology, Spring Conference,2009
[28]孔金生,瞿弦.车辆导航中的交互多模卡尔曼滤波跟踪方法[J].计算机工程与应用,2009,45(14)：198-200.
[29]Moravec H. Robot spatial perception by stereoscopic vision and 3D evidence grids [M]. Tech. Rep. CMU-RI-TR-96-34, Robotics Institute, Pittsburgh, PA, September 1996.
[30]Roth-Tabak y, Jain r, Building an environment model using depth information [J]. Computer, Jun 1989,22(6):85-90
[31]Schnabel R, Klein R. Octree Based Point Cloud Data Compression [C]. In Proceedings of the Eurographics Symposium on Point Based Graphics,2006:15-23.
[32]吴晓军,刘伟军,王天然.基于八义树的三维网格模型体素化方法[J],工程图学学报,2005,4：15-22.
[33]Meagher D. Geometric modeling using octree encoding [J]. Computer Graphics and Image Processing,1982,19(2):129-147.
[34]Payeur P, Hebert P, Laurendeau D, Gosselin C. Probabilistic octree modeling of a 3D dynamic environment [C]. in Proc. of the IEEE Int. Conf. on Robotics & Automation (ICRA), 1997.
[35]Gallup D, Frahm J M, Pollefeys M. Piecewise planar and non-planar stereo for urban scene reconstruction [C]. Proceedings of the 23rd CVPR. June 2010.
[36]Surmann H, Nuchter A, Hertzberg J. An autonomous mobile robot with a 3D laser range finder for 3D exploration and digitalization of indoor environments [J]. Robotics and Autonomous Systems.2003,45:181-198.
[37]Besl P, McKay N. A method for registration of 3D shapes [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence. February 1992,14(2):239-256.
[38]Labatut P, Pons J P, keriven R. Efficient multi-view reconstruction of large-scale scenes using interest points, delaunay triangulation and graph cuts [C]. Proceedings of the 11th ICCV. October 2007.
[39]Sequeira V, Ng E K, Goncalves J, Hogg D. Automated 3D reconstruction of interiors with multiple scan-views [C]. Proceedings of SPIE, Electronic Imaging'99. January 1999.
[40]Allen P, Stamos I, Gueorguiev A, Gold E, Blaer P. Automated site modelling in urban environments [C]. Proceedings of the Third International Conference on 3D Digital Imaging and Modeling. May 2001.
[41]Thrun S, Burgard W, Fox D. A real-time algorithm for mobile robot mapping with applications to multi-robot and 3D mapping [C]. Proceedings of ICRA. April 2000.
[42]Surmann H, Lingemann K, Nuchter A, Hertzberg J. A 3D laser range finder for autonomous mobile robots [C]. Proceedings of the 32nd International Symposium on Robotics. April 2001.
[43]Sappa A, Restrepo-Specht A, Devy M. Range image registration by using an edge-based representation [C]. Proceedings of the Ninth International Symposium on Intelligent Robotic Systems. July 2001.
[44]Nuchter A, Lingemann K, Hertzberg J, Surmann H.6D SLAM-3D mapping outdoor environments [J]. Field Robotics.2007,24(8/9):699-722.
[45]Cole D, Newman P. Using laser range data for 3D SLAM in outdoor environments [C]. Proceedings of the 2006 ICRA. May 2006.