An Efficient Path Planning Strategy for a Rotorcraft UAV in 3D Cluttered Mountainous Environments
ZHANG Yiwei1,2, TAN Jianhao1,2, WANG Yaonan1,2
1. College of Electrical and Information Engineering, Hunan University, Changsha 410082, China;
2. National Engineering Laboratory for Robot Visual Perception and Control Technology, Changsha 410082, China
张艺巍, 谭建豪, 王耀南. 3维复杂山地环境下旋翼无人飞行器高时效航迹规划策略[J]. 机器人, 2016, 38(6): 727-737.DOI: 10.13973/j.cnki.robot.2016.0727.
ZHANG Yiwei, TAN Jianhao, WANG Yaonan. An Efficient Path Planning Strategy for a Rotorcraft UAV in 3D Cluttered Mountainous Environments. ROBOT, 2016, 38(6): 727-737. DOI: 10.13973/j.cnki.robot.2016.0727.
Abstract:A time-efficient and low-cost path planning strategy is proposed by designing and using a fusion algorithm composed of an improved sparse A* algorithm and a bio-inspired neural dynamics model, and it is an optimal strategy for a rotorcraft UAV (unmanned aerial vehicle) when performing non-collision flying tasks in three-dimensional low-altitude cluttered mountainous environments. The bio-inspired neural dynamics model is integrated into sparse A* global optimal search to adjust local paths in order to speed up the formation of the final optimal path in the proposed fusion algorithm, and the neural dynamics model is adopted to obtain and process local dynamic information from the environment in real time. Therefore, the online path planning is realized by the fusion algorithm, and dynamic path planning problem is solved, which is impossible for the traditional best-first search algorithm. Experiments are carried out in an emulational 3D task space of multi-peak mountainous environment, especially for the concave mountainous environment. Experimental results show that the proposed fusion algorithm not only reduces complexity and time consumption of A* algorithm, but also takes the cost of the path into account which isn't considered in the bio-inspired neural dynamics model. Furthermore, it can cope with unexpected threats in the task space on line. Then finally, a low-cost and high-quality path is planned out to reach target position safely and quickly for a rotorcraft UAV flying in cluttered environment containing both static and dynamic obstacles.
[1] de Filippis L, Guglieri G, Quagliotti F. Path planning strategies for UAVs in 3D environments[J]. Journal of Intelligent and Robotic Systems, 2012, 65(1-4): 247-264.
[2] Yang K, Gan S K, Sukkarieh S. An efficient path planning and control algorithm for RUAV's in unknown and cluttered environments[J]. Journal of Intelligent and Robotic Systems, 2010, 57(1-4): 101-122.
[3] Roberge V, Tarbouchi M, Labonte G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J]. IEEE Transactions on Industrial Informatics, 2013, 9(1): 132-141.
[4] 王怿,祝小平,周洲,等.3维动态环境下的无人机路径跟踪算法[J].机器人,2014,36(1):83-91. Wang Y, Zhu X P, Zhou Z, et al. UAV path following in 3-D dynamic environment[J]. Robot, 2014, 36(1): 83-91.
[5] Raja P, Pugazhenthi S. Optimal path planning of mobile robots: A review[J]. International Journal of Physical Sciences, 2012, 7(9): 1314-1320.
[6] 康亮,赵春霞,郭剑辉.基于模糊滚动RRT算法的移动机器人路径规划[J].南京理工大学学报:自然科学版,2010,34(5):642-648. Kang L, Zhao C X, Guo J H. Path planning based on fuzzy rolling rapidly-exploring random tree for mobile robot[J]. Journal of Nanjing University of Science and Technology: Natural Science, 2010, 34(5): 642-648.
[7] 温乃峰,苏小红,马培军,等.低空复杂环境下基于采样空间约减的无人机在线航迹规划算法[J].自动化学报,2014,40(7):1376-1390. Wen N F, Su X H, Ma P J, et al. Sampling space reduction-based UAV online path planning algorithm in complex low altitude environments[J]. Acta Automatica Sinica, 2014, 40(7): 1376-1390.
[8] Balaprakash P, Wild S M, Hovland P D. An experimental study of global and local search algorithms in empirical performance tuning[C]//10th International Conference on High Performance Computing for Computational Science. Berlin, Germany: Springer, 2012: 261-269.
[9] Aarts E, Korst J, Michiels W. Simulated annealing[M]//Search Methodologies. New York, USA: Springer, 2014: 187-210.
[10] 辛煜,梁华为,杜明博,等.一种可搜索无限个邻域的改进A* 算法[J].机器人,2014,36(5):627-633. Xin Y, Liang H W, Du M B, et al. An improved A* algorithmfor searching infinite neighbourhoods[J]. Robot, 2014, 36(5): 627-633.
[11] 刘艳丽,樊晓平,张恒.基于启发式搜索的移动机器人主动定位[J].机器人,2012,34(5):590-595,603. Liu Y L, Fan X P, Zhang H. Heuristic search assisted active localization for mobile robot[J]. Robot, 2012, 34(5): 590-595, 603.
[12] Liu Y, Li G X, Xia D, et al. Identifying dynamic parameters of a space robot based on improved genetic algorithm[J]. Journal of the Harbin Institute of Technology, 2010, 42(11): 1734-1739.
[13] 朱毅,张涛,宋靖雁.未知环境下势场法路径规划的局部极小问题研究[J].自动化学报,2010,36(8):1122-1130. Zhu Y, Zhang T, Song J Y. Study on the local minima problem of path planning using potential field method in unknown environments[J]. Acta Automatica Sinica, 2010, 36(8): 1122-1130.
[14] Cetin O, Zagli I, Yilmaz G. Establishing obstacle and collision free communication relay for UAVs with artificial potential fields[J]. Journal of Intelligent and Robotic Systems, 2013, 69(1-4): 361-372.
[15] 欧阳鑫玉,杨曙光.基于势场栅格法的移动机器人避障路径规划[J].控制工程,2014,21(1):134-137. Ouyang X Y, Yang S G. Obstacle avoidance path planning of mobile robots based on potential grid method[J]. Control Engineering of China, 2014, 21(1): 134-137.
[16] 王伟峰,吴勇超,张旭,等.基于栅格法的移动机器人单元分解遍历方法研究[J].自动化技术与应用,2013,32(11):34-38,42. Wang W F, Wu Y C, Zhang X, et al. Research of the unit decomposing traversal method based on grid method of the mobile robot[J]. Techniques of Automation and Applications, 2013, 32(11): 34-38,42.
[17] Yang S X, Meng M Q H. Real-time collision-free motion planning of a mobile robot using a neural dynamics-based approach[J]. IEEE Transactions on Neural Networks, 2003, 14(6): 1541-1552.
[18] Luo C M, Yang S X. A bioinspired neural network for real-time concurrent map building and complete coverage robot navigation in unknown environments[J]. IEEE Transactions on Neural Networks, 2008, 19(7): 1279-1298.
[19] Li S, Guo Y. Neural-network based AUV path planning in estuary environments[C]//10th World Congress on Intelligent Control and Automation. Piscataway, USA: IEEE, 2012: 3724-3730.
[20] 朱大奇,孙兵,李利.基于生物启发模型的AUV三维自主路径规划与安全避障算法[J].控制与决策,2015,30(5):798-806. Zhu D Q, Sun B, Li L. Algorithm for AUV's 3-D path planning and safe obstacle avoidance based on biological inspired model[J]. Control and Decision, 2015, 30(5): 798-806.
[21] 宋大雷,孟祥冬,齐俊桐,等.3自由度旋翼飞行机械臂系统动力学建模与预测控制方法[J].机器人,2015,37(2):152-160. Song D L, Meng X D, Qi J T, et al. Strategy of dynamic modeling and predictive control on 3-DoF rotorcraft aerial manipulator system[J]. Robot, 2015, 37(2): 152-160.
[22] 阮晓钢,侯旭阳,龚道雄.可重构旋翼无人飞行器的动力学建模与分析[J].机器人,2013,35(2):227-238. Ruan X G, Hou X Y, Gong D X. Dynamics modeling and analysis of a reconfigurable rotorcraft unmanned aerial vehicle[J]. Robot, 2013, 35(2): 227-238.
[23] Thomas A, Kaltschmidt C. Bio-inspired neural networks[M]// Memristor Networks. New York, USA: Springer, 2014: 151-172.
[24] Hodgkin A L, Huxley A F. A quantitative description of membrane current and its application to conduction and excitation in nerve[J]. Journal of Physiology, 1952, 117(4): 500-544.
[25] Szczerba R J, Galkowski P, Glickstein I S, et al. Robust algorithm for real-time route planning[J]. IEEE Transactions on Aerospace and Electronic Systems, 2000, 36(3): 869-878.
[26] 姚远,周兴社,张凯龙,等.基于稀疏A*搜索和改进人工势场的无人机动态航迹规划[J].控制理论与应用,2010,27(7):953-959. Yao Y, Zhou X S, Zhang K L, et al. Dynamic trajectory planning for unmanned aerial vehicle based on sparse A* search and improved artificial potential field[J]. Control Theory and Applications, 2010, 27(7): 953-959.
[27] Nosrati M, Karimi R, Hasanvand H A. Investigation of the *(star) search algorithms: Characteristics, methods and approaches[J]. World Applied Programming, 2012, 2(4): 251-256.
[28] Rana K, Zaveri M. A-star algorithm for energy efficient routing in wireless sensor network[M]//Trends in Network and Communications. Berlin, Germany: Springer, 2011: 232-241.
[29] Fomin F V, Kratochvil J, Lokshtanov D, et al. On the complexity of reconstructing H-free graphs from their star systems[J]. Journal of Graph Theory, 2011, 68(2): 113-124.
[30] Cartis C, Gould N I M, Toint P L. An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity[J]. IMA Journal of Numerical Analysis, 2012, 32(4): 1662-1695.
[31] Grossberg S. Nonlinear neural networks: Principles, mechanisms, and architectures[J]. Neural Networks, 1988, 1(1): 17-61.
[32] Cohen M A, Grossberg S. Absolute stability of global pattern formation and parallel memory storage by competitive neural networks[J]. IEEE Transactions on Systems, Man and Cybernetics, 1983, 13(5): 815-826.
[33] 徐飞,高俊钗.自主移动机器人局部优化导航算法研究[J].西安工业大学学报,2014,5(3):183-187. Xu F, Gao J C. Research of locally-optimized navigation algorithm for autonomous mobile robots[J]. Journal of Xi'an Technological University, 2014, 5(3): 183-187.