无人机因具有灵活性强、小型化、可代替人工执行危险任务等特点，已在应急救援、农业植保、电力巡检、物流配送等民用领域得到广泛应用，引领智慧城市创新发展。主动和精准的 路径规划是保障无人机应用效果和提高作业效率的关键，面向环境的感知能力则是实现无人机 路径规划的前提，但传统方法在复杂城市超低空场景中显得无能为力。本文提出一种基于环境 感知的无人机路径规划方法，通过激光雷达点云障碍物检测实现无人机环境感知，为基于融合 改进 RRT*的无人机路径规划提供输入。该方法在弥补现有环境感知方法缺陷的同时，优化路 径规划策略。论文的具体研究内容和成果包括以下方面：

（1）提出基于激光雷达点云分割的城市超低空障碍物检测方法。针对激光雷达原始点云数据存在的噪声和离群点，使用最小封闭超球体对原始点云数据进行离群检测，预优化处理提高 数据可信度；研究了一种基于密度的球柱变邻域空间聚类算法，根据每个点的三维位置信息确 定其合适的聚类邻域，即一种点云自适应聚类分割障碍物检测方法，有效抑制障碍物过分割、 漏检、聚类缺失等异常情况。

（2）提出基于方向包围盒（Oriented Bounding Box，OBB）的城市超低空障碍物模型构建 方法，为无人机的路径规划工作提供了构型空间。首先，为构建和简化障碍物模型以便获取其 三维尺寸和位置信息，使用 OBB 模型包裹聚类分割后的障碍物点云簇；其次，对于尺寸满足 一定条件的包围盒进行再分割优化处理，提高了包围盒内部空间占用率。然后，将无人机简化 为球模型，研究了一种基于胶囊体与 OBB 相交测试的无人机与障碍物的碰撞检测方法，用于 验证所规划路径是否满足无障碍约束。

（3）提出基于融合改进快速遍历随机树（Rapidly-exploring Random Tree Star，RRT*）的 无人机路径规划方法。分析了无人机快递末端配送、应急医疗物资配送、城市交通巡检 3 种典 型的城市超低空应用场景，并总结了 6 个无人机运动学约束条件；对 RRT*算法进行了融合改 进，将启发式搜索、引力偏移、检测限制、反向冗余剪枝 4 个策略依次加入随机点采样、新节 点扩展、碰撞检测和可行路径优化过程，弥补了传统 RRT*路径规划方法搜索效率低、优化迭 代慢的缺陷。

本文基于城市超低空场景下的激光雷达点云数据对上述方法进行了验证，试验结果表明：本文所提出的障碍物检测、障碍物模型构建以及无人机路径规划方法具有有效性和可靠性。

UAVs have been widely used in civil industries such as emergency rescue, agricultural plant protection, power inspection, and logistics distribution due to their flexibility, miniaturization, and ability to replace people to perform dangerous tasks, leading the innovative development of smart cities. Active and accurate path planning is the key to ensure the application effects and improve the operating efficiency of UAV. The ability of environmental perception is the premise of path planning, but traditional methods are powerless in the complex scene of ultra-low altitude in urban areas. This paper puts forward a path planning method of UAV. In the method, we use LiDAR to detect obstacles formed by point clouds, so as to realize the environmental perception of UAV and provide inputs for path planning based on the fused and improved RRT* algorithm. This method while make up for the defects of the existing environmental perception methods and optimize the path planning strategies. The specific research contents and achievements of this paper include the following aspects:

（1）An obstacle detection method at ultra-low altitude in urban areas is proposed based on the LiDAR point cloud segmentation. Due to the existence of noise and outliers, the minimum closed hypersphere is used for outlier detection of the original point cloud data, that is, the reliability of the data is improved through pre-optimization processing. An improved DBSCAN (Density-Based Spatial Clustering of Applications with Noise) algorithm with spherical or cylindrical neighborhood is studied. The appropriate clustering neighborhood is determined according to the three-dimensional position information of each point. That’s an obstacle detection method based on adaptive clustering and segmentation of point cloud, which can effectively reduce the occurrence of abnormal situations such as excessive segmentation, missed detection, and cluster loss of obstacles.

（2）An obstacle model construction method at ultra-low altitude in urban areas based on OBB (Oriented Bounding Box) is proposed which provides configuration space for UAV path planning. Firstly, in order to construct and simplify the obstacle model to obtain its three-dimensional size and position information, the OBB model is used to wrap the obstacle point cloud cluster. Secondly, the bounding box whose size meets certain conditions will be segmented again to improve its space occupancy rate. Then, the UAV is simplified into a ball model, and a collision detection method between the UAV and obstacles is studied based on the intersection test of capsule and OBB, which is used to verify whether the planned path meet the barrier-free constraints.

（3）A UAV path planning method based on the fused and improved RRT* (Rapidly-exploring Random Tree Star) is proposed. In this secession, we analyze three typical application scenarios of UAV in ultra-low altitude of urban areas: express terminal distribution, emergency medical supplies distribution and urban traffic inspection, and summarize six kinematic constraints of UAV. In addition, we improve the RRT* algorithm by respectively adding four strategies of heuristic searching, gravitational offset, detection restriction and reverse redundancy pruning to the process of random point sampling, new node expansion, collision detection and feasible path optimization, which makes up for the defects of low search efficiency and slow optimization iteration of traditional RRT* path planning method.

In this paper, the above methods are verified based on the LiDAR point cloud data in minimum altitude airspace of urban areas. The experimental results show that the methods of obstacle detection, obstacle model construction and UAV path planning proposed in this paper are effective and reliable.

[1]中国民用航空局.《“十四五”民用航空发展规划》[EB/OL].http://211.65.106.2/cache/2/03/www.caac.gov.cn/2eef0844aac8941a9b6096ec13be7b38/P020220107443752279831.pdf, 2021-12-14.

[2]中国民用航空局.《“十四五”通用航空发展专项规划》[EB/OL]. http://211.65.106.2/cache/6/03/www.caac.gov.cn/9fc28a0f29a05637e2130546dbf277fe/P020220613533137333208.pdf, 2022-6-13.

[3]中国民用航空局.《“十四五”航空物流发展专项规划》[EB/OL]. http://211.65.106.2/cache/2/03/www.caac.gov.cn/a0e64228935a681fb2f5891755d803cb/P020220216509409346164.pdf, 2022-2-16.

[4]中国民用航空局.《无人机适航管理路线图》[EB/OL].http://www.caac.gov.cn/XXGK/XXGK/ZFGW/202102/P020210226498275556329.pdf,2017-8-18.

[5]中国民用航空局.《基于运行风险的无人机适航审定指导意见》[EB/OL]. http://211.65.106.2/cache/9/03/www.caac.gov.cn/e593c68d37e96011550c6f3ce45d8eaa/P020190125609946283900.pdf, 2019-1-23.

[6]Yang S Y, Meng Z J, Chen X Z, et al. Real-time obstacle avoidance with deep reinforcement learning Three-Dimensional Autonomous Obstacle Avoidance for UAV[C]. Proceedings of the 2019 International Conference on Robotics, Intelligent Control and Artificial Intelligence(RICAI 2019), New York: Assoc Computing Machinery, 2019: 324-329.

[7]Amarat S B, Zong P. 3D path planning, routing algorithms and routing protocols for unmanned air vehicles: a review[J]. Aircraft engineering and aerospace technology, 2019, 91(9): 1245-1255.

[8]陈卫东, 张飞. 移动机器人的同步自定位与地图创建研究进展[J]. 控制理论与应用, 2005, 22(03): 445-460.

[9]Yu X, Zhang Y M. Sense and avoid technologies with applications to unmanned aircraft systems: Review and prospects[J]. Progress in Aerospace Sciences, 2015, 74: 152-166.

[10]雷劲博, 朱雪耀, 李智, 等. 货运无人机感知与规避技术[C]. 2018惯性技术发展动态发展方向研讨会文集, 北京: 中国惯性技术学会, 2018: 136-139.

[11]Lee H C. Implementation of collision avoidance system using TCAS II to UAVs[J]. IEEE aerospace and electronic systems magazine, 2006, 21(7): 8-13.

[12]林琳, 刘志勇, 刘引川, 等. ADS-B的无人机冲突检测告警技术[J]. 遥感信息, 2017, 32(06): 33-37.

[13]Juang J G, Tu G T, Liao Y H, et al. Drone patrol using thermal imaging for object detection[C]. Proceedings of the SPIE, USA: SPIE, 2020, 11503: 152-158.

[14]Sree B N, Raj C V, Madhavan R. Obstacle avoidance for UAVs used in road accident monitoring[C]. Proceedings of 2017 1st International Conference on Electronics, Materials Engineering and Nano-Technology (IEMENTech), New York: IEEE, 2017: 1-6.

[15]Nyasulu T D, Du S Z, van Wyk B, et al. Comparison study of low-cost obstacle sensing solutions for Unmanned Aerial Vehicles in wildlife scenery[C]. Proceedings of 2017 3rd IEEE International Conference on Computer and Communications (ICCC), New York: IEEE, 2017: 1072-1076.

[16]Liu H Q, Li N, Guan D Y, et al. Date analysis of non-scanning multi target millimeter-wave radar in traffic flow detection applications [J]. Sensors, 2018, 18(9): 2756.

[17]Yu H, Zhang F, Huang P F, et al. Autonomous Obstacle Avoidance for UAV based on Fusion of Radar and Monocular Camera[C]. Proceedings of 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), New York: IEEE, 2020: 5954-5961.

[18]Zhang X Y, Zhou M, Qiu P , et al. Radar and vision fusion for the real-time obstacle detection and identification[J]. Industrial Robot: the international journal of robotics research and application, 2019, 2019, 46(3): 391-395.

[19]Ma Z W, Wang C, Niu Y F, et al. A saliency-based reinforcement learning approach for a UAV to avoid flying obstacles[J]. Robotics and Autonomous Systems, 2018, 100: 108-118.

[20]Lee H Y, Ho H W, Zhou Y. Deep Learning-based Monocular Obstacle Avoidance for Unmanned Aerial Vehicle Navigation in Tree Plantations[J]. Journal of Intelligent & Robotic Systems, 2021, 101(1): 1-18.

[21]Dai X, Mao Y X, Huang T P, et al. Automatic Obstacle Avoidance of Quad-rotor UAV via CNN-based Learning[J]. Neurocomputing, 2020, 402: 349-358.

[22]Zhu X W, Lei X S, Sui Z H. Research on detection method of UAV obstruction based on binocular vision[C]. Liu L, Yang C, Ke J. AIP Conference Proceedings, USA: AIP Publishing, 2018, 1955: 040010.

[23]Shuai C, Wang H L, Zhang W, et al. Binocular Vision Perception and Obstacle Avoidance of Visual Simulation System for Power Lines Inspection with UAV[C]. Liu T, Zhao Q. Proceedings of the 36th Chinese Control Conference, New York: IEEE, 2017: 10480-10485.

[24]Chen Z Y, Luo X Y, Dai B C. Design of Obstacle Avoidance System for Micro-UAV Based on Binocular Vision[C]. Proceedings of 2017 International Conference on Industrial Informatics-Computing Technology, Intelligent Technology, Industrial Information Integration (ICIICII). New York: IEEE, 2017: 67-70.

[25]Zhu P, Zhen Z Y, Qin H Q, et al. Stereo Vision and Optical Flow Based Obstacle Avoidance Algorithm for UAVs[J]. Electronics Optics & Control, 2017, 24(12): 31-35.

[26]赵良玉, 朱叶青, 金瑞．多旋翼无人机单目V-SLAM研究综述[J]．航空兵器, 2020, 27(2): 1-14.

[27]Steinvall O K, Soederman U, Ahlberg S, et al. Airborne laser radar: systems and methods for reconnaissance and terrain modeling[C]. Kamerman G W, Werner C. Proceedings of SPIE, USA: SPIE, 1999, 3707: 12-26.

[28]Xie Y X, Tian J J, Zhu X X. Linking Points With Labels in 3D: A Review of Point Cloud Semantic Segmentation[J]. Geoscience and remote sensing, 2020, 8(4): 38-59.

[29]Agapaki E, Brilakis I. Instance segmentation of industrial point cloud data[J]. Journal of Computing in Civil Engineering, 2021, 35(6): 04021022.

[30]Yang C . FMP-Net: Fractal Multi-Gate Mixture-of-Experts Panoramic Segmentation for Point Cloud[C]. Proceedings of 2022 IEEE International Conference on Multimedia and Expo (ICME), New York: IEEE, 2022.

[31]Boulch A, Guerry J, Le Saux B, et al. SnapNet: 3D point cloud semantic labeling with 2D deep segmentation networks[J]. Computers & Graphics, 2018, 71: 189-198.

[32]Maturana D, Scherer S. VoxNet: A 3D Convolutional Neural Network for real-time object recognition[C]. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), New York: IEEE, 2015: 922-928.

[33]Tchapmi L P, Choy C B, Armeni I, et al. SEGCloud: Semantic segmentation of 3D point clouds[C]. Proceedings of International Conference on 3D Vision (3DV), New York: IEEE, 2017: 537-547.

[34]Qi C R, Su H, Mo K C, et al. PointNet: Deep learning on point sets for 3D classification and segmentation[C]. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, New York: IEEE, 2017: 77-85.

[35]Qi C R, Yi L, Su H, et al. PointNet++: Deep hierarchical feature learning on point sets in a metric space[C]. Guyon I, Luxburg U V, Bengio S, et al. Advances in Neural Information Processing Systems, California: Neural Information Proceeding Systems (NIPS), 2017, 30.

[36]刘娜, 薛河儒, 马学磊. 基于改进K-means的羊体点云分割方法[J]. 江西农业大学学报, 2020, 42(5): 1078-1086.

[37]李真, 汪沛, 张青. 树干与地面点云分类K-means方法的改进[J]. 东北林业大学学报, 2019, 47(1): 41-46.

[38]麻卫峰, 王金亮, 麻源源, 等. 改进K均值聚类的点云林木胸径提取[J]. 测绘科学, 2021, 46(9): 122-129.

[39]杨永涛, 黄国言, 张坤, 等. 一种利用曲率约束的改进K-means三维点云数据分割方法[J]. 小型微型计算机系统, 2017, 38(11): 2573-2579.

[40]Hui Z Y, Jin S G, Xia Y P, et al. A mean shift segmentation morphological filter for airborne LiDAR DTM extraction under forest canopy[J]. Optics and laser technology, 2021, 136: 106728.

[41]Lei L T, Yin T, Chai G Q, et al. A novel algorithm of individual tree crowns segmentation considering three-dimensional canopy attributes using UAV oblique photos[J]. International Journal of Applied Earth Observation and Geoinformation, 2022, 112: 102893.

[42]Zhang C Q, Fan H C. An Improved Multi-Task Pointwise Network for Segmentation of Building Roofs in Airborne Laser Scanning Point Clouds[J]. Photogrammetric Record, 2022, 37(179): 260-284.

[43]Sun Y X, Luo Y S, Chai X Y, et al. Double-Threshold Segmentation of Panicle and Clustering Adaptive Density Estimation for Mature Rice Plants Based on 3D Point Cloud[J]. Electronics, 2021, 10(7): 872.

[44]杨征鹤, 喻晨, 杨会民, 等. 基于LiDAR的温室番茄冠层几何参数提取[J]. 新疆农业科学, 2021, 58(10): 1909-1917.

[45]Amarat S B, Zong P. 3D path planning, routing algorithms and routing protocols for unmanned air vehicles: a review[J]. Aircraft engineering, 2019, 91(9): 1245-1255.

[46]Lavalle S M. Rapidly-exploring random trees: A new tool for path planning[R]. Ames: Computer Science Department, Iowa State University, 1998.

[47]Karaman S, Frazzoli E. Sampling-Based Algorithms For optimal Motion Planning[J]. International journal of robotics research, 2011, 30(7): 846-894.

[48]Islam F, Nasir J, Malik U, et al. RRT*-smart: Rapid convergence implementation of RRT* towards optimal solution[C]. Proceedings of 2012 IEEE international conference on mechatronics and automation, IEEE, 2012: 1651-1656.

[49]Gammell J D, Srinivasa S S, Barfoot T D. Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]. Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, New York: IEEE, 2014: 2997-3004.

[50]Qureshi A H, Ayaz Y. Potential functions based sampling heuristic for optimal path planning[J]. Autonomous Robots, 2016, 40(6): 1079-1093.

[51]Jeong I B, Lee S J, Kim J H. Quick-RRT*: Triangular inequality-based implementation of RRT* with improved initial solution and convergence rate[J]. Expert Systems with Applications, 2019, 123: 82-90.

[52]Li Y J, Wei W, Gao Y, et al. PQ-RRT*: An improved path planning algorithm for mobile robots[J]. Expert Systems with Applications, 2020, 152: 113425.

[53]Wang J K, Chi W Z, Li C M, et al. Neural RRT*: Learning-based Optimal Path Planning[J]. IEEE Transactions on Automation Science and Engineering, 2020, 17(4): 1748-1758.

[54]Yi J H, Yuan Q N, Sun R T, et al. Path planning of a manipulator based on an improved P_RRT* algorithm[J]. Complex & Intelligent Systems, 2022, 8(3): 2227-2245.

[55]Lu L, Zong C X, Lei X Y, et al. Fixed-Wing UAV Path Planning in a Dynamic Environment via Dynamic RRT Algorithm[C]. Mechanism and Machine Science, Singapore: Springer, 2017, 408: 271-282.

[56]Guo Y C, Liu X X, Liu X H, et al. FC-RRT*: An Improved Path Planning Algorithm for UAV in 3D Complex Environment[J]. ISPRS International Journal of Geo-Information, 2022, 11(2): 112.

[57]Xu D, Qian H Y, Zhang S H. An improved RRT*-based real-time path planning algorithm for UAV[C]. Proceedings of IEEE International Conference on High Performance Computing & Communications, New York: IEEE, 2021: 883-888.

[58]Yang Y Y, Leeghim H, Kim D. Dubins Path-Oriented Rapidly Exploring Random Tree* for Three-Dimensional Path Planning of Unmanned Aerial Vehicles[J]. Electronics, 2022, 11(15): 2338.

[59]Zhao Y Q, Liu K, Lu G H, et al. Path Planning of UAV Delivery Based on Improved APF-RRT* Algorithm[J]. Journal of Physics: Conference Series, 2020, 1624: 042004.

[60]Fan J M, Chen X, Wang Y, et al. UAV trajectory planning in cluttered environments based on PF-RRT* algorithm with goal-biased strategy[J]. Engineering Applications of Artificial Intelligence, 2022, 114: 105182.

[61]王文曦, 李乐林. 深度学习在点云分类中的研究综述[J]. 计算机工程与应用, 2022, 58(01): 26-40.

[62]Ester M, Kriegel H P, Sander J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]. Simoudis E, Han J, Fayyad U. Proceedings of the second International Conference on Knowledge Discovery and Data Mining(KDD’96), 1996: 226-231.

[63]金立生, 贺阳, 王欢欢, 等. 基于自适应阈值DBSCAN的路侧点云分割算法[J]. 汽车工程, 2022, 44(07): 987-996.

[64]张长勇, 陈治华, 韩梁. 基于改进 DBSCAN 的激光雷达障碍物检测[J]. 激光与光电子学进展, 2021, 58(24): 443-450.

[65]Fu H P, Li H, Dong Y Q, et al. Segmenting Individual Tree from TLS Point Clouds Using Improved DBSCAN[J]. Forests, 2022, 13(4): 566.

[66]Wang C X, Ji M, Wang J, et al. An Improved DBSCAN Method for LiDAR Data Segmentation with Automatic Eps Estimation[J]. Sensors, 2019, 19(1): 172.

[67]刘天慧. 实时碰撞检测算法技术[M]. 北京: 清华大学出版社, 2010: 148-149.

[68]民航资源网. 低空空域使用管理规定（试行）（征求意见稿）[EB/OL]. http://news.carnoc.com/list/288/288814.html, 2014-7-23.

[69]廖小罕, 徐晨晨, 叶虎平, 等. 无人机应用发展关键基础设施与低空公共航路网规划[J]. 中国科学院院刊, 2022, 37(07): 977-988.

[70]交通运输部. 《无人机物流配送运行规范》编制说明征求意见稿[EB/OL]. https://xxgk.mot.gov.cn/2020/jigou/kjs/202110/P020211019522678373746.pdf, 2021-10-06.

[71]Yakushiji K, Fujita H, Murata M, et al. Short-range transportation using unmanned aerial vehicles (UAVs) during disasters in Japan[J]. Drones, 2020, 4(4): 68.

[72]Shi Y H, Lin Y, Li B, et al. A bi-objective optimization model for the medical supplies’ simultaneous pickup and delivery with drones[J]. Computers & Industrial Engineering, 2022, 171: 108389.

[73]Ke R M, Feng S, Cui Z Y, et al. Advanced framework for microscopic and lane-level macroscopic traffic parameters estimation from UAV video[J]. IET Intelligent Transport Systems, 2020, 14(7): 724-734.

[74]Zheng C W, Li L, Xu F J, et al. Evolutionary route planner for unmanned air vehicles[J]. IEEE Transactions on Robotics, 2005, 21(4): 609-620.

[75]Yang P, Tang K, Lozano J A, et al. Path planning for single unmanned aerial vehicle by separately evolving waypoints[J]. IEEE Transactions on Robotics, 2015, 31(5):1130-1146.

[76]Cheng Z K, Zhao L Y, Shi Z J. Decentralized Multi-UAV Path Planning Based on Two-Layer Coordinative Framework for Formation Rendezvous[J]. IEEE access, 2022, 10: 45695-45708.

[77]王康, 郭剑东, 桑标. 基于综合改进RRT算法的无人机三维航路规划[J]. 计算机仿真, 2021, 38(9): 40-44, 69.

[78]Ren X P, Li Tan, Shi J Q, et al. Multi-target UAV path planning based on improved RRT algorithm[J]. Journal of Physics: Conference Series, 2021, 1786(1): 012038.

[79]Yi J H, Yuan Q N, Sun R T, et al. Path planning of a manipulator based on an improved P_RRT* algorithm[J]. Complex & Intelligent Systems, 2022, 8(3): 2227-2245.

[80]Shi Y Y, Li Q Q, Bu S Q, et al. Research on Intelligent Vehicle Path Planning Based on Rapidly-Exploring Random Tree[J]. Mathematical Problems in Engineering, 2020, 2020: 5910503.

[81]Yang S M, Lin Y A. Development of an improved rapidly exploring random trees algorithm for static obstacle avoidance in autonomous vehicles[J]. Sensors, 21(6): 2244.

[82]Behley J, Garbade M, Milioto A, et al. SemanticKITTI: A Dataset for Semantic Scene Understanding of LiDAR Sequences[C]. IEEE/CVF International Conference on Computer Vision, New York: IEEE, 2019: 9297-9307.

[83]Geiger A, Lenz P, Urtasun R. Are we ready for autonomous driving? The KITTI vision benchmark suite[C]. IEEE Conference on Computer Vision and Pattern Recognition, New York: IEEE, 2012: 3354-3361.

[84]张长勇, 陈治华, 韩梁. 基于改进DBSCAN的激光雷达障碍物检测[J]. 激光与光电子学进展, 2021, 58(24): 443-450.

Hahsler M, Piekenbrock M, Doran D. dbscan: Fast Density-Based Clustering with R[J]. Journal of Statistical Software, 2019, 91(1): 1-30.