路径规划范文1
【关键词】移动机器人 最优路径规划 栅格法 A*算法
自从有移动机器人这一概念以后，*成为长期以来研究的最热门的内容之一。移动机器人可研究的领域相对较多，其关键技术有传感器信息结合、创建地图、定位导航、路径规划等。其中核心技术之一是路径规划技术，从起始点到终点，快速在环境地图中找到最短或最佳的无碰撞路径，这是路径规划的主要任务。本文是以“探索者-1”移动机器人作为研究平台。它由多个CPU控制，通过扫描式超声波传感器探测周边环境。当机器人接收到超声障碍信息后，可生成栅格环境地图，并基于迷宫八方向搜索的思想找到最佳路径。
1 机器人路径规划环境模型建立
在有障碍的环境中，移动机器人根据传感器发出的信息，生成环境地图，才可以实现路径规划以及导航，而栅格地图、拓展地图、几何三维特征地图是移动机器人生成的环境地图的三种表示方法。当移动机器人在获得信息时，会在一定程度上存在较多的不确定性，这是由传感器差异造成的。由于获得的信息不确定导致处理数据方法也不确定。解决这一问题，概率法，灰色理论，模糊理论等起到一定的作用。
1.1 栅格地图的创建
在栅格地图模型中，移动机器人所接收的每个栅格的信息直接与地图中的每个区域相匹配，这样移动机器人就可以根据栅格地图进行定位甚至导航。
“探索者-1”得到环境障碍信息主要途径依托于扫描式超声传感器，但是这种传感器具有盲区、多次反射等缺陷，所以超声信息存在很大的不确定性。因此可采用灰色系统理论来创建完善的栅格地图模型。
1.2 栅格地图创建实验结果
以“探索者-1”移动机器人作为实验对象进行实验，实验环境和实验结果如图1所示。
实验结果：采用栅格法，有一定的辨别真伪能力，能够有准备地描绘所需要的环境地图。
2 A*路径规划算法与传统算法的比较优势
传统算法生成的相邻子节点的作用是相同的，且不分先后顺序。如果不利用优先级的子节点生成策略，会产生许多问题，比如没有考虑机器人的宽度，而生成越过障碍物顶点栅格顶格的路径规划。A*路径规划算法是一种非常经典的启发式搜索算法，它的估计函数计算式为：f（x）=g（x）+h（x），其中f（x）为节点x的估价函数；g（x）为实际代价；h（x）是最佳路径的估价，在函数中作用最大。另外，估价函数决定着A*算法的正确与否。取g（x）在状态空间到x节点的深度，如图2所示。其中h（x）的计算方法为：h（x）=|Xd―Xs|+|Yd―Ys|。式中：（Xd，Yd）表示目标点坐标，（Xs，Ys）表示当前点坐标。
3 改进A*路径规划的算法
机器人定位前，A*算法已规划好最佳的路径，但路径中夹杂了多余的点坐标，当移动机器人到达拐点处时，不能自行地调整姿态。因此，我们对A*算法提出两个方面的改进：
（1）简化坐标点，除去冗余的坐标点，只剩下起点、拐点和终点。
（2）解出拐点处的旋转方向和最小角度，当机器人到达拐点处时，根据角度和方向自行处理自己的位态。用A*规划任意路径，通过实验证明它的正确性，如图3中A所示。
改进A*算法后的路径规划如图3中B所示，路径只包含起点1、拐点3、6、8、9和终点11。
4 仿真分析
为了验证A*算法的可靠性，在不同环境下，可选用编译工具Matlab 7.0对移动机器人进行路径规划仿真。其结果表明：采用改进的A*路径规划算法，使得要计算的路径点减少，且当机器人到达拐点处时，能够自动调节位态，使移动机器人更好地自主定位。
5 结语
基于A*路径规划算法移动机器人，找到的最优路径要满足几何长度的最短与时间最短的条件，只有这样的无碰路径才是最优路径。在栅格环境下，采用A*算法的移动机器人其实并不能完美满足实际应用，为了使其路径更加完美，则需要继续地实验论证，期待未来的移动机器人不但可让路径简单化，而且还能找到其在拐角处旋转的方向和角度，满足定位要求。
参考文献
路径规划范文2
关键词:移动机器人 路径规划 障碍物
中图分类号:TP24 文献标识码:A 文章编号:1007-9416(2010)08-0015-02
1 引言
在有障碍物的工作环境中,如果机器人及障碍物的位置可以实时测得,则可以寻找一种移动机器人的优化路径规划算法,使机器人在运动过程中无碰撞地绕过所有的障碍物,安全的到达指定目标位置[1]。
路径规划问题根据机器人的工作环境模型可以分为两种,一种是基于模型的路径规划,作业环境的全部信息都是预知的;另一种是基于传感器的路径规划,作业环境的信息是全部未知或部分未知的。
本文提出一种计算简单、容易实现的移动机器人路径规划方法,可供侧重于应用的读者参考。
2 问题描述
设机器人在长度为L的L×L的二维平面上能够自由运动,将机器人模型化为点状态机器人,在L×L的二维平面上存在若干个静态障碍物和在一定范围内运动的动态障碍物,根据安全性的要求进行了相应的“膨胀化”处理,使“膨胀化”后的障碍物边界为安全区域,“膨胀化”后的障碍物边界区域内为凸型,边界为光滑曲线,边界上各点曲率半径≤δ(其中δ是正常量,可假设为圆的半径),曲率中心在障碍物内部,单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径[2]。设终点(目标)的坐标为已知,机器人在任何时刻都能测出机器人所在位置与终点连线和机器人到障碍物边界的切线的夹角。根据夹角的大小来判断所选择的无碰撞行走路径[3]。如图1所示,由于角α
3 路径规划原理
3.1 求切线法的路径规划原理
根据几何学园外两点到园的四条切线,其切线与两点连线夹角小的两条线段之和小于切线与两点连线夹角大的两条线段之和。如图2所示。设A和B两点坐标分别为(XA,YA)和(XB,YB),如果角α
由(X-XB)/(XA-XB)=(Y-YB)/(YA-YB)得:(YA-YB)X-(XA-XB)Y+(XAYB-YAXB)=0
(2)利用夹角求切线方程
如果测出过A、B两点与园的切线和AB直线的夹角,则可求出切线方程。
在图2中,直线AN的方程为:Y-YA=tanα(X-XA)
直线AM的方程为:Y-YA=tanβ(X-XA)
直线NB的方程为:Y-YB=tanα1(X-XB)
直线MB的方程为:Y-YB=tanβ1(X-XB)
(3)由四条切线求点A到点B的最短路径
根据角α
3.2 首先判断机器人和给定的目标位置之间是否存在障碍物
如图1所示,以R代表机器人,坐标为(XR,YR),以G代表目标位置,其坐标为(XG,YG),障碍物为A、B、C、D、E、F等,坐标为 (XA,YA)、(XB,YB)、(XC,YC)、(XD,YD)、(XE,YE)、(XF,YF)等。Rr表示机器人半径、Ri(i=A、B、C、D、E、F)表示障碍物的碰撞半径,也就是说在其半径以外无碰撞的危险。要根据实际情况和控制要求来确定碰撞半径。碰撞半径Rp一般选择大于障碍物的半径Ri加上机器人半径Rr,即Rp>Ri+Rr。
3.3 单障碍物情况
机器人在任何时刻都能够测得机器人的位置坐标(XR,YR),目标位置是已知的(XG,YG),可测量出机器人与目标连线和机器人与障碍物碰撞圆的切线的两个夹角αi和βi(i=1,2,…)。若αi
3.4 多障碍物情况
对于多障碍物情况,可将移动机器人绕过多个障碍物最终到达目标位置作为一个总任务,每当绕过一个障碍物作为一个分任务。总任务就可分解为多个分任务,设第i个分任务的目标点为Gi和中途点为Bi,执行第i个分任务时,如果在到达Gi的路径上存在障碍物,则增加第i+1个分任务,此时目标点Gi+1就是Bi;以此类推,寻找切线路径直至到达给定的最终目标位置,计算所有分任务的最短切线路径之和即为所求的最优路径[4]。
4 行路径算法
(1)机器人朝着目标按直线方向行走,直到以下任一情况发生:
①已经到达目标,结束。
②在机器人与目标之间发现障碍物,转(2);
(2)按路径规划的原理选择路径,转(1)。
5 结语
移动机器人路径规划的算法有很多,每一种算法能够适用于几种特定的场合。一个好的算法,不但理论简单,计算快捷,容易理解,便于实现,而且实现的效果好,能够提高运行效率。本文介绍的移动机器人的路径规划方法,容易理解,便于实现,可适用于某些特定的场合。
参考文献
[1] 李彩虹,李贻斌,范晨.移动机器人动态避障算法[J].山东大学学报,2007,5(37):60-64.
[2] 陈刚.复杂环境下路径规划问题的遗传路径规划方法[J].机器人,2001,(3):230-233.
路径规划范文3
【关键词】模糊控制 双足机器人 路径规划 超声波传感器
机器人路径规划一直是机器人研究领域的热点问题。路径规划是在有障碍物的环境下找到一条由给定点到达目标点的最优路径，使机器人能够绕过障碍物，在不与障碍物相碰撞的情况下到达目标点。机器人在移动过程中必须安全无障碍的绕过所有障碍物，寻求一条安全的运动轨线判断并自动躲避障碍物顺利抵达目的地并且尽可能使所走路径最短。目前，常用的局部路径规划算法有势场法、A* 算法、栅格法及模糊算法。其中模糊算法有效的减小了对环境信息的依赖性，具有良好的鲁棒性和实效性。
本文主要采用模糊算法解决直立行走机器人在静态未知环境中的局部最优路径规划问题，并通过MATLAB仿真实验验证了模糊算法的有效性和可行性。
1 超声波传感器
双足直立机器人实现避障行走，首先需要对外界环境进行感知，探测到障碍物的方位。而超声波作为一种距离探测传感器，以其质量可靠，成本低廉为特点，在机器人测距中得到了广泛应用。基于双足直立机器人在速度上有限制的前提条件，采用周期扫描模式进行距离检测是最可行的方案，即将机器人的视野范围均分为若干份，记录每个视角检测到障碍物的距离，进而获得完整的外界环境的知识。同时为了消除机器人在运动过程中的抖动对测距的影响，为测距模块搭建了云台系统，使测距模块在运动过程中始终保持水平状态。
2 模糊控制器设计
2.1 确定模糊控制器的输入变量和输出变量
模糊控制器的输入是超声波采集的距离信号和双足机器人与目的地方向的夹角信息，输出是双足机器人的转动角度。双足机器人的构成包括支架、舵机、目标传感器、超声波传感器等部分。超声波采集的距离信息是机器人当前位置与障碍物的距离，超声波在机器人前进方向的180度范围内采集与障碍物的距离信息，取其中最左、最右及正前方的距离信息为三个输入变量，定义最左侧距离为DL、正前方距离为DC、最右侧距离为DR。通过目标传感器，确定双足机器人当前位置与目的地方向的夹角D0为角度输入变量。利用这些条件推理出输出变量OUT，即双足机器人的转动角度，如图1所示。
2.2 输入变量及输出变量的模糊化
定义距离输入变量的模糊语言为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）所示。
2.3 确立模糊控制规则
模糊控制规则（控制策略）的选择是模糊控制器设计非常关键的一步。它是基于手动控制策略，是操作者经验和技术知识的集合 。模糊控制规则实际上是一系列模糊条件语句的集合，反映了输入量与输出量的关系。按照双足机器人的实际控制进行模糊逻辑推理，确定了四个输入信号，一个输出信号，构成一个多输入单输出的模糊控制系统。
双足机器人在行进过程中，根据与障碍物的距离信息及与目的地的夹角信息进行决策推理出转动角度，从而实现最佳的路径规划。当采集到障碍物信息时，双足机器人将转动一定角度，改变行进轨迹实现有效避障的功能。机器人行进规则如下：
（1）当目标点位于障碍物左（右） 侧时，则机器人左（右）转；
（2）当目标点在机器人正前方且障碍物距离机器人很近时，则机器人需根据它的左侧和右侧的障碍物信息来决定左转还是右转；
（3）当左侧障碍物距离大于右侧障碍物距离时， 机器人选择向左转，反之向右转。
根据确定的输入输出变量的论域，采用模糊规则的一般形式If（条件）then（结果）进行描述。模糊规则如表1所示。
2.4 模糊决策
模糊决策（模糊推理）是根据模糊逻辑的关系及推理规则来进行的 。根据模糊规则推出输出量的隶属度函数。下面将通过简单举例来说明模糊控制器的原理。
以双足机器人在DL=0 ，DC=2.5，DR=3，C0=8的状态为例，该状态对应模糊表中的第11、12、18条规则，由此状态下的模糊规则进行推理合成，得到输出量的隶属度函数。
第11、12、18条规则推理结果及合成隶属度函数结果如图3中（a）-（d）所示。
2.5 解模糊
经模糊推理得到的是一个模糊集合 。通过解模糊得到精确值，确定实际输出对双足机器人进行转角控制。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-），男，河北省唐山市人。现为华北理工大学学生。研究方向为智能机器人控制。
路径规划范文4
【关键词】AUV；自动路径规划算法
1.引言
AUV自主水下航行器是近些年来快速发展的一种新型海上平台装备。这种水下航行器能够执行多种军事任务，例如进行海上军事探测、反水雷等。另外AUV在民用方面也有着广泛应用，AUV能够用于海洋环境探测、海底管道铺设和检查。然而，由于海洋地理环境比较复杂，这给AUV的水下航行路线带来了一定困难，为了能够选择正确方便的路径，人们研究了许多AUV路径规划算法。本文想就此问题提供一种适用于AUV的自动路径规划算法。
所谓自动路径规划算法是指从电子海图上面提取地理数据，然后根据这些数据产生从开始点到目标点的航路点序列；该算法能应用于任意海军平台的路径规划。这种算法可适用于海军的各种领域，如AUV（包括UUV和ROV）航行器的航路计算，鱼雷发射航路的计算，水面舰艇和潜艇的导航等等。开发这种算法的目的是寻找通过给定区域并能避开所有障碍物的一条最佳路径。路径中的航路点序列来自之前扫描发现的点集。目前算法是针对二维航路点规划设计的，同时也考虑了海区的深度。但在产生的航路点序列中没有深度值，这是下一步需要研究的内容。
在本文中算法的边界条件定义如下：在开始计算时先获取自身和所有已知目标的真实位置，假定计算过程中这些目标的位置保持不变。因为整过计算过程仅几秒钟，这样做是可行的。在这短短的计算时间内，位置的变化量可以忽略。算法的另一个约束是最大计算时间不能超过20s。为了适应作战系统，采用这一时间约束是必要的。为了用于其他作战系统，很容易就可以改变该值的大小。考虑这些边界条件后，对算法进行了开发和实现。
2.算法实现
本文中的算法分为两大重要部分，他们是程序内独立的两个模块，这样保证了程序的可重用性和可维护性。
第一个模块为AUV自主航行器生成一个图，该图含有AUV周围区域的地理数据和区域内障碍物的数据。这种地理数据是从标准电子海图中提取的，并处理成数字地形模型。该过程是由剖面评算用电子海图分析器来完成。该程序从海图中获取给定区域的深度数据后生成光栅格式的地形图。光栅中的每一点表示一个深度值，因此整个区域都由深度值来描述。
这样的地形模型是生成图的基础。这些光栅点表示图的节点和边。节点为图的接合点，一条边连接两个接合点。边可以赋予权重以表示从起始节点到目标节点之间的距离，如图1所示。
当地形模型转为图后，一个光栅点就对应一个节点，光栅点的深度值就表示从该点到相应节点的边的加权值，如图2所示。
图2上除了按沿直角运动外，还可以沿对角线运动。依照不同的角度（由两节点之间x和y的差值来决定），路径长度不同，因此边的权重也不同。当角度为45度时，目标节点的深1度值需要乘上，如图3所示。
为了寻找一条能避开岛屿等障碍物的路径，程序必须能确定是否达到了某一最小深度值。因此图上所有深度值都与最小深度比较。如果某一节点的深度比最小深度还深，该深度值将被定义为一个给定的值，比如1000，否则设置为1。这种区别对于路径规划算法来说是必要的。
除了（船或飞机）残骸等地理障碍物以外，石油平台和其他船只也需要一起考虑。因此在每个障碍物的周围定义一个危险区域。危险区域内的节点深度值都设置为1000。如果程序用于计算鱼雷射击诸元，目标船的探测范围也必须认为是障碍物。这种区域的深度值是可变的以便将探测距离定义为“可穿越”的障碍物。
图3生成后就可以开始寻找从起点到目标点的最优路径，这个功能由第二个程序模块完成。根据给定的地理起始节点和目标节点位置以及地形模型的地理坐标，就可以用A*算法计算最优路径。该算法来源于导航和机器人领域，在图格式中应用得很好。
算法原理如下：
算法首先建立“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列表，算法结束。这时最佳的路径就可以从目标节点根据前驱节点从目标节点回溯到起始节点。
当最佳路径决定后，需要将其简化为航路点列表，因此对于最佳路径上的每一个节点，如果节点改变了路径方向就将其加入到航路点序列，这样就将所有节点转换为实际的地理位置。
若想定复杂，计算最佳路径的时间可能超过20s。计算机系统的性能也会影响计算时间。为了满足时间约束，A*算法能加速，不足的是会降低规划路径的质量。在距离估算项乘以一个常数因子，计算速度就会增加，因子越大，计算速度越快。
通过实际测试，它能计算出两个地理位置之间的最佳路径并能避开所有障碍物。
3.结束语
在绝大多数的实际想定中，计算最佳路径和相应的航路点列表的时间小于3s。就是对于军事应用，这一时间也是很理想了，因为手工计算要慢得多。在一些特例中，最佳路径的质量有所差别。加速因子取值为1.5时，A*算法在计算的时间和路径质量方面达到较好的平衡。但是因子依赖不同想定和图，在有些想定和图中，算法会扩展很多不必要的节点。因子取值越大，路径的质量差别越明显。
在所有测试中，给定的20s时间约束存在2%的误差，若不存在路径，就将20.2s作为最大计算时间。这是A*算法中止执行的标准，如果计算时间超过这个值就认为不存在路径。A*算法操作的时间限制为20秒，过了这个值就可以中止执行算法操作了。依赖于计算机系统性能的时间认为与A*算法没有关系。
程序在应用于AUV水下航行器前，还需要做一些修改，如对程序进行扩展以改进与海图的接口。根据路径质量要求，可以增加相应的曲线平滑算法，以尽量减少确定的路径与最优路径的差异。
作者简介：
路径规划范文5
【关键词】海军平台;自动路径;规划算法
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所示。从图中可以明显看出，随着因子的增大，路径质量不断下降。因子从1.0增加到30时计算时间从14.9s减少到0.4s。经过几个系列测试分析后，选择1.5作为算法的加速因子，这一因子在不明显影响计算路径的质量的前提下大大缩短了计算时间。若计算时间超过给定值，程序会自动增加因子的大小。
图7 因子从1.0到1.5的加速测试
图8 因子从2.0到3.0的加速测试
4.结束语
程序的实现和测试都取得成功，它能计算出两个地理位置之间的最佳路径并能避开所有障碍物。
在绝大多数的实际想定中，计算最佳路径和相应的航路点列表的时间小于3s。就是对于军事应用，这一时间也是很理想了，因为手工计算要慢得多。在一些特例中，最佳路径的质量有所差别。加速因子取值为1.5时，A*算法在计算的时间和路径质量方面达到较好的平衡。但是因子依赖不同想定和图，在有些想定和图中，算法会扩展很多不必要的节点。因子取值越大，路径的质量差别越明显，如图7和图8所示。
在所有测试中，给定的20s时间约束存在2%的误差，若不存在路径，就将20.2s作为最大计算时间。这是A*算法中止执行的标准，如果计算时间超过这个值就认为不存在路径。A*算法操作的时间限制为20s，过了这个值就可以中止执行算法操作了。依赖于计算机系统性能的时间认为与A*算法没有关系。
程序在应用于海军平台前，还需要做一些修改，如对程序进行扩展以改进与海图的接口。根据路径质量要求，可以增加相应的曲线平滑算法，以尽量减少确定的路径与最优路径的差异。
参考文献
路径规划范文6
关键词:医药物流遗传算法路径规划旅行商问题
中图分类号:TP301文献标识码:A文章编号:1009-3044(2010)11-2717-02
医药物流是指医药器械从医药配送中心分发、配送到各个医院和医疗中心的过程,甚至包括通过医院到达消费者(患者)手中的过程,其中所产生的物流成本是医药器械成本的重要组成部分。降低医药运输成本是减少患者医疗负担的重要途径之一。而药物配送实际上就是旅行商问题[1]。遗传算法作为一种求解问题的高效并行全局搜索方法,成为目前解决NP完全问题的较为有效的方法之一。
1 旅行商问题与遗传算法
1.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的距离。
1.2 遗传算法基本原理与描述
1.2.1 算法原理
遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法,由美国J.Holland教授提出,其主要内容是种群搜索策略和种群中个体之间的信息交换,搜索不依赖于梯度信息。该算法是一种全局搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题。
1.2.2 算法描述
该算法包括以下6个基本要素:
1) 编码:遗传算法不能直接处理解空间的数据,必须通过编码将它们表示成基因型串数据。常对参数采用二进制编码,编码当作一条染色体,编码前应先量化[3]。
2) 生成初始种群:初始种群的个体通过随机方法产生,且对应研究问题的一个解。
3) 评估适应度:遗传算法在搜索过程中用适应度来评估个体的优劣,并把它作为遗传操作的依据。适应度函数常取非负数,且适应度增大的方向与目标函数的优化方向一致。
4) 选择:根据适者生存的选择原理,从当前种群中选择生命力强的个体(即适应度高的个体),产生新的种群。适应度越高的个体,被选择的机会就越大,但并不意味着适应度高的个体一定会被选择[4]。
5) 交叉:将选择出的个体存入配对库,用随机的方法进行配对,以产生新一代的个体。
6) 变异:在交叉过程中可能丢失一些重要的遗传信息(特定位置的0或1)1必须引入适度的变异,即按一定的概率改变染色体基因位。
2 优化路径遗传算法的构造
针对优化物流配送路径的特点,本文构造了求解该问题的遗传算法。
2.1 初始种群的生成与编码方法的选定
随机生成规模为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]。
2.2 适应度评估
对于某条染色体,设其对应的配送路径方案的不可行路径数为Ni(Ni=0表示该个体对应一个可行解),其目标函数7值为Td,则该个体的适应度可用下式表示:,式中α为对每条不可行路径的惩罚权重,可根据目标函数的取值范围取一个相对较大的正数(α值太小则会影响适应度的比较)。
2.3 遗传操作
2.4.1 选择操作
选择将使适应度较大个体有较大的存在机会,而适应度较小的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制,令Σfi表示群体的适应度值之总和,fi表示种群中第i个染色体的适应度值,它产生后代的能力正好为其适应度值所占份额fi/Σfi。作为其被选中的概率Psi。这方法既可保证最优个体生存至下一代,又能保证适应度较大的个体以较大的机会进入下一代。
2.4.2 杂交操作
采用顺序编码法后,若用简单的一点杂交或多点杂交,必然会导致未能完全遍历所有城市的非法路径。如城市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处销售点,通过路径规划希望找出最优路径以节省运输成本。
3.1 运行参数设计
本实验采用n城市的遍历顺序编码法,适应度函数取总长度Td的倒数(无惩罚函数)。选择机制是保留M个较优个体,在每一代运算中,个体被选中的概率与其在群体中的相对适应度成正比。杂交操作采用OX(次序杂交)法。为使算法尽快地收敛,在经过杂交变异操作后,增加了局部优化过程,提高个体对环境的适应。群体规模取56,交叉概率和变异概率分别取0.9和0.01, 最大迭代数2000。
3.2 实验结果
运行环境:操作系统Microsoft Windows XP;仿真软件:MierosoftVisualC++6.0。
在实验计算中采用以上设定参数对该公司配送路径问题求解,所得到的优配送化路径最优长度为862,用时126秒,迭代次数1528。得到的路径线路如图1所示。
4 结论
在此也可以看到,运用遗传算法解决实际问题,算法是使用参数的编码集,而不是参数本身,参数的选择十分方便;遗传算法与其他计算机算法不同,相比之下,它比较具有随机性而不是稳定性,遗传算法是在点群中,而不是在一个单点寻优。因此利用遗传算法解决实际问题需要选取大量数据,通过多次实验的数据分析不断改进算法和设置参数来求得更优的结果。用遗传算法求解组合优化问题具有巨大的优越性[7]。非常有助于物流企业根据自己的实际情况科学、有效地制定物流决策,降低风险,降低成本,提高经济效益和自身的竞争力。
参考文献:
[1] 田贵超,黎明.旅行商问题(TSP)的几种求解方法[J].计算机仿真,2006,23(8):153-157.
[2] Holland J H.Adaptation 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.
