路径规划（精彩4篇）

【导言】此例“路径规划（精彩4篇）”的范文资料由阿拉题库网友为您分享整理，以供您学习参考之用，希望这篇资料对您有所帮助，喜欢就复制下载支持吧！

路径规划【第一篇】

关键词模糊控制 双足机器人 路径规划 超声波传感器

机器人路径规划一直是机器人研究领域的热点问题。路径规划是在有障碍物的环境下找到一条由给定点到达目标点的最优路径，使机器人能够绕过障碍物，在不与障碍物相碰撞的情况下到达目标点。机器人在移动过程中必须安全无障碍的绕过所有障碍物，寻求一条安全的运动轨线判断并自动躲避障碍物顺利抵达目的地并且尽可能使所走路径最短。目前，常用的局部路径规划算法有势场法、A* 算法、栅格法及模糊算法。其中模糊算法有效的减小了对环境信息的依赖性，具有良好的鲁棒性和实效性。

本文主要采用模糊算法解决直立行走机器人在静态未知环境中的局部最优路径规划问题，并通过MATLAB仿真实验验证了模糊算法的有效性和可行性。

1 超声波传感器

双足直立机器人实现避障行走，首先需要对外界环境进行感知，探测到障碍物的方位。而超声波作为一种距离探测传感器，以其质量可靠，成本低廉为特点，在机器人测距中得到了广泛应用。基于双足直立机器人在速度上有限制的前提条件，采用周期扫描模式进行距离检测是最可行的方案，即将机器人的视野范围均分为若干份，记录每个视角检测到障碍物的距离，进而获得完整的外界环境的知识。同时为了消除机器人在运动过程中的抖动对测距的影响，为测距模块搭建了云台系统，使测距模块在运动过程中始终保持水平状态。

2 模糊控制器设计

确定模糊控制器的输入变量和输出变量

模糊控制器的输入是超声波采集的距离信号和双足机器人与目的地方向的夹角信息，输出是双足机器人的转动角度。双足机器人的构成包括支架、舵机、目标传感器、超声波传感器等部分。超声波采集的距离信息是机器人当前位置与障碍物的距离，超声波在机器人前进方向的180度范围内采集与障碍物的距离信息，取其中最左、最右及正前方的距离信息为三个输入变量，定义最左侧距离为DL、正前方距离为DC、最右侧距离为DR。通过目标传感器，确定双足机器人当前位置与目的地方向的夹角D0为角度输入变量。利用这些条件推理出输出变量OUT，即双足机器人的转动角度，如图1所示。

输入变量及输出变量的模糊化

定义距离输入变量的模糊语言为DL={Near，Far}， DC={Near，Far}，DR={Near，Far}；角度输入变量C0的论域为C0={LB，LM，LS，ZO，RS，RM，RB}；输出变量OUT的论域为OUT={OLB，OLM，OLS，OZ，ORS，ORM，ORB}。各个变量的隶属度函数图形为对称三角形且模糊分割完全对称，DL、DR、DC、 C0及OUT的隶属度函数图形如图2中（a）-（e）所示。

确立模糊控制规则

模糊控制规则（控制策略）的选择是模糊控制器设计非常关键的一步。它是基于手动控制策略，是操作者经验和技术知识的集合 。模糊控制规则实际上是一系列模糊条件语句的集合，反映了输入量与输出量的关系。按照双足机器人的实际控制进行模糊逻辑推理，确定了四个输入信号，一个输出信号，构成一个多输入单输出的模糊控制系统。

双足机器人在行进过程中，根据与障碍物的距离信息及与目的地的夹角信息进行决策推理出转动角度，从而实现最佳的路径规划。当采集到障碍物信息时，双足机器人将转动一定角度，改变行进轨迹实现有效避障的功能。机器人行进规则如下：

（1）当目标点位于障碍物左（右） 侧时，则机器人左（右）转；

（2）当目标点在机器人正前方且障碍物距离机器人很近时，则机器人需根据它的左侧和右侧的障碍物信息来决定左转还是右转；

（3）当左侧障碍物距离大于右侧障碍物距离时， 机器人选择向左转，反之向右转。

根据确定的输入输出变量的论域，采用模糊规则的一般形式If（条件）then（结果）进行描述。模糊规则如表1所示。

模糊决策

模糊决策（模糊推理）是根据模糊逻辑的关系及推理规则来进行的 。根据模糊规则推出输出量的隶属度函数。下面将通过简单举例来说明模糊控制器的原理。

以双足机器人在DL=0 ，DC=，DR=3，C0=8的状态为例，该状态对应模糊表中的第11、12、18条规则，由此状态下的模糊规则进行推理合成，得到输出量的隶属度函数。

第11、12、18条规则推理结果及合成隶属度函数结果如图3中（a）-（d）所示。

解模糊

经模糊推理得到的是一个模糊集合 。通过解模糊得到精确值，确定实际输出对双足机器人进行转角控制。MATLAB 提供5种解模糊方法：面积重心法、面积等分法、平均最大隶属度法、最大隶属度取小法和最大隶属度取大法 。本文模糊控制器采用面积重心法进行解模糊，将模糊输出量清晰化，得到精确值来控制双足机器人转动角度。

3 Matlab实验仿真

在Matlab中进行双足机器人路径规划仿真实验，实验中圆形障碍物的半径和位置随机设置，起点设定为原点，终点的位置任意设置， 进行路径规划的同时描绘出机器人的运动轨迹，仿真实验可以在任意环境下检验算法的正确性和可靠性。实验结果如图4所示。

由图4可知（a）图起点为（0，0），目标点为（500，550）；（b）图起点为（0，0），目标点为（300，350）。改变目标点位置，障碍物随机设定，机器人均可实时躲避障碍物，并规划出最短路径，验证了利用模糊算法进行双足机器人路径规划的有效性和可行性。

4 小结

本文介绍了基于模糊控制算法的双足机器人路径规划方法，系统的描述了模糊规则控制器的建立，利用MATLAB进行了仿真实验，实验结果表明模糊算法可以有效地减小双足机器人在路径规划中对于环境信息的依赖性，保证了实时性并提高了双足机器人路径规划的精确度。

参考文献

[1]曹宇杰，邓本再，詹一佳。基于模糊神经网络的RoboCup足球机器人局部路径规划方法研究[J].电子设计工程，2015（23）：141-144.

[2] 李庆春，高军伟，谢广明。基于模糊控制的仿生机器鱼避障算法[J].兵工自动化，2011，30（12）：65-69.

[3]孙大勇，苏庆宇。井下机器人路径规划中的模糊逻辑控制算法[J].电气技术， 2007（3）：47-49.

[4]霍迎辉，张连明。一种移动机器人的路径规划算法[J].自动化技术与应用，2003，22（5）：8-10.

[5]王妹婷，陆柳延，齐永锋，等。基于模糊算法的水下机器人路径规划研究[J].机床与液压，2014（3）.

[6]张营，鲁守银。基于模糊控制算法的变电站巡检机器人路径规划[J].制造业自动化，2015（11）：53-55.

[7]郝宗波，洪炳熔。未知环境下基于传感器的移动机器人路径规划[J].电子学报，2006，34（5）：953-956.

[8]刘丽萍。硒砂瓜温室种植模糊控制系统设计[J].电子设计工程，2012，（20）：62-64.

[9]高扬，孙树栋，赫东锋。部分未知环境中移动机器人动态路径规划方法[J].控制与决策，2010，25（12）：1886-1889.

[10]姚毅，陈光建，贾金玲。基于模糊神经网络算法的机器人路径规划研究[J].四川理工学院学报：自然科学版，2014， 27（6）：30-33.

[11]柳长安，鄢小虎，刘春阳，等。基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报，2011，28（5）：1220-1224.

[12]黄大志，张元良，陈劲松。基于模糊控制的自主寻迹机器人研究[J].机床与液压，2012，40（9）：35-37.

[13]朱兴柯，叶飞，李斌，等。变电站巡检机器人运动控制系统研究[J].现代制造， 2014（30）：122-124.

[14]陈卫东，朱奇光。基于模糊算法的移动机器人路径规划[J].电子学报， 2011（4）：971-974.

[15]肖瑛，董玉华。一种级联混合小波神经网络盲均衡算法[J].信息与控制，2009， 38（4）：479-483.

作者简介

鲁红权（1994-），男，河北省唐山市人。现为华北理工大学学生。研究方向为智能机器人控制。

路径规划【第二篇】

关键词路径规划；电子地图；应用

所谓电子地图是一项结合计算机制图以及数据库处理和信息系统等学科为一体的图形表现形式。在现代社会中，电子地图在各个行业中应用广泛如在车载导航系统中，它已成为路径规划中一项较为重要的技术。但有关电子地图的详细应用主要在快速生成卫星影像和航空相片以及行数据的记录和新数据的派生方面。存在的问题是其技术的应用还不够广泛和深入。所以，本文结合实例对电子地图中的数据特点以及路径算法和算法的改进进行分析，同时对路径规划中电子地图的应用进行探讨。

1.实例应用

在计算机的相关软件的运行环境下，用VisualC++开发某市实验用地图上提取的300个道路所用点，同时添加附加信息，实施路径规划。在地图上制定路径的起始点和终止点之后，电子地图可在很短的时间内确定最优化的路径，同时该路径的各种辅助设备能够满足实际车载和各种应急需求。

2.电子地图的数据特征与路径算法

数据特征

电子地图的数据特征是按照一定图层进行叠加的，在电子地图中的各种点、线、面等的集合就是图层。在电子地图中的数据分为两种：（1）空间数据。它主要是对空间对象的几何特征、位置关系以及拓扑关系进行存放。（2）属性数据。主要是对空间对象的类别、名称以及特征等进行确定。在本文所引用的Shape File中，属性数据主要以dbf的形式储存于数据库中，相对的空间数据则主要以Shape File所固有的格式进行数据的储存。这两种数据通过一定的形式联系在一起。电子地图中，将城市的道路网建设成一个图层，将其命名为道路网，同时在地图上实施路径规划，要对道路进行操作，那么就不涉及其它图层。

电子地图的路径算法

在电子地图的路径规划中，路径算法是重要的工作过程之一。现在电子地图中最长用的算法是启发式搜索算法，其主要的模型为f（x） =g（x）+h（x）.（1）式中：g（x）表示从起点到搜索点的实际花费；h（x）表示从起点到终点的预估花费，称为启发函数；f（x）表是总花费。在采用启发模型之后，可以对驱动模型进行改进：（1）在每次新生成的节点展开之前，要对显示的同一位置两个节点的花费进行比较，在新生成节点大于已生成节点的前提下，可放弃已生成节点，反之用原节点。（2）将最小距离作为搜索信息，其花费的现实随节点的开展而增加。（3）在节点的数量增加后，综合代价增加，在每次新生成的节点的花费大于原来节点的情形下，可将新生成的节点淘汰用原来的路径。

3.路径规划中电子地图的应用

在路径规划过程中，电子地图重新定义了地图在人们心中的形象。在电子地图的帮助下，可以将现成的路径规划中出现的各种要素进行不同形式的组合最后连接成新的地图；同时交通部门可以根据电子地图在路径规划中的应用，对各种交通情况诸如交通事故、天气变化、不同路段的情况进行不同程度的监管；此外，路径规划中电子地图的使用为各种市民和公民进出入不同的城市提供便捷的服务，可以在现有的地址、地址范围和地理位置以及道路的交叉口等进行准确的定位，帮助人们在不熟悉路径以及路况的情况下正确的选择道路。

起终点问题

在实际的生活过程中，电子地图上的起终点并不能代表实际路线中的出发点和结束点。在我们的日常生活中较为常见的是起点和终点都位于某一个路段的中间部分，在此时，必须将路段的出发点作为起点，目的地作为终点，在电子地图中输入该城市的行政规划图，通过电子地图对该路径数据的处理和分析，得出最佳路径区划图。

最优路径模型的确立

电子地图在路径规划中的应用中所要解决的最优路径问题并不仅仅指最短的路途。它还包括利用电子地图在最短时间和最小花费内寻找到最合适的通向目的地的路径或者在电子地图的帮助下，将这几个问题全部综合在一起，最后使问题得到解决。同时在电子地图对路径的道路级别、人流量的大小以及转弯限制等做出详细的判断之后，确定最佳的路径模式。此时可将启发式模型中的g（x）进行一定程度的修改：g（x）=∑aijLij+∑bmnTmn。在该式中，Lij表示的是i和j之间的路径长度；其中aij表示的是相应的权值，这个参数与道路的级别和流量有关；Tmn表示的是从路段m到路段n之间所需要的花费（如时间等）；与之相应的bmn代表的是穿越的权值。若在该路段处禁止转弯则可将其设置为常数，g（x）则表示从起点到所要到达的地点之间的花费。在电子地图启用最佳模型的情况下，进行路径的选择。

确立加权模型

电子地图的工作过程中如何利用启发式算法进行信息的启发也是关键工作之一，加权函数的常用表达形式是f（x）=λ1g（x）+λ2h（x），λ1+λ2=1 λ1>0，λ2>0。在该式中主要的调节系数是λ1和λ2。在λ1>λ2表示搜索过程准备好；在λ2>λ1时表示启发开始，搜索将沿着最佳路线进行搜索，这时搜索的速度较快，有利于降低完备性。在确定加权模型的情况下，电子地图可就本车中的车载以及前面的路线情况进行分析，最后计算出加权函数，得出行车的最佳路线，最终可帮助人们很快的实现快速到达的目的。

路径规划【第三篇】

关键词：医药物流遗传算法路径规划旅行商问题

中图分类号：TP301文献标识码：A文章编号：1009-3044(2010)11-2717-02

医药物流是指医药器械从医药配送中心分发、配送到各个医院和医疗中心的过程，甚至包括通过医院到达消费者(患者)手中的过程，其中所产生的物流成本是医药器械成本的重要组成部分。降低医药运输成本是减少患者医疗负担的重要途径之一。而药物配送实际上就是旅行商问题[1]。遗传算法作为一种求解问题的高效并行全局搜索方法，成为目前解决NP完全问题的较为有效的方法之一。

1 旅行商问题与遗传算法

旅行商问题原理

旅行商问题(Traveling Saleman Problem,TSP)是VRP[2]的特例，已证明TSP问题是NP难题。旅行商问题(TSP)又译为旅行推销员问题、货郎担问题，简称为TSP问题。TSP问题可描述为：给定一组n个城市和它们两两之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次而且总的旅行路径最短。TSP问题的描述很简单，简言之就是寻找一条最短的遍历n个城市的路径，或者说搜索整数子集X={1,2,…,n}(X中的元素表示对n个城市的编号)的一个排列π(X)={v1,v2,…,vn},使取最小值。式中的d(vi,vi+1)表示城市vi到城市vi+1的距离。

遗传算法基本原理与描述

算法原理

遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法，由美国教授提出，其主要内容是种群搜索策略和种群中个体之间的信息交换，搜索不依赖于梯度信息。该算法是一种全局搜索算法，尤其适用于传统搜索算法难于解决的复杂和非线性问题。

算法描述

该算法包括以下6个基本要素：

1) 编码：遗传算法不能直接处理解空间的数据，必须通过编码将它们表示成基因型串数据。常对参数采用二进制编码，编码当作一条染色体，编码前应先量化[3]。

2) 生成初始种群：初始种群的个体通过随机方法产生，且对应研究问题的一个解。

3) 评估适应度：遗传算法在搜索过程中用适应度来评估个体的优劣，并把它作为遗传操作的依据。适应度函数常取非负数，且适应度增大的方向与目标函数的优化方向一致。

4) 选择：根据适者生存的选择原理，从当前种群中选择生命力强的个体(即适应度高的个体),产生新的种群。适应度越高的个体，被选择的机会就越大，但并不意味着适应度高的个体一定会被选择[4]。

5) 交叉：将选择出的个体存入配对库，用随机的方法进行配对，以产生新一代的个体。

6) 变异：在交叉过程中可能丢失一些重要的遗传信息(特定位置的0或1)1必须引入适度的变异，即按一定的概率改变染色体基因位。

2 优化路径遗传算法的构造

针对优化物流配送路径的特点，本文构造了求解该问题的遗传算法。

初始种群的生成与编码方法的选定

随机生成规模为N的初始种群。采用巡回旅行路线所经过的各个城市的顺序排，列来表示各个个体的编码串，这是TSP问题最自然的一种个体编码方式。例如对于一个10个城市的TSP:2-5-3-4-7-1-6-8-9(可简单表示为[253471698]),表示从城市2出发依次经过城市5,3,4,7,1,6,8,9,然后返回城市2的一条路径。这种编码方式满足TSP问题的约束条件，保证了每个城市经过且只经过一次，在任何一个城市子集中不形成回路[5]。

适应度评估

对于某条染色体，设其对应的配送路径方案的不可行路径数为Ni(Ni=0表示该个体对应一个可行解),其目标函数7值为Td,则该个体的适应度可用下式表示：,式中α为对每条不可行路径的惩罚权重，可根据目标函数的取值范围取一个相对较大的正数(α值太小则会影响适应度的比较)。

遗传操作

选择操作

选择将使适应度较大个体有较大的存在机会，而适应度较小的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制，令Σfi表示群体的适应度值之总和，fi表示种群中第i个染色体的适应度值，它产生后代的能力正好为其适应度值所占份额fi/Σfi。作为其被选中的概率Psi。这方法既可保证最优个体生存至下一代，又能保证适应度较大的个体以较大的机会进入下一代。

杂交操作

采用顺序编码法后，若用简单的一点杂交或多点杂交，必然会导致未能完全遍历所有城市的非法路径。如城市9的TSP问题的两个父路径为：1 2 3 4 |5 6 7 8 9; 9 8 7 6 |5 4 3 2 1,若采取一点杂交，杂交点随机选为4,则杂交产生的两个后代为：9 8 7 6 |5 6 7 8 9;1 2 3 4 |5 4 3 2 1,显然，这两个子路径均未能遍历所有9个城市都违反了TSP问题的约束条件，为解决这一问题，既要进行杂交操作，又要满足约束条件，就必须对杂交操作进行修正[6]。关于路径表示的常用的几种修正的杂交操作方法为：

1) 部分映射杂交(PMX, partially-mapped cross-over)。

在PMX操作中，先随机地在父体中选取两杂交点，并交换相应段。再根据段内的城市确定部分映射。在每父体中先填入无冲突的城市，而对有冲突的城市分别执行这些部分映射直到填入无冲突，则获得杂交后的两后代。例如，两父体A1、A2为('|'标记截断点) A1=(2 6 4 |7 3 5 8 |9 1), A2=(4 5 2 |1 8 7 6 |9 3)。则由交换段确定的部分映射为：7-1,3-8,5-7,8-6,先交换相应的段得B1=(### |1 8 7 6|##),B2=(### |7 3 5 8 |##)。此处'#'表示城市待定。再从各自的父体中填入无冲突的城市得B1=(2#4 |1 8 7 6 |9#),B2=(4#2 |7 3 5 8 |9#)。个体B1第一个'# '处原处为6,映射到8后仍有冲突，再将8映到3填入。第二个'#'处原处为1,映射到7后仍有冲突，再将7映到5填入。类似地求得B2。于是两后代为B1=(2 3 4 |1 8 7 6 |9 5), B2=(4 1 2 |7 3 5 8 |9 6)。这样，子代仍是遍历的，但每个子代的次序部分地由其父代确定。

2) 次序杂交(OX, order crossover)。

次序杂交的操作与部分映射杂交的操作非常类似。也是首先随机地在父体中选择两杂交点，再交换杂交段，其它位置根据保持父体中城市的相对次序来确定。例如，设两父体及杂交点仍为前述的A1和A2, A1=(2 6 4 |7 3 5 8 |9 1), A2=(4 5 2 |1 8 7 6 |9 3)。交换杂交段于是仍有B1=(### |1 8 7 6 |##),B2=(### |7 3 5 8 |##)。从B1的第二个杂交点开始，将路径依原次序排列，即： 9-1-2-6-4-7-3-5-8去除杂交段中的城市，得子路径9-2-4-3-5。依次顺序从第二个杂点开始填入得B1=(4 3 5 |1 8 7 6 |9 2),类似地有B2=(2 1 6 |7 3 5 8 |9 4),虽然， PMX法与OX法非常类似，但它们处理相似特性的手段却不同。PMX法趋向于所期望的绝对城市位置。本算法采用此方法交杂交。

3) 循环杂交(CX, cycle crossover)

循环杂交将另一父体作为参照以对当前父体中的城市进行重组。先与另一父体实现一个循环链，并将对应的城市填入相应的位置。循环组成后，再将另一父体的城市填入相同的位置。例如，仍考虑前两个父体路径A1=(2 6 4 7 3 5 8 9 1), A2=(4 5 2 1 8 7 6 9 3)。先从A1中取第1个城市作为B1的起始点，于是B1=(2########),由于后代中第一个城市都必须从父体相同位置的城市中选取，于是根据循环原则，2对应于A2中的城市4,而在A1中位于第3位，所以应有B1=(2#4######),又A1中城市4对应于A2中的2,于是组成了一个环。再将A2中剩余的城市填入对应的相同位置得到B1=(2 5 4 1 8 7 6 9 3),类似地可得到B2=(4 6 2 7 3 5 8 9 1),由此可见，循环杂交保持其父体串中城市所处的绝对位置。

3 算法实现和结果

下面对某市一医药公司的销售点的物流配送路径规划用遗传算法进行优化。该公司有56处销售点，通过路径规划希望找出最优路径以节省运输成本。

运行参数设计

本实验采用n城市的遍历顺序编码法，适应度函数取总长度Td的倒数(无惩罚函数)。选择机制是保留M个较优个体，在每一代运算中，个体被选中的概率与其在群体中的相对适应度成正比。杂交操作采用OX(次序杂交)法。为使算法尽快地收敛，在经过杂交变异操作后，增加了局部优化过程，提高个体对环境的适应。群体规模取56,交叉概率和变异概率分别取和, 最大迭代数2000。

实验结果

运行环境：操作系统Microsoft Windows XP;仿真软件：MierosoftVisualC++。

在实验计算中采用以上设定参数对该公司配送路径问题求解，所得到的优配送化路径最优长度为862,用时126秒，迭代次数1528。得到的路径线路如图1所示。

4 结论

在此也可以看到，运用遗传算法解决实际问题，算法是使用参数的编码集，而不是参数本身，参数的选择十分方便；遗传算法与其他计算机算法不同，相比之下，它比较具有随机性而不是稳定性，遗传算法是在点群中，而不是在一个单点寻优。因此利用遗传算法解决实际问题需要选取大量数据，通过多次实验的数据分析不断改进算法和设置参数来求得更优的结果。用遗传算法求解组合优化问题具有巨大的优越性[7]。非常有助于物流企业根据自己的实际情况科学、有效地制定物流决策，降低风险，降低成本，提高经济效益和自身的竞争力。

参考文献：

[1] 田贵超，黎明。旅行商问题(TSP)的几种求解方法[J].计算机仿真，2006,23(8):153-157.

[2] Holland J in natural and artificial systems[M].Ann Arbor,Ml:The University Michigan Press,1975.

[3] 余有明，刘玉树。遗传算法的编码理论与应用[J].计算机工程与应用，2006,42(3):86-89.

[4] 陈国良，王煦法，庄镇泉，等。遗传算法及其应用[M].北京：人民邮电出版社，1996.

[5] 唐坤。车辆路径问题中的遗传算法设计[J].东北大学学报：自然科学版，2002,28(1):66-70.

路径规划【第四篇】

关键词海军平台；自动路径；规划算法

1.引言

开发适用于海军平台的自动路径规划算法的目的是寻找通过给定区域并能避开所有障碍物的一条最佳路径。路径中的航路点序列来自之前扫描发现的点集。目前算法是针对二维航路点规划设计的，同时也考虑了海区的深度。

算法的边界条件定义如下：在开始计算时先获取自身和所有已知目标的真实位置，假定计算过程中这些目标的位置保持不变。因为整过计算过程仅几秒钟，这样做是可行的。在这短短的计算时间内，位置的变化量可以忽略。本文研究的算法的一个约束是最大计算时间不能超过20 s。其目的是为了适应多种水下作战系统。

2.算法实现

算法分为两大重要部分，它们是程序内独立的两个模块，这样保证了程序的可重用性和可维护性。

第一个模块为海军平台生成一个图，该图含有平台周围区域的地理数据和区域内障碍物的数据。这地理数据是从国际标准电子海图（ECDIS图型）提取的，并处理成数字地形模型。该过程是由剖面评算用电子海图分析器ESCAPE完成的。该程序从海图中获取给定区域的深度数据后生成光栅格式的地形图，如图1所示。光栅中的每一点表示一个深度值，因此整个区域都由深度值来描述。

图1 海图区域（左）转换为地形模型后的效果图（右）

这样的地形模型是生成图的基础。这些光栅点表示图的节点和边。节点为图的接合点，一条边连接两个接合点。边可以赋予权重以表示从起始节点到目标节点之间的距离，如图2所示。

节点 边 权重边

图2 描述节点和边的符号

图3 用图表说明地形模型

图4 对角线边

当地形模型转为图后，一个光栅点就对应一个节点，光栅点的深度值就表示从该点到相应节点的边的加权值，如图3所示。

图3上除了按沿直角运动外，还可以沿对角线运动。依照不同的角度（由两节点之间x和y的差值来决定），路径长度不同，因此边的权重也不同。当角度为45度时，目标节点的深1度值需要乘上，如图4所示。

为了寻找一条能避开岛屿等障碍物的路径，程序必须能确定是否达到了某一最小深度值。因此图上所有深度值都与最小深度比较。如果某一节点的深度比最小深度还深，该深度值将被定义为一个给定的值，比如1000，否则设置为1。这种区别对于路径规划算法来说是必要的。

除了（船或飞机）残骸等地理障碍物以外，石油平台和其他船只也需要一起考虑。因此在每个障碍物的周围定义一个危险区域。危险区域内的节点深度值都设置为1000。如果程序用于计算鱼雷射击诸元，目标船的探测范围也必须认为是障碍物。这种区域的深度值是可变的以便将探测距离定义为“可穿越”的障碍物。

图生成后就可以开始寻找从起点到目标点的最优路径，这个功能由第二个程序模块完成。根据给定的地理起始节点和目标节点位置以及地形模型的地理坐标，就可以用A*算法[2]计算最优路径。该算法来源于导航和机器人领域，在图格式中应用得很好。

算法原理如下：

算法首先建立“Open_List”和“Close_List”两张空列表。Open_List存储所有进入考虑视野但尚未处理的节点，一开始它只存储了起始节点。两个列表中的节点有三个数据域，其中d表示当前节点与起始点的距离，g表示与目标节点的估算距离，k表示其前驱节点的序号。对于起始节点s，定义d[s]=0和g[s]=0;对于其他节点，d和g的初始值为无穷大。所有节点的前驱节点为空。Close_List初始化为空列表。

算法依次考虑Open_List列表中d+g为最小的点。在第一步，该最小点就是起始点本身。首先把起始节点从Open_List列表删除后添加到Close_List列表。然后把起始节点的所有相邻节点加入到Open_List列表，对每一个节点计算到距离d和对应边权重值之和，然后在不考虑边权重的情况下估算到目标点的距离g。新得出来的值与邻节点对应值相比较，如果新值小，那么将用新的d和g代替原来的对应值，并把当前节点存储为邻节点的前驱节点。

当目标节点被添加到Close_List列表，算法结束。这时最佳的路径就可以从目标节点根据前驱节点从目标节点回溯到起始节点。

当最佳路径决定后，需要将其简化为航路点列表，因此对于最佳路径上的每一个节点，如果节点改变了路径方向就将其加入到航路点序列，这样就将所有节点转换为实际的地理位置。

若想定复杂，计算最佳路径的时间可能超过20秒。计算机系统的性能也会影响计算时间。为了满足时间约束，A*算法能加速，不足的是会降低规划路径的质量。在距离估算项乘以一个常数因子，计算速度就会增加，因子越大，计算速度越快。

3.测试结果

开发的算法进行了一系列测试。针对不同的想定，在德国Bight平台上已经完成功能等测试。目的是规划出鱼雷从我方船只到目标船只（用深灰色的圆做标记）的航行轨迹。图5提供了其中两种想定。黑色区域代表深度值在最小深度之下，被定义为威胁区域。灰色区域表示深度在我船深度之下，需要鱼雷改变航行深度。白色区域表示水深合适。圆的深灰色地区表示目标船的探测范围，红色线是计算得出的路径。

图5 German Bight试验结果

除了几个一般功能测试外，也对一些极端情形进行了测试。图6显示了从迷宫左下角出发到迷宫中心的路径，在这个测试中没有考虑时间限制。

图6 极端情况下的试验结果

此外还分析了A*算法的加速效果，在评估中用了几个不同的因子，如图7和图8所示。从图中可以明显看出，随着因子的增大，路径质量不断下降。因子从增加到30时计算时间从减少到。经过几个系列测试分析后，选择作为算法的加速因子，这一因子在不明显影响计算路径的质量的前提下大大缩短了计算时间。若计算时间超过给定值，程序会自动增加因子的大小。

图7 因子从到的加速测试

图8 因子从到的加速测试

4.结束语

程序的实现和测试都取得成功，它能计算出两个地理位置之间的最佳路径并能避开所有障碍物。

在绝大多数的实际想定中，计算最佳路径和相应的航路点列表的时间小于3s。就是对于军事应用，这一时间也是很理想了，因为手工计算要慢得多。在一些特例中，最佳路径的质量有所差别。加速因子取值为时，A*算法在计算的时间和路径质量方面达到较好的平衡。但是因子依赖不同想定和图，在有些想定和图中，算法会扩展很多不必要的节点。因子取值越大，路径的质量差别越明显，如图7和图8所示。

在所有测试中，给定的20s时间约束存在2%的误差，若不存在路径，就将作为最大计算时间。这是A*算法中止执行的标准，如果计算时间超过这个值就认为不存在路径。A*算法操作的时间限制为20s，过了这个值就可以中止执行算法操作了。依赖于计算机系统性能的时间认为与A*算法没有关系。

程序在应用于海军平台前，还需要做一些修改，如对程序进行扩展以改进与海图的接口。根据路径质量要求，可以增加相应的曲线平滑算法，以尽量减少确定的路径与最优路径的差异。

参考文献