[1]QI Xiaogang,LI Bo,FAN Yingsheng,et al.A survey of mission planning on UAVs systems based on multiple constraints[J].CAAI Transactions on Intelligent Systems,2020,15(2):204-217.[doi:10.11992/tis.201811018]
Copy

A survey of mission planning on UAVs systems based on multiple constraints

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 15 Number of periods: 2020 2 Page number: 204-217 Column: 综述 Public date: 2020-03-05
Title:
A survey of mission planning on UAVs systems based on multiple constraints
Author(s):
QI Xiaogang1; 3;  LI Bo1;  FAN Yingsheng1;  LIU Lifang2; 3
1. School of Mathematics and Statistics, Xidian University, Xi’an 710071, China;
2. School of Computer Science and Technology, Xidian University, Xi’an 710071, China;
3. Xidian-Ningbo Information Technology Institute, Ningbo 315200, China
Keywords:
unmanned aerial vehicle; mission planning; task assignment; path planning; heuristic algorithm; intelligence optimization algorithm; smoothing; flyable
CLC:
TP393
DOI:
10.11992/tis.201811018
Abstract:
Depending on the highly developed information technology, unmanned aerial vehicles (UAVs) have shown unprecedented advantages in combat. Accurate mission planning technique for UAVs provides an important guarantee for completing a given mission. Task assignment and path planning are the two core components of the mission planning technology for UAVs. Based on this technology, first, the development status, classification standards, and architecture of the mission planning for UAVs are discussed. Second, the important indicators, which affect task assignment and path planning are described in detail; they include classification criteria, constraint indicator, corresponding model, representative algorithm, and evaluation indicator. Then, the strength and weakness of the algorithms for solving tasks are compared, such as heuristic algorithm, mathematical programming method, and stochastic intelligent optimization algorithm. Similarly, for the path planning problem, the advantages and disadvantages of its algorithms, which include mathematical programming method, artificial potential field method, graphic-based method, and intelligent optimization algorithm, are also analyzed. Finally, open problems, the future work, and the research focus in UAVs mission planning are summarized.
References:
[1] 秦博, 王蕾. 无人机发展综述[J]. 飞航导弹, 2002(8): 4-10
QIN Bo, WANG Lei. Overview of UAV development[J]. Winged missiles journal, 2002(8): 4-10
[2] 孔嘉诚. 无人机(UAV)架构发展历程和方向[J]. 中国新通信, 2018, 20(2): 74
KONG Jiacheng. Architecture development history and direction of UAV[J]. China new telecommunications, 2018, 20(2): 74
[3] 李远. 多UAV协同任务资源分配与编队轨迹优化方法研究[D]. 长沙: 国防科学技术大学, 2011.
LI Yuan. Research on resources allocation and formation trajectories optimization for multiple UAVs cooperation mission[D]. Changsha: National University of Defense Technology, 2011.
[4] 赵明. 多无人机系统的协同目标分配和航迹规划方法研究[D]. 哈尔滨: 哈尔滨工业大学, 2016.
ZHAO Ming. Research on cooperative target assignment and path planning for multi-Unmanned aircraft system[D]. Harbin: Harbin Institute of Technology, 2016.
[5] 柳长安. 无人机航路规划方法研究[D]. 西安: 西北工业大学, 2003.
LIU Chang’an. Study on route planning method of UAV[D]. Xi’an: Northwestern Polytechnical University, 2003.
[6] ZHANG Xiangyin, DUAN Haibin. An improved constrained differential evolution algorithm for unmanned aerial vehicle global route planning[J]. Applied soft computing, 2015, 26: 270-284.
[7] 杜萍, 杨春. 飞行器航迹规划算法综述[J]. 飞行力学, 2005, 23(2): 10-14
DU Ping, YANG Chun. Introduction of air vehicle path planning algorithms[J]. Flight dynamics, 2005, 23(2): 10-14
[8] 闵昌万, 袁建平. 军用飞行器航迹规划综述[J]. 飞行力学, 1998, 16(4): 14-19
MIN Changwan, YUAN Jianping. Introduction of military aircraft route planning[J]. Flight dynamics, 1998, 16(4): 14-19
[9] 王春颖, 刘平, 秦洪政. 移动机器人的智能路径规划算法综述[J]. 传感器与微系统, 2018, 37(8): 5-8
WANG Chunying, LIU Ping, QIN Hongzheng. Review on intelligent path planning algorithm of mobile robots[J]. Transducer and microsystem technologies, 2018, 37(8): 5-8
[10] 杨晨, 张少卿, 孟光磊. 多无人机协同任务规划研究[J]. 指挥与控制学报, 2018, 4(3): 234-248
YANG Chen, ZHANG Shaoqing, MENG Guanglei. Multi-UAV cooperative mission planning[J]. Journal of command and control, 2018, 4(3): 234-248
[11] 邢立宁, 陈英武. 任务规划系统研究综述[J]. 火力与指挥控制, 2006, 31(4): 1-4
XING Lining, CHEN Yingwu. Overviews on mission planning system research[J]. Fire control and command control, 2006, 31(4): 1-4
[12] 魏瑞轩, 李学仁. 先进无人机系统与作战运用[M]. 北京: 国防工业出版社, 2014.
[13] 孙鑫, 陈晓东, 曹晓文, 等. 军用任务规划技术综述与展望[J]. 指挥与控制学报, 2018, 3(4): 289-298
SUN Xin, CHEN Xiaodong, CAO Xiaowen, et al. Review and prospect of military mission planning technology[J]. Journal of command and control, 2018, 3(4): 289-298
[14] 毛红保, 田松, 晁爱农. 无人机任务规划[M]. 北京: 国防工业出版社, 2015.
[15] SUD A, ANDERSEN E, CURTIS S, et al. Real-Time path planning in dynamic virtual environments using multiagent navigation graphs[J]. IEEE transactions on visualization and computer graphics, 2008, 14(3): 526-538.
[16] 林林. 基于协同机制的多无人机任务规划研究[D]. 北京: 北京邮电大学, 2013.
[17] 叶文, 廉华耕, 漆云海, 等. 无人机航路规划算法研究[J]. 电光与控制, 2011, 18(2): 8-12, 17
YE Wen, LIAN Huageng, QI Yunhai, et al. Path planning algorithm for UAV[J]. Electronics optics & control, 2011, 18(2): 8-12, 17
[18] BABEL L. Coordinated target assignment and UAV path planning with timing constraints[J]. Journal of intelligent & robotic systems, 2018.
[19] ZHEN Ziyang, XING Dongjing, GAO Chen. Cooperative search-attack mission planning for multi-UAV based on intelligent self-organized algorithm[J]. Aerospace science and technology, 2018, 76: 402-411.
[20] ZHENG Changwen, LI Lei, XU Fanjiang, et al. Evolutionary route planner for Unmanned Air Vehicles[J]. IEEE transactions on robotics, 2005, 21(4): 609-620.
[21] BELLINGHAM J, TILLERSON M, RICHARDS A, et al. Multi-task allocation and path planning for cooperating UAVs[C]//Proceedings of Cooperative Control: Models, Applications and Algorithms, Conference on Coordination, Control and Optimization. [S. l.] 2001: 1-19.
[22] 陈星. 无人机多目标的航线规划和任务分配算法研究[D]. 南京: 南京大学, 2018.
CHEN Xing. Research on multi-objective route planning and task allocation algorithm for UAVs[D]. Nanjing: Nanjing University, 2018.
[23] BROWN D T. Routing unmanned aerial vehicles while considering general restricted operating zones[D]. Ohio: Air Force Institute of Technology, 2001.
[24] 沈林成, 牛轶峰, 朱华勇. 多无人机自主协同控制理论与方法[M]. 北京: 国防工业出版社, 2013.
[25] BUI H, HAN Xu, MANDAL S, et al. Optimization-based decision support algorithms for a team-in-the-loop planning experiment[C]//Proceedings of IEEE International Conference on Systems, Man and Cybernetics. San Antonio, TX, USA, 2009: 4684-4689.
[26] 梁星星, 马扬, 冯旸赫, 等. 面向多旅行商问题的多目标模拟退火算法研究[J]. 南京师范大学学报(自然科学版), 2017, 40(3): 80-86
LIANG Xingxing, MA Yang, FENG Yanghe, et al. Research on multi-objective simulated annealing algorithm for multi-traveling salesman problem[J]. Journal of Nanjing Normal University (Natural Science Edition), 2017, 40(3): 80-86
[27] SOYLU B. A general variable neighborhood search heuristic for multiple traveling salesmen problem[J]. Computers & industrial engineering, 2015, 90: 390-401.
[28] KOTA L, JARMAI K. Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming[J]. Applied mathematical modelling, 2015, 39(12): 3410-3433.
[29] 刘光远, 贺一, 温万惠. 禁忌搜索算法及应用[M]. 北京: 科学出版社, 2014.
[30] 王凌. 智能优化算法及其应用[M]. 北京: 清华大学出版社, 2001.
[31] 夏洁, 高金源, 余舟毅. 基于禁忌搜索的启发式任务路径规划算法[J]. 控制与决策, 2002, 17(S1): 773-776
XIA Jie, GAO Jinyuan, YU Zhouyi. Heuristics decision algorithm for mission path planning based on tabu search[J]. Control and decision, 2002, 17(S1): 773-776
[32] 丁明跃. 无人飞行器航迹规划[M]. 北京: 电子工业出版社, 2009.
[33] 王宝广. 无人机任务规划系统研究[D]. 沈阳: 沈阳航空航天大学, 2013.
WANG Baoguang. The research of unmanned aerial vehicles mission planning system[D]. Shenyang: Shenyang Aerospace University, 2013.
[34] 贾广芝. 基于遗传算法和稀疏A*算法的无人机三维航迹规划研究[D]. 南京: 南京邮电大学, 2017.
JIA Guangzhi. Research on three-dimensional path planning of UAV based on genetic algorithm and sparse A* algorithm[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2017.
[35] 周明, 孙树栋. 遗传算法原理及应用[M]. 北京: 国防工业出版社, 1999.
[36] 李华昌, 谢淑兰, 易忠胜. 遗传算法的原理与应用[J]. 矿冶, 2005, 14(1): 87-90
LI Huachang, XIE Shulan, YI Zhongsheng. Theory and application of genetic algorithm[J]. Mining and metallurgy, 2005, 14(1): 87-90
[37] 周爱武, 于亚飞. K-Means聚类算法的研究[J]. 计算机技术与发展, 2011, 21(2): 62-65
ZHOU Aiwu, YU Yafei. The research about clustering algorithm of K-Means[J]. Computer technology and development, 2011, 21(2): 62-65
[38] BORCHERS B. MINLP: branch and bound methods[M]//FLOUDAS C A, PARDALOS P M. Encyclopedia of Optimization. Boston, MA: Springer, 2001.
[39] 叶媛媛, 闵春平, 朱华勇, 等. 基于整数规划的多UCAV任务分配问题研究[J]. 信息与控制, 2005, 34(5): 548-552
YE Yuanyuan, MIN Chunping, ZHU Huayong, et al. Multiple UCAV mission assignment based on integer programming[J]. Information and control, 2005, 34(5): 548-552
[40] 杨杰, 席建祥, 王成, 等. 多无人机协同巡视任务规划方法综述[J]. 飞行力学, 2018, 36(5): 1-6
YANG Jie, XI Jianxiang, WANG Chneg, et al. Summary of multi-UAV cooperative patrol task planning methods[J]. Flight dynamics, 2018, 36(5): 1-6
[41] 程春英. 群体智能算法的研究及MATLAB实现[M]. 赤峰: 内蒙古科学技术出版社, 2015.
[42] 郑金华. 多目标进化算法及其应用[M]. 北京: 科学出版社, 2007.
[43] 云庆夏. 进化算法[M]. 北京: 冶金工业出版社, 2000.
[44] KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks. Perth, WA, Australia, 2002: 1942-1948.
[45] 李士波. 基于粒子群算法的多无人机任务分配[J]. 软件导刊, 2018, 17(7): 193-195, 213
LI Shibo. Multi-UCAV mission allocation based on particle swarm optimization[J]. Software guide, 2018, 17(7): 193-195, 213
[46] WU Xiande, BAI Wenbin, XIE Yaen, et al. A hybrid algorithm of particle swarm optimization, metropolis criterion and RTS smoother for path planning of UAVs[J]. Applied soft computing, 2018, 73: 735-747.
[47] 彭斯俊, 黄樟灿, 刘道海, 等. 基于蚂蚁系统的TSP问题的新算法[J]. 武汉汽车工业大学学报, 1998, 20(5): 88-92
PENG Sijun, HUANG Zhangcan, LIU Daohai, et al. Ant colony system: a new algorithm for TSP[J]. Journal of Wuhan Automotive Polytechnic University, 1998, 20(5): 88-92
[48] 杨剑峰. 蚁群算法及其应用研究[D]. 杭州: 浙江大学, 2007.
YANG Jianfeng. Research on Ant colony algorithm and its application[D]. Hangzhou: Zhejiang University, 2007.
[49] DORIGO M, STüTZLE T. The ant colony optimization metaheuristic: algorithms, applications, and advances[M]//GLOVER F, KOCHENBERGER G A. Handbook of Metaheuristics. Boston, MA: Springer, 2003: 250-285.
[50] 段海滨, 丁全心, 常俊杰, 等. 基于并行蚁群优化的多UCAV任务分配仿真平台[J]. 航空学报, 2008, 29(S1): 192-197
DUAN Haibin, DING Quanxin, CHANG Junjie, et al. Multi-UCAVs task assignment simulation platform based on parallel ant colony optimization[J]. Acta aeronautica et astronautica sinica, 2008, 29(S1): 192-197
[51] 高尚, 杨静宇. 群智能算法及其应用[M]. 北京: 中国水利水电出版社, 2006.
[52] 符小卫, 高晓光. 威胁联网环境下多无人机协同控制[M]. 北京: 科学出版社, 2018.
[53] 郑昌文, 严平, 丁明跃, 等. 飞行器航迹规划研究现状与趋势[J]. 宇航学报, 2007, 28(6): 1441-1446
ZHENG Changwen, YAN Ping, DING Mingyue, et al. Research status and trend of route planning for flying vehicles[J]. Journal of astronautics, 2007, 28(6): 1441-1446
[54] BORTOFF S A. Path planning for UAVs[C]//Proceedings of the 2000 American Control Conference. Chicago, IL, USA, 2002: 364-368.
[55] 孙洪俊. 小型无人机多机路径协同规划方法研究[D]. 沈阳: 沈阳航空航天大学, 2018.
SUN Hongjun. Research on the collaborative planning method of Multi -Small UAV path[D]. Shenyang: Shenyang Aerospace University, 2018.
[56] WANG Yu, WANG Shuo, TAN Min, et al. Real-time dynamic dubins-helix method for 3-D trajectory smoothing[J]. IEEE transactions on control systems technology, 2015, 23(2): 730-736.
[57] AMBROSINO G, ARIOLA M, CINIGLIO U, et al. Algorithms for 3D UAV Path Generation and Tracking[C]//Proceedings of the 45th IEEE Conference on Decision and Control. San Diego, CA, USA, 2006: 5275-5280.
[58] DUBINS L E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents[J]. American journal of mathematics, 1957, 79(3): 497-516.
[59] 韩松臣, 秦俊奇, 韩品尧, 等. 马尔可夫决策过程在目标分配中的应用[J]. 哈尔滨工业大学学报, 1996, 28(2): 32-36
HAN Songchen, QIN Junqi, HAN Pinyao, et al. An application of the Markov decision process to target assignment[J]. Journal of Harbin Institute of Technology, 1996, 28(2): 32-36
[60] ZENG Wenhui, YI Jin, RAO Xiao, et al. A two-stage path planning approach for multiple car-like robots based on PH curves and a modified harmony search algorithm[J]. Engineering optimization, 2017, 49(11): 1995-2012.
[61] KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots[C]//Proceedings of IEEE International Conference on Robotics and Automation. St. Louis, MO, USA, 2003: 500-505.
[62] CONN R A, KAM M. Robot motion planning on N-dimensional star worlds among moving obstacles[J]. IEEE transactions on robotics and automation, 1998, 14(2): 320-325.
[63] 宋佳瑞. 基于人工势场法的机器人避障问题研究[D]. 沈阳: 沈阳工业大学, 2017.
SONG Jiarui. Obstacle avoidance problem study of Robot Based on Artificial Potential field method[D]. Shenyang: Shenyang University of Technology, 2017.
[64] 刘砚菊, 代涛, 宋建辉. 改进人工势场法的路径规划算法研究[J]. 沈阳理工大学学报, 2017, 36(1): 61-65, 76
LIU Yanju, DAI Tao, SONG Jianhui. Research of path planning algorithm based on improved artificial potential Field[J]. Journal of Shenyang Ligong University, 2017, 36(1): 61-65, 76
[65] 艾海舟, 张钹. 基于拓扑的路径规划问题的图形解法[J]. 机器人, 1990, 12(5): 20-24
AI Haizhou, ZHANG Bo. A graphic approach to path planning problem based on topological method[J]. Robot, 1990, 12(5): 20-24
[66] 王娟娟, 曹凯. 基于栅格法的机器人路径规划[J]. 农业装备与车辆工程, 2009(4): 14-17
WANG Juanjuan, CAO Kai. Path-planning for robot based on grid algorithm[J]. Agricultural equipment & vehicle engineering, 2009(4): 14-17
[67] 乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报, 1999, 24(3): 209-212
YUE Yang, GONG Jianya. An efficient implementation of shortest path algorithm based on Dijkstra Algorithm[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1999, 24(3): 209-212
[68] 皇甫淑云, 唐守锋, 童紫原, 等. 自主移动机器人路径规划方法研究综述[J]. 软件导刊, 2018, 17(10): 1-5
HUANGFU Shuyun, TANG Shoufeng, TONG Ziyuan, et al. A survey of path planning methods for autonomous mobile robots[J]. Software guide, 2018, 17(10): 1-5
[69] HE Xiaoxi, CHEN Leiting. Path planning based on Grid-Potential fields[C]//Proceedings of 2008 International Conference on Computer Science and Software Engineering. Hubei, China, 2008: 1114-1116.
[70] BEARD R W, MCLAIN T W, GOODRICH M A, et al. Coordinated target assignment and intercept for unmanned air vehicles[J]. IEEE transactions on robotics and automation, 2002, 18(6): 911-922.
[71] OVERMARS M H. A random approach to motion planning[R]. RUU-CS-92-32. The Netherlands: Utrecht University, 1992.
[72] 齐乃明, 孙小雷, 董程, 等. 航迹预测的多无人机任务规划方法[J]. 哈尔滨工业大学学报, 2016, 48(4): 32-36
QI Naiming, SUN Xiaolei, DONG Cheng, et al. Mission planning based on path prediction for multiple UAVs[J]. Journal of Harbin Institute of Technology, 2016, 48(4): 32-36
[73] CAO Wen, SHI Hui, ZHU Shulong, et al. Application of an improved A* algorithm in route planning[C]//Proceedings of 2009 WRI Global Congress on Intelligent Systems. Xiamen, China, 2009: 253-257.
[74] 史辉, 曹闻, 朱述龙, 等. A*算法的改进及其在路径规划中的应用[J]. 测绘与空间地理信息, 2009, 32(6): 208-211
SHI Hui, CAO Wen, ZHU Shulong, et al. Application of an improved A* Algorithm in shortest route planning[J]. Geomatics & spatial information technology, 2009, 32(6): 208-211
[75] TSOURDOS A, WHITE B, SHANMUGAVEL M. 无人机协同路径规划[M]. 祝小平, 周洲, 王怿译. 北京: 国防工业出版社, 2013.
[76] 闫俊丰. 无人机航路规划评估及修正方法研究[D]. 哈尔滨: 哈尔滨工业大学, 2016.
[77] NIKOLOS I K, VALAVANIS K P, TSOURVELOUDIS N C, et al. Evolutionary algorithm based offline/online path planner for UAV navigation[J]. IEEE transactions on systems, man, and cybernetics, part B (cybernetics), 2003, 33(6): 898-912.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems