时间：2023-01-02 06:18:34
引言：易发表网凭借丰富的文秘实践，为您精心挑选了九篇路径规划范例。如需获取更多原创内容，可随时联系我们的客服老师。
关键词 自动泊车；最佳泊车路径
中图分类号：TP182 文献标识码：A 文章编号：1671—7597（2013）041-184-01
经过一百二十多年的发展，汽车逐渐向小型化、智能化和安全化的方向发展。而随着我国经济的发展，汽车的需求量逐年递增。于此同时带来的问题是停车位需求量越来越大。而在国内，城市占道停车不但能有效的满足停车位的需求，而且能有效缓解交通堵塞。但是，对于许多驾驶员而言，顺式驻车通常是驾驶员考试中最令人担心的一项，而且几乎每个人都会在某些地点碰到这样的事情。大城市停车空间有限，将汽车驶入狭小的空间已成为一项必备技能。 很少有不费一番周折就停好车的情况，特别是城市占道停车可能导致交通阻塞、神经疲惫和保险杠被撞弯，占道停车成为了一种痛苦的经历。
在实际泊车中驾驶员的视野狭隘，仅通过后视镜来观察车身后面和车周围的情况，即使如此，也很难准确的把握车尾的情况。不仅如此，驾驶员还要兼顾控制方向盘、油门、刹车和换挡等，易造成操作失误。如果停车时间过长，又容易造成交通堵塞，特别是驾车新手，在缺乏经验的情况下，很难准确停入车位。
基于以上问题，寻找到了最佳泊车路径，以解决广大驾驶员泊车难的问题。
1 自动泊车最佳路径规划
最佳路径虽然可以通过数学建模和泊车经验等方法得出，但可靠性低，运算复杂，而且变量较多，如果通过CAD与Pro/e等绘图软件模拟其几何路径，则可节省多处计算而且能简洁直观的表达。使用CAD绘图软件寻找最佳路径，主要是通过一些相关约束条件和泊车要求绘制最佳几何路径。
1.1 泊车危险点与安全圆
倒车最难在于兼顾控制车辆的时候，难以观察自己车辆是否与其它车辆相撞，经过分析可知，倒车时，最容易触碰的地方是尾部的后对角点和前部的前对角点。根据避免碰撞要求，可以在停车前方的最佳停车位上的对角点绘制一个以汽车前轮轴中点与对角的距离为半径的圆R1，圆R1称为安全圆。
汽车行驶的轨迹为一个个圆弧构成的圆，由此可知，只需要其自动泊车轨迹与安全圆相离或者相切就不会与前方车辆相撞，而后对角点只需控制其倒车行程即可避免碰撞。
1.2 泊车关键圆的确定
自动泊车进入车位是关键阶段，把倒入车位的大圆称为关键圆。首先可以认为轴距是其轨迹圆的一根弦，经分析可知，此圆越大，倒入车位后此弦与水平线所成的夹角a也就越小，泊车就越准确，泊车后需要调整的角度就越小，因此假设关键圆R2与R1相切，且与车位中线相切时可取最大圆，由于与R1安全圆相切，所以能保证两个对角点不与其他车辆发生碰撞，并且有足够的空间可以进行泊车后的角度调整。
由CAD模拟可以直接测量得出R2=5702 mm，又由汽车参数可知模拟车辆最小转弯半径为r=5500 mm，有R2>r，所以其关键圆R2符合汽车的行驶要求。
1.3 泊车辅助圆的确定
辅助圆是为了帮助车辆倒入关键圆的一段圆弧，使得车辆最终在倒车时能够按照R1的轨迹进入车位。经过分析可知，辅助圆R3越大，越是难以矫正车辆进入关键圆R2，故以最小转向半径5500 mm计算，经过测试调查可知，驾驶员使车辆行驶在车道中间较容易控制，所以把初始位置定在车道中线上，故辅助圆需与行驶车道中线和关键圆R2相切，这样便可以确定辅助圆R3。
另外，考虑到变换轨迹时，车辆是以车身前后轴中心的连线即轴距所构成的弦进入R2轨道，所以，需使R3向左平移，使得R3与R2相割所构成的弦与车身前后轴中心的连线即轴距长度相等。经过CAD模拟和测量可知需使R3向左平移452.3 mm，即可获得R3的最终位置。
1.4 泊车路径总结
如上分析和建模可知，找到了安全圆、关键圆和辅助圆，将其合并在一起，即可得到最佳泊车路径如图1所示。
如上所示，驾驶员需要先将车辆行驶至道路中间，当找到停车位时，驾驶员需要寻找一定的参照，使得车量后轮与车位前方车辆的前轮稍后的地方确定初始位置。首先把方向盘右转至打死，开始倒车，车辆进入辅助圆，当车辆与水平方向夹角大致成50度时，再把方向盘左转打死，直到车辆进入车位，再调整车辆与水平线所成的角度，即可进入最佳车位。
如上所述可得到泊车的完整路径，不容易与其他车辆发生碰撞，并且容易确定泊车的初始位置，所以安全可靠，具有较高的可行性。但是，即使最佳路径也不可能一次性倒入车位。第一次倒入车位后需要细微的调整，由于调整路径比较复杂，其规律性需要从汽车试验中寻找规律，所以调整路径暂不使用模拟CAD得出。
2 泊车最佳路径的验证
选择模拟小车对最佳路径进行验证，模拟小车的实际尺寸与研究对象车辆的实际尺寸比为1：10.47，由最佳路径分析中的CAD模拟路径可知，辅助圆半径为5500 mm，而关键圆半径为：5702 mm。验证过程选择PWM波来控制模拟小车转向，查阅资料可得以上辅助圆应当采用PWM波比值约为900/200，而关键圆应当采用PWM波值为：1100/200，再使用单片机控制PWM波的输出进行实验。最终，顺利验证了最佳泊车路径的可行性和实用性。
参考文献
[1]王芳成.自动平行泊车系统的研究[J].中国科技大学，2010.
[2]周健.嵌入式模糊自动泊车系统的研究[J].广东工业大学，2011.
关键词：分层路网；拓扑结构提取；路径规划；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分层路网拓扑结构提取
关键词：移动机器人；路径规划技术；综述
DOI：10.16640/ki.37-1222/t.2016.21.135
0 前言
移动机器人的实现涉及自动控制、智能、机械等多种学科。它通常被应用在医疗领域、工业领域等方面。从整体角度来讲，移动机器人的应用促进了生产效率的显著提升。路径规划技术是移动机器人的关键技术之一，研究该技术具有一定的现实意义。
1 路径规划技术的作用
将路径规划技术应用在移动机器人中，能够产生的作用主要包含以下几种：
（1）运动方面。路径规划技术的主要作用是其能够保证移动机器人完成从起点到终点的运动。（2）障碍物方面。设计移动机器人的最终目的是将其应用在实际环境中，在实际环境下，移动机器人的运行路线中可能存在一定数量的障碍物，为了保证最终目的地的顺利达到，需要利用路径规划技术实现对障碍物的有效避开[1]。（3）运行轨迹方面。对于移动机器人而言，除了实现障碍物躲避、达到最终目的地这两种作用之外，应用路径规划技术还可以产生一定的优化运行轨迹作用。在移动机器人的使用过程中，在路径规划技术的作用下，机器人可以完成对最佳运行路线的判断，进而更好地完成相应任务。
2 移动机器人路径规划技术综述
移动机器人的路径规划技术主要包含以下几种：
2.1 局部路径规划方面
在局部路径规划方面，能够被应用在移动机器人中的技术主要包含以下几种：
（1）神经网络路径规划技术。从本质上讲，可以将移动机器人的路径规划看成是空间到行为空间感知过程的一种映射，因此，可以利用神经网络的方式将其表现出来。就神经网络路径规划技术而言，首先需要将相关传感器数据当成网络输入，并将网络输出看成是某固定场合中期望运动方向角增量。在这种情况下，原始样本集则可以用不同选定位置对应的数据代替。为了保证样本集数据的有效性，需要将原始样本集中的冲突样本数据以及重复样本数据剔除掉。对最终样本集应用模糊规则，实现神经网络的有效训练。当典型样本学习完成之后，移动机器人对规则的掌握水平发生了显著提升，进而使得移动机器人在产生智能性能的基础上，顺利完成相应运动[2]。
（2）人工势场路径规划技术。这种规划技术是指，将移动机器人在实际环境中的运动过程当成其在虚拟人工受力场中的一种运动。在虚拟人工受力场中，目标终点会对移动机器人产生一定的引力，而该受力场中的障碍物则会对其产生一定的斥力。在某固定算法的作用下，这两种不同的作用力会产生相应的势，进而形成势场。当移动机器人在该场中运动时，势场中的抽象力会作用在移动机器人上，使得其完成对障碍物的有效避开。在人工势场路径规划技术的实际应用过程中，由于结构简单等因素的影响，移动机器人在到达终点之前可能会停留在局部最优点位置上。对此，需要从数学的角度出发，对势场方程进行重新定义，通过这种方式排除势场中的局部极值，继而保证移动机器人运动的顺利进行[3]。
（3）遗传路径规划技术。这种路径规划技术建立在自然遗传机制等理论的基础上。这种技术通过变异、选择以及交叉对控制机构的正确计算程序进行合理编制，进而实现数学方式基础上生物进化过程的合理模拟。当移动机器人的适应度函数为正数时，允许适应度函数具有不连续或不可导特点。由于这种路径规划技术不涉及梯度信息，因此其能够更好地解决移动机器人在实际运动过程中遇到的问题。遗传路径规划技术的应用优势在于，它能够实现跟踪与规划的同时进行，因此，遗传路径规划技术通常被应用在具有时变特点的未知环境中。
2.2 全局路径规划方面
在该方面，可以被应用在移动机器人中的技术主要包含以下几种：
（1）栅格路径规划技术。这种技术是指，在将实际工作环境分成许多包含二值信息的网格单元的基础上，应用优化算法完成最佳路径的规划搜索。在这种规划技术中，其网格单元通常是由八叉树或者四叉树的方式表示出来。在该技术的应用中，栅格的作用是完成相关环境信息的记录。如果栅格中某位置的累计值相对较低，代表移动机器人可以从该位置通过；如果栅格中某个位置的累计值相对较高，则表示该位置存在障碍物，此时，移动机器人需要利用优化算法将该障碍物避开[4]。
（2）可视图路径规划技术。这种路径规划技术是指，将整个移动机器人看成一个点，然后分别将其与障碍物以及目标终点连接起来，上述连线要求为保证所连直线不会碰触障碍物。当所有连线都连完之后，即完成了一整张可视图。在该可视图中，由于起点到目标终点之间的连线都不涉及障碍物，因此上述所有连线都属于有效直线。在这种情况下，需要解决的问题主要是从这些连线中找出一条距离最短的连线。对此，需要应用优化算法将可视图中距离较长的连线删除，这种处理方式能够有效提升移动机器人的搜索时间。
（3）拓扑路径规划技术。这种规划技术是指，将移动机器人的移动范围，即规划区域分成多个具有拓扑特征的子空间，然后利用不同子空间之间的连通性完成拓扑网络的构建。当该网络构建完成后，直接从网络中找出能够使得机器人顺利从起点移动到终点的拓扑路径，将所得的拓扑路径作为参考依据完成几何路径的计算。这种规划技术的劣势主要表现为其拓扑网络的构建过程较为复杂。但这种规划技术可以实现移动机器人搜索空间的有效缩小[5]。
3 结论
路径规划技术主要分为局部规划和全局规划两方面。这两方面分别包含人工势场路径规划技术以及神经网络路径规划技术等。应用这些规划技术之后，移动机器人可以在避开障碍物的基础上，顺利完成起点到终点最优运行轨迹的运动。
参考文献：
[1]朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010（07）：961-967.
[2]张捍东，郑睿，岑豫皖.移动机器人路径规划技术的现状与展望[J].系统仿真学报，2005（02）：439-443.
[3]鲍庆勇，李舜酩，沈`，门秀花.自主移动机器人局部路径规划综述[J].传感器与微系统，2009（09）：1-4+11.
[4]孔峰，陶金，谢超平.移动机器人路径规划技术研究[J].广西工学院学报，2009（04）：70-74.
摘 要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。
关键词：多机器人；路径规划；强化学习；评判准则
Abstract:This paper analyzed and concluded the main method and current research of the path planning research for multirobot.Then discussed the criterion of path planning research for multirobot based large of literature.Meanwhile，it expounded the bottleneck of the path planning research for multirobot，forecasted the future development of multirobot path planning.
Key words:multirobot；path planning;reinforcement learning;evaluating criteria
近年来，分布式人工智能(DAI)成为人工智能研究的一个重要分支。DAI研究大致可以分为DPS（distributed problem solving）和MAS（multiagent system）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术界研究的热点，而路径规划研究又是其核心部分。
机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果[1~3]，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi图法、自由空间法、栅格法、拓扑法、链接图法、DempsterShafer证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划研究比单个机器人路径规划要复杂得多，必须考虑多机器人系统中机器人之间的避碰机制、机器人之间的相互协作机制、通信机制等问题。
1 多机器人路径规划方法
单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径。多个机器人的路径规划侧重考虑整个系统的最优路径，如系统的总耗时间最少路径或是系统总路径最短等。从目前国内外的研究来看，在规划多机器人路径时，更多考虑的是多机器人之间的协调和合作式的路径规划。
目前国内外多机器人路径规划研究方法分为传统方法、智能优化方法和其他方法三大类。其中传统方法主要有基于图论的方法（如可视图法、自由空间法、栅格法、Voronoi图法以及人工势场方法等）；智能优化方法主要有遗传算法、蚁群算法、免疫算法、神经网络、强化学习等；其他方法主要有动态规划、最优控制算法、模糊控制等。它们中的大部分都是从单个机器人路径规划方法扩展而来的。
1）传统方法 多机器人路径规划传统方法的特点主要体现在基于图论的基础上。方法一般都是先将环境构建成一个图，然后再从图中寻找最优的路径。其优点是比较简单，比较容易实现；缺点是得到的路径有可能不是最优路径，而是次优路径。薄喜柱等人[4]提出的一种新路径规划方法的基本思想就是基于栅格类的环境表示和障碍地图的。而人工势场方法的基本思想是将移动机器人在环境中的运动视为一种虚拟人工受力场中的运动。障碍物对移动机器人产生斥力，目标点产生引力，引力和斥力周围由一定的算法产生相应的势，机器人在势场中受到抽象力作用，抽象力使得机器人绕过障碍物。其优点是适合未知环境下的规划，不会出现维数爆炸问题；但是人工势场法也容易陷入局部最小，并且存在丢失解的部分有用信息的可能。顾国昌等人[5]提出了引用总体势减小的动态调度技术的多机器人路径规划，较好地解决了这个问题。
2）智能优化方法 多机器人路径规划的智能优化方（算）法是随着近年来智能计算发展而产生的一些新方法。其相对于传统方法更加智能化，且日益成为国内外研究的重点。
遗传算法是近年来计算智能研究的热点，作为一种基于群体进化的概率优化方法，适用于处理传统搜索算法难以解决的复杂和非线性问题，如多机器的路径规划问题。在路径规划中，其基本思想是先用链接图法把环境地图构建成一个路径节点链接网，将路径个体表达为路径中一系列中途节点，并转换为二进制串；然后进行遗传操作（如选择、交叉、复制、变异），经过N次进化，输出当前的最优个体即机器人的最优路径。遗传算法的缺点是运算速度不快，进化众多的规划要占据很大的存储空间和运算时间；优点是有效避免了局部极小值问题，且计算量较小。
孙树栋等人[6，7]在这方面较早地展开了研究，提出的基于集中协调思想的一种混合遗传算法来规划多机器人路径方法较好地解决了避障问题。但不足的是该方法必须建立环境地图，在环境未知情况下的规划没有得到很好的解决；且规划只能保证找到一个比较满意的解，在求解全局最优解时仍有局限。
文献[8]中提出的一种基于定长十进编码方法有效降低了遗传算法的编码难度，克服了已有的变长编码机制及定长二进制编码机制需特殊遗传操作算子和特殊解码的缺陷， 使得算法更加简单有效。
智能计算的另一种常见的方法——蚁群算法属于随机搜索的仿生算法。其基本思想是模拟蚂蚁群体的觅食运动过程来实现寻优，通过蚂蚁群体中各个体之间的相互作用，分布、并行地解决组合优化问题。该算法同样比较适合解决多机器人的路径规划问题。
朱庆保[9]提出了在全局未知环境下多机器人运动蚂蚁导航算法。该方法将全局目标点映射到机器人视野域边界附近作为局部导航子目标，再由两组蚂蚁相互协作完成机器人视野域内局部最优路径的搜索，然后在此基础上进行与其他机器人的碰撞预测与避碰规划。因此，机器人的前进路径不断被动态修改，从而在每条局部优化路径引导下，使机器人沿一条全局优化的路径到达目标点。但其不足是在动态不确定的环境中路径规划时间开销剧增，而且机器人缺乏必要的学习，以至于整个机器人系统路径难以是最优路径。
强化学习[10，11] (又称再激励学习)是一种重要的机器学习方法。它是一种智能体从环境状态到行为映射的学习，使得行为从环境中获得积累奖赏值最大。其原理如图1所示。
强化学习算法一般包含了两个步骤：a）从当前学习循环的值函数确定新的行为策略；b）在新的行为策略指导下，通过所获得的瞬时奖惩值对该策略进行评估。学习循环过程如下所示，直到值函数和策略收敛:
v0π1v1π2…v*π*v*
目前比较常见的强化学习方法有：Monte Carlo方法、动态规划方法、TD（时间差分）方法。其中TD算法包含Sarsa算法、Q学习算法以及Dyna-Q算法等。其Q值函数迭代公式分别为
TD（0）策略： V(si)V(si)+α[γi+1+γV(si+1)-V(si)]
Sarsa算法： Q(st，at)Q(st，at)+α[γt+1+γQ(st+1，at.+1)-Q(st，at)]Qs′学习算法： Qπ(s，a)=∑Pαss′[Rass′+γVπ(s′)]
近年来，基于强化学习的路径规划日益成为国内外学者研究的热点。M. J. Mataric[12]首次把强化学习引入到多机器人环境中。而基于强化学习的多机器人路径规划的优点主要体现在：无须建立精确的环境模型，简化了智能体的编程；无须构建环境地图；强化学习可以把路径规划、避碰、避障、协作等问题统一解决。
张芳等人[13]提出了基于再激励协调避障路径规划方法，把再励函数设计为基于行为分解的无模型非均匀结构，新的再励函数结构使得学习速度得以提高且有较好的鲁棒性。同时，证明了在路径规划中，机器人的趋向目标和避障行为密切相关，对反映各基本行为的再励函数取加权和来表示总的再励函数要优于取直接和的表示方式，也反映了再励函数设计得合理与否及其确切程度将影响再励学习的收敛速度。王醒策等人[14]在动态编队的强化学习算法方面展开了研究。宋一然[15]则提出了分段再励函数的强化学习方法进行路径规划。其缺点是学习次数较多、效率不高，当机器人数目增加时，它有可能面临维数灾难的困难。所以，基于强化学习的路径规划在多机器人环境下的学习将变得比较困难，需要对传统的强化学习加以优化，如基于人工神经网络的强化学习[16]等。
3)其他方法 除了以上国内外几种比较常见且研究较多的方法外，还有唐振民等人[17]提出的基于动态规划思想的多机器人路径规划，把运筹学中的动态规划思想与Dijkstra算法引入到多机器人的路径规划中，用动态规划的基本思想来解决图论中的费用流问题和路径规划中的层级动态联盟问题。其选择距离邻近法作为联盟参考依据。一个机器人的邻居是指在地理位置上分布在这个机器人周围的其他机器人；与该机器人最近邻的机器人为第一层邻居，第一层邻居的邻居为该机器人的第二层邻居， 依此类推。那么层级越高（即越近)的邻居，它满足协作要求的可能性越大。动态规划算法实质上是一种以空间换时间的技术，它在实现的过程中，必须存储产生过程中的各种状态，其空间复杂度要大于其他算法，故动态规划方法比较适合多机器人的全局路径规划。
孙茂相等人[18]提出了最优控制与智能决策相结合的多移动机器人路径规划方法。其首先构造一个以各机器人最优运动状态数据库为核心的实时专家系统， 在离线状态下完成; 然后各机器人在此专家系统的支持下， 以最优规划策略为基础， 采用速度迁移算法， 自主决定其控制。该方法拥有较好的稳定性与复杂度。焦立男等人[19]提出的基于局部传感和通信的多机器人运动规划框架较好地解决了多机器人路径规划在局部在线规划的系统框架问题。沈捷等人[20]提出了保持队形的多移动机器人路径规划。以基于行为的导航算法为基础，把机器人队列的运动过程划分为正常运动、避障和恢复队形三个阶段。在避障阶段，引入虚拟机器人使队形保持部分完整;当队形被严重打乱时，规划机器人的局部目标位姿使队列快速恢复队形。其算法重点为避障机器人进入避障状态，暂时脱离队列，并以虚拟机器人代替避障机器人。
2 多机器人避碰和避障
避障和避碰是多机器人路径规划研究中需要考虑的重点问题之一。避障和避碰主要讨论的内容有防止碰撞；冲突消解、避免拥塞；如何避免死锁。在路径规划中常见的多机器人避障方法[21]有主从控制法、动态优先法（建立在机器人之间的通信协商上）、交通规则法、速率调整法，以及障碍物膨胀法、基于人工势场的方法等。
目前国内外对于多机器人避障展开的研究还不是很多，比较典型的有徐潼等人[22]以Th.Fraichard的思想为基础，扩充并完善了路径/速度分解方案来协调多机器人，设立集中管理agent进行整体规划，为每个机器人规划路径；并根据优先级规则对运动特征进行分布式规划以避免机器人间的冲突。周明等人[23]提出分布式智能避撞规划系统，将原来比较复杂的大系统转换为相对简单的子系统问题，由各智能机器人依据任务要求和环境变化， 独立调整自身运动状态，完成任务的分布式智能决策体系结构。任炏等人[24]提出了基于过程奖赏和优先扫除的强化学习多机器人系统的冲突消解方法。该算法能够显著减少冲突，避免死锁，提高了系统整体性能。欧锦军等人[25]提出了通过调整机器人的运动速度实现多机器人避碰，将避碰问题转换为高维线性空间的优化问题， 并进一步将其转换为线性方程的求解。该方法的缺点是系统的复杂度较高、计算量太大。
人工势场方法的特点是计算简洁、实时性强、便于数学描述，且适合于多自由度机器人环境，但容易产生抖动和陷入局部极小。为了克服其缺点，景兴建等人[26]提出了人工协调场的方法，在传统排斥力场中增加一个协调力，并将吸引力、排斥力和协调力与局部环境下机器人的运动状态和运动要求结合起来，有效地保证机器人的安全性，提高机器人在复杂动态环境下行为决策的准确性和鲁棒性。
3 多机器人协作和协调机制
多机器人间的运动协调[27~31]是多机器人路径规划的关键，也是多机器人与单机器人路径规划相区别的根本所在。多机器人系统在复杂动态实时环境下，由于受到时间、资源及任务要求的约束，需要在有限时间、资源的情况下进行资源分配、任务调配、冲突解决等协调合作问题，而机器人间的协调与协作，能够大大地提高整个系统的效率和鲁棒性，成为系统完成控制或解决任务的关键。
目前已有的协调方式分为集中式、分布式和混合式三种。在集中式协调中，集中规划器详细地规划出每个机器人的动作，通常的做法是将多个机器人看做一个多自由度的机器人进行规划；而分布式协调规划中，机器人之间进行合作，将一个任务分成多个子任务，根据各自的特点完成不同的子任务，从而共同完成总任务；混合式协调是集中式和分布式混合在一起的形式。
多机器人间典型的协调方法[32]有合同网协议[33]、黑板模型、结果共享的协同方法、市场机制。近年来强化学习在多机器人协作方面也得到很好的应用，陈雪江[32]在基于强化学习的多机器人协作方面展开了研究，提出了多智能体协作的两层强化学习方法来求解在多智能体完全协作、有通信情况下的协作问题。其主要通过在单个智能体中构筑两层强化学习单元来实现：第一层强化学习单元负责学习智能体的联合任务协作策略；第二层强化学习单元负责学习在本智能体看来是最有效的行动策略。陈伟等人[34]提出基于多目标决策理论的多机器人协调方法；通过对环境的拓扑建模，从基于行为的机器人学角度出发，对任务进行分解并设计目标行为，以多目标行为决策理论作为决策支持，从而达到多机器人运动协调的目的。
4 多机器人路径规划方(算)法的判优准则
通常评价机器人路径规划方(算)法的标准文献[35]有正确性、时间/空间复杂度、并行性、可靠性、扩展性、鲁棒性和学习。而多机器人的路径规划除了以上一些衡量标准之外，还需要考虑整个系统的最优化以及机器人间的协调性。
1)正确性 是分析算法的最基本的原则之一。一般来说算法的正确性是指:在给定有效的输入数据后，算法经过有穷时间的计算能给出正确的答案。但在多机器人路径规划算法中，正确性主要指:路径规划算法要生成多个机器人协调运动的无碰安全路径;这条路径是优化的。
2)安全性 一般指多机器人所生成的各路径中节点与障碍物有一定的距离。但在实际的应用背景下，有人认为安全性可以从两个方面来理解：a）狭义地讲，它就是机器人在行走过程中所做的功。在一定的条件下，它与路径长度准则是一致的。b）广义地讲，它是各种优化条件加权综合而得到的结果。
3)复杂度 一个算法的复杂性高低体现在该算法所需要的计算机资源的多少上面。所需要的资源越多，该算法的复杂性越高；反之，所需要的资源越少，该算法的复杂性就越低。算法的复杂性包括时间复杂度和空间复杂度。
在多机器人的路径规划算法中，算法的复杂度分析显得尤为重要。一般地，单机器人路径规划算法的时空复杂度已经颇高，它们的数量级至少是O(n2)；多机器人的路径规划算法不仅是m-O(n2)(即m个机器人路径规划简单地叠加)，它们之间还存在着对运动空间竞争的冲突，面对不断变化的冲突的协调需要花费大量的时间和空间。通常多机器人的路径规划算法与机器人的个数呈指数关系O(km×n2)（k为常数）。这对多机器人路径规划算法的时间/空间复杂度控制是一个很严峻的考验。
4)并行性 算法的并行性从算法设计、编写程序、编译和运行等多个不同的层次来体现。路径规划过程需要大量的计算，当处理的环境比较复杂，机器人工作的环境过于紧凑，尤其是机器人数量很多时，算法的时间/空间复杂度势必会成为算法效率的关键。因此，在算法设计和运行上的并行性是通常考虑的方法。对多个机器人的路径规划尽量采用分布式多进程的规划机制，以实现每个机器人路径规划的并行性。
5)可靠性 把多个机器人及其工作环境看成是一个系统，多机器人处于它们各自的起始点时，称该系统处于初始状态；当它们处于各自的目标点时，称该系统处于目标状态。多机器人的路径规划就是在该系统的这两个状态间建立一串合理的状态变迁。这一状态变迁过程可能会历经许多状态，如果在状态变迁过程中，路径规划算法控制不好各状态间的转移关系，就会导致系统紊乱，出现机器人间的碰撞、找不到路径等恶性后果，使任务失败。所以这就对算法的可靠性和完备性提出了挑战。为了很好地克服这一困难，需要对系统的各种可能状态建模，分析它们相互间的关系，建立有限状态自动机模型或Petri网模型，并以此为指导，按照软件工程的思想，构造恰当的算法输入来对算法的可靠性进行检验。
6)可扩展性 在多机器人的路径规划算法中，可扩展性主要是指一种路径规划算法在逻辑上，或者说在实现上能否容易地从2D空间扩展到3D空间，从低自由度扩展到高自由度，从较少的机器人数到更多的机器人数。可扩展性在各种路径规划算法之间没有一种量的比较标准，只能从实际的具体情况出发、从对环境描述的适宜程度出发、从算法解决这一问题的复杂度出发、从算法本身的自适应出发等来考虑。
7)鲁棒性和学习 鲁棒性对于多机器人系统非常重要。因为许多应用，如路径规划要求连续的作业、系统中的单个机器人出现故障或被破坏，要求机器人利用剩余的资源仍然能够完成任务。学习是在线适应特定的任务。虽然通用的系统非常有用，但将它用于特定应用上时，通常需要调整一些参数。具有在线调整相关参数的能力是非常吸引人的，这在将体系结构转移到其他应用时可以节省许多工作。尤其是多机器人系统中机器人的自身学习和相互间的学习能够大大提高整个系统的效率和系统的稳定性。
8）最优化 对动态环境有优化反应。由于有些应用领域涉及的是动态的环境条件，具有根据条件优化系统的反应能力成为能否成功的关键。
5 结束语
综上所述，国内外研究者在多机器人路径规划取得了一些成果，但是在协作、学习、通信机制等方面仍面临很大的困难和不足。如何进一步提高机器人间的协调性，增强机器人自身以及相互间的学习以提高多机器人系统的效率和鲁棒性都有待深入研究。近年来无线通信技术得到长足发展，但在目前的技术条件下，在多机器人系统中实现所有机器人之间的点对点实时通信还有较大困难，这也是大多数多机器人系统仍然采用集中通信方式的主要原因。因此，如何降低多机器人系统对通信速度的依赖程度也是一个非常重要的问题。
总之，多机器人路径规划设计和实现是一项极其复杂的系统工程，展望其能在结合计算智能方法，如差分进化、遗传算法、粒子群算法、免疫算法、模糊逻辑算法、BP网络、人工势场的改进、模拟退火和环境建模方法等方面取得新的突破。
参考文献：
［1］WEISS G.Multiagent systems:a modern approach to distributed modern approach to artificial intelligence[M].Cambridge， Massachusetts：MIT Press，1999：121-161.
[2]蔡自兴，徐光祐.人工智能及其应用:研究生用书[M].3版.北京：清华大学出版社，2004：124-198.
[3]谭民，王硕，曹志强.多机器人系统[M].北京：清华大学出版社，2005：6-81.
[4]薄喜柱，洪炳熔.动态环境下多移动机器人路径规划的一种新方法[J].机器人，2001，23（5）：407-410.
[5]顾国昌，李亚波.基于总体势减小的动态调度技术解决多机器人的路径规划[J].机器人，2001，23（2）：171-174.
[6]孙树栋，林茂.基于遗传算法的多移动机器人协调路径规划[J].自动化学报，2000，26（5）：672-676.
[7]周明，孙树栋，彭炎午.基于遗传算法的多机器人系统集中协调式路径规划[J].航空学报，2000，21（2）：146-149.
[8]CAI Zixing，PENG Zhihong.Cooperative coevolutionary adaptive genetic algorithm in path planning of cooperative multimobile robot systems[J].Journal of Intelligent and Robotic Systems:Theory and Applications，2002，33(1):61-71.
[9]朱庆保.全局未知环境下多机器人运动蚂蚁导航算法[J].软件学报，2006，17（9）：1890-1898.
[10]SANDHOLM T W，CRITES R H.Multiagent reinforcement learning in the iterated prisoner’s dilemma[J].BioSystems，1996，37(1):147-166.
[11]高阳，陈世福，陆鑫.强化学习研究综述[J].自动化学报，2004，30（1）：
86-100.
[12]MATARIC M J.Interaction and intelligent behavior[D].Massachusetls:Department of Electrical Engineering and Computer Science，MIT，1994.
[13]张芳，颜国正，林良明.基于再励学习的多移动机器人协调避障路径规划方法[J].计算机工程与应用，2003，39（3）：80-83.
[14]王醒策，张汝波，顾国昌.多机器人动态编队的强化学习算法研究[J].计算机研究与发展，2003，40（10）：1444-1450.
[15]宋一然.基于强化学习的多机器人路径规划方法[J].莆田学院学报，2006，13（2）：38-41.
[16]韩学东，洪炳熔.基于人工神经网络的多机器人协作学习研究[J].计算机工程与设计，2002，23（6）：1-3.
[17]唐振民，赵春霞，杨静宇，等.基于动态规划思想的多机器人路径规划[J].南京理工大学学报，2003，27（5）：610-615.
[18]孙茂相，周明，王艳红，等.多移动机器人实时最优运动规划[J].控制与决策，1998，
13（2）：125-130.
[19]焦立男，唐振民.基于局部传感和通讯的多机器人运动规划框架[J].计算机工程与应用，2007，43(17)：89-93.
[20]沈捷，费树岷，郑波.多移动机器人保持队形路径规划[J].东南大学学报，2005，35(3):391-395.
[21]MANSOR M A，MORRIS A S.Path planning in unknown environment with obstacles using virtual window[J].Journal of Intelligent and Robotic Systems，1999，24(3):235-251.
[22]徐潼，唐振民.多机器人系统中的动态避碰规划[J].计算机工程，2003，29(17):
79-81，104.
[23]周明，孙茂相，尹朝万，等.多移动机器人分布式智能避撞规划系统[J].机器人，1999，21（2）：139-143.
[24]任炏，陈宗海.基于强化学习算法的多机器人系统的冲突消解的方法[J].控制与决策，2006，21(4):430-434，439.
[25]欧锦军，朱枫.一种多移动机器人避碰规划方法[J].机器人，2000，22(6):474-481.
[26]景兴建，王越超，谈大龙.基于人工协调场的多移动机器人实时协调避碰规划[J].控制理论与应用，2004，21(5):757-764.
[27]PANAIT L，LUKE S.Cooperative multiagent learning:the state of the art[J].Autonomous Agents and MultiAgent Systems，2005，11(3):387-434.
[28]TZAFESTAS C S，PROKOPIOU P A，TZAFESTAS S G.Path planning and control of a cooperative three robot system manipulating large objects[J].Journal of Intelligent and Robotic Systems，1998，22(2):99-116.
[29]薛宏涛，叶媛媛，沈林成，等.多智能体系统体系结构及协调机制研究综述[J].机器人，2001，23（1）：85-90.
[30]周风余，李贻斌，宋锐，等.基于混合式多智能体系统的协作多机器人系统研究[J].山东大学学报:工学版，2005，35(1):82-87.
[31]夏冰，张佐，张毅，等.基于多智能体系统的动态路径选择算法研究[J].公路交通科技，2003，20（1）：93-96.
[32]陈雪江.基于强化学习的多机器人协作机制研究[D].杭州：浙江工业大学，2004.
[33]SMITH R.The contract net protocol:highlevel communication and control in a distributed problem solver[J].IEEE Trans on Computer，1980，C-29(12):1104-1113.
关键词：企业物资；配送；车辆路径问题；路径规划；里程节约法
一、前言
随着信息技术在现代企业中的广泛应用和高速发展，企业信息化程度大幅提高，企业的许多革命性的创新成果得益于此。在激烈的市场竞争中，仓储配送和信息技术的有机结合为企业带来了新的机遇，建设智慧仓储网络的理念应运而生。而配送作为衔接各个物流节点的关键流程，使仓储网络形成为一个系统性的整体，保证了物资的正常供应。优化配送车辆路径能提高配送效率，降低配送成本，并提升配送准确性。
物资公司作为公司的专业分公司，负责管理在上海区域所有工程及运维检修物资的供应。工程项目物资的供应分为供应商直送现场和仓库供应现场两种类型。其中，供应商直送现场为一次配送，关键点在于供应计划与供应商的有效衔接与调度协同；而利用公司仓储配送网络，通过中心库向各周转库配送以供应现场物资需求的过程为二次配送。合理二次配送车辆路径规划与实施，能提高后续工程建设、运维检修及应急抢修的需求响应速度，增强物资供应的计划性和准确性，可有效提升物资供应管理水平。
二、车辆路径问题定义
车辆路径问题是指存在几个物资需求方，各有一定数量的物资需求，由一个配送中心提供物资，并安排一个车队配送物资。为此需要规划合理的行车路线以使他们的物资需求得到满足，且能在一定的约束条件下，达到路程最短或耗时最少的目标。
公司有十二个周转库，当周转库内某种物资数量低于安全库存时，由中心库提供物资进行补库。由于工程项目对响应速度要求较高，当需要对多个周转库进行补库时，必须综合周转库的地理位置、物资需求量、车辆的运载量、配送次数等，设计出合理的车辆配送路径。
三、配送路径规划意义
1.避免交叉运输
中心库车辆配送路径规划，将原先零散配送的物资进行整合后，以合理的配送路径集中配送，避免了交叉运输的情况，缩短了总配送距离，降低了运输成本。
2.推进节能环保
车辆配送路径优化在满足各周转库的物资需求的前提下，以缩短配送车辆的总行驶距离为目标，能提高能源利用效率，推动公司更积极地承担节能环保的社会责任。
四、配送路径规划过程
1.组织结构
物资公司仓储配送网络包括了集中的物资调配中心、一个中心库以及十二个周转库。
（1）物资调配中心作为信息汇集、指令的中心，实时获取中心库和周转库内库存物资数量、物资需求数量等信息，并根据这些信息判断是否需要补库。
（2）如果周转库需要补库，物资调配中心发送补库指令给中心库。
（3）中心库综合需补库的周转库数量、地理位置及物资需求量等，规划所需的车辆数、配送路径等信息，将物资配送至周转库。
2.车辆路径问题描述
对于物资仓储配送网络，配送车辆路径问题可以描述为，十二个周转库的位置固定且各有一定的需求量，中心库用多辆载重量固定的汽车进行配送，要求合理安排汽车路线以使总距离最短，并能满足以下条件：
（1）每个周转库的物资需求到能满足；
（2）每个周转库的物资必须由尽可能少的车辆配送，例如在周转库的需求能由一辆汽车满足的情况下，必须只由一辆汽车配送；
（3）每条配送路径上各周转库的需求量总和不能超过汽车载重量。
3.车辆路径规划
将中心库及十二个周转库构成的13个的节点两两连线，共有C132=78种组合，即这13个仓库中任意两个仓库间的路径共计78条。利用Google、百度等电子地图软件，将两个仓库分别作为起点和终点，搜索出这78条路线以及之间的行驶距离。以字母O表示中心库，字母A至L表示十二个周转库。当有多个周转库需要补库时，配送路径确定步骤如下：
（1）确定各个周转库需要的物资数量；
（2）与汽车载重量进行比较，确定需要的汽车数量；
（3）根据各周转库的需求量，运用里程节约法，就近的仓库由同一汽车配送，同时避免交叉运输的情况，形成配送路径；
（4）根据实时路况，对配送路径进行一定调整，避免高峰期路段拥堵导致无法及时配送。
由于从实际情况考虑，为减少最后配送到的几个仓库的等待时间，在12个周转库中按地理位置分为两块区域，在郊环附近的7个仓库为一个配送区域，郊环线以内的4个仓库和崇明区域为一个配送区域。
以郊环线附近7个仓库的配送为例，如下图所示，每汽车载重量为5吨，A至G共7个周转库需中心库O配送物资，直线上的数字为距离，括号内的为对应的周转库的物资需求量。
4.路径信息
配送路径规划完毕后，将行车路线信息给对应的汽车司机。车辆出发后，利用短信在途跟踪获取车辆实时的位置信息，并将实时路况信息传递给司机，减少因交通拥堵造成的配送延误。
五、结语
本文综合各周转库地理位置、需求数量、汽车运载量等方面，运用里程节约法规划出车辆配送路径。车辆配送路径规划将对原先粗放式的配送方式进行优化，积极配合政府及上级公司对节能环保提出的要求，在满足各仓库需求的前提下缩短总配送距离，提高物资配送效率，降低配送成本。物资公司后续将逐步加强自动化和信息化建设，推进仓储网络各类信息的实时共享、获取、分析和处理，运用先进信息技术提高配送准确性和效率效益，确保智慧仓储网络的配送脉络高效稳定，构建一个现代化、智慧化、特色化的仓储配送体系。
参考文献：
[1]张玲，王朝霞.物流配送路径优化的模型与求解[J].商场现代化，2006.11.
关键词:路径规划; 地标; 预处理; 层次缩减算法; 三角启发算法
中图分类号: TP312.8文献标志码:A
Landmark.oriented heuristic routing algorithm in traffic network
MENG Ke*, ZHANG Chun.yan
School of Computer Science and Technology, China University of Mining and Technology, Xuzhou Jiangsu 221008, China
Abstract:
To improve the query efficiency of road routing algorithm in large-scale traffic network, a landmark-oriented algorithm based on A* algorithm was proposed. Select the most important vertexes and edges as landmarks during preprocessing, choose appropriate landmarks as the reference parameters and calculate in sections in point-to-point routing. Experiment results indicate that it has higher query efficiency and more reasonable results in long-distance road routing.
To improve the query efficiency of road routing algorithm in large.scale traffic network, a landmark.oriented algorithm based on A* algorithm was proposed. Select the most important vertexes and edges as landmarks during preprocessing, choose appropriate landmarks as the reference parameters and calculate in sections in point.to.point routing. The experimental results indicate that it has higher query efficiency and more reasonable results in long.distance road routing.
Key words:
path.planning; landmark; preprocessing; Contraction Hierarchies (CH) algorithm; A* Landmarks Triangle (ALT) algorithm
0 引言
对于大规模交通网络，Dijkstra算法［1］需要花费长时间进行计算，不符合实时性的要求。目前相关的优化算法有启发式算法和预处理算法两种。启发式算法(A*)［2］使用合适的启发函数减少搜索空间以获得较高的查询效率，启发函数会直接影响最后的计算结果；预处理算法使用点或边标记法、快捷路径法、区块分割法等对网络中的边进行合并和标记以迅速求出最短路径，但需要大量的辅助存储空间。
根据实际交通网络的特点：在主干道上通过的最短路径最多，存在重要的边和点；对于长距离的路径规划，出发点和目标点的中间节点有可能成为最短路径上的点。本文以A*算法为基础，将地图中关键的节点选为地标，并将地标作为启发函数的启发参数来求得路径规划的合理解。为提高长距离路径规划的查询效率，使用分段处理的思想将查询分割为若干子查询，并给出相关的优化方法。
1 相关研究
对于静态网络图G=(V,E)，大多数优化算法需要经过充分的预处理。三角启发算法（A* Landmarks Triangle，ATL）［3］39算法将图G按中心点划分为若干区域，每个区域选取一个标志点(LandMark)，根据三角不等式使搜索路径趋向于目标节点，大幅度减少搜索空间，从而提高查询效率。
文献［4］提出一种分层合并的预处理算法CH，对原始图G的边进行迭代合并，产生一组生成图{G1,G2,…,Gh}，生成图和原始图的边使用标号对应，以便求解后还原原始路径。这种预处理算法非常消耗存储空间，不适合于大规模网络，但是可以快速求出最短路径。经过预处理的CH算法时间复杂度可以达到O（N log H），N为合并图的平均边数，H为合并图的层数。
Arc.Flags［5］基于区域划分的思想对图进行预处理。将图划分为K个区域，每一条边(v,w)存储一个K比特的参数，第i位代表从点v到区域i的最短路径中包含此边。ARC.Flags可以精确求出最短路径，但预处理时间较长。Chase算法［6］综合CH和ARC.Flags的特点，对ARC.Flags划分的区域使用CH算法进行合并处理，加快预处理时间。
Bauer等［7］提出一种混合算法SHARC，对CH和ARC.Flags进行了多项改进，提出分层标记的思想，可以缩短预处理时间和减少额外空间。分层的ARC.Flags提供搜索方向，CH加速区域内的路径搜索，在单向搜索环境中SHARC可以提供非常高效的精确最短路径。经过修改的SHARC可以进行时变最短路径问题的搜索，文献［8］对此有详细描述。
2 地标导向的启发式算法
2.1 地标的选取
交通网络图一般拥有层次关系，乡镇与城市之间有干道相连，城市与城市之间有高速相连，在路径规划中这些连接线路被通过的次数最多。对于具有这一特点的图G，地标集的定义如下：
设r为一个搜索半径，点u为中心，2r为半径的G的子图记为Bu,2r，选取满足以下条件的最短路径P，PBu,2r并且Len(P)>r（Len(P)为P的欧拉长度）；如果存在点集Cu对于所有的P满足Cu P，则Cu为Bu,2r的地标集，并且设h=max(|Cu|)为G的地标度数（|Cu|为Cu的节点个数）。显然h越大地标对最短路径的贡献越大，在路径规划时可利用的地标节点越多。
计算大规模交通网络的地标集，采用以下几个步骤。
1)选择节点密集型的区域，将图分割为搜索半径为r的不同区域。在实验中会讨论r在不同取值时地标集获取情况以及启发式算法的查询速度。
2)对于区域Bu,2r，使用CH算法进行预处理以便于快速计算最短路径。
3)为Bu,4r中的每一个点对计算最短路径，获取最短路径集合P={Pv,w|v,w ∈Bu,4r ,|Pv,w|>r}。
4)对P中所有的路径取交集获得地标集Cu。
2.2 启发式算法设计
本文将地标节点作为启发式搜索的启发节点，求解思想如下。
对于点对（s,t）如果属于同一分割区域，由于使用了CH算法进行预处理，可以快速求得精确的最短路径。如果（s,t）属于不同区域则使用以下启发式规则。
1)从s所在区域的地标集中选取距离t最近的地标c作为下一跳的启发节点，s到c的最短路径使用CH求得。如果s所在区域没有地标集，则设c=s，转向第2）步。
2)从邻近区域的地标集中选取距离t最近的地标c′作为启发点，使用ALT算法求出（c,c′）的最短路径。
3)重复以上步骤直到c′与t在同一分割区域，使用CH算法计算（c′,t）最短路径。
4)对最短路径进行合并输出。
CH算法在区域内进行快速搜索，同时对于不同区域采用ALT算法控制搜索方向，使搜索始终沿着目标进行，这是一种分段搜索的思想，对于长距离的最短路径求解由于有地标集提供搜索参考，搜索线路比ALT更加精确，耗时更短。
2.3 算法分析与优化
CHALT算法的地标集预处理比较耗时，但可以在多项式时间之内完成计算。对于G的一个稠密子图，从空集开始， 使用CH算法从所有待处理的路径中选取一个覆盖所有路径的点，然后将此点从图中移除，对剩余路径迭代计算，直到不存在满足条件的点为止，在有限次迭代后算法会终止。对子图预处理的时间复杂度为O(n log nO(CH))，其中n为子图的节点个数，O（CH）为CH算法的时间复杂度。
对于ALT算法，双向搜索的收敛速度一般比单向搜索快［9］，因此使用双向CHALT查询可以获得更好的时间效率，具体执行步骤如下：
1)使用前向搜索计算(s,t)的最短路径获取一个启发点cf;
2)使用后向搜索计算(t,s)的最短路径获取一个启发点cb;
3)设s=cf , t=cb 重复1)，2)两步，最终搜索会在同一个节点相遇;
4)合并前向搜索和后向搜索的最短路径后输出。
对于地标集，可以使用TNR［10］的思想进行最短路径索引，TNR计算并存储所有地标之间的最短路径并存储在一张|C| × |C|的表格中，其中|C|为图G中地标节点的个数。如果s和t分别在不同的分割区域，并且存在地标，则根据索引表查询地标之间的最短路径，否则执行启发式搜索。对地标的查询可以在常数时间之内完成。大规模网络图使用CHALT+TNR算法可以在牺牲少量存储空间的前提下提供最优的性能。
3 实验
使用Intel Pentium CPU 2.5GHz、2GB RAM完成本算法和其他算法的比较实验，算法采用C++编写。实验数据选用北京市交通路网（包含81534个路段和34219个节点）。最短路径的度量标准为距离最短，在实验中使用欧拉距离完成路径计算。
表1为不同的最短路径算法在1000组随机查询中的平均时间比较。预处理的时间使用分钟计算，预处理每节点所占用的额外空间单位为字节，额外空间为负说明预处理后的搜索图比原图规模小。从表1中可以看出ARC.Flags和SHARC虽然执行效率比较高，但需要长时间的预处理，并且节点变更对算法的影响大，不适用于大规模网络；CHALT算法执行时间属于中上等，但预处理时间短，在经过TNR优化后的执行时间接近SHARC算法的查询时间；双向CHALT算法在时间上比单向快一些。由于CHALT使用地标节点作为启发参数，地标节点仅占所有节点的小部分，不容易受到节点变更的影响。
在CHALT算法中，划分区域的大小将影响地标集的选取和路径规划结果。表2表示不同搜索半径r对查询速度的影响，r的单位为km。从表2中可以看出在r=3km和r=4km时候在预处理时间少的情况下依然可以获得不错的查询效率，极端情况下r=0时算法变为ALT算法；r=∞时算法将仅使用CH算法，地标节点个数接近于0，启发函数不可用，也就失去了地标的参考价值。在实际应用中需要根据实验来确定合适的搜索半径，来达到效率与合理性的权衡。CHALT算法获取的解为近似解，但接近最优解，如图1(图1中黑色路径为CHALT算法，白色路径为Dijkstra算法)。CHALT算法优先选择重要的节点和边，在地图上表现为主要的街道和路口；Dijkstra算法对所有与(s,t)相关的路径计算以获得最优解，而不会考虑节点的重要性，在实际应用中存在不合理性。CHALT算法获取的路径比Dijkstra更平滑并且更合理。
4 结语
为解决大规模长距离的最短路径规划问题，本文根据分
段计算的思想，使用地标集将启发式搜索限制在靠近最短路径的方向。实验证明CHALT算法在保证预处理和查询效率的基础上，得出更合理的计算结果，优化后的算法查询效率更高，可以应用在大型交通网络中。下一步研究方向为以地标为导向的启发式算法在离散变权网络中的应用。
参考文献:
［1］
DIJKSTRA E W. A note on two problems in connexion with graphs ［J］. Numerische Mathematik, 1959(1):269-271.
［2］
GOLDBERG A V, KAPLAN H, WERNECK R F. Reach for A*: Efficient point.to.point shortest path algorithms ［C］// Proceedings of 7th International Workshop on Algorithm Engineering and Experiments. Miami: SIAM, 2006:129-143.
［3］
GOLDBERG A V, KAPLAN H, WERNECK R F. Better landmarks within reach［C］// WEA07: Proceedings of the 6th International Conference on Experimental Algorithms. Berlin: Springer.Verlag,2007:38-51.
［4］
GEISBERGER R, SANDERS P, SCHULTES D, et al. Contraction hierarchies: faster and simpler hierarchical routing in road networks［C］// WEA08: Proceedings of the 7th International Conference on Experimental Algorithms. Berlin: Springer.Verlag,2008:319-333.
［5］
KHLER E, MHRING R H, SCHILLING H. Fast point.to.point shortest path computations with arc.flags［C］// The Shortest Path Problem: Ninth DIMACS Implementation Challenge. Piscataway: IEEE, 2009:41-72.
［6］
LAUTHER U. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background［EB/OL］.[2011-07-02].gi.days.de/archive/2004/downloads/gitage2004/vortraege/lauther.pdf.
［7］
BAUER R, DELLING D. SHARC: Fast and robust unidirectional routing ［J］. ACM Journal of Experimental Algorithmics, 2009, 14(12):12-26.
［8］
DELLING D. Time.dependent SHARC.routing ［J］. Algorithmica, 2009, 60(7): 60-94.
［9］
GOLDBERG A V, HARRELSON C. Computing the shortest path: A* search meets graph theory, #MSR.TR.2004.24 ［R］.USA: Microsoft Research, 2004.
［10］
BAST H, FUNKE S, SANDERS P, et al. Fast routing in road networks with transit nodes ［J］. Science, 2007,316(5824):566-593.
［11］
HILGER M. Accelerating point.to.point shortest path computations in large scale networks［R］. Berlin: Technische University, 2007.
关键词： 增维启发式搜索； 智能车； 路径规划； 高效率； 平衡
中图分类号： TP311 文献标识码：A 文章编号：1009-3044（2016）36-0188-04
Increment-dimensional Heuristic Search Motion Planning Algorithm
WU Hong
（Department of Computer Science and Technology， Tongji University， Shanghai 201804， China）
Abstract： For intelligent vehicle motion planning， effective enough is always an important issue. The huge statue-space， high time complexity of the high dimensional search approach is always the bottle-neck of the algorithm. To solve this problem， this paper proposes a new method， increment-dimensional heuristic search algorithm. This method is a stepped-up heuristic search to reduce the searching status and improve the search algorithm execution efficiency. In experiment， the result shows that this algorithm reduces 87% of searching status and executes time is nearly 1/10 of that of the traditional heuristic search method. It is a very good trade-off between execution efficiency and trajectory quality.
Key words： increment-dimensional heuristic search； intelligent vehicle； motion planning； effective； trade-off
1 引言
在智能无人车领域，智能车无人车的行驶安全以及驾驶舒适度一直是一个非常重要的研究问题。而智能无人车的路径规划是这一问题的核心。智能无人车路径规划算法需要在有限的时间内，输出高质量高精度的路径，传输给智能无人车的控制模块、执行模块加以执行。一般的移动机器人路劲规划算法研究的是在高维度的空间里探索出一条路径，相比之下，智能无人车的路径规划则需要考虑车辆动力学模型约束，通常我们需要考虑四维状态。二维状态（x， y），表示车辆的地理坐标，车辆的航向角θ，以及行驶速度v。在四维状态空间里搜素出一条可行路径，是一个计算密集型的任务。与此同时，智能无人车的行驶速度可能很高，因此要求规划算法能够在一个非常有限的时间里给出搜索的结果。
为了解决这一问题，本文给出一种增维启发式路径规划搜索算法。该算法采取一种分阶段，逐步增加搜索维度的方法来生成路径。在每一个阶段，增维搜索算算法选择离车辆当前位置附近的一个区域，增加状态空间维度，进行启发式搜索。因此该算法的输出轨迹是多精度的轨迹。在车辆附近位置，输出轨迹为高维度高精度，充分考虑车辆动力学模型，驾驶舒适度，能耗以及可靠性。而在远处，低维度低精度的轨迹依然可以引导智能无人车的行驶方向正确，充分考虑的地图信息，障碍物信息。从人类正常的驾驶习惯上来说，驾驶员总是对近处的驾驶精度较高，而远处相对较低。该算法充分利用了这一点原理，牺牲了远处的轨迹精度，极大地提高了算法的运行效率。在频繁联系的反复规划中，车辆会一直执行高精度部分轨迹。因此，该算法在运行效率以及输出轨迹质量方面，取得一个非常好的均衡。
为了展示该算法的性能，本文进行了仿真实验。在实验中，智能无人车刚刚进入一个停车场，需要在目标停车位泊车。实验结果表明，相比传统的高维度启发式搜索算法，该算法减少了超过87%的搜索状态，运行性能提高了近10倍。
2 研究现状及文献综述
从20世纪70年代开始，欧美的西方国家开始无人驾驶汽车方面的研究工作，并在智能无人车的控制和商用化方面取得一定进展。在汽车工业非常发达的德国，各大汽车公司都资助或者联合高等院校以开发可在普通道路上行驶的智能无人车。目前，欧盟已启动一个名叫CyberCars的智能无人车项目，以推动智能无人车的研究和各国间智能无人车技术的信息共享。
在20世纪的80年代，我国部分大学开始智能无人车的研究工作，虽然起步较晚也取得一定成果。目前，从事这方面研究工作的 主要是国防科技大学、军事交通学院及清华大学等科研机构。[1-6]
在智能无人车决策模块的相关研究中，最核心的部分是路径规划算法的研究。文献[7]提出一种快速扩展随机树生成算法―RRT （Rapid-Exploring Random Tree）算法。RRT是一种多维空间中有效的路径规划算法。它以一个初始点作为根节点，通过随机采样增加叶子节点的方式，生成一个随机扩展树，当随机树中的叶子节点包含了目标点或者进入目标区域，便可以在当前随机树中找到一条从初始点到目标点的路径。文献[8]在RRT算法在自动驾驶汽车以及宇宙空间探测器路径规划上的应用。文I[9]对RRT算法提出优化方法并通过实验，解决了基本RRT算法存在的动态环境中规划路径不稳定的问题，同时提出双向RRT生成算法以及动态步长等优化方法，提高了RRT算法生成初始点到目标点路径生成的速度。然而RRT算法在规划路径的过程中产生的是可行解，而非最优解。文献[10]提出了RRT*算法，RRT算法进行了改进，保证了RRT算法生成解是渐进最优解。然而RRT*算法在时间复杂度上远高于朴素的RRT算法。文献[11]提出了一种RRT*算法加速的方法，通过使用预生成RRT随机树，在使用RRT*_S算法优化当前随机树，构造出与RRT*算法生成随机树本质相同的RRT*_S随机树，从而实现RRT*算法的加速。文献[12]为麻省理工学院将RRT*算法运用于叉车移动路径规划的一次应用实践，并对RRT算法与RRT*算法在实际应用中的结果给出对比分析。
文献[13][14][15][16]给出了2007年美国DARPA智能无人车比赛麻省理工学院（MIT）参赛智能无人车的整体架构，MIT智能无人车的轨迹生成算法，主要是用RRT算法生成可行路径，并对该路径进行平滑，以此为基础生成智能无人车运动轨迹。
文献[17][18][19][20][21][22]主要阐述了状态空间搜索算法，通过估价函数进行启发式搜索以及状态空间搜索剪枝。文献[23]提出了ARA*（Anytime A*）算法，对短时间间隔内连续反复用A*搜素算法进行空间状态搜索这一类状态空间搜索应用场景进行优化。
3 增维启发式搜索算法
增维启发式搜索是一种两阶段的启发式搜索算法。在算法的第一阶段，搜索出一条从车辆当前位置到目标位置的几何最短路的轨迹。在第一阶段的搜索，我们只考虑二维的搜索状态空间（x， y），即车辆的地理坐标。第二阶段，选取第一阶段的路径中的一个点作为本阶段目标点，搜索状态加入车辆的航向角θ，以及行驶速度v，总体状态空间提升到四维，并且考虑车辆动力学模型，在此状态空间下，搜索出一条高精度可执行的车辆行驶轨迹。
3.1 第一阶段搜索
在这一阶段，因为我们只考虑二维状态空间（x， y），即车辆的地理坐标。如果将状态空间离散化，这一搜索问题会退化成一个图论的最短路问题。虽然图论的最短路问题有很多经典成熟的算法。但是在这里还是有一些值得讨论的问题。
3.1.1 栅格随机化
一般地，在执行最短路算法之前，会把状态空间离散化成栅格，然后对栅格做4联通或者8联通处理，但是这种离散化方法会使最短路失去最优解，如图1a、1c所示。
图1 a. 离散化使得几何最短路失解；b. 随机化18联通栅格法；c. 8联通栅格法几何最短路（黑），随机化18联通栅格法几何最短路（红）。
a b c
为了解决这一问题。如图1b所示，算法使用一种随机化18联通的栅格法来离散化空间。即在栅格之间连边的时候，每个栅格除了相邻向相邻8个栅格联通，同时随机向其他10个栅格联通。选取的10个栅格满足与该栅格曼哈顿距离小于7，满足条件的格子约为100个，足以随机化，同时连边长度小于两个栅格长度，也方便计算是否与障碍物碰撞。
3.1.2 最短路算法
在离散化为栅格之后，采用单源最短路算法来计算车辆当前位置到其他位置的几何最短路，虽然单源最短路算法非常的经典成熟，但依旧有值得讨论的地方。
最短路的经典算法是堆优化的Dijkstra算法，该算法时间复杂度为 [O（eloge）]，其中[e]代表离散化后边的数量，然而在稀疏图中，SPFA算法的实际时间复杂度约为[O（e）]，在18随机联通结构的图中效率比价高，因而在本阶段中，我们采用SPFA算法计算单源最短路。
3.2 第二阶段搜索
在第二阶段的搜索中，我们选取第一阶段结果，几何最短路上的一个点来作为目标点，在搜索状态加入车辆的航向角θ，以及行驶速度v，在搜索中充分考虑车辆动力学模型，搜索出一条高精度可执行的车辆行驶轨迹。
3.2.1 启发函数
在启发式搜索过程中，一个强力有效的启发式函数对搜索效率来说至关重要。启发式函数不仅为搜索的实际代价提供了一个下界，同时也是实际代价的一个良好估算，可以引导搜索往正确的方向扩展，并且实现搜索剪枝，在第二阶段的搜索中，使用以下启发式函数。
动力学约束无障碍启发函数，[hnh（x，y，θ，v）]，该函数忽略障碍物信息，考虑车辆动力学模型，在此条件下求出最优的路径。这一启发式函数因为忽略了障碍物信息，只考虑动力学模型，所以可以离线计算、存储，在真实路径规划的过程中查询，计算速度极快。该函数极大的消除接近目标点航向角错误的搜索分支。
地图信息非动力学模型启发函数，[hh（x，y）]，该启发函数是上一启发函数的对偶函数，忽略车辆动力学模型，以几何最短路作为启发函数。该启发函数充分考虑的地理信息，消除了错误行驶方向的搜索分支。
结合二者，选取启发函数[h（x， y，θ，v）] = max（[hnhx，y，θ，v， hh（x，y））]，
fxyv） = g（x， y， ，v） + h（x， y， ，v） （1）
fxyv） Fxyv） （2）
f 为状态[（x， y， θ， v）]的估价函数， g为当前搜索状态[（x， y， θ， v）]的实际代价， [F]为实际搜索代价。
在该启发函数的引导下，第二阶段启发式搜索可以高效地计算出四维高精度路径。
4 仿真实验以及实验结果
为了展示该算法的性能，本文进行了仿真实验。在实验中，智能无人车刚刚进入一停车场，需要在目标停车位泊车。实验环境为Ubuntu 12.04 Linux系统，Intel i5处理器， 8GB内存。停车场大小为长80米宽50米，栅格离散化精度为10厘米，车辆采用72个不同的航向角，同时采用两个速度，最大的前向速度以及最大的后向速度。
图2 a朴素四维启发式搜索；b增维启发式搜索；c朴素四维启发式搜索输出路径；d增维启发式搜索输出路径
a
b
c
d
表1 算法性能比^
[ 阶段 朴素四维启发式搜索 增维启发式搜索 搜索状态数量 第一阶段 400000 第二阶段 10808634 408773 共计 10808634 808773 算法运行时间
（毫秒） 第一阶段 142 第二阶段 2844 141 共计 2844 283 ]
如图1b，对于每一次路径规划，增维启发式搜索算法可以有效地减少搜索状态的数量，因为高维度高精度部分的搜索集中在离车辆较近的区域，而从全局的角度，二维的几何最短路依旧引导着轨迹往正确的方向。相比之下朴素的四维启发式搜索搜索量极大（图2b）。从输出轨迹上看，两者的输出轨迹质量几乎相同（图2c、2d）。
5 结论
本文展示了增维启发式搜索路径规划算法。该算法分为两阶段。第一阶段在全局考虑二维的搜索状态空间，得出起始点到目标位置的几何最短路。在第一阶段几何最短路基础上选取一个目标点作为第二阶段目标状态空间，进而得到考虑了车辆动力学模型、四维的高精度可执行轨迹。仿真实验结果表明，在现实场景下，该算法极大地减少了搜索状态数量，提高了算法执行效率，同时输出高质量的智能无人车行驶轨迹。
参考文献：
[1] 杨明.无人驾驶车辆研究综述与展望[J]..哈尔滨工业大学学报，2006，38（增刊）：1259-1262.
[2] 孙振平.自主驾驶汽车智能控制系统[D].国防科技大学，2004.
[3] 杨森森.基于GPS/INS/激光雷达的无人车组合导航[D].上海交通大学硕士学位论文，2013.
[4] 钱钧，杨汝清，王晨，等，基于路标的智能车辆定位[J].上海交通大学学报，2007，41（6）：894-898.
[5] 王曦鸣.军用无人车的路径规划与仿真研究[D].北京交通大学硕士学位论文，2010.
[6] 曹玉芬，张国斌.美国无人地面车辆计划[J].国外坦克，2004（5）：25-27.
[7] Rapidly-exploring random trees： A new tool for path planning. S. M. LaValle. TR 98-11， Computer Science Dept.， Iowa State University， October 1998
[8] RRT-based trajectory design for autonomous automobiles and spacecraft. P. Cheng， Z. Shen， and S. M. LaValle. Archives of Control Sciences， 11（3-4）：167--194， 2001.
[9] Rapidly-exploring random trees： Progress and prospects. S. M. LaValle and J. J. Kuffner. In Proceedings Workshop on the Algorithmic Foundations of Robotics， 2000.
[10] S. Karaman and E. Frazzoli， Sampling-based algorithms for optimal motion planning，I. Robotic Res.， vol. 30， no. 7， pp. 846C894， 2011.
[11] Yun-xiao Shan Bi-jun Li Jian-Zhou Yue-Zhang，An Approach to Speed Up RRT* ，2014 IEEE Inteligent Vehicles Symposium （IV） June 8-11
[12] Karaman S， Walter M R， Perez A， et al. Anytime motion planning using the RRT*[C]//Robotics and Automation （ICRA）， 2011 IEEE International Conference on. IEEE， 2011： 1478-1483.
[13] Leonard J， How J， Teller S， et al. A perception-driven autonomous urban vehicle[J]. Journal of Field Robotics， 2008， 25（10）： 727-774.
[14] Kuwata Y， Fiore G， Teo J， et al. Motion planning for urban driving using RRT[C]//Intelligent Robots and Systems， 2008. IROS 2008. IEEE/RSJ International Conference on. IEEE， 2008： 1681-1686.
[15] Leonard J， Barrett D， How J， et al. Team MIT urban challenge technical report[J]. 2007.
[16] Kuwata Y， Karaman S， Teo J， et al. Real-time motion planning with applications to autonomous urban driving[J]. Control Systems Technology， IEEE Transactions on， 2009， 17（5）： 1105-1118.
[17] Barbehenn， M. and Hutchinson， S. （1995）. Efficient search and hierarchical motion planning by dynamically maintaining single-source shortest path trees. IEEE Transactions on Robotics and Automation， 11（2）： 198C214.
[18] Gaschnig， J. G. （1979）. Performance measurement and analsis of certain search algorithms. Ph.D. Dissertation， Carnegie Mellon University.
[19] Stentz， A. （1995）. The Focussed D* Algorithm for real-time replanning. Proceedings of the International Joint Conference on Artificial Intelligence （IJCAI）， pp. 1652C1659.
[20] Pearl， J. （1984）. Heuristics： Intelligent Search Strategies for Computer Problem Solving. Boston， MA： Addison-Wesley
【关键词】虚拟场景；路经规划；八叉树；A*算法
中图分类号：TP39文献标识码A文章编号1006-0278（2013）06-172-01
一、引言
随着虚拟现实技术的日益成熟，只有景色、建筑物等一般视景信息的虚拟场景已不能满足人们的视觉需求，迫切需求一个有生命的对象引入到虚拟场景中，增加浏览者的沉浸感。虚拟场景中虚拟人的路径规划是虚拟现实研究中的一项关键技术。目前，研究者们已经把研究的重心放在如何为虚拟人规划出一条行走的最优路径，使虚拟人的路径导航更具有真实感和可信度。
由于虚拟环境中的模型多由三角面网格组成，通过使用基于空间多层次划分的八叉树方法，充分发挥了其空间划分的优势，加快了场景的渲染速度，减少了确定对象的处理时间以及存储空间①。
文章采用八叉树和A*算法相结合的方法，对路径进行规划，并对A*算法做了改进，以适应八叉树的存储结构。
二、密集型区域八叉树划分算法
八叉树是由四叉树推广到三维空间而形成的一种三维栅格数据结构，它作为一种场景组织方法，广泛应用于虚拟现实系统，可显著减少对场景中多边形进行排序的时间。
由于传统八叉树对空间的划分是均匀的，导致了最终生成一个结构不平衡的八叉树，从而增加整个八叉树的存储空间以及各结点的遍历时间。文章采用了对传统八叉树算法进行改进，采用基于密集型区域八叉树划分方法。密集型区域八叉树的网格划分算法是对每一子空间重新建立最小包围盒，这样避免了在建立顶点树时，由于该部分顶点在空间上分布不均匀而导致树的深度的增加，进而减少了存储空间，加快了网格模型数据的读取速度。另外，由于建立了顶点的最小包围盒，在误差较小时，只有空间距离比较近的顶点才会聚合在一起；而相距较远的顶点只有在深层次简化时才会聚合，这些特点在一定程度上保证了简化时网格模型的逼真度。
密集型区域八叉树划分方法的算法描述如下：
步骤1使用OBB包围盒方法建立模型的最小包围盒。
步骤2以包围盒的X轴、Y轴、Z轴方向的中分面作为分割基准，将包围盒平均划分为八个子包围盒。
步骤3如果每个子空间内存在物体的属性不相同或未达到规定的限差，则重新从步骤1开始进行划分。否则，划分结束，并对划分后的每一个结点记录下结点编号、划分标志、结点在顶点树中的深度以及它所含的景物面片表的入口指针。
三、A*算法
A*算法是建立在典型的Dijkstra算法上的，是由Hart，Nilsson，Raphael等人首先提出的。该算法的创新之处在于选择下一个被检查的节点时引入了已知的全局信息，对当前节点距终点的距离做出估计，作为评价该节点处于最优路线上的可能性的量度，这样就可以首先搜索可能性较大的节点，从而提高了搜索过程的效率。
下面是对A*算法的介绍，我们首先来介绍一下启发式搜索中的估计函数。因为在启发式搜索中，对位置的估价是十分重要的。估价函数的表示如下：
其中是节点的估价函数，是已知的，指在状态空间中从初始节点到节点的实际代价；是从结点到目标节点最佳路径的估计代价，它体现了搜索的启发信息，启发信息决定着算法的启发能力。启发信息越多，估价函数就越好，即约束条件越多，则排除的节点就越多，说明这个算法越好。这种做法存在一个平衡的问题，也会使算法的准确性下降。具体的说，代表了搜索的广度优先趋势，当时，可以省略，这样就提高了搜索效率。
A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：
这里，是估价函数，是起点到终点的最短路径值，是到目标的最短路经启发值。由于这个其实是无法预先知道的，所以我们用前面的估价函数做近似。代替，但需要满足（在大多数情况下都满足时，可以不用考虑）。代替，并满足。可以证明应用这样的估价函数是可以找到最短路径的。
四、基于密集型区域八叉树的A*算法改进
由于使用八叉树存储结构存储的环境地图扩展步长不一致，采用传统的A*算法效率较低，因此对A*算法做了改进，以适应八叉树结构的搜索。改进的办法是从叶节点开始搜索并为Open表设置两个优先队列，命名为队列1和队列2（队列1中存放的节点总是高于队列2），在两个队列中分别存放相邻层次的全部节点，层次越高的优先级越高。通过这种分层次的搜索，也大大缩小了搜索的空间并缩短了搜索时间，这样一来大大提高了搜索效率。
五、结束语
针对于复杂的3D环境，文章根据八叉树适合虚拟场景划分的特点，采用了一种适合密集型区域的八叉树划分方法，进行场景划分。为适合八叉树的存储结构，对A*算法做了改进，引入优先级队列并采用了分层结构，采用了从叶节点到根节点的搜索方法，规划出了虚拟人行走的最优路径。
关键词：滚转角控制 区域规避 路径约束
中图分类号：V279 文献标识码：A 文章编号：1674-098X（2014）04（b）-0057-02
当前实时实现路径规划优化设计的算法比较复杂而且要求具有很好的精确性，同时各个优化方法也趋向混合，采用两种或两种以上的方法来研究，这样结合了各个方法的优点。由于高速飞行器通过改变航向角的方式来进行转弯，转弯半径比较大，影响飞行器机动性，对行器变轨、避障和改变打击角度，都有很大的影响。所以本文采用基于滚转角控制转弯的方法，保证了转弯半径尽可能的小，增加了飞行器的机动性能。同时也要考虑飞行器的动力学模型、气动、过载等物理参数的约束影响。
1 动力学方程
本文直接选取某一飞行器，其三自由度质点运动方程组：
（1）
（2）
（3）
（4）
（5）
（6）
再入轨道约束包括热耗率、垂直加速度或者过载系数和动压。
≤ （7）
≤ （8）
≤ （9）
所有上面的约束都被认为是硬性约束。对于有中等或者很大的升阻比的飞行器，平衡滑翔条件是另一个路径约束。
≤0 （10）
其中是一个确定的滚转角，该约束可以减少高度随返回轨道的长周期变化，考虑到轨迹发散，同时保证了充分的滚转角裕度，这是个软约束。
对于再入飞行器从再入段终点开始，通过机动飞行消耗能量，降低速度、高度，调整航向到自动着陆起点为止的飞行段。要实施最终的能量管理（TAEM，terminal area energy management），此时由能量管理系统控制。在TAEM的接口处，轨迹必须有正确的条件以保证TAEM和进场航线顺利实施。典型的再入条件为：
（11）
在TAEM处的相对速度有靠近航向对准锥（HAC，heading alignment cone）的切点决定，以保证获得HAC在TAEM阶段的切线。引入定义
（12）
其中是当前飞行器在大圆中的位置与HAC的方位角。对于最终航向角的一个约束为：
≤ （13）
是提前设定的值。最终飞行器在TAEM接口处变为平飞姿态。在TAEM处过大的|σ|会导致TAEM控制有很长的过度响应。所以对于水平着陆的飞行器而言，最终在TAEM处的滚转角约束为
≤ （14）
其中是一个确定的值，一般取在5～15 °范围内。
2 滚转角约束设计
如果要基于滚转角控制，就要把原来基于速度、高度的限制条件，转化为基于滚转角的限制条件。下面分两部分解决这个问题。
（1）初始下降最大可行滚转角
根据入口界面给定的条件，取滚转角为常值（符号由水平制导决定），对再入飞行器三自由度质点运动方程组数值积分。当在速度为Vpt时满足下式，则停止积分。
≤ （15）
是一个很小的预置正数，其中
（16）
当滚转角为0时，准平衡滑翔条件为：
（17）
（2）QEGC限制跟随速度变化的滚转角
在知道均衡滑翔条件后，微分方程可简化为代数方程。但是实际的航迹角是随时间变化的，在大多数的情况下都是小振幅长周期的振动。我们可以得到
（18）
根据三个路径约束在给定速度下共同确定的约束边界，大气密度ρ随着高度被表示为v的函数，攻角α也可以表示为速度的函数。应用可以确定出升力随速度的变化关系。设定方程（5.24）中的r≈1，因为。用替代掉L，可以求得最大的可行滚转角。
（19）
QEGC给出了在保证其他约束条件下确定滚转角的方法。滚转角的范围有如下形式：
≤≤ （20）
这样对于复杂的约束条件只需简单的选择滚转角，就能够保证所有的条件成立。综合上面的内容，可以得出滚转角的在整个返回飞行中的取值如下：
（21）
在上式中Vpt是初始下降阶段的末速度。在整个包络可容许的滚转角范围为
≤≤ （22）
3 仿真实现
飞行器仿真对象选择某类飞行器。其仿真参数如表1所示。
攻角α变化范围为[0°，45°]；马赫数Ma变化范围为[3，25]；高度变化范围为[0km，120km]。初始条件表2。
攻角α的规律如下，
（23）
当时，当时，。
大气密度与高度的关系式：
（24）
其中，，，可以求得任意海拔高度的大气密度值。
气动参数的确定：
记 如果，升力系数和阻力系数由下式求得：
（25）
滚转角的选取：
我们综合上面所讲约束条件，可以设定的值为常值，这是符号随时间变化，达到规避威胁的目的。这个也是整个算法的关键。
避障算法仿真，最终的位置是自由的，没有约束。避开障碍是最主要的目的。在选择滚转角时，要考虑到最小转弯半径的约束。实验中我们采用手动的方式来生成避障轨迹，对于滚转角取为±60°。具体的变化时刻，输入的时间序列得到。滚转角变化曲线。结果如图1、2、3、4。
再入飞行器规划路径仿真结果表明基于滚转角控制轨迹优化方法保证了飞行器的快速性和机动性，减小了转弯半径，提高了转弯效率，可以快速、方便的达到规避障碍的目的。
