低空复杂环境下基于采样空间约减的无人机在线航迹规划算法

温乃峰; 苏小红; 马培军; 赵玲玲

doi:10.3724/SP.J.1004.2014.01376

低空复杂环境下基于采样空间约减的无人机在线航迹规划算法

doi: 10.3724/SP.J.1004.2014.01376

1.
哈尔滨工业大学计算机科学与技术学院哈尔滨 150001

基金项目:

国家自然科学基金（61175027）资助

详细信息

作者简介:
苏小红博士，哈尔滨工业大学计算机科学与技术学院教授. 主要研究方向为信息融合，软件工程和神经网络.E-mail：sxh@hit.edu.cn

计量
- 文章访问数: 1788
- HTML全文浏览量: 83
- PDF下载量: 976
- 被引次数: 0
出版历程
- 收稿日期: 2013-01-31
- 修回日期: 2014-01-03
- 刊出日期: 2014-07-20

Sampling Space Reduction-based UAV Online Path Planning Algorithm in Complex Low Altitude Environments

1.
School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001

Funds:

Supported by National Natural Science Foundation of China (61175027)

摘要

摘要: 针对低空复杂环境下障碍物密集且类型多样、带有多通道并存在不确定信息的无人机在线航迹规划问题，为了减少碰撞检测次数，提高航迹搜索速度，降低航迹代价，提出一种基于采样空间约减的无人机在线航迹规划算法. 算法通过引入代价模型，提出约减域逐步构造方法，引导规划树快速有效扩展，改善了基于动态域的快速拓展随机树（Dynamic domain rapidly-exploring random tree，DDRRT）算法中存在的采样空间过度约减问题. 算法通过密度划分索引的方法逐步构建多棵Kd 树（K-dimensional tree）并采用多近邻节点搜索方法，加快了近邻树节点搜索速度. 仿真实验结果表明，与DDRRT方法相比，该方法在保证对采样空间约减合理性的同时，提高了航迹规划效率和通道内的寻路能力.
- 在线航迹规划 /
- 多约束条件 /
- 快速拓展随机树算法 /
- 采样空间约减 /
- 碰撞检测
Abstract: The unmanned aerial vehicle (UAV) online path planning in low altitude complex environments is complicated due to the planning spaces of densely distributed obstacles with various shapes, narrow passages for the solution path to pass through, and uncertain information. For solving this problem, a sampling space reduction-based algorithm is proposed to reduce the number of collision detection calls, accelerate the path-search process and decrease the path cost. To deal with the over-reduction problem existing in the dynamic domain rapidly-exploring random tree (DDRRT) method, the algorithm makes the space reduction gradually by employing a cost model. Thus the planning tree can extend rapidly and efficiently under the guidance of the reduction. It also promotes the near neighbors searching speed by a new storage structure for tree nodes and a novel near neighbor searching approach. Indexes are built based on the density of tree nodes to construct the storage structure composed by multiple K-dimensional trees (Kd trees). Simulation results certify that our algorithm can ensure the rationality of the sampling space reduction and improve the efficiency of path planning and the ability of path-searching in passages, as compared to the DDRRT.
- Online path planning /
- multi-constraint /
- rapidly-exploring random tree (RRT) /
- sampling space reduction /
- collision detection

HTML全文

参考文献(39)

[1]	Ye Wen, Fan Hong-Da, Zhu Ai-Hong. Mission Planning for Unmanned Aerial Vehicles. Beijing: National Defense Industry Press, 2011. 1-201(叶文, 范洪达, 朱爱红. 无人飞行器任务规划. 北京: 国防工业出版社, 2011. 1-201)
[2]	Frazzoli E, Dahleh M A, Feron E. Real-time motion planning for agile autonomous vehicles. Journal of Guidance Control and Dynamics, 2002, 25(1): 116-129
[3]	Kim Y, Gu D W, Postlethwaite I. Real-time path planning with limited information for autonomous unmanned air vehicles. Automatica, 2008, 44(3): 696-712
[4]	Zhao Ming, Su Xiao-Hong, Ma Pei-Jun, Zhao Ling-Ling. A unified modeling method of UAVs cooperative target assignment by complex multi-constraints conditions. Acta Automatica Sinica, 2012, 38(12): 2038-2048(赵明, 苏小红, 马培军, 赵玲玲. 复杂多约束UAVs协同目标分配的一种统一建模方法. 自动化学报, 2012, 38(12): 2038-2048)
[5]	Tsourdos A, White B A, Shanmugavel M. Cooperative Path Planning of Unmanned Aerial Vehicles. West Sussex: Wiley & Sons, 2011. 1-185
[6]	LaValle S M. Planning Algorithms. Cambridge: Cambridge University Press, 2006. 482-580
[7]	Yuan Kui, Li Yuan, Fang Li-Xin. Multiple mobile robot systems: a survey of recent work. Acta Automatica Sinica, 2007, 33(8): 785-794(原魁, 李园, 房立新. 多移动机器人系统研究发展近况. 自动化学报, 2007, 33(8): 785-794)
[8]	Zhu Yi, Zhang Tao, Song Jing-Yan. Study on the local minima problem of path planning using potential field method in unknown environments. Acta Automatica Sinica, 2010, 36(8): 1122-1130(朱毅, 张涛, 宋靖雁. 未知环境下势场法路径规划的局部极小问题研究. 自动化学报, 2010, 36(8): 1122-1130)
[9]	Zhang Chun-Gang, Xi Yu-Geng. A real-time path planning method for mobile robot avoiding oscillation and dead circulation. Acta Automatica Sinica, 2003, 29(2): 197-205(张纯刚, 席裕庚. 一种克服振荡与死循环的机器人实时路径规划方法. 自动化学报, 2003, 29(2): 197-205)
[10]	LaValle S M, Kuffner J J. Randomized kinodynamic planning. In: Proceedings of the IEEE International Conference on Robotics and Automation. Detroit, USA: IEEE, 1999, 1: 473-479
[11]	Cheng Peng, Shen Zuo-Jun, LaValle S M. RRT-based trajectory design for autonomous automobiles and spacecraft. Archives of Control Sciences, 2001, 11(3): 167-194
[12]	Toda Y, Kubota N. Path planning using multi-resolution map for a mobile robot. In: Proceedings of the Society of Instrument and Control Engineers Annual Conference. Tokyo, Japan: IEEE, 2011. 1276-1281
[13]	Poppinga J, Birk A, Pathak, K, Vaskevicius N. Fast 6-DOF path planning for Autonomous Underwater Vehicles (AUV) based on 3D plane mapping. In: Proceedings of IEEE International Symposium on Safety, Security, and Rescue Robotics. Kyoto, Japan: IEEE, 2011. 345-350
[14]	Hsu D, Kindel R, Latombe J C, Rock S. Randomized kinodynamic motion planning with moving obstacles. The International Journal of Robotics Research, 2002, 21(3): 233-255
[15]	Zucker M, Kuffner J, Bagnell J A. Adaptive workspace biasing for sampling-based planners. In: Proceedings of the IEEE International Conference on Robotics and Automation. Kobe, Japan: IEEE, 2008. 3757-3762
[16]	Rodriguez S, Tang X Y, Lien J M, Amato N M. An obstacle-based rapidly-exploring random tree. In: Proceedings of the IEEE International Conference on Robotics and Automation. Orlando, USA: IEEE, 2006. 895-900
[17]	Yershova A, Jaillet L, Siméon T, LaValle S M. Dynamic-domain RRTs: efficient exploration by controlling the sampling domain. In: Proceedings of the IEEE International Conference on Robotics and Automation. Barcelona, Spain: IEEE, 2005. 3856-3861
[18]	Jaillet L, Yershova A, LaValle S M, Siméon T. Adaptive tuning of the sampling domain for dynamic-domain RRTs. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Edmonton, Canada: IEEE, 2005. 2851-2856
[19]	Montemanni R, Gambardella L M, Donati A V. A branch and bound algorithm for the robust shortest path problem with interval data. Operations Research Letters, 2004, 32(3): 225-232
[20]	Karaman S, Frazzoli E. Optimal kinodynamic motion planning using incremental sampling-based methods. In: Proceedings of the IEEE Conference on Decision and Control. Georgia, USA: IEEE Control Systems Society, 2010. 7681-7687
[21]	Urmson C, Simmons R. Approaches for heuristically biasing RRT growth. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Las Vegas, USA: IEEE, 2003, 2: 1178-1183
[22]	Lee J, Pippin C, Balch T. Cost based planning with RRT in outdoor environments. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Nice, France: IEEE, 2008. 684-689
[23]	Jaillet L, Cortés J, Siméon T. Transition-based path planning on configuration-space costmaps. IEEE Transactions on Robotics, 2010, 26(4): 635-646
[24]	Ferguson D, Stentz A. Anytime RRTs. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Beijing, China: IEEE, 2006. 5369-5375
[25]	Yang K J, Sukkarieh S. 3D smooth path planning for a UAV in cluttered natural environments. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robot and Systems. Nice, France: IEEE, 2008. 794-800
[26]	Karaman S, Walter M R, Perez A, Frazzoli E, Teller S. Anytime motion planning using the RRT. In: Proceedings of the IEEE International Conference on Robotics and Automation. Shanghai, China: IEEE, 2011. 1478-1483
[27]	Lindemann S R, LaValle S M. Incrementally reducing dispersion by increasing Voronoi bias in RRTs. In: Proceedings of the IEEE International Conference on Robotics and Automation. New Orleans, USA: IEEE, 2004, 4: 3251-3257
[28]	Lindemann S R, LaValle S M. Steps toward derandomizing RRTs. In: Proceedings of the Fourth International Workshop on Robot Motion and Control. Poznan, Poland: IEEE, 2004. 271-277
[29]	Bruce J, Veloso M. Real-time randomized path planning for robot navigation. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Lausanne, Switzerland: IEEE, 2002, 3: 2383-2388
[30]	Shi B F, Cheng P, Cheng N. 3D flight path planning based on RRTs for RNP requirements. In: International Conference on Information and Automation. Shenyang, China: IEEE, 2012. 51-56
[31]	Yang G, Kapila V. Optimal path planning for unmanned air vehicles with kinematic and tactical constraints. In: Proceedings of the 41st IEEE Conference on Decision and Control. Las Vegas, USA: IEEE, 2002, 2: 1301-1306
[32]	Guo Suo-Feng, Shen Gong-Zhang, Wu Cheng-Fu. Advanced Flight Control System. Beijing: National Defense Industry Press, 2003. 180-185(郭锁凤, 申功璋, 吴成富. 先进飞行控制系统. 北京: 国防工业出版社, 2003. 180-185)
[33]	Shanmugavel M, Tsourdos A, Zbikowski R, White B A. 3D dubins sets based on coordinated path planning for swarm of UAVs. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference and Exhibit. Colorado, USA: AIAA, 2006. 21-24
[34]	Ardiyanto I, Miura J. Real-time navigation using randomized kinodynamic planning with arrival time field. Robotics and Autonomous Systems, 2012, 60(12): 1579-1591
[35]	Aoude G S, How J P, Garcia I M. Two-stage path planning approach for solving multiple spacecraft reconfiguration maneuvers. The Journal of the Astronautical Sciences, 2008, 56(4): 515-544
[36]	Scheuer A, Fraichard T. Continuous-curvature path planning for car-like vehicles. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Grenoble, France: IEEE. 1997. 2: 997-1003
[37]	Garcia I, How J P. Trajectory optimization for satellite reconfiguration maneuvers with position and attitude constraints. In: Proceedings of the 2005 American Control Conference. Michigan, USA: American Automatic Control Council. 2005. 2: 889-894
[38]	Yershova A, LaValle S M. Improving motion-planning algorithms by efficient nearest-neighbor searching. IEEE Transactions on Robotics, 2007, 23(1): 151-157
[39]	Atramentov A, LaValle S M. Efficient nearest neighbor searching for motion planning. In: Proceedings of the IEEE International Conference on Robotics and Automation. Washington D C. USA: IEEE, 2002. 1: 632-637