路径规划十篇

路径规划篇1

关键词：分层路网；拓扑结构提取；路径规划；A算法；二叉堆

0引言

路径规划是车载导航系统最重要的功能之一[1]。根据图论中最短路径理论，不管是最短路径规划、最短时间规划还是最低消费规划，都可以通过赋予图中的边以相应的权值来满足用户的不同需求。

通常情况下，路径搜索可以分为平面搜索和分层搜索两大类。平面搜索算法中最经典的是20世纪60年代初期由Dijkstra提出的Dijkstra算法，非常适合在带权有向图中解决最短路径问题。但是该算法的时间复杂度为O（n2），效率比较低，因此在实际应用时受到了很大的限制。后来许多学者在存储结构和排序算法上对Dijkstra算法进行了改进[2-3]，通常改进算法的时间复杂度与节点数成正比，如O（mlbn）或O（m+nlbn）[4]。也有学者通过引入启发函数的方式进行改进，启发式搜索以1968年Hart等提出的A*算法为代表，现在仍被广泛应用，但这些改进算法的效率会随节点数的增加而急剧下降。此外，平面搜索算法计算出的“最短”路径并不一定是“最优”路径，最短路径中可能存在大量的窄小拥挤的小巷，而最优路径要尽可能多地包括主干道等快速路段[5]，这就有了分层思想。文献[6]首先提出了层次空间的推理过程，文献[7]又将层次空间推理法则引入到行车最优路径搜索中，但这两篇文献均没有给出具体的路网层次拓扑结构的表达方法[8]。有代表性的分层算法有最近E节点法[9]和最佳E节点法[10]，其中最近E节点法简单但准确率不高，最佳E节点法能够得到最优解，但效率低[11]。

本文试图设计一种实用的分层路径规划算法。首先建立分层路网的拓扑结构，然后从搜索空间、搜索策略和数据结构三个方面进行研究，采用启发式的A*算法作为主搜索方式，引入优先队列二叉堆作为数据存储结构，最后通过实验验证每项措施的改善效果。

1分层路网拓扑结构提取

路径规划篇2

【关键词】自动导航小车；路径；规划；控制

随着科技的不断进步，我国自动化技术发展越来越好，这对提高人们的生活质量有着较大帮助。应用自动化技术，可以生产出具有更多功能的机器与设备，比如，自动导航小车就是一种新型的机器，其具有自动定位与行驶的特点，可以利用计算机技术，对小车的行驶路径进行规划与控制。自动导航小车的设计与制作涉及多个领域，在科技不断发展的背景下，我国自动化控制水平越来越高，这也促进了自动导航小车的发展。下面笔者对自动导航小车的路径规划以及控制方法进行简单分析。

1.自动导航小车路径规划的定义与方法

1.1自动导航小车路径规划的定义

有学者对自动导航小车这类机器的路径规划有着如下定义：在自动导航小车中，设有自动导航系统，该系统是由较多的刚体部件构成的，而且有着不同的自由度。如果该系统可在二维或者三维空间中运行，则说明小车可以在不破坏自身运动约束的条件下，进行自由运动。另外，在工作空间中，也存在较多的几何参数障碍。路径规划指的是自动导航小车在系统设定的连续动作下，由给定的初始位形运动到目标位形的设计。位形指的是自动导向小车位置与形态，相关设计人员通过改变位形，可以控制小车的行车路线。

1.2路径规划的方法

自动导航小车路径规划的方法主要有两类，其一是传统方法，其二是智能方法。第一类传统路径规划方法中，常用的有自由空间法、图搜索法、人工势场法等；第二类智能路径规划方法中，常用的是基于遗传算法的路径规划、基于人工势场的路径规划等等。在现代自动导航小车设计中，应用智能方法比较多，其可以提高路径规划的准确性，下面笔者对自动导航小车的路径规划常用的几种智能方法进行简单的介绍。

1.2.1基于遗传算法的路径规划

基于遗传算法的路径规划在自动导航小车路径研究中应用比较广泛，其是由国外的学者提出的，是在模拟达尔文生物进化论的基础上创建的，应用这种方法可以解决传统路径规划中存在的漏洞。遗传算法具有随机性，而且具有针对性，利用遗传算法可以对自动导航小车的移动路径进行准确的规划，其具有高效的特点。

1.2.2基于人工势场的路径规划

人工势场是一种虚拟的方法，其将自动导航小车的运动路径看做是人工受力场下运动，应用虚拟的方法，主要是利用障碍物对自动导航小车所产生出的斥力，以及目标点对小车产生的引力而完成运动路径的。在斥力与引力的共同作用下，自动导航小车可以从初始位形移动到目标位形，由于斥力与引力对小车的速度有着较大影响，所以，利用加速力相关人员还可以计算出小车所处的位置，从而控制小车的运动方向以及路径规划。

2.不同环境下自动导航小车的路径规划策略

自动导航小车是一种新型的机器，其在未知的环境下，收集信息的情况也有一定差异，通过分析发现，其收集信息主要有两种类型，一种是在已知的信息环境下，全局路径的规划；另一种是在未知的环境信息下，局部路径的规划。下面笔者主要对静态已知环境下局部路径规划方法以及静态未知环境下局部路径规划方法进行分析。

2.1静态已知环境下局部路径规划方法

静态已知的信息环境下，对小车局部路径进行规划是一种比较容易实现的方法，这种规划方法有着广泛的应用空间，这种方式最早应用的是可视图算法，随着科技的不断发展，相关人员又提出了随机路图法，这两种方法有着各自的适用范围。可视图算法提出的时间比较早，其广泛应用是在1987年，研究人员利用可视图算法，解决了小车路径规划问题。可视图是由节点与可视边组成，在已知的环境下，技术人员通过设置障碍点以及目标点，可以帮助小车快速到达指定位置。为了提高小车运动的效率，设计人员需要了解可视图算法的最短路径定理，该定理指出，从初始点到目标点含有穷路径集合，为了得到最短路径的算法，需要全面考虑可视图构造，这种方法在二维空间中发挥较高的效用，但是在高维空间中并不适用。

2.2静态未知环境下局部路径规划方法

静态未知环境下，自动导航小车需要利用自身传感器对环境进行感知，在获得局部信息后，对局部路径进行规划，这种规划方式主要采用了势场法，但是在应用的过程中也存在一定局限性，设计人员需要重点考虑梯度以及积分问题，而且需要通过分析多个局部信息，掌握全局信息。这种路径规划法效用的发挥与传感器性能有较大关系，为了更好的掌握全局信息，设计人员多采用的是实时传感器。这种规划方法的基本思路是：自动导航小车向目标点运动的过程中有多种路径，相关人员需要将所有可能性进行量化，在通过分析障碍物信息，从而得出最佳的规划路径。在对通路进行检测时，要避免小车进入死路，通过测量障碍物间的距离，判断小车是否可以通行，如果通路被堵塞，则需要重新优化路径。

3.自动导航小车的路径控制

控制软件与各模块驱动程序是保障系统正常运行不可或缺的部分。控制软件在主机上实现，各模块驱动程序在各自模块中运行，控制软件与各模块驱动程序之间可通过主从式结构进行必要的通信联系。子机可向主机发出异常情况处理信号，利用通信技术，还可以控制各子模块的运行状况。

3.1运动控制的位置环调节

参数调节运动控制驱动器的位置控制回路时，运用基于观测器的状态变量控制技术。采用此技术，运动控制驱动器的优点是：⑴系统将具有很高的动态刚度；⑵即使负载和电机的惯量有较大差别，仍可有效减少跟踪误差。在运动之前，必须进行轨迹参数设置及完成参数设置。初始调节时，一般设定运动速度、加速度、加加速度为较大值，而运动位置为一较小值。

3.2轴的运动

轴运动有两种，一种是单轴运动，另一种是多轴协调运动。单轴运动是指某一种运动模式设定后，该轴将保持这种运动模式，直到设置新的运动模式为止。多轴协调运动是指运动控制器可以实现两种轨迹的多轴协调运动。对于各模式之间的切换，除电子齿轮模式之外，其他模式必须是在当前轴运动完全停止的情况下进行。控制器中不同的轴可以工作在不同的运动模式下，在某些情况下，为了安全起见，需要在某些位置或某个时刻使运动停止。

4.结语

通过上文的分析可以看出，自动导航小车具有较高的性能以及较多的功能，其性能体现了我国科技的进步性。在计算机技术的影响下，相关设计人员利用传感器，使自动导航小车获取周围环境的信息，其获取的方式有两种，一种是在已知的信息环境下，获取全局信息，另一种是在未知的环境下，获取局部的信息。为了更好的控制小车路径，相关人员需要掌握传感器信息融合算法，还要避免外界环境对信息准确性的影响，这样才能提高路径规划与控制测量的可行性。

【参考文献】

[1]陈亮，黄玉美，林义忠，史恩秀，高峰.陀螺仪角速度的检测与处理[J].传感器与微系统，2006（04）.

路径规划篇3

    关键词:移动机器人 路径规划 障碍物

    中图分类号:TP24 文献标识码:A 文章编号:1007-9416(2010)08-0015-02

    1 引言

    在有障碍物的工作环境中,如果机器人及障碍物的位置可以实时测得,则可以寻找一种移动机器人的优化路径规划算法,使机器人在运动过程中无碰撞地绕过所有的障碍物,安全的到达指定目标位置[1]。

    路径规划问题根据机器人的工作环境模型可以分为两种,一种是基于模型的路径规划,作业环境的全部信息都是预知的;另一种是基于传感器的路径规划,作业环境的信息是全部未知或部分未知的。

    本文提出一种计算简单、容易实现的移动机器人路径规划方法,可供侧重于应用的读者参考。

    2 问题描述

    设机器人在长度为L的L×L的二维平面上能够自由运动,将机器人模型化为点状态机器人,在L×L的二维平面上存在若干个静态障碍物和在一定范围内运动的动态障碍物,根据安全性的要求进行了相应的“膨胀化”处理,使“膨胀化”后的障碍物边界为安全区域,“膨胀化”后的障碍物边界区域内为凸型,边界为光滑曲线,边界上各点曲率半径≤δ(其中δ是正常量,可假设为圆的半径),曲率中心在障碍物内部,单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径[2]。设终点(目标)的坐标为已知,机器人在任何时刻都能测出机器人所在位置与终点连线和机器人到障碍物边界的切线的夹角。根据夹角的大小来判断所选择的无碰撞行走路径[3]。如图1所示,由于角α<β,所以,机器人行走路径为RPPQQG。

    3 路径规划原理

    3.1 求切线法的路径规划原理

    根据几何学园外两点到园的四条切线,其切线与两点连线夹角小的两条线段之和小于切线与两点连线夹角大的两条线段之和。如图2所示。设A和B两点坐标分别为(XA,YA)和(XB,YB),如果角α<β,则AN+NB  (1)利用两点式求出机器人与目标之间的直线方程

    由(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的最短路径

    根据角α<β,可求出点A到点B的最短路径为AN+NB

    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<βi,则选αi方向的切线作为行走路径;否则,则选βi方向的切线作为行走路径;则如图1所示。

    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.

路径规划篇4

关键词：危险天气区域；航班改航；路径规划

一、引言

危险天气区域下，导致飞行事故症候的事件比较频繁。在飞机巡航期间，由于受大范围天气系统的影响，雷雨，冰雹，龙卷风、闪电等，如果飞机在航路上遇到大面积雷雨区时，一般就会飞机返航、备降。而通常雷暴是在云层中，有的时候即使不下雨，但是云层中依然会有雷暴。雷暴区域附近产生的下击暴流和风切变，会直接造成起降飞机失控。风切变即是在短距离内风向、风速发生明显突变的状况。强烈的风切变瞬间可以使飞机过早地或者被迫复飞。在一定程度下就可以导致飞机失速和难以操纵的危险，造成飞行事故。机组由于对雷暴的认识不清，签派员在遇到雷雨天气条件下航班的放行时，往往主对天气的了解和掌握也主要集中在机场终端区雷雨天气的研究。航路雷雨天气下的放行成为一个难点，对其发展趋势不明白，没有事先做好充分的绕飞计划，以及绕飞油量没有带够等因素而导致返航备降。在航路上飞机飞行高度都比较的高，而空域范围较广，并且受到的地形限制非常小，解决的办法可以让飞机进行绕飞或改变在云上飞行飞行高度等措施来避开雷暴等危险天气的影响。本文将探讨的就是危险天气区域下的航班改航路径规划。

二、人工势场法路径规划

人工势场模型人工势场法由Khatib 1986年提出的一种虚拟力法，起初只是为了解决机械手臂在移动抓取物体的时候，能够不碰到工作台。他的基本思想是把机器人在周围环境中的运动，设计成一种抽象的人造引力场中的运动，目标点对移动机器人产生“引力”，障碍物对移动机器人产生“斥力”，最后通过求合力来控制移动机器人的运动。后来该方法在移动机器人上应用也有很好的效果，能产生出非常平滑的运行轨迹。人工势场法的基本思想是在环境中建立目标位置引力场和受限区周围斥力场共同作用的人工势场，搜索势函数的下降方向来寻找无碰撞路径。引力和斥力的合力作为移动物体加速力来控制移动物体的运动方向和计算移动物体的位置。该方法结构简单，在实时避障和平滑控制轨迹方面得到了广泛的运用。在采用传统人工势场路径规划模型进行航空器改航路径规划时，在狭窄区域容易发生振荡现象，导致航空器左右来回运动，造成了规划的不稳定。人工鱼群算法人工鱼群算法是一种群智能多点并行搜索优化算法。该算法的主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，有着较快的收敛速度，具有克服局部极值获得全局极值的能力。王飞等将该算法应用机着落排序问题和地面等待策略问题，取得了较好的应用效果。通过构造单个人工鱼来控制人工势场函数的参数，调用改进人工势场模型进行改航路径规划，生成多条改航路径，利用适应度函数对生成的改航路径进行评估，通过算法的觅食、聚群、追尾等行为的选择，选出适应度好的人工鱼参与下一组鱼群的进一步计算，通过随机行为可以在新的空间进行新一轮的搜索，最终生成最优的改航路径。

如事例1、某航班执行成都—西宁航线，由于西宁机场雷雨天气备降兰州。飞机在兰州落地之后，西宁天气好转，雷暴向东移出本场，往兰州机场方向移动，正好在兰州到西宁的航路上，且范围较广。考虑到兰州到西宁的航线距离较近，不到150公里，且该航路标高较高，地形较复杂，飞机起飞后绕飞困难等因素，通过对天气演变趋势的详细研究，制定详细的绕飞计划和带够足够的绕飞油量后，再次放行飞往西宁。

事例2、某航班执行成都—张家界航线，在飞机进入长沙管制区后，由于航路上有大面积雷暴区，使得飞机绕飞比较困难，而且机载油量有限，备庆。最终由于该天气系统往张家界机场方向发展，时间较长，且考虑到该机场是特殊机场，取消该航班。

事例3飞行受限区域昆明到贵阳航线所经航路点为： 昆明（ KMG） - 过马河（SL）- P72- 贵阳（KWE）； 通过 Mercator投影建立经纬度与X - Y 轴的投影关系，则KMG、SL、P72、和 KWE在该平面直角坐标系中坐标分别为 （ - 124. 8 220，64. 2 764）、（ - 118. 6 788，68. 3 736）、（ - 103. 9 652，71. 6 366） 和（ - 82. 2 684，76. 8 524）。根据天气预报生成飞行受限区域，图 1 中阴影部分为雷暴云团 A、B、C。假设雷暴云团 A向东北方向以 40 km /h的速度匀速漂移，云团的形状、面积和强度保持不变；云团 B绕云团几何中心旋转，云团 C处于扩张阶段。

图 1 飞行受限区域

优化后的改航路径利用人工势场- 人工鱼群算法，得到优化的改航路径。

如图 2、图 3所示。

图 2 优化的改航路径

图 3 路径规划中的航线角度

改航路径的修正通过对转弯角度较大的改航路径点的判断，来确定分段点，从而将初始的改航路径分成 7段进行线性拟合，并计算出拟合后 7段航线的交点，将交点顺次连接，生成拟合的改航路径。

图 4 分段拟合后生成的改航路径

如图 4中实线所示。由于在第 6航段不满足与受限区的最小距离的约束，所以需要进一步修正。具体如下： 将图 4中的航段 1、2、3，截弯取直，合并为如图 5中的第 1航段，原航段 4改为第 2航段，将原航段 5、6合并为第 3航段，原航段 7变为第 4航段，如图 5所示。经验证修正后的改航路径，满足约束条件，这样就得到最终的改航路径。

参考文献

[1] 谢春生，李雄. 危险天气影响航路飞行区域的划设及评估[J]. 中国安全科学学报. 2010（10）

[2] 张静，徐肖豪，王飞. 天气影响的机场容量概率分布[J]. 南京航空航天大学学报. 2011（01）

[3] 李雄，徐肖豪，赵嶷飞，卫东选. 散点状分布危险天气区域下的航班改航路径规划[J]. 航空学报. 2009（12）

路径规划篇5

关键词：机器人路径规划算法

一、本文就常见的几种常见的路径规划算法及应用进行简单的探讨如下：

（一）遗传算法概念

遗传算法是根据达尔文的进化论，模拟自然选择的一种智能算法，“适者生存”是它的核心机制。遗传算法是从代表问题可能潜在解集的一个种群开始的。基于随机早期人口，根据的原则，优胜劣汰，适者生存，世代演化产生更好的人口大概。在每一代，根据问题域的个体适应度大小来选择个人，然后选定的个人在自然遗传学，遗传算子组合交叉和变异，产生代表性的解集的人口 。通过这些步骤，后生代种群比前代对于环境具有更好的适应性。人口最优个体解码后可作为近似最优解。

（二）遗传算法的特点

作为一种智能算法，遗传算法具有如下特点：①遗传算法在寻优过程中，只把适应度函数的值作为寻优判据。②遗传算法是由一个问题集合（种群）开始的，而不是从一个个体开始的。故而遗传算法的搜索面积很大，适合全局寻优。③遗传算法根据概率性的变换规则进行个体的优胜劣汰并推动种群的进化。④遗传算法具有隐含的并行性。⑤遗传算法具有自组织、自适应以及内在的学习性，同时遗传算法具有很强的容错能力。⑥遗传算法的基本思想简单。对于复杂的和非线性的问题具有良好的适应性。

（三）遗传算法的应用

遗传算法提供了一个整体框架地址复杂系统问题，它不依赖于俞特定领域的问题，问题的类型、 已是强的鲁棒性，所以广泛应用余许多科学： 功能优化遗传算法的经典应用，是遗传算法的性能评价的常见的例子，许多人建设的各种复杂的表格功能测试： 连续函数和离散函数，凸、 凹函数、 低维功能和高尺寸功能、 单式功能和更多峰值函数。一些非线性、 多模型、 多目标函数优化问题和其他优化方法很难解决，GA 你可以更好的结果。增加问题的规模，搜索空间的组合优化问题，将会迅速增加，有时的当前枚举方法和计算很难找到最佳的解决方案。实践证明，遗传算法、 组合优化问题的粒子非常有效。例如，已成功应用遗传算法解决旅行商问题、 背包问题、 装箱问题、 图形划分问题。此外，遗传算法的生产调度、 自动控制、 机器人技术、 图像处理和机器学习，人工生命，遗传编码，已获得广泛的应用。

二、蚁群算法及其应用

（一）蚁群算法概念

蚁群算法又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法。

（二）蚁群算法的特点

①蚁群算法是一种自组织算法。在早期的算法，单一的人工蚂蚁障碍找到求解算法，久而久之，通过信息作用的激素，人工蚂蚁进化将找到一些解决办法更接近最优的解决方案，它是无序到有序的过程。

②蚁群算法的并行算法是一种基本的。每个蚁群搜索进程独立的对方，只能通过信息素通讯。因此，蚁群算法可以看作是一种分布式的多智能体系统，它在问题空间搜索算法开始是一个独立的解决方案，不仅提高了可靠性，这使得该算法具有强的全局搜索能力。

③蚁群算法是一种积极的反馈的算法。从蚂蚁觅食中不难看到蚂蚁已设法找到最短路径的信息的过程取决于直接上的最短路径的积累，以及信息素的积累是一个积极的反馈过程。这种正反馈的过程进行初步的差距有不断扩大，并导致系统的最优解的方向发展。

④蚁群算法具有较强的鲁棒性。比较与其他算法、 蚁群算法、 初始对齐要求不高，外务大臣蚁群算法用于路由和搜索过程的初步结果不需要手动调整。第二，设立简单、 便于应用的蚁群算法求解组合优化问题的蚁群算法参数的殖民地，数目。

（三）蚁群算法应用

蚁群算法应用包括：二次分配问题、车间任务调度问题、车辆路线问题、机构同构判定问题、学习模糊规则问题、旅行社新旅游线路与旅行产品的制作等领域。

三、神经网络算法

（一）神经网络的概念

人工神经网络也被称为神经网络连接模式，它是一种动物模型，神经网络的行为特征，分布式并行处理算法的数学模型。网络依赖于复杂的系统，通过调整内部之间的联系，大量节点，以实现节能的目的，信息处理。

特征的神经网络模型的人工神经网络的主要网络连接拓扑，神经元的特点，学习规则。目前，近40种神经网络模型，其中有一个BP网络，传感器网络，自组织映射，神经，波尔兹曼机，自适应共振理论。系统的稳定性与联想记忆功能密切相关。

神经网络的应用

人工神经网络的非线性自适应信息处理能力，克服了传统人工智能方法的直觉，作为模型，语音识别，非结构化信息处理方面的缺陷，使神经网络专家系统，模式识别，智能控制，组合优化，预测等领域得到成功应用。人工神经网络和其他传统方法相结合，将促进人工智能和信息处理技术的发展。近年来，人工神经网络模拟人类认知方式更深入的发展，模糊系统，遗传算法，进化机制相结合，形成智能计算，人工智能，已成为一个重要的方向，在实际的应用开发。信息几何学应用于人工神经网络的研究，人工神经网络理论开辟了一条新的途径。

路径规划篇6

Key words:distribution regional division; distribution vehicle routing optimization; algorithm

0 引 言

流通领域中,许多物流配送企业借助外部经济的发展,实现了规模扩张与快速发展,但对如何控制成本,提高运营效率的迫切性并不强。现在随着经营环境的变化,物流需求量更大,客户、网络更复杂,对服务的要求更多样化。但面临的竞争更加激烈,不管是从事跨区域配送还是城市配送,首先需要考虑顾客服务水平,赢得客户的认可,然后考虑配送运营的成本问题,因而如何创新物流服务,提高运营效率和控制日常运营成本成为每个配送企业需要时刻思考的问题。

传统的基于经验的方法,在企业规模有限,客户数量不是非常多,配送网络相对简单的情况下,只要员工和管理者技能过关,执行力好,都应该能够较好地完成配送任务,获得企业的发展。但是随着销售区域扩大,客户数量的不断增加,客户需求持续增长,配送业务量大增,配送周期缩短,配送线路更复杂,并且需求的随机性、变动性加大,光凭经验和手工安排,已无法做到配送计划的优化,必须借助于统计分析、利用数学模型和智能算法,才能获得较好的配送计划,节省时间,提高效率。本文就是针对这些问题,从企业应用的角度,提出先合理划分配送区域,再优化配送路线的方法,从而达到降低成本,提高竞争力的目标。

1 论文总体思路综述

排单和车辆调度是整个配送计划和作业实施的核心,是配送任务和客户服务按时完成的有力保证。

传统的订单排单和车辆调度、路线安排都是由公司里业务能手来完成,送货区域大了,客户多了,这项工作的效率和完成工作的成本控制都会不理想,现在常用的智能优化方法,把它作为一个典型的VSP问题,建立数学模型,利用智能化的算法,求解可行的配送路径规划,作为理论研究,这样的做法是有意义的。但是有两个问题:(1)这个模型数据的收集整理工作量特别大,计算过程也较长,因而成本不会低。(2)模型本身一定要适合实际的作业过程,这就需要有一个不断测试和优化的过程,并且还要适应每天的动态变化,否则反而会影响到日常的作业过程。许多研究理论完备、精深,但是在适应产业化运营时,工程上的可实现性还有待提高和完善。因而影响了这些很有价值的研究在企业实际中的运用。

本文的研究并不针对配送路径规划做理论上的深究,而是立足实际应用,在可接受的范围内,利用较简易实用的智能优化方法,在较短的时间内,以较低的成本获得相对优化的配送路径规划方案。不求最佳,但求有效。为今后电子排单和送货线路优化软件的开发和应用作必要的铺垫。

具体设想:第一步,利用聚类分析法对配送区域进行合理分区,先把复杂问题简单化。第二步,每个分区内就是个典型的TSP问题,有很成熟的解决办法。在平衡好各分区工作时间安排后,就能很快获得较理想的配送方案。

重点是第一步,分区时一定要考虑到客户位置、需求量、车辆载重、作业时间均衡限制等因素,需要花费好多功夫。

2 配送区域动态优化及其方法

2.1 配送区域的初始划分方法。配送区域优化方法对最终优化的结果有很大的影响,因而合理的划分方法的选择十分重要,目前常用的划分方法有扫描法和聚类算法,在配送客户有限、区域较小时运用扫描法就可以了,但是当客户数量很多,区域较大,又要考虑约束条件时,聚类算法就是我们必然的选择了,聚类算法中K- means比较成熟,操作简单,原理是:把大量d维(二维)数据对象n个聚集成k个聚类k 在运用聚类分析法时有几个问题要注意:第一,k的选择,以一天送货总量/单车载重量,也可以放宽一些,到:一天送货总量/单车载重量+1。第二,k个聚类内的密度,分区密度大,效率高,成本低。第三,每个分区内工作时间大体相当,这样便于运行的稳定,进行成本控制和人员、车辆的考核。第四,每个聚类间不重合。做到这样分区效果会比较好。

传统的K-means聚类法,k个聚类区内,初始点是随机产生的,运行时间长,收敛效果差。基于均衡化考虑,在配送对象分布不均匀时,用密度法效果较好,初始中心点以密度来定义,运用两点间欧氏距离方法,求解所有对象间的相互距离,并求平均数,用meanD表示,确定领域半径R,n是对象数目,coefR是半径调节系数,0 coefR=0.13时,效果最好。如果使用平均欧

氏距离还不理想,可增加距离长度,甚至用最大距离选择法,收敛速度比较快。 在配送对象分布较均匀时,可考虑用网格法,效果较好,整个配送区域划分用k=Q/q,k为初始点个数,假设k=mn,将地图划分成m行n列,以每格中心点为初始点,通过网格内的反复聚类运算,达到收敛,获得网格稳定的聚类中心。

2.2 分区内配送工作量的均衡。这样就完成了配送区域的初步划分,但是没有考虑各个分区内工作量的均衡问题,如果工作量不均衡,对于客户服务水平的保证,成本的控制,作业的安排,人员、车辆的考核都存在问题。

在实际的物流企业配送作业过程中,一般一辆车一天也就送货10多家或20来家,多余的时间要用于收款,与公司财务部门交账,核算出车相关费用,所以不考虑同一车同一天出车多次的情况,多次出车待以后深入探讨。那么就意味着每个分区就是一辆车一条线路,把问题大大简化了,需要说明的是:这种方法对于配送规模不是特别大的单个城市配送是适用的,也具有广泛性。

各分区内的每日配送工作量是以配送作业耗用时间来衡量的,耗用时间有两部分构成:(1)车辆行驶时间;(2)客户服务时间。由于配送分区有限,每个分区内的客户数量不是很多,可以采用实地测时的方式,把每条线路的配送时间统计出来,这是一种手工办法,但比较符合实际来调整超过差值的分区内的客户,从而使得各区作业时间基本均衡。

如果客户数量众多,分区也较复杂,就需要借助统计学方法,通过对样本线路车辆行驶时间以及服务时间,拟合出分区作业时间函数,然后,计算出所有线路作业时间,即使分区重新调整,线路重新组合,仍可以很快计算出线路作业时间。本文不在这个方面进行深入探讨。

2.3 重新组合客户,确定最终区域划分。观察各线路作业时间超过允许差值的部分,由大到小来调整,将离聚类中心最远的数据点弹出,使本区T值下降,直至在差值以内,将弹出点加入到临近的不足均衡作业时间的分区内,如果临近分区作业时间超过允许差值,这个点就不能弹出,只能弹出另外的次远数据点,以此类推,任何一个数据点只能弹出一次,直到所有数据点和分区调整完毕。

这样最终确定的分区,既能做到区域划分紧密,效率、成本更低,又能做到各区作业时间均衡,便于工作指派,车辆、人员核算。

以上是本文的第一部分工作,也是最有意义的工作,确定好合理的区域划分,不仅是配送作业合理化的重要步骤,也是业务人员访销工作和客户服务的重要依据。

3 基于改进蚁群算法的分区线路优化方法

分区内线路安排,就是一辆送货车由DC出发,依次经过分区内每一个客户点,完成送货后返回DC,求出近似最优的行车顺序,这是个典型的旅行商问题(Traveling Salesman Problem,TSP),TSP是NP完全问题,解法很多,有精确算法,也有启发式算法,目前许多智能算法就属于启发式算法,可以解决较复杂的线路优化问题,对于一般线路优化也能做得更准确,这里介绍蚁群算法解决实际问题。原因是蚁群算法与其他启发式算法相比,在求解性能上,具有较强的鲁棒性和搜索较好解的能力,是一种分布式的并行算法,一种正反馈算法,易于与其它方法结合。克服基本算法缺点,改善算法性能。

3.1 蚁群算法简介。蚁群算法(Ant Colony Algorithm, ACA)是由意大利学者M.Dorigo等人于20世纪90年代初提出的一种新的模拟进化算法,其真实地模拟了自然界蚂蚁群体的觅食行为。 M.Dorigo等人将其用于解决旅行商问题TSP,并取得了较好的实验结果。

蚁群算法用于解决优化问题的基本思路是:用蚂蚁的行走路径表示待优化问题的可行解,整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素数量较多,随时间推移,较短路径上积累的信息素浓度逐步增高,选择该路线的蚂蚁数量也越来越多,最终整个蚂蚁会在正反馈的作用下集中到最佳线路上,这个路线就是最有解。

蚁群算法解决TSP问题具体步骤:(1)基本参数设置:包括蚂蚁数m,信息素重要程度因子0≤α≤5,启发函数重要因子1≤β≤5,信息素消逝参数0.1≤ρ≤0.99,信息素释放总量10≤Q≤10 000,最大迭代次数iter_max,迭代次数初值iter=1。用试验方法确定α、β、ρ、Q值,以获得较优的组合,有助于改进基本蚁群算法,提高整体优化效果,并缩短运算时间。(2)初始解的求解:利用最近邻算法,以缩短算法运算时间,并以此算法产生初始解的路径长度作为产生初始信息素的基础。 (3)构建解空间:将各个蚂蚁随机地置于不同出发点,对每个蚂蚁,按公式(1)计算其下一个待访问的网点,直到所有蚂蚁访问完区域内所有网点。(4)更新信息素:计算各个蚂蚁经过的路径长度Lk=1,2,…,m,记录当前迭代次数中的最优解。同时,根据(2)式和(3)式对各个网点连接路径上的信息素浓度进行更新。(5)判断是否终止:若iter 蚁群算法如结合其他启发式算法,建立混合算法,能够解决许多现实问题,达到较好运算效果,结合具体问题,可以深入研究。

4 本文的局限与进一步研究的方向

路径规划篇7

    关键词:农民工;职业生涯规划;路径

    浙江是一个劳务输入大省,温州也是一个劳务输入比较集中的城市。2005年起温州市政府把到温州务工的农民工称为“新温州人”,充分体现了政府号召人们对进城务工人员的认可和尊重,从思想观念上消除对农民工的歧视和偏见,切实让农民工享有平等待遇。据温州市公安局统计,2008年12月,温州市公安局对外公布全市登记在册的外地暂住人口为3 396 053,主要以湖南、湖北、贵州、江西、安徽、四川等省,暂住人口中务工的为3 135 307人,从事服务业的58 805人,务农的24 250人,温州已经成为创业的第二故乡。温州对农民工有着巨大的吸引力,温州的发展也同样离不开农民工。

    一、职业生涯规划内容

    随着越来越多的农民工朋友进入到城市里展开个人的城市生涯,每个人都要借助于谋求职业而实现自我的发展。职业生涯规划,简称职业规划,就是对个人的职业历程乃至整个一生进行持续的、系统的、规划性的设计的过程。从个人角度和企业角度,职业生涯规划又划分为两个方面的内容:

    1.个人职业生涯规划:企业中的大多数员工,其中包括受过良好教育的员工,都有从自己现在和未来的工作中得到成长、发展和获得满足的强烈愿望和要求。为了实现这种愿望和要求,他们不断地追求实现职业的理想,能主动根据个人的特点、企业发展的现实和社会发展的需要,制定自己的职业规划。

    2.企业员工职业生涯管理:在广大员工希望得到成长、发展的强烈要求推动下,企业人力资源管理部门(或人事部)为了更好地开展工作,在了解员工个人的特点,成长和发展的方向及兴趣的基础上,通过一些宣传、教育和咨询等活动,帮助员工制订有关个人成长、发展的计划以及与组织需求和发展相结合的计划,不断地增强他们的满意感,并使他们与企业组织的发展统一协调起来。可见,职业生涯规划既要体现员工发展的需要,又要体现企业发展的需要,是员工个人发展与企业发展的一种协调与相融。

    二、农民工做好职业生涯规划的意义

    职业生涯规划对所有工作年龄的人来说都很重要,在人一生的历程中,需要靠职业来生存和发展。每个人都需要规划好自己的职业生涯,主动去把握它、迎合它、顺应它才是生存之道。有些农民工朋友会说,职业生涯规划,那是大学生的事,我们居无定所,四处漂泊,生活如无根的浮萍,天天生活在变化中,甚至工作有没有着落也不清楚,还需要做职业生涯规划吗?实际上这样的看法并不在少数,正是由于存在这样的观点,很多农民工朋友的城市生活才没有更多的长进。离开家乡进城工作,可不能像当年游击队一样,打一枪换一个地方,如果没有合理的、长远的、多方面的规划,就无法进一步实现个人的职业理想和生活理想。那么怎样看待农民工做职业生涯规划这个问题呢?

    1.从社会的角度看。每年一度的春节,大量的农民工返乡,春节过后又有大批农民工进城,在上亿的劳动力大军流动过程中,许多人完成了一年的职业劳作,来年又重归游离的状态,不能也无法重新回归从前的单位,也不能从事原先的职业。于是乎,大量的人力资源耗费在等待、煎熬、徘徊和痛苦之中。这中间有很多原因是由于农民工朋友在自己进入城市之后,没有对自己能做什么,个人想要什么,有什么基础,个人发展的方向是什么等问题,做深入、系统的分析和探讨而造成的。农民工朋友做好自己的职业生涯规划,有利于建立科学的择业观,提高就业的成功率,还可以减少失业、被辞职的情况,从社会角度来看对降低就业压力是有较大帮助的。因此,农民工朋友做职业生涯规划是社会现实的需要。

    2.从企业发展的角度看。长期以来,由于中国拥有巨大的劳动力资源优势,整个劳动力市场呈严重的供过于求的状态。大量进城务工人员一方面为企业提供了大量的廉价劳动力,另一方面上到国家、下到企业都逐渐产生了员工流动和使用的依赖,中外企业招聘员工一般不用发愁。但是,目前大多数企业对待农民工劳动力,都是重在使用而轻视培养,重视招聘新员工而轻视已有劳动力的再提高,更不用说对员工进行职业发展规划和技能提升。实际上,企业员工缺乏职业安全感和职业发展需求的满足感,员工的安心工作就会出现波动,企业发展就会有隐患。如果农民工劳动力资源没能及时有效地得到规划、开发与储蓄,大部分农民工很可能将永久性地退出劳动力市场。为了农民工的“再出发”与产业的“再发展”,就必须做好劳动力供给的“蓄水池”,进行科学的职业发展规划与开发。

    3.从个人发展的角度看。从个人的角度来讲,农民工朋友绝大多数原来是在土地上从业的农民,由于寻求个人的发展等动力促进,离开了自己熟悉的家乡,来到全新的城市环境里,谋求有所发展,但是如果个人在进入城市职场之前,对自己的未来发展没有规划和目标,那么会对个人的发展造成障碍的。特别对刚刚成长起来的步入城市的年轻打工者(新生代农民工),该用怎样的眼光来看待自己未来的发展道路,将对其一生的成就产生重大影响。农民工做好个人的职业生涯规划,对个人发展的意义主要体现为以下几个方面:(1)做好职业生涯规划,可以分析自我,个人可以准确评价自身的职业能力、性格特点、价值追求、优势与劣势等,在职业竞争中发挥个人优势。以既有的成就为基础,确立人生的方向,提供奋斗的策略。(2)通过职业生涯规划,可以重新安排自己的职业生涯,突破原有生活的局限,塑造全新、充实的自我。即使自己已经进城打工多年,还可以评估个人目标和现状的差距,提供前进的动力。(3)通过职业生涯规划重新认识自身的价值并使其增值。通过自我评估,知道自己的优缺点,然后通过反思和学习,不断完善自己,使个人价值增值。还有助于全面了解自己,增强职业竞争力,发现新的职业机遇。(4)职业生涯规划通常建立在个体的人生规划上,因此,做好职业生涯规划将个人生活、事业与家庭联系起来,让生活充实而有条理。

    三、农民工做好职业生涯规划的路径

    根据职业生涯规划理论,农民工朋友规划自己的职业生涯可以从以下几个方面入手。

    1.评价自我。即审视自己、认识自己、了解自己,做自我评估。自我评估就是对自己做全面分析,通过自我评估才能对自己的职业作出正确的选择,才能选定适合自己发展的生涯路线,才能对自己的生涯目标作出最佳抉择。因此,自我评估是职业规划的重要步骤之一。自我评估包括自己的兴趣、特长、性格、学识、技能、智商、情商、思维方式、思维方法、道德水准以及社会中的自我等内容。也许农民工朋友会说,我没有什么特长,其实不是这样的,每个人都有自己的特长,只是平时没有去挖掘发现而己,仔细分析自己,就会发现原来我还有这样或那样的特长。

    2.评估职业机会。主要分析内外因素对自己职业选择的影响,每一个人都处在一定的环境之中,离开了这个环境,便无法生存与成长。所以,在制定个人的职业规划时,要分析环境条件的特点,

    环境的发展变化情况,自己与环境的关系,自己在这个环境中的地位,环境对自己提出的要求,以及环境对自己的有利条件与不利条件等等。只有对这些环境因素充分了解,才能做到在复杂的环境中避害趋利,使职业规划具有实际意义。农民工要把自己作为一个职业人来了解周围的环境、你所在的地区、你将要就业的行业等,只有清晰掌握周围的环境,才能权衡利弊。

    3.选择职业。通过自我评估、生涯机会的评估,认识自己、分析环境,在此基础上对自己的职业作出选择。也就是在职业选择时,要充分考虑到自身的特点,即自己的能力、性格和兴趣,特别是个人的工作能力,工作能力往往是限制一个人在劳动力市场选择合适岗位的因素。分析自我、了解自己、分析环境、了解职业世界,使自己的性格、兴趣、特长与职业相吻合。通过对自己以往的经历及经验的分析,找出自己的特长与兴趣点。选择职业重要的是能正确地分析自己,找到自己最适合做的专业,然后努力成为本行业的佼佼者。职业的选择决定以后的成长道路,所以每一位农民工朋友千万不要简单的认为找一份工份就是自己以后的职业,随意从这个工作跳到那个工作,这里不行就到那里。对待自己的工作选择要慎重。

    4.制订职业计划。在做个人职业发展计划的时候,要考虑你所选择的工作,能否帮助你实现人生的最终目标?你是否有办法可以让你现有的职业与你的人生基本目标一致起来?简单的说,就是你希望在多少年之内达到什么目标,根据这个目标我又该怎么做?通常在制订职业计划时,先制定一个长期目标,然后把长期目标分解成一个个短期和中期目标,这样对于每一个短期目标就会变得贴近生活、容易达到。

    5.实施行动。开始行动,这是所有生涯设计中最艰难的一个步骤,因为行动就意味着你要停止梦想而切实地开始行动。如果想法不转换成行动,就是一纸空文,目标也只能停留在梦想阶段。如果你想成为一个电工或家政人员,当你制定职业规划后就立即行动起来,你可以参加政府提供的免费技能培训,针对大量需要培训的农民工,政府每年都会提供大量的资源为农民工进行多种形式的免费培训的,那农民兄弟们可以充分利用这些机会,提升自己的能力。立即行动,无论你是处于刚刚踏上职业路途的年轻人,还是40岁左右并且正陷在一份你不喜欢的工作之中的中年人,现在都是你进行职业规划的好时机。只要你还没有到安享晚年的地步,任何时候开始你的职业规划都不为晚。

    参考文献:

    [1]邹树新.中国城市农民工问题[M].北京:群言出版社,2007.

    [2]陆汉洲.聚焦中国民工[M].北京:中国经济出版社,2005.

    [3]沈立人.中国农民工[M].北京:民主与建设出版社,2005.

    [4]隋光明.中国民工调查[M].北京:群言出版社,2005.

路径规划篇8

Abstract： The current traffic situation makes people feel the excessive congestion， frequent accidents， exhaust emissions， energy supply imbalance and other issues， which has become an inevitable obstacle in economic sustainable development. Intelligent transportation is a information revolution of solving the problem of traffic. the optimal dynamic path planning strategy as an important issue in intelligent traffic network information management system， is worthy of study. This paper established the dynamic mathematical model of single vehicle， used vehicle planning algorithm based on period， effectively avoided the traffic road， reduce vehicle travel cost， improve the real-time effect and accuracy of the vehicle path planning.

关键词： 智能交通；动态路径规划；A*算法

Key words： intelligent transportation；dynamic path planning；A* algorithm

中图分类号：U495 文献标识码：A 文章编号：1006-4311（2013）33-0182-02

0 引言

在智能交通道路网中，一方面当交通实时周围信息不能得到有效的反馈时，车辆的路径规划只能依据车载交通路网的电子地图进行道路静态路径规划；另一方面，在能够采集道路交通信息，并能够对正确的道路交通周围情况进行信息反馈，可采用车辆的动态最优路径规划，这也是智能交通工程科研领域研究的热点问题。车辆行驶的动态路径规划比静态路径规划更能够体现车辆行驶过程中状态的可信性、实时性及准确性[1]。

1 单车动态路径规划数学模型

对于最优道路路径规划策略的研究上来说，道路口节点和路径就可以对智能交通网进行数学逻辑上的描述，这一个基本的数字路网模型图可以表示为：

G=（N，R，f）N={n1，n2，n3，…}ni=（xi，yi）R={r1，r2，r3，…}f：f（ri）=f（nj，nk）（1）

式中：G为智能交通道路的基本电子路网模型；N为道路网络路口节点的集合，ni为表示道路路网的任意一个节点，xi，yi为该任意节点的横和纵坐标；R为道路路网层路径的ri集合，为道路路网任意一段路径，f为两个道路口节点之间或任意一条道路径的权重值。

依据智能交通原始电子地图，创建交通路网的空间拓扑结构相图G，以此为基础建立动态路径规划数学模型，模型具体描述如下：

1.1 模型建立的假设条件：①忽略交通网交通状况传感器检测的基本误差值；②智能交通网中的动态交通路况信息更新时间T，符合道路交通信息变化和动态路径规划时间需求；③智能交通网的实时交通信息流，能实时上传到交通网中心路径规划平台和车载路径规划端。

1.2 建立数学模型 ①智能交通路网动态实时信息的R（G，t）周期时间T内，认为动态交通信息没有改变。R（G，t）可采用离散数学方式进行描述，R（G，wi），式中wi为周期时间数值为i×T时刻的交通网状态信息。在周期时间T内，由于当前的交通路况信息不变及道路阻抗不变，可应用车辆的静态路径规划算法。

②智能交通网中的动态道路阻抗函数确实。假设车辆行驶路段的实时交通平均车流速度，由安装与城市出租车上的GPS近似估算。取动态道路阻抗为车辆行驶路段的平均动态行驶时间为：tij=■（2）

式中dj为道路路径的长度；vij为GPS计算获得的第i个周期T的行驶车辆行驶在j道路路径上的车流量平均速度。

③车辆道路路径规划的价值函数。在车辆的动态最优路径规划中，不能同静态路径规划的价值函数一致，即目标函数上不能选取动态交通信息中的最短路径。通常选择车辆行驶的最短路径时间为目标函数，根据智能交通网的道路交通方式不同，动态路径规划的价值目标函数即不同。

2 基于周期的单车辆规划算法

该算法的难度系数与车辆行驶工程中，实时交通信息的更新频率有关。设经过N次交通信息的更新，计车辆的动态路径规划为N+1。每一次动态道路路径的规划，应用A*算法，则算法的难度系数计算累加公式为：

（N+1）O（bx）=O（（N+1）bx）（3）

式中b为道路口节点的均值路段数，d为始末节点的查询深度指标。算法的计算量较大，但是平均分配在车辆行驶过程中的每一个阶段，则计算量将减少。同时N可以根据具体的时间交通道路信息，进行必要的调整。基于周期的单车动态路径规划算法流程图如图1所示。

3 实验研究

将智能交通道路的交通状况分为1，2，3，4四个等级，等级越高，表示拥挤现象越严重。图中黑色标记的上三角形为车辆行驶过程中的起点，下三角形为车辆行驶过程中的末点。黑线为车辆的行驶过程中的交通堵塞路径。实验的过程是，在车辆行驶的路径过程中，设置交通状态管制信息，对于实时的当前交通信息，进行新的路径规划。图2车辆行驶过程中，改变当前的交通信息，设置黑线为交通堵塞路径，重新进行的路径规划，图3是车辆行驶过程中，设置的道路拥挤的情况，新的最优路径规划，对该交通堵塞道路口节点，进行了绕行，最终车辆到达了行驶者设定的末点。

4 结论

基于周期的单车动态路径规划算法，有效实时的规划车辆行驶道路路径，可以对交通实时增加的交通堵塞，进行绕行，能够降低对车辆行驶者的出行成本，由于是基于一定周期的自主车辆规划算法，在基于交通路径规划的中心式处理系统中，不会出现计算、处理上的不可控，并能够有利于中心的处理器进行有效的计算。该算法的优势就是在于能够充分使用系统的计算资源。根据申请导航的车辆数量，进行算法的有效更变频率，满足了车辆行驶过程中的实时性要求，同时能够产生相应控制的系统自适应性及鲁棒性。算法的不足之处就是未对车辆行驶过程中，对交通道路的影响进行考虑。

参考文献：

[1]胡金星，刘允才.面向动态导航的城市路网实时交通信息服务系统研究[J].交通与计算机，2005（06）：49-52.

[2]毕军，付梦印，周培德.基于城市道路网的快速路径寻优算法[J].计算机工程，2002，28（12）：36-38.

[3]仝秋红，赵忠杰.汽车驾驶智能化中路线规划及导航的最佳路径求解法[J].西安公路交通大学学报，1999，19（03）：87-90.

路径规划篇9

机器人路径规划问题一直是机器人学的一个重要研究课题. 也是目前研究的热点领域。机器人路径规划问题是指在有障碍物的工作环境中， 如何寻找一条从给定起点到终止点的较优的运动路径， 使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物， 且所走路径最短.本质是多约束多目标的最优化问题[1]。

采用智能优化算法求解航迹规划问题是目前使用的主流方法。文献[2]中，蚁群算法的机器人路径规划需要存储的信息多，在搜索过程中易出现停滞现象或陷入死循环;文献[3]中的人工势场法虽便于底层的实时控制，但缺乏全局信息，存在局部最优值的问题;文献[4]中，模糊推理法最大的优点是实时性非常好， 但是模糊隶属函数的设计、模糊控制规则的制定主要靠人的经验。遗传算法[6]已证明是一种全局搜索能力强的算法，具有强的鲁棒性，并行性，但大量实验结果表明，应用标准遗传算法对该问题求解时局部寻优精度较差，稳定性不好[6]。

对此，本文提出一种改进遗传算法的机器人路径规划方法，并进行了仿真实验，结果证明了该方法是有效可行的。

路径规划篇10

关键词：移动机器人 未知环境 路径规划 矢量场

0 引言

当前移动机器人在生产车间、抢险救灾、资源勘探、医疗服务等领域得到了广泛应用，在诸多机器人技术当中，路径规划技术是移动机器人成功走向应用的关键技术，因此该项技术的研究得到了广泛关注。所谓路径规划就是指移动机器人按照某一性能指标（如距离、时间、能量等）搜索一条从起始状态到目标状态的最优或次优路径[1]。

为了解决该问题，经过多年的发展，已经涌现出了许多有效的求解方法[2]，诸如可视图法[3][4]、人工势场法[5]、自由空间法[6]、遗传算法[7]等。但是已有算法不同程度都存在一定的局限性，诸如环境依赖性强、算法复杂、效率不高等，尤其对复杂未知工作环境，有些路径规划算法甚至无法求解，因此本论文提出了矢量场法用于移动机器人的路径规划，该方法对环境依赖程度低，能够有效的进行复杂未知环境下的路径规划，并且程序易于实现。

1 矢量场法简介

矢量场法严格意义上说是一种人工势场法的变异，传统人工势场法利用障碍物和目标产生势能，给机器人进行导航，主要应用在全局环境已知的情况下进行路径规划，而矢量场法则是利用机器人自身传感器测出障碍物的距离以及目标距离，继而产生虚拟势能进行导航，因此可以用于复杂未知环境的路径规划。

本文以载有五个测距传感器并以45度夹角布置的移动机器人为例介绍该方法。为了便于阐述，将机器人近似成一质点，如图1-1中心黑点所示。移动机器人使用该法进行路径规划时，首先通过测距传感器获取周围障碍物的距离值，再将这些距离值转化成对应的排斥力，其大小为关于距离值的函数。移动机器人运动的目标位置产生一个吸引力，最终这些力的合力方向形成移动机器人的运动方向。

图1-1为某时刻移动机器人在某点处测距传感器测得周围障碍物的信息，障碍物的位置向量使用灰色实线标出，而其表现出的斥力用黑色虚线表示，最终这些虚拟斥力合成合斥力Fobs，图中用点线标注。

矢量场生成的力是关于距离的函数，障碍物离机器人越远，相应产生的虚拟力也就越小，其对机器人移动方向的影响也就越小，生成的斥力可由下列公式求得。

最终的合力是由合斥力和引力合成，该合力可以通过公式1-2求出，此时合力的方向便是当时机器人航向。

2 实验

为了验证算法的可行性，借助Matlab对矢量场法用于移动机器人路径规划进行仿真。实验中使用的地图为大小4000×4000的栅格地图，每栅格尺寸对应1mm，搭建好的地图如图2-1所示，地图布局模拟了实际办公室一角布局，对于移动机器人该地图信息是未知的。

根据地图信息，确定起始坐标和目标坐标分别为（-640，-1600）和（-680，1600），同时设定测距传感器最大测距范围为500mm，斥力和引力的权值w和w根据情况，初定为w=1、w=5进行实验，实验进行过程中根据权值w和w的不同，进行多组实验，寻找最优权值。最终经过对比发现当w=1、w=3时，此时移动机器人在地图中路径规划效果最好。图2-2即为此时机器人运行的轨迹，图中连续线条为机器人运动路径，周围不规则的圈为测距传感器测得的周围障碍物情况。通过仿真，可以看出移动机器人利用矢量场法在未知复杂环境下能够进行有效的路径规划，同时合适的引斥力权值则能够进一步优化路径。

3 结论

论文对未知工作环境移动机器人路径规划问题进行了研究，鉴于已有算法在未知复杂环境中的一些局限性，提出了利用矢量场法进行路径的实时规划，该方法对环境依赖程度低，算法简单，程序易于实现，仿真实验结果验证了移动机器人利用矢量场法在未知复杂环境下进行路径规划的可行性，并且表明合适的引斥力权值能够进一步优化规划路径。

参考文献：

[1]李磊等.移动机器人技术研究现状与未来[J].机器人，2002（5）：475-480.

[2]康亮.自主移动机器人运动规划若干算法的研究[D].南京：南京理工大学，2009.

[3]李大东，孙秀霞，彭建亮，孙彪.基于可视图法的改进Dijkstra算法[J].电光与控制，2010，17（3）：40-43.

[4]李劲松，颜国正，吕恬生，宋立博.一种移动机器人全局路径规划新方法[J].机械设计与研究，2009，25（3）：30-32.

[5]张建英，赵志萍，刘暾.基于人工势场法的机器人路径规划[J].哈尔滨工业大学学报，2006（8）：1306-1309.

[6]朱明华，王霄，蔡兰.机器人路径规划方法的研究进展与趋势[J].机床与液压，2006（3）：5-8.