基于边缘计算的无人机路径规划技术文献综述

文 献 综 述

1. 问题定义：

无人飞行器(Unmanned Aerial Vehicle, UAV)简称无人机，是指飞行器自主控制， 配备驱动装置和控制系统，能够执行任务的无人驾驶航空器。

无人机路径规划是无人机任务规划的一部分，也是无人机自主性的一个基本方面，要求在各种约束条件下，找到任务出发点到任务结束点的无人机飞行路径，并且找到的该条飞行路径要满足某种性能指标函数的度量。

其中，路径规划器是无人机（UAV）自主控制模块的关键要素。它允许无人机自动计算从起点到终点的最佳路径。商业航空公司始终遵循规定的航迹，而UAV在运营中则是在不断变化的航迹，这些航迹取决于其飞行时所处的特定地形和条件。过去，最佳路径是与最短路径相关联的，而确定性搜索算法则用于找到最短路径。此后，问题的定义不断发展，现在已经演化为，最佳路径与最小化行进距离，平均高度，燃油消耗，雷达辐射等的路径相关联。这些是需要考虑的因素的一些典型因素，并且清楚地表明问题的复杂性在增加。为了应对这种复杂性，研究方法已逐渐从使用确定性算法转变为使用非确定性算法[2]。

本课题使用两种不确定性算法来开发固定翼UAV的运行路径规划模块，用遗传算法（GA）和粒子群优化算法（PSO）来解决问题的复杂性，并在复杂的3D环境中针对无人机的可行性和准最优轨迹进行计算。

1. 研究背景及意义：

无人机研究在过去几年得到广泛关注，随着无人机自治性的提高，它在未来实际应用中的角色将越来越重要。无人机相对有人飞行器的主要优势在于它可以深入危险环境执行任务，例如战场或无人区。可以想见它在作战，救生，森林火险监测，救灾和天气预报方面的广泛应用。

无人机的飞行环境将是十分复杂的，需要综合考虑障碍物、威胁以及许多其他不利的影响因素。这些对无人机的环境感知能力提出了很高要求，环境感知是一个动态过程：一方面信息获取是从模糊到清晰的过程，另一方面目标和威胁在动态地变化，因此对无人机实时在线自主规划提出了很高的要求

可见，无人机研究是一个复杂多变系统工程，涉及到多个方面甚至多个领域，如果同时处理诸多问题将非常复杂；而且考虑到各种不确定因素，如导航误差、目标无规则的运动，新威胁的出现以及软硬件错误，进一步加大了无人机自主飞行的难度。针对上述的各种问题，研究无人机问题必须采取模块化方案，将复杂任务分解并针对具体的物理问题适当建模，形成可操作的子问题。本文采用遗传算法（GA）和粒子群优化算法（PSO）来优化无人机路径规划，这对于无人机的自主性进一步发展和提高有着重要的意义和价值。

1. 研究现状：

最初无人机只是作为训练靶机使用，限于当时电子技术发展状况，无人机直到20世纪八十年代才逐渐得到广泛应用，并在之后的海湾战争等局部战争中发挥了举足轻重的作用。鉴于无人机在战争中的特殊作用，各大国纷纷开始自主研发国产无人机。到目前为止，已有近百种无人机面世。全球鹰的飞行控制系统采用 GPS/INS组合导航方式，可自主完成从起飞到着陆的整个飞行过程，它是目前世界上飞行高度最高、航程最远、滞空飞行时间最长的无人机，也是当今世界上最先进的无人侦察机。

无人机系统主要包括飞行控制系统、电源系统、测控系统、机载系统、发射/回收系统、数据链路系统和地面控制站，机载系统中的导航系统是无人机重要组成部分。相比于有人驾驶飞机，无人机有以下优势：空间利用率高，用途广泛，滞空时间长，生存能力强，成本低，效费比高，无人员伤亡风险。随着军事科学技术的发展，无人机作战环境变得越来越复杂，对无人机的智能化程度要求越来越高。在复杂环境条件下，现有的无人机如果没有人为控制干预，往往不能顺利完成既定任务。在传统控制模式中，无人机的控制可以由混合编队中的有人驾驶飞机通过近距离数据链实现，也可以通过远距离的地面或空中的指挥平台实现，还可以通过卫星通信中继实现。

以上方法都是通过外界的数据通信链实现对无人机的控制，然而无人机尤其是无人作战飞机，在飞行过程中遇到极端恶劣环境的概率非常大，在这种情况下通信数据链很有可能变得不再畅通可靠，这对顺利完成任务构成非常大的威胁。因此，无人机必须具备一定的自主决策能力，能够自适应地改变飞行路径以适应复杂变化的环境。无人机的飞行一般都需要执行特定的飞行任务，所以无人机的航迹规划首先要满足任务要求。无人机航迹规划就是在综合考虑任务要求、威胁代价、油耗代价、载荷性能的情况下，为无人机规划出一条从起始点到目标点的最优飞行航迹。无人机航迹规划可以分为离线航迹规划和在线航迹规划，离线航迹规划是指在无人机起飞前，地面规划系统预先为无人机规划的航迹；在线航迹规划是指无人机起飞后，由于飞行空间的不完全已知性，飞行环境可能发生威胁变化或地理环境变化等，此时离线规划航迹不再是最优航迹，这就要求规划系统根据当前飞行状态和最新探测到的规划环境进行航迹重规划，以保证无人机能够安全到达目标区域，并完成指定任务。

无人机路径规划是指在综合考虑任务要求、威胁代价、约束条件等因素的前提下，为无人机规划出一条从起始点到目标点的最优或次优的飞行路径，以保证飞行器圆满完成飞行任务，并安全返回基地。路径规划结果的优劣主要取决于所采用的路径规划算法，现有的路径规划算法主要有以下几种：基于概略图的规划方法 ，人工势场法 ，数学规划方法 ，基于遗传算法的方法以及基于粒子群优化算法的方法。

本课题中，我们使用了遗传算法(GA)和粒子群算法(PSO)两种不确定性算法来开发固定翼UAV的运行路径规划模块。遗传算法是一种基于人口的不确定性优化方法，由约翰·霍兰德（John Holland）在1960年代开发，并于1975年首次发表[15]。遗传算法基于达尔文进化论的遗传理论，模拟了一组解决方案的进化以优化问题。与世代相适应的生物体相似，遗传算法中的解决方案使用类似生物学的算子，例如染色体的交叉，基因的突变和基因的倒置，在迭代过程中采用适应功能。粒子群算法是Kennedy和Eberhart在1995年提出的基于PSO种群的不确定性优化方法[19]。与GA相似，PSO最近也被广泛应用，例如无限冲激响应数字滤波器的设计和优化[20]。该算法模拟多维搜索空间中一群粒子向最佳解前进的运动，每个粒子的位置代表一个候选溶液，并且是随机引发的。

同时本课题采用将物理空间具体化为对路径规划算法有意义的表示形式。这种表示形式与研究算法紧密相关，而某些算法与特定的环境表示形式相结合，则能表现得很好。 [10]中概述了使用不同算法的不同表示的性能。在实现中，我们使用二维网格对地形进行近似单元分解，其中矩阵的每个元素代表地形的高程。这种表示方式使我们可以使用GeoBase [11]存储库中免费提供的数字高程图，而无需进行进一步处理，减少了算法的计算量。

我们的研究工作提出了三个重要的贡献。首先，我们提出了一个综合成本函数，其中包括优化和可行性标准。这允许使用通用的优化算法（未经修改）作为搜索算法。其次，我们提出了并行化GA和PSO的方法，来最小化进程之间的通信，以实现更高的线性速度并充分利用当今多核CPU的计算能力。其次，我们将基于GA和PSO的路径规划人员生成的轨迹质量之间的统计进行比较。两种算法最近都已广泛用于无人机路径规划[3] – [8]和[9]。然而，据相关资料显示，当将这两种算法应用于该特定问题时，没有进行严格的比较，所以本课题也将研究，对于在复杂3D环境中的UAV路径规划中，这两种算法哪种优化算法更适合用来进行无人机路径规划。

参考文献：

[1] H.Chen,X.-M.Wang,andY.Li,“Asurveyofautonomouscontrolfor UAV,” in Proc. 2009 Int. Conf. Artif. Intell. Comput. Intell., 2009, vol. 2, pp. 267–271.

[2] E. Masehian and D. Sedighizadeh, “Classic and heuristic approaches in robot motion planning—A chronological review,” World Academy of Science, vol. 29, pp. 101–106, 2007.

[3] P. Y. Volkan, “A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV,” Aerosp. Sci. Technol., vol. 16, no. 1, pp. 47–55, Jan. 2012.

[4] D. G. Macharet, A. A. Neto, and M. F. M. Campos, “Feasible UAV path planning using genetic algorithms and Bezier curves,” in Proc. SBIArsquo;10, Berlin, Germany, 2010, pp. 223–232.

[5]Z.Cheng,Y.Sun,andY.Liu,“Pathplanningbasedonimmunegenetic algorithm for UAV,” in Proc. Int. Conf. Electric Inform. Control Eng., 2011, pp. 590–593.

[6] Y. Bao, X. Fu, and X. Gao, “Path planning for reconnaissance UAV basedonparticleswarmoptimization,”inProc.2ndInt.Conf.Comput.Intell.Natural Comput., CINCrsquo;10, Wuhan, China, 2010, vol. 2, pp. 28–32.

[7] Y. Fu, M. Ding, and C. Zhou, “Phase angle-encoded and quantum-behaved particle swarm optimization applied to three-dimensional route planningforUAV,”IEEETrans.Syst.,Man,Cybern.,vol.42,no.2,pp. 511–526, 2012.

[8] D. M. Pierre, N. Zakaria, and A. J. Pal, “Master-slave parallel vectorevaluated genetic algorithm for unmanned aerial vehiclersquo;s path planning,” in Proc. Int. Conf. Hybrid Intell. Syst., 2011, pp. 517–521.

[9]G.Wang,Q.Li,andL.Guo,“MultipleUAVsroutesplanningbasedonparticleswarmoptimizationalgorithm,”inProc.2ndInt.Symp.Inform.Eng.Electronic Commerce, 2010, pp. 1–5.

[10] N.SariffandN.Buniyamin,“Anoverviewofautonomousmobilerobot path planning algorithms,” in Proc. 4th Student Conf. Res. Develop., Piscataway, NJ, USA, 2006, pp. 183–188.

[11] GeoBase—Canadian Digital Elevation Data Accessed: Apr. 3, 2012. [Online]. Available: http://www.geobase.ca/geobase/en/index.html

[12] G. Labonteacute;, “Mathematical relations to analyze aircraft performance for trajectory planning” Defense Research and Development, Ottawa, ON, Canada, Contract Rep. CR 2010-249, Dec. 2010.

[13] J.D.J.Anderson,IntroductiontoFlight,6thed. NewYork:McGrawHill, 2008.

[14] J. Bresenham, “Algorithm for computer control of a digital plotter,” IBM Syst. J., vol. 4, no. 1, pp. 25–30, 1965.

[15] J. H. Holland, Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press, 1975.

[16] A. Slowik, “Application of evolutionary algorithm to design minimal phase digital filters with non-standard amplitude characteristics and finite bit word length,” Bull. Polish Acad. Sci.: Tech. Sci., vol. 59, no. 2, pp. 125–135, 2011.

[17] A. Slowik and J. Slowik, “Multi-objective optimization of surface grinding process with the use of evolutionary algorithm with remembered Pareto set,” Int. J. Adv. Manuf. Technol., vol. 37, no. 7–8, pp. 657–669, 2008.

[18] X.YuandM.Gen,IntroductiontoEvolutionaryAlgorithms. London, U.K.: Springer, 2010.

[19] J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proc. IEEE Int. Conf. Neural Networks, Perth, WA, Australia, 1995, vol. 4, pp. 1942–1948.

[20] A. Slowik and M. Bialko, “Design and optimization of ir digital filters withnon-standardcharacteristicsusingparticleswarmoptimizationalgorithm,” in Proc. ICECSrsquo;07, Piscataway, NJ, 2007, pp. 162–165.

[21] M. Clerc, Particle Swarm Optimization. Paris, France: Lavoisier, 2005.

[22] G. Labonteacute;, “On the construction of dynamically feasible aircraft trajectoriesusingseriesoflinesegments,”Comput.Intell.Res.Lab,RMC, Nov. 2009. [Online]. Available: http://cirl.dyndns.org/en/downloads/ internal-publications/58-g

[23] I. Hasircioglu, H. R. Topcuoglu, and M. Ermis, “3-D path planning for the navigation of unmanned aerial vehicles by using evolutionary algorithms,”inProc.10thAnnu.Conf.GeneticEvol.Comput.,Atlanta, GA, 2008, pp. 1499–1506.

[24] E. P. Anderson, R. W. Beard, and T. W. McLain, “Real-time dynamic trajectory smoothing for unmanned air vehicles,” IEEE Trans. Control Syst. Technol., vol. 13, no. 3, pp. 471–477, May 2005.

[25] C. L. Bottasso, D. Leonello, and B. Savini, “Path planning for autonomous vehicles by trajectory smoothing using motion primitives,” IEEE Trans. Control Syst. Technol., vol. 16, no. 6, pp. 1152–1168, 2008.

[26] S. N. Sivanandam and S. N. Deepa, Introduction to Genetic Algorithms. New York: Springer, 2008.

[27] MATLABTwo-SampleT-TestAccessedApr.3,2012.[Online].Available: http://www.mathworks.com/help/toolbox/stats/ttest2.html