空中机器人（UAV）轨迹规划设计与仿真说明书

1、河海大学文天学院I毕业设计（论文）空中机器人（UAV）轨迹规划设计与仿真摘要机器人轨迹布局不仅是机器人技术的一个非常重要的钻研范围，也是人工智能和机器人技术的一个有趣的组合。轨迹规划是无人机的一项关键技术。这也是无人机自主导航的先决条件。静态环境下分布的障碍，寻求最短路径从起点到目标点的全局路径规划具有重要的科学意义。本课题是关于无人机的轨迹规划与设计。使用网格来处理无人机的弹道环境，然后找到最短路径从起点到基于栅格化环境下使用 A*算法的目标点。轨迹规划仿真是驾驭在微软 Visual C+ 6 开发环境下的。通过模拟运动轨迹，我们可以清楚地证明，无人机可以寻求最短路径从起点到基于 A*算法的

2、目标点关键词：空中机器人（UAV）；轨迹规划；A*算法；Visual C+ 仿真I河海大学文天学院I毕I 业设计（论文）ABSTRACTRobot trajectory planning is not only an important research field of robot technology, is also an interesting combination of artificial intelligence and robotics. Trajectory planning is a key technology of uav. This is also the prer

3、equisite for UAV autonomous navigation. The distribution of obstacles in a static environment, seeking the shortest path has important scientific significance for global path planning from the starting point to the target point.This paper is about the design and trajectory planning of uav. Use the g

4、rid to deal with the UAV trajectory environment, and then use the grid environment based on the target discovery shortest path from the starting point to the A * algorithm. Simulation of trajectory planning is in the hands of Microsoft Visual C+ 6 development environment. By simulating the trajector

5、y, we can clearly demonstrate the UAV can seek the shortest path from the starting point to the target point based on A * algorithm.Key words: Aerial Robot (UAV);Trajectory planning;A* algorithm; simulation based on Visual C+II河海大学文天学院II毕I 业设计（论文）目 录IV摘要IABSTRACTII第 1 章 绪论11.1 空中机器人（UAV）概述11.2 轨迹规划概

6、述21.3 国内外对空中机器人（UAV）研究状况41.4 课题背景和研究意义61.5 设计的要求和内容61.5.1 设计要求61.5.2 设计内容7第 2 章 空中机器人轨迹规划方案与环境描述92.1 空中机器人（UAV）飞行控制与管理92.2 空中机器人（UAV）轨迹环境描述122.2.1 栅格法简介122.2.2 建立轨迹的环境模型122.3 空中机器人（UAV）轨迹规划的算法142.3.1 空中机器人(UAV)轨迹规划常用算法142.3.2 遗传算法（Genetic Algorithm，GA ）162.3.3 A*算法（A-star Algorithm，A*）182.4 空中机器人(UA

7、V)轨迹规划算法选择19第 3 章 基于A*算法的空中机器人轨迹规划设计203.1 A*算法203.1.1 基本概念203.1.2 评价函数203.2 A*算法的性质223.2.2 可用性223.3 A*算法的衡量标准233.4 A*算法的不足24第 4 章 空中机器人轨迹规划仿真264.1 算法的步骤264.2 算法的流程274.3 空中机器人（UAV）轨迹规划仿真294.3.1 数据结构294.3.2 主要函数和功能324.3.3 主要函数及功能354.4 空中机器人（UAV）轨迹规划仿真图49第 5 章 结论51致谢52参考文献53河海大学文天学院毕业设计（论文）第 1 章 绪论1.1

8、空中机器人（UAV）概述空中机器人（英文缩写:Unmanned Aerial Vehicle），我们也可以叫作无人机。它是没有驾驶室不载人飞机，而且是一个独立的程序控制装置使用的无线电遥控设备。低空，船或母机遥控站人员经过雷达设施控制。在无线电遥控像个别飞机一样腾飞或发射火箭，但也由机器到空中的航行。自动回到陆地，并且回收， 跟一般飞机相比较，着陆方式完全相同，远程控制也可以通过降落伞或块回收。可反复使用多次。很大范围在空中侦察，侦察，通讯，电子干扰，反潜艇中运用。图 1.1 空中机器人（UAV）伴随着科学技术的进步，和当今战场上所要需求，越来越多的人们对军事空中机器人的研究更加关注。当前空中

9、机器人机的发展，主要经历了以下几个段：1. 无人机充当会飞的航空炸弹和靶机阶段：无人机的早期阶段，机构简单， 短距离，有效载荷低，单任务的执行。轰炸的无人机任务开始，“柯蒂斯”无人机是轰炸机，飞到目标区域时，发动机停止工作，随着机身携带炸弹，设定目标54在一起。世界上第一个研究还具有无人机目标的实用价值和大规模生产机。在1934 到 1943 期间，英国无人机生产了 400 多架。在无人机靶机的发展史上占有重要地位，大多数物种。2. 由无人机执行其他任务阶段：伴随着相应技术的展开，一些国家试图化装侦察，遥感，在目标检测、电子器件，具有战场侦察，监视，目标检测，电子战的能力，甚至是无人作战飞机的

10、想法，所以没有目标函数对其他人机功能的转型与发展。在这一阶段，国家已定型生产的“猎人”，“先锋”，“凤凰”，“鹭，哨兵 CL - 227，cl-289，“巨嘴鸟”进行侦察，监视，电子干扰，无人机的火灾和其他任务。3. 将攻击、侦察等一些任务于一身的无人机阶段：二十世纪 80 年代微电子、光电技术和计算机技术的发展，无人机跨世代的进步，提供了物质基础，也奠定了自由人类发展的实践基础。美国研制的“天睛”40 型多用途无人机翼，你可以安装 6 枚 10 公斤，70 毫米发射导弹，已完成多重任务的能力。1.2 轨迹规划概述轨迹规划措施主要分为两个方面：工业机器人是指两个方向，机械臂末端行走的曲线轨迹，

11、其机械臂在各个方面被运用；关于移动机器人，则途径规划有时是指移动机器人，如机器人是移动机器人的情况下，不管有没有地图的情况下，按照什么样的路径走。1. 工器人的轨迹规划（1） 常见的工业机器人作业有两种： 1）点位作业（PTP=point-to-point motion）2）连续路径作业（continuous-path motion），或者称为轮廓运动（contourmotion）。（2） 操作臂最常用的轨迹规划方法有两种：第一种是要求对于选定的轨迹结点（插值点）上的位姿、速度和加速度给出一组显式约束（例如连续性和光滑程度等），轨迹规划器从一类函数（例如 n 次多项式）选取参数化轨迹，对结点进

12、行插值，并满足约束条件。第二种方法要求给出运动路径的解析式。 2 图 2.工业机器人轨迹规划2. 移动机器人轨迹规划移动机器人的发现开于20世纪6O年代末期 Shakey自主移动机器人被斯坦福研究院研制出来。研究出移动机器人是为了在艰难环境下钻研人工智能技术机器人系统的自主推理、布局和管制。移动机器人的路径规划在机器人的范围中起到一个重要环节。移动机器人的最优路径是通过某一性能指标搜索一条从起始到目标。其主要触及的效果包含：运用取得的移动机器人环境信息树立较为正当的模型图1.3移动机器人轨迹规划1.3 国内外对空中机器人（UAV）研究状况从国内外人机历史的发展来观察，许多国家已经对空中机器人研

13、究非常的热情，许多国家在军用上已经配备了无人机。空中机器人引领 21 世纪航空科技发展的中心力量通过它的平台特有的才能。无人机的航行高度非常的高，航程也非常的长。无人机这么快能受到重视是因为其承担的工作种类比较多，从起初的一些简单辅助性机型到从执行高任务的作战型机型，无人机的作用越来越大，在军事方面已经无法超越。就目前的形势来看，我相信无人机在不久的将来发展主要会沿着无人作战飞机的模式发展。通过国内外一些专家研究，机器人研究中机器人轨迹规划是非常重要的一个环节。而且是机器人技术和人工智能技术的结晶，机器人的轨迹规划出现的一些问题能够被咱们建模为一个约束优化，必需完成轨迹布局，定位和避障工作。机

14、器人导航中最重要的工作是路径规划，依据移动机器人的机器人和环境信息的水平和环境信息的程度把握差别的移动轨迹规划，基本上可以分为多种。不管什么样的机器人，轨迹规划属于属于哪一类，应用什么样的规划算法， 都应该遵守下面方法；（1） 建立环境模型，即将现实世界的问题进行抽象后建立相关的模型（2） 途径搜查措施，即寻觅契合条件的途径的算法。全局轨迹布局包含环境建模和途径搜寻战略 2 个子效果，其中局域轨迹规划按世界模型表达方式的差别存在三种相比经典的环境建模措施：构型空间法、自由空间法、和栅格法等。局部轨迹规划的主要方法有：人工势场法、遗传算法、模糊逻辑算法、蚁群算法等。3 4 5 下面主要介绍各种研

15、究方法的优缺点：1 构型空间方法的基本思想是一个机器人可以减少到一个点，根据形状和大小的机器人障碍扩大。其中钻研较成熟的有：1）可视图法，此法将一切障碍物的顶点和机器人起始点及目标点用直线组合相连，机器人与障碍物之间的顶点的要求，和障碍物的每个顶点和顶点与顶点之间的连接的每一个障碍可以穿梭障碍， 即，直线是“视觉”，并采用搜索从起始点到目标点的最优方式直径一定的方法， 寻找最佳路径问题转化为从起始点到目标点的最短间隔通过视觉线。2）优化算法（如 Dijkstra法等），这种方法可以除掉一些没用用的连线以简化可视图、缩短寻觅工夫可以求得最短途径。假定机器人的尺寸大小可以不去计算，会让机器人经过障

16、碍物顶点时离障碍物太靠近。其他的缺点就是这个方法没有灵活的性能，如果机器人的开始点和目标点发生改变的化，就要重新建造麻烦可视图。62 自由空间法使用定义的开始，为广泛的圆锥状凸多边形构建简单的自由空间和自由空间表示为连通图，再经过寻找一个连通图轨迹规划应用轨迹分布。相比有点柔性这样的措施，改变的起点和终点，不构成连通图的重建，但数量是成正比的算法级和障碍的复杂性，而不是在任何情况下能够获得更短的路径。4.基于实时传感信息的含糊逻辑算法，得到规划信息通过查表，实现局部轨迹规划。这种措施克服了势场法发生的部分问题，一般用于不知道的环境下的轨迹规划。而含糊优化算法则是把约束和目的模糊化使用附属度函数

17、寻觅使多种条件达到称心的水平，这样在含糊意义下最优解的求取就成为可能。 10 11 12通过国内外的一些专家的研究，我们知道了，在建立模型这么多算法中， 每一个算法都有着本身的有点，但是它们也存在自己的缺点。所以我们需要进一步的研究，通过不同的要求，选择最准确的算法来对空中机器人（UAV）轨迹规划进行设计。我们要努力避免一切误差，将空中机器人的轨迹设计的最完美， 最准确。1.4 课题背景和研究意义空中机器人（UAV）的轨迹规划一般指在确定空中机器人（UAV）起飞位置、目标位置和飞行途中的目标任务后的一系列优化问题，根据空中机器人（UAV） 机动飞行，地理环境和威胁信息的计划来满足飞行条件下的最

18、优或次优路径。优化后的路线应能保证空中机器人（UAV）有效地避开敌方雷达的探测和攻击，并能有效地避免在飞行环境和危险的地形和其他不利因素的障碍。空中机器人（UAV）参考飞行轨迹规划也应该能够在规定的时间内及时到达目标点，当飞行或飞行任务已知的环境变化，轨迹规划系统应能而不是一个新的参考轨迹飞行轨迹的实时规划。空中机器人（UAV）轨迹规划是任务规划系统的关键组成部分,是确保空中机器人（UAV）有效作战, 其中的关键技术之一，对预期的任务圆满完成（UAV）同时，空中机器人轨迹规划是实现安全的无人机自主控制技术。空中机器人（UAV） 的迅速发展和广泛应用，空中机器人（UAV）越来越严格的技术要求对轨

19、迹规划系统,也由于轨迹规划的重要性使得轨迹规划技术成为研究热点之一。1.5 设计的要求和内容1.5.1 设计要求空中机器人（UAV）轨迹规划的核心目的就是寻找一条满足各种要求的轨迹，其中的要求条件包括隐蔽性要求,飞行任务要求及实时性要求等。(1) 隐蔽性要求安全环境保障是隐蔽的空中机器人的轨迹（UAV）在战场上的首要条件，安全，空中机器人（UAV）将尽可能降低通过空中机器人的设计（UAV）雷达截面与敌方雷达探测到的概率降低。但空中机器人（UAV）在高海拔飞行，仍然不可避免地雷达信号被敌人发现，所以隐蔽性的轨迹是满足飞行轨迹要求的关键。可以通过降低飞行高度或者使空中机器人（UAV）远离雷达范围来

20、达到隐蔽的目的。(2) 飞行任务要求在空中机器人（UAV）的任务序列中会给出空中机器人（UAV）从初始点到达目标点时间，进入目标点方向等任务要求，这就要求空中机器人（UAV）轨迹规划系统规划出在分布有静态障碍物环境下的从初始点到目标点的一条最优路径。因此轨迹长度必须小于等于预设的最大值。(3)实时性要求一方面在不断发生变化的飞行环境中的信息,另一方面空中机器人（UAV）经常需要临时更改或添加任务，当这些条件发生变化时，轨迹规划系统需要实时的飞行路径规划能力。1.5.2 设计内容针对空中机器人轨迹规划设计要求,本文重点是飞行环境建模方法的改进 和利用 A*算法对空中机器人进行导航，同时使用 Vi

21、sual C+ 对轨迹进行仿真。本文的组织结构如下:第1章:绪论。简要介绍了空中机器人（UAV）和轨迹规划，对课题所研究的背景及意义作说明。分析了当前课题国内外研究状况，几种常见的规划算法被主要介绍，最后将本文的设计要求和设计内容作了说明。第2章:空中机器人（UAV）轨迹规划总体方案和环境描述。首先介绍空中机器人（UAV）自主飞行管理系统。其次是空中机器人（UAV）轨迹环境的描述，采用 栅格化模型对环境进行建模。最后介绍了常用的几种算法，通过空中机器人（UAV） 算法的选择，如遗传算法和蚁群算法，并选择A*算法为本课题轨迹规划的算法。第3章: 基于 A*算法的空中机器人（UAV）轨迹规划与设计

22、，详细的对 A* 算法进行说明，A*算法的特点，对标准算法 A*克服不足和放弃的最佳路径，利用多个搜索缺陷的方法。第4章:空中机器人（UAV）轨迹规划仿真。这章主要介绍了如何采用 Visual C+ 编程的方法将 A*算法实现的过程。详述了算法的具体步骤，和 A*算法详细的流程图，并且介绍对其数据结构和主要函数及功能。最后呈现仿真图，以表算法之实践性。第5 章:通过研究得出结论，并且对未来展望。对本次研究作了总结，将重要结论叙述了下，同时空中机器人（UAV）轨迹规划设计与仿真是机器人研究领域的关键技术，需要长远研究，不断更新算法，以使空中机器人（UAV）实现更多广泛的要求。第 2 章 空中机器

23、人轨迹规划方案与环境描述空中机器人轨迹规划算法（UAV）系统中的一个关键技术，规划一个合理的路径考虑空气的流动性，各方面的机器人任务，地理环境，气候，环境和其他威胁的信息，对这些因素的考虑是在空中机器人自主飞行管理系统的不同模块进 行。所以，在轨迹规划算法的研究了解空中机器人是必要的（无人机）自主飞行管理系统的概念，结构，系统包括的模块，每个模块的功能。及相互之间的作用关系。通过对该体系结构的了解,了解空中机器人（UAV）轨迹规划所涉及的内容及其在空中机器人（UAV）自主飞行管理中的地位与作用,及与其它模块的关系。自主控制强调的是没有外部干预，自我决定，所以人类直接控制的不足，它涉及多种学科的

24、知识，人工智能，信息理论，自动控制，计算机科学，运筹学等， 本质上是一种智能控制，自主控制与智能自动化程度非常高控制，在未知环境中使用没有外界干预过程的控制主要是由不确定性引起的。所以挑战是自主控制在实时或近实时的系列优化问题求解未知环境。空中机器人（UAV）自主飞行管理系统需要实现多种复杂的功能，这些功能包括任务规划，图像识别，轨迹规划和跟踪，飞行控制和导航等。空中机器人系统（UAV）自主飞行管理智能递阶控制系统结构，分层结构的设计可以降低系统间干扰，提高整个系统的稳定性。2.1 空中机器人（UAV）飞行控制与管理常见的空中机器人（UAV）自主飞行管理系统主要由三层组成,包括有任务规划层、决

25、策规划层和执行规划层:（1）High level(任务规划层)，任务管理的水平，环境模型和其他功能的设置，包括任务规划是这一层的主要功能。环境模型，在这一章中详细描述。任务规划的主要功能是分解成任务包括几个小任务序列并结合中间层是决策层来完成这些任务序列。(2)Middle level(决策规划层),该层主要实现轨迹规划的功能,包含有环境感知性能和轨迹布局功能, 轨迹规划包括离线轨迹规划和实时重规划。根据接收到的信息的任务和合理的轨迹规划决策层。当轨迹规划模块接收任务信息， 该模块将生成一个链接的起始点和终止点的轨迹。当一个突发威胁的紧急情况下，实时规划模块将修改的轨迹规划，轨迹产生的信息将被

26、转移到规划层的实现。（3）Low level(执行规划层), 主要功能是根据空中机器人(UAV)轨迹规划层的决策信息处理，包括空中机器人(UAV)的控制和飞行轨迹跟踪。执行计划层将控制指令的不同阶段转向命令操作控制面的变化，飞机往往设置状态，从而控制空中机器人。简化的空中机器人（UAV）自主飞行管理系统框图如图2.1所示：图2.1 空中机器人（UAV）自主飞行管理系统框图2.2 空中机器人（UAV）轨迹环境描述空中机器人（UAV）的设计有限平面区域D的二维平面的工作空间，一个静态障碍物的分布，和位置，已知障碍物的大小。目的是使机器人由起点gbegin安全地避碰地沿一条较短路径到达终点gend。

27、为了简化问题，假设机器人，运动中的地位，障碍物的大小不改动。2.2.1 栅格法简介WEHowden 在 19 世纪 70 年代提出栅格法的，栅格（Grid）表示地图被运用了在他进行途径规划时。设环境的最大长度为 L， 宽度为W， 栅格的尺度（ 长，宽）均为 b， 则栅格数为（L b）×（W b）， 环境 Map 由栅格mapi 形成：Mapmapi , mapi0 或1, i 为整数其中mapi =0 表现为该格为自由区域， mapi= 1 表示该格为阻碍区域。栅格法是机器人规划空间网格的方法分解成一系列的价值观与两个单位的信息网络，任务空间分解为单位采纳启发式算法在安全单位路径搜索

28、。用四叉树和八叉树的工作空间的搜寻过程。一致的标准的网格使栅格空间中简单的邻接关系。给每个网格的一个常见因素，路径规划问题成为搜索最优路径在网格网络的两个网格节点的问题。2.2.2 建立轨迹的环境模型1.栅格地图设计在进行轨迹规划时，采纳栅格（grid）为基本单位表示为环境信息。栅格的大小通常与空中机器人的航行步长相适应，即机器人的飞行就可以转化为从一个齐全可行栅格移动到别的一个完全可行栅格。设机器人能自由运动的领域为 0, Ra 。依据栅格与不可行区域的交加，可将栅格分为三种：（1） 完全可行栅格，栅格内一切区域都是平安可行的。（2） 完全不可行栅格，栅格内的一切区域都不是安然可行的。（3）

29、 不完全可行栅格，栅格内的一部分区域是安全可行的，另一局部区域不是安然可行的。本文首先将不齐全可行栅格归于完全不可行栅格，这样能够防止将不完全可行栅格细分，导致整个环境栅格数量增加，从而增加搜索路径的困难。为此，先粗略搜索到次优路径后，再将不完全可行栅格还原到原工作环境中。在第一步的搜索过程中，首先将安全可行栅格表示为空白方格，完全不可行栅格表示为涂黑方格，机器人的整个活动环境如图2.2所示（图2.2表示的是将不完全可行栅格归于完全可行栅格后的整个活动环境图）。图2.2不完全可行栅格归于完全可行栅格后的整个活动环境栅格法以每个栅格为基本单元， 栅格图中每两个相邻的单元栅格是否能安全通过， 用数

30、值表示出来。两个栅格之间完全不可行时，取值为 0，完全可行时，取值为1，即可由如下公式表示：式（2-1）2.3 空中机器人（UAV）轨迹规划的算法2.3.1 空中机器人(UAV)轨迹规划常用算法空中机器人(UAV)轨迹规划，解决了环境模型的建立问题，另一个主要问题便是轨迹规划算法的选择。选择怎样的算法，对于轨迹规划至关关键。目前国内外在空中机器人(UAV)轨迹规划方面已经研究了很多种算法，这些算法总体可以概括为传统经17典算法和现代智能算法。具体分类如图2.5所示图2.5轨迹规划算法分类1. 传统经典算法：1）数学归纳法，算法简单、可以综合考虑多种与路径相关的其他要素( 路径的安全性、可执行性

31、等) 。但计算量大、计算时间长、易受部分最小值影响坠入部分最优解。适用于局部航迹规划。2） 动态归纳法，算法简单、不要求威胁场连续性、可获得全局最优解。但计算量大、随着规划空间扩大会出现组合爆炸、不易应用于三维空间、计算时间长。适用 于小范围内的多级策略航迹规划。3） 最优控制法，可将两端固定的问题简化为一端固定, 一端自由的问题,简化伴随向量求解。但对地形要求高、模型复杂、复杂地形下易出现死锁、规划时间长。适用于简单地形条件下的航迹规划。4） 导数相关，算法简单、收敛速度快、对地形要求不高。但计算量大、易陷入局部最优解、不能准确考虑威胁要素。适用于问题规模较小的航迹规划。通过上面可以知道,

32、传统的轨迹规划算法存在着共同的缺陷: 容易陷入局部最优解、计算量比较大、规划时间比较长、没有智能搜索性能等。2.现代智能算法：目前，空中机器人(UAV)轨迹规划中常用的算法主要是人工智能规划算法, 这其中包含 A*算法、遗传算法、人工神经网络算法、粒子群优化算法、蚁群算法以及模拟退火算法等。而基于这些算法的改进型或者混合型将是以后人工智能算法的发展方向, 本节主要介绍目前较为常用的遗传算法、蚁群算法和A*算法。2.3.2 遗传算法（Genetic Algorithm，GA ） 1、遗产算法的由来遗传算法（Genetic Algorithm，简称 GA）起源于对生物系统的计算机仿真研究。自上世纪

33、 40 年代，科学家不断努力寻求从生物学科学和新思想的人工系统，用于计算新方法。许多学者从进化生物学和遗传激励在现实世界的复杂适应系统的发展为计算技术研究生物进化系统的计算模型，为探索和研究的长期发展模拟进化算法。约翰遗传算法由 H.荷兰教授和学生提出了一个重要的发展方向。根据达尔文的进化论和孟德尔的遗传理论的遗传算法，摩根。根据达尔文的进化论，地球上的所有物种在漫长的进化历史，从一开始。从生物种群的低型， 逐渐成为一种复杂的简单。各种生物的生存，必须进行生存斗争，包括在同一种群内和种群间的斗争，斗争，生物与无机环境之间的斗争。随着生物个体能够生存，生存能力强，并有更多的机会产生后代；较低的生

34、存能力是消除个人的机会越来越少，或后代。，和死亡。达尔文把这个过程称为“自然选择，适者生存”。根据遗传的孟德尔和摩根的理论，遗传物质在每个细胞的密码指令包，并在染色体上基因排列的形式，每个基因有一定的特点和生物控制的特殊地位。个体对环境的适应有不同的基因组合是不一样的，通过杂交和基因突变可产生较强的环境适应性的后代。在优胜劣汰的自然选择和适应程度高的基因结构的生存保留下来，逐渐形成一种经典遗传学染色体理论，从而揭示遗传和变异的基本规律。2、遗传算法的流程遗传算法在遗传操作的进化过程是随机的，但它显示的特点是没有一个完整的搜索，它可以有效地利用历史信息来推测下一代所需的性能提高了搜索的优势。这一

35、代的进化，最终收敛到最适应环境的个体，问题的最优解。遗传算法有五个关键要素：参数编码，初始群体的设定，适应集设计和控制功能的设计参数， 遗传操作。流程如图 1 所示。图 1遗传算法基本流程对简单遗传算法的运行过程是一个典型的迭代过程，它必须完成的工作内容和基本步骤如下：1） 选择编码策略，把参数集合 X 和域转换为位串结构空间 S。2） 定义适应度函数 。3） 确定遗传战略，包含选择群体大小 n，抉择、穿插、变异措施，以及确定穿插概率 、变异概率 、等遗传参数。4） 随机初始化生成种群 P。5） 计算群体中个体位串解码后的适应度值 。6） 按照遗传策略，运用选择、交叉和变异算子作用与群体，形成

36、下一代群体。7） 判别群体功能能否满足某一目的，或许已实现预约迭代次数，不满足则前往步骤 6），或者批改遗传战略再返回步骤 6）。2.3.3 A*算法（A-star Algorithm，A*）A*算法是一种典型的启发式搜查措施，以估价函数指导搜索的进行，由该函数可获得各点的代价，求解出形态空间搜查的最短路经。A*算法是人工智能的一种典型算法，它不仅可以应用在游戏地图的最短路径上的搜索，而且可以使用在复杂环境的棋类游戏的最佳选择中。至于 A*算法的详细介绍将在后文中阐述，这里不再赘述，下面重点介绍下启发式搜索方法。启发式搜索是每个搜查黄金位置，状态空间搜索进行评价，得到最好的位置，从这个位置搜索

37、直到目标。这可以省去很多不必要的搜索路径，提高效率。在初始状态的假设定义，操作和目标状态是完全确定的，然后确定搜索空间，从而有效的搜索空间，这种技术的搜索通常需要对信息领域相关的一些具体问题的特征，这些信息被称为启发式，启发式搜索方法用启发式搜索方法。启发式搜索的基本思想是:在控制性知识中增加关于被解问题的某些特性,以便指导搜索向最有希望和最有前途的方向前进。所以,启发式搜索与不自觉搜寻不同,他原则上只需要知道问题的部分状态空间就可以求解该问题,搜索效率较高。经过使用启示信息来决议哪一个是下一步要扩充的节点,这种搜索总是选择最有希望和前途的节点作为下一个被扩展的节点,因此,把这种搜索称为有序搜

38、索。2.4 空中机器人(UAV)轨迹规划算法选择空中机器人（UAV）轨迹规划算法的选择是机器人学的关键技术，需要选取满足设计要求的算法。本文的设计要求是隐蔽性要求、飞行任务要求及实时性要求等，针对这些要求，综合考虑各种算法的优缺点，同时考虑作者自身研究条件，最后选择 A*算法作为空中机器人（UAV）轨迹规划算法。A*算法能够解决本文所述的在已知环境下寻找到一条从初始点到目标点的分布有有限个静态障碍物的轨迹。此算法简单，容易理解，且具有很多优点， 完全可以胜任本文要求的轨迹规划。故而，下文重点详述基于 A*算法的空中机器人轨迹规划设计与仿真。第 3 章 基于A*算法的空中机器人轨迹规划设计A*算

39、法是一种典型的启发式搜寻方式，以估价函数指导搜索的进行，由该函数可以获得各点的代价，求出状态空间搜索的最短路径。本文针对空中机器人在具有障碍物的空间环境中的轨迹问题，利用栅格化的环境模型，使用 A*算法进行轨迹规划。 243.1 A*算法3.1.1 基本概念因此，就把利用评估函数f(n)=g(n)+h(n)来排序节点的图搜索算法称为A算法。如果对轨迹搜索问题中的所有节点 n，存在h(n) £ h* (n) ,它表示偏于保守的估计，则 A算法一定会找到一条从起始点到达目标点的最佳路径。在A 算法中，假设采纳 h*（n）的下界h(n)作为启示函数，则该算法称为A* 算法。在h=0的情况下

40、，A*算法就成为了有序搜索算法。3.1.2 评价函数现在的评价函数，在任何节点上的函数值 f（n）可以估计从初始节点到节点 n 的成本最小成本路径，并从节点 n 的最小成本路径到目的节点的成本之和， 换句话说，f（n）是由对最小费用路径节点 n 的估计成本约束。因此，具有最小F 值的节点，与剖面线最严格约束估计。此外，下一步，如果你想扩展这个节点， 是合情合理的。把函数g*(n)定义为从已知起始节点到任意节点n 的一条最佳路径的代价, 函数 h*(n)定义为整个目的节点集合上所有从节点 n 到目标节点最小代价路径的代价,在这里,从节点n到目标节点可以取得h*(n)的随意一条途径,就是一条从节点

41、n到某个目标节点的最佳路径,关于那些齐全不能够抵达目标节点的节点 n,把从他到目标节点的路径长度定义为无穷大。接下来,定义函数f*(n),使得在一个节点 n 上,其函数值就是从初始节点到节点n的一条最佳途径的实际代价加上从节点n到某个目标节点的一条最好途径的代价的总和,用公式表示如下式（3-1）,即f * (n) = g* (n) + h* (n)式（3-1）对上式来说，函数 f *(n) 的值就是从初始节点开始，约束地通过了节点n的一条 最佳路径代价，从初始节点和节点n 两个综合起来时，上面的公式（3-1）的表达式就是式（3-2）f * (n) = h* (n)此时表示一条从初试节点到目标节

42、点，其中无约束的一条最佳路径的代价。所以，前面所述的评价函数 f (n) = g(n) + h(n) 是 f *(n) 的一个估计，其中，g(n) 是g* (n) 的一个估计，也就是说，g(n)是g* (n) 的一个估价函数，并且，他们之间满足 g(n) ³ g* (n) 。同理，也就是h(n)是h* (n) 的一个估计，也就是h* (n) 的一个估价函数。算法的效率受到如下三个重要因素的影响：（1） 被发现路径的代价；（2） 在发现路径中被用来扩张的节点数；（3） 用来计算的计算量的多少。选择恰当的启发式函数，可以使影响算法效率的综合因素达到一个合理值。对于有些实际问题，可能要扩张

43、的节点非常多，导致计算量很大，以至于在很短时间内计算困难，此时，要使影响效率的各个因素的综合达到一个合理值，不能片面要求所花费的时间少。A*算法的关键在于评价函数的定义，从找到一条最小代价的思路出发，在计算可以把评价函数值分为从初始节点到节点 n 的代价，和从节点 n 到达目标节点的代价两部分来进行计算和分析。3.2 A*算法的性质3.2.1 一致性假设 ni 是 n 任意一个子节点，如果在搜索图中，对所有的 n 都满足以下条件：h（n）- h（ ni ）c（n ，ni ） 式（3-3）且有 h(sg ) =0，其中，在上式（3-3）中，C（n， ni ）表示节点 n 到 节点 ni 的代价。

44、对于式（3-3）也可以变形为h（n）h（ ni ）+ c（n，ni ）或者h（n）- c（n，ni ）h（ ni ） 式（3-4）则称 h 满足单调性质，也可以说 h 服从一致性条件，也即随着节点深度的增加，其启发函数值是单调下降的，一直到目标节点，期间，启发函数值变为 0，被选来扩展的节点 n，满足 g (n) g * (n) 。在搜索树中，对于所 扩展的节点序列，当前节点远离初始节点时，其中，f 值的大小是单调非递减的。一致性条件对搜索算法来说非常重要，很多启发式函数都满足一致性条件。当一个启发式函数不满足一致性条件时，如果其他方面的条件是可以接受的，那么在搜索期间可以通过调整该函数使其满

45、足一致性条件。3.2.2 可用性A*算法除了具有采纳性之外，还有如下性质。,在 A*算法结束之前的任何时刻，OPEN 表中总是存在一个节点 n ，它是在从初始节点到达某一个目标节点的最佳路径上，具有 f (n, ) £ f* (s) 。在对可解的状态空间图来说，A*算法一定可以结束，且在OPEN 表中任何一个满足 f (n) £ f(s) 的节点都将被此算法选作扩展节点。由A*算法选来用于扩展的节点n，都满足性质f (n ) £ f(s) 。如果评价函数中的h部分满足单调性限制，则被算法选来扩展的节点n满足关系式g(n) = g(n) 。在搜索树中，如果存在一条从

46、初始节点到某一目标节点的路径，则 A*算法将由于找到一条最佳路径而结束，所以A*算法是可以采纳的。在以前讨论的许多搜索算法中，当没有启发信息时，即在h=0的条件下，得到的是相同代价算法，这些算法和广度优先算法都可以看作是A*算法的特殊情况。3.3 A*算法的衡量标准在求解一个问题时候，求解方法的选择是否恰当，将很大程度上影响着问题的结 果。对于解决简单的问题，一般就应选择那些简单易行或者曾经多次用来解决该类问题的方法。对于求解一些复杂的问题，我们不可以很随便的找一个方法就拿来应用，此时就需要小心的挑选和比较。一个算法运行状况和很多因素都有关系，同一个算法在速度不同的计算机上运行，执行速度相差也

47、可能很大。如果编译器不同，完成同样功能所需要的时间也不尽相同。在对算法进行比较时，一般来说很看重计算机时间和存储空间，前者相对来说 线 更关键一些，但是后者也很重要。在常规情况下，我们衡量的依据就如下面所述。判断一个算法的优劣，主要有下面几个标准：1. 准确性要求算法能够正确的执行预先规定的功能和性能要求。这是最重要的标准， 要求对问题要有正确的了解，并能正确的、无歧义的描述和利用某种语言正确的实现对算法的要求。2. 可使用性3. 可读性3.4 A*算法的不足在使用 A*路径搜索算法进行从初始节点开始到目标节点的搜索时，过逐步的向目标节点靠近，直至找到路径，在这个过程中，经过分析和研究，初步发

48、现存在着一些问题，简单来说他们是：(1) 对于障碍物少或者没有障碍物的地图来说，虽然此算法能找到一条搜索的最佳路径，但是搜索时过多的扩展了节点的数量，导致搜索效率不高，占用内存等资源比较大，以至占用了过多的时间和空间，使资源没有达到很好的利用。(2) 在轨迹搜索过程中，有时候会把最优路径舍弃了，主要是最优路径上的一些节点，由于当时还不知道这些点属于最优路径上的。这说明这个算法在对前面某些点进行扩张后，放弃了最优路径上的某些点。这种情况下，我们找到的路径就不是最佳路径。(3) 对于一些凹形和凸形的障碍物来说，由障碍物构成的地图形状复杂，对寻找最优路径造成了困难，在搜索过程中好多时候要绕开许多路，

49、导致搜索的时间消费和空间占用都非常大。为提高效率，在条件允许的情况下，有时候需要牺牲一些空间来换取时间，并且也要保证搜索到的路径成为最优路径，对那些空间要求不高但对于时间非常珍贵的情况，牺牲的空间也是值得的。第 4 章 空中机器人轨迹规划仿真A*算法作为解决空中机器人轨迹规划搜索类问题的一个主要方法,我们在对该算法进行了分析与研究的基础之上,通过有效的方法与措施对其进行了优化与改进,使其搜索的效率有了很大地提高。接下来,我们将对该算法所作的研究,通过在 Microsoft Visual C+ 6.0 开发环境中进行编程，来进行模拟与实现,以验证其有效性。4.1 算法的步骤在算法的模拟与实现过程

50、中,需要有结构 G,表示当前已经生成的显示搜索图，一张 OPEN 表,用来存放己经生成而尚未进行扩展处理的节点，一张 CLOSED 表,用来存放已经生成且进行过处理的节点。其模拟与实现的具体步骤如下:(l)建立一个只有初始节点 s 组成的搜索图 G，把初始节点 s 送入 OPEN 表,OPEN=(s)，CLOSED=()。此时,CLOSED 表为空表,也就可以表示为f(s)=0+h(s)。(2) 重复下列过程,直至找到目标节点为止。如果 OPEN 表为空表,也就是OPEN=(),则退出,即宣告失败,结束。(3) 选取 OPEN 表中未设置过的具有最小 f 值的节点为最佳节点记做 n, 并把它从

51、 OPEN 表中取出,放入到 CLOSED 表中。(4) 如果最佳节点是一个目标节点,也就是说到达了目标终点,则搜索成功求得一个解,算法结束,通过追踪主链的指针,给出初始节点到这个最佳节点 n 的路径。(5) 如果最佳节点 n 不是目标节点,则扩展此节点,生成 n 的所有不是他的先辈节点的后继节点集 M=m,把 m 作为 n 的后继节点添加到搜索图 G中。(6) 如果 m 既没有在 OPEN 中出现,也没有在 CLOSED 表中出现过,则把m 添加到 OPEN 表中。(7) 如果 m 在 OPEN 表中出现了重复节点 k,且 g(m)<g(k),则从 OPEN 表中移除节点 k，把节点

52、m 添加到 OPEN 表中。(8) 如果后继节点 m 不在 OPEN 表中,则看他是否在 CLOSED 表中,若后继节点 m 在CLOSED 表中有重复节点 k,并且有 g(m)<g(k),则就要进行如下地操作:a. 要把 CLOSED 表中的节点 k 改为节点 m；b. 按照后继元素,修改 k 的所有在 OPEN 表和 CLOSED 表中的后继 g、f 的值。(9) 按照 f 值从小到大的次序,对 OPEN 表中的节点重新排序。(10)跳转到第(2)步,循环。4.2 算法的流程在算法具体模拟与实现过程中,对于 OPEN 表和 CLOSED 表来说,他们中的节点除含有其他的状态描述外,还

53、包含有该节点的代价估计值 g 和 f,后继元素,以及一个主链的前趋指针,指明该节点在通向初始节点的最佳通路上的父节点，有了主链,我们就可以在找到目标节点后,很容易的只要沿着主链的指针追踪到初始节点,就可以获得整个搜索求解的路径。具体模拟如图 4.1。图4.1 仿真流程图4.3 空中机器人（UAV）轨迹规划仿真4.3.1 数据结构在仿真过程中，由于篇幅有限，主要介绍定义和声明的主要参数、变量或者函数的形式结构。1. 在Head Files的AstarNode.h中class CAstarNode : public tagPOINT/定义节点public:CAstarNode();explicit

54、 CAstarNode(const CPoint& pt); virtual CAstarNode();CAstarNode& operator=(const CAstarNode& rhs); BOOL operator=(const CAstarNode& rhs); CAstarNode *Clone();double DistanceTo(CAstarNode *rhs);public:doublef;/定义fdoubleg;/定义gdoubleh;/定义h，即f（n）=g(n)+h(n)CAstarNode *parent;/父节点;其中,g,h 分别

55、表示评价函数中从初始节点到此节点之间的代价,和从此节点到达目标节点之间的代价两个部分。*pParent表示指向此节点的父节点。2. 在Head Files的AstarDemoDoc.h 中/ Attributes public:int m_nMapwidth/定义地图宽度int m_nMapHeight/定义地图高度unsigned char m_cMapMAP_HEIGHTMAP_WIDTH; / 保存点的数组void UpdateStartBlock(int x, int y);/更新起始点void UpdateEndBlock(int x, int y);/更新终止点void UpdateBarrierBlock(int x, int y, BOOL bAdd = TRUE);/更新障碍物点void AddPathBlock(int x, int y);/增加障碍物点void CleanPathBlocks();/清除障碍物点BOOL GetStartPoint(CPoint&