路径规划典型算法优选九篇

引言：易发表网凭借丰富的文秘实践，为您精心挑选了九篇路径规划典型算法范例。如需获取更多原创内容，可随时联系我们的客服老师。

第1篇

作者简介： 朱新平（1983-），男，博士，研究方向为先进机场场面运行控制，电话：13419037831，E-mail：

通讯作者： 韩松臣（1963-），男，教授，博士，研究方向为空中交通安全、空域规划管理，E-mail：

文章编号： 0258-2724（2013）03-0565-09DOI： 10.3969/j.issn.0258-2724.2013.03.027

摘要：

为支持先进机场场面活动引导与控制系统（A-SMGCS，advanced surface movement guidance and control system）实施航空器滑行的精确引导，将场面分为滑行道交叉口和直线段等典型运行单元，利用改进的扩展赋时库所Petri网，建立了场面运行模块化模型；采用该模型进行染色体编码，并考虑场面运行管制规则，提出了染色体合法性检测与修复算法，以及染色体交叉和变异算法.基于首都国际机场01号跑道实际运行数据，用本文模型和算法进行了多个航班滑行初始路径规划，研究结果表明：与节点-路段类模型相比，本文模型能更充分地描述场面管制规则约束，可避免生成违反管制规则的路径；本文算法的每个航班初始路径规划耗时小于10 s，符合A-SMGCS的要求；由于考虑了航空器滑行速度调整特征，更符合场面运行的实际情况.

关键词：

空中交通；A-SMGCS；滑行路由规划； Petri网；遗传算法

中图分类号： V351.11文献标志码： A

航空器滑行自动路由规划可以协调进离港航班安全有序地滑行，从而减少场面拥堵并提升场面容量.在国际民航组织（International Civil Aviation Organization， ICAO）提出的先进机场场面引导与控制系统（advanced surface movement guidance and control system， A-SMGCS）中，路由规划功能是实现航空器场面滑行精确引导的前提[1].航空器场面滑行具有并发、资源共享特性，并受多种管制规则约束. A-SMGCS路由规划不同于传统道路网络中的车辆路径规划，文献[2]提出了A-SMGCS三阶段路由规划策略：

（1） 初始路径规划，为进离港航班确定最优滑行路径和s-1个次优滑行路径（s值由管制员动态交互确定）；

（2） 滑行前路由指派，依据航空器开始滑行前的场面态势，为其确定合理路由；

（3） 路由实时更新，在航空器滑行过程中实时调整路由，以避免冲突发生.

本文仅考虑第（1）阶段，即初始路径规划问题.

Petri网广泛用于A-SMGCS场面运行过程的建模与冲突监控[3-4]，但较少用于航空器滑行路由规划.文献[5]将无向交通网络转换为Petri网表示的有向图，并通过Petri网仿真器求解最短有向路径.文献[6]将机场滑行路径描述为有向图，并转换为Petri网图求解最佳滑行路径.文献[2]建立了基于Petri网的场面活动模型，并通过时间窗调度来进行路由规划.上述研究建立的Petri网模型对场面管制规则约束考虑不全面，在算法设计上未充分利用Petri网的数学特征，且通常针对某一特定机场进行分析，实用性和通用性均显不足.另一方面，将航空器场面滑行速度假设为恒定值[7-9]，忽略了航空器在场面不同区域滑行速度的调整变化，导致所得路由结果不能支持航空器滑行的精确引导.

在文献[2]的基础上，本文从以下方面展开研究：

（1） 给出一种扩展赋时库所Petri网（extended timed place Petri net， ETPPN），以准确描述场面运行管制规则约束，并提出一种模块化、面向路由规划的场面运行ETPPN模型建模方法；

（2） 采用遗传算法规划航空器初始滑行路径，其染色体编码采用场面ETPPN模型的变迁激发序列，且交叉和变异均仅针对模型中的变迁进行，避免了以滑行道系统拓扑结构中的交叉口或直线段为基因组成染色体，在此基础上展开的遗传操作保证了方法的通用性；

（3） 与文献[7-9]中关于航空器场面滑行速度恒定的假设不同，细化了航空器加减速特性对路段占用时间的影响，使路由规划结果的精确度更高，实用性更强.

1

航空器场面运行过程建模

1.1

面向资源的场面运行过程建模

可见，采用ETPPN模型对场面运行进行建模，可描述航空器对场面各单元的动态占用与释放，以及航空器在各单元滑行应遵循的管制规则.场面其它典型单元运行过程的Petri网建模也可采用本节的方法.不同机场的场面交通系统具有不同构型，但基本组成单元类似且有准确的数量和明确的运行规则.因此，利用各单元对应的ETPPN模型，并采用Petri网同步合成技术[10]可实现场面运行过程建模.

1.2

航空器滑行特征分析

航空器场面滑行速度具有以下特征：

（1） 当航空器先后通过的两路段均为直线或弯道时，无须加减速；

（2） 当航空器从弯道滑入直线段时，须启动加速过程；

（3） 当航空器从直线段滑入弯道时，减速过程通常在进入弯道前完成.

2

基于GA的初始路径规划算法

2.1

面向初始路径规划的GA设计

遗传算法（genetic algorithm， GA）在工程优化领域已得到广泛应用[11]，并越来越多地应用于航空器路由优化[12-15].本文提出基于场面ETPPN模型和GA的初始路径规划方法，基本思路为：

（1）

采用第1节方法，建立场面活动区中各典型运行单元对应的ETPPN模型，同时将场面管制规则约束集成到Petri网元素中，最终得到场面ETPPN模型；

（2）

以场面ETPPN模型为基础，采用合适的编码方式对模型中所含相关元素进行染色体编码，并设计相关遗传操作，求解初始滑行路径集合（包括1个最优和s-1个次优滑行路径）.

上述思路的优势在于，对任何一个机场的航空器初始路径规划，所要解决的问题只需采用第1节的模块化建模方法，将场面交通系统映射为对应的ETPPN模型并输入管制规则约束即可，因而保证了所给算法的实用性和通用性.

2.2

染色体编码

染色体应满足以下约束：

（1） 物理约束.指与航空器自身占用物理空间大小或与滑行性能相关的约束，如翼展对通过某些区域的限制等.

（2） 管制规则约束.指管制规则确定的航空器在某些路段的滑行约束，如滑行速度约束、进出某机坪必经的交叉口等.

算法2中，步骤1保证了染色体不会出现重复基因，即所规划滑行路径不会出现环路；步骤2保证了航空器在单元内部的滑行过程满足航空器性能要求，例如航空器在同一交叉口滑行时不能多次转弯；步骤3～5保证了航班按照所规划路径滑行时能满足相关约束.

2.3

选择算子与遗传算子

2.3.1选择算子

2.3.2

交叉算子

2.3.3

变异算子

由于采用变迁激发序列进行染色体编码，若采取随机改变某一基因位变迁进行变异，则极有可能产生不满足可激发约束的解.以往采取两种方法解决该问题：第1种方法是随机改变染色体，当生成了不满足约束的解时再进行改正；第2种方法是在进行变异时保证不产生不可行解[16].

3

仿真试验

3.1

仿真试验设计

以首都国际机场为研究对象，采集T3航站楼东侧飞行区某日实际运行数据，为所有进离港航班规划初始滑行路径集.该部分飞行区的场面交通系统结构如图6所示，采用北向运行模式（使用01号跑道），且假设所有离港航班均使用全跑道起飞，即从跑道等待区Q0处（图中方框所示区域）进入跑道起飞，进港航班从快速脱离道Q5、Q6、Q7脱离的比例为0.1∶0.6∶0.3.作为对比，采用文献[12]的方法为图6所示飞行区建立对应的节点-路段类有向图模型，并采用基于遗传算法的路径规划方法为航班规划滑行路径.

文献[12]采取的优化目标是所有航班滑行的总里程最短，将其修改为与本文算法相同的优化目标，即滑行时间较短的s条滑行路径（设s=3）.对比的目的是：

（1） 检验用本文所建场面模型进行路径规划是否比节点-路段类模型能更好地遵循管制规则；

（2） 检验本文初始路径规划算法的效率和有效性.

计算环境CPU为Interl（R） Pentium Dual 2.2 GHz，内存为4 GB.

具体实施过程为：在基于Anylogic的场面运行仿真平台上建立对应的场面ETPPN模型，然后解析得到该模型对应的关联矩阵并导入MATLAB2008a中，采用Sheffield大学的遗传算法工具箱GATBX求解滑行路径.在求解过程中，MATLAB可直接调用Anylogic存储的相关库所属性数据库，并采用遗传算法工具箱GATBX进行求解.文献[12]中算法的实现直接用MATLAB的遗传算法工具箱GATBX完成.

3.2

仿真试验结果及分析

为了给每个航班的进离港滑行规划s

个滑行时间较短的初始滑行路径，需要设置合理的遗传算法参数.但目前在遗传算法参数设定方面缺乏通用理论，一般根据问题难易程度和染色体编码形式，由经验和反复试凑来设定参数值.

用上述参数为离港航班SK996（所在机位511）规划初始滑行路径集（包含3条路径）.由于遗传算法具有一定的随机性，可进行多次试验，每次试验得到的最短滑行时间均为246 s，因此认为对应的滑行路径为最短滑行路径.

图8为在1次随机试验中不同遗传代数所得路径集的最短滑行时间和平均滑行时间变化曲线.由图8可以看出，每次优化均能获得最短滑行路径，且随着进化代数的增加，平均滑行时间越来越接近最短滑行时间，表明算法收敛性良好.

最终为该航班确定的初始滑行路径集如表3所示.对每条路径进行分析可知，在优化场面资源使用的同时，满足了各类场面运行管制规则约束.

采用文献[12]的遗传算法为该航班规划初始滑行路径集，将求出的前3条较短滑行路径参照图6转化为对应的节点形式，如表4所示.

由表4可见，路径1和路径2分别在滑行道K5和K4上未遵循该路段的运行方向约束，这与该算法设计仅考虑避免航空器之间的滑行冲突约束但未充分考虑其它约束有关.可见，在节点-路段类模型中，模型本身对管制规则约束的描述能力有限，仅在算法实现过程中考虑各类约束，可能影响路径规划结果的有效性.

此外，文献[12]中设定的航空器具有单一固定滑行速度5 m/s，路径3的滑行时间为467 s（表4），用本文方法路径3的滑行时间为260 s（表3），二者相差较大.可见，考虑航空器滑行速度的调整特性，可更精确地计算航空器的滑行时间.

4

结束语

提出了一种面向A-SMGCS的航空器场面滑行初始路径规划方法，该方法具有以下特点：

（1） 定义一种扩展赋时库所Petri网（ETPPN），可对航空器场面滑行过程进行建模，该模型充分体现了管制规则约束；

（2） 考虑航空器场面滑行速度调整特性，使规划结果更接近实际运行需要；

（3） 采用场面运行ETPPN模型中的变迁激发序列进行GA染色体编码，结合场面滑行特征给出交叉与变异设计，改变以往研究中对问题空间（场面拓扑结构）的直接处理，算法的通用性更好.

在求解初始滑行路径时仅以滑行时间最短作为优化目标，今后需要考虑更多的优化目标，例如航空器加减速次数、转弯次数等，并与其它路径规划方法进行比较.

参考文献：

[1]International Civil Aviation Organization （ICAO）. Doc.9830-AN/452， Advanced surface movement guidance and control systems （A-SMGCS） manual[S]. 2004.

[2]汤新民，王玉婷，韩松臣. 基于DEDS的A-SMGCS航空器动态滑行路径规划研究[J]. 系统工程与电子技术，2010，32（12）： 2669-2675.

TANG Xinmin， WANG Yuting， HAN Songchen. Aircraft dynamic taxiway routes planning for A-SMGCS based on DEDS[J]. Systems Engineering and Electronics， 2010， 32（12）： 2669-2675.

[3]朱新平，汤新民，韩松臣. 基于EHPN的A-SMGCS机场滑行道运行控制建模[J]. 交通运输工程学报，2010，10（4）： 103-108.

ZHU Xinping， TANG Xinmin， HAN Songchen. EHPN-based modeling of airport taxiway operation control in A-SMGCS[J]. Journal of Traffic and Transportation Engineering， 2010， 10（4）： 103-108.

[4]朱新平，汤新民，韩松臣. 基于DES监控理论的滑行道对头冲突控制策略[J]. 西南交通大学学报，2011，46（4）： 664-670.

ZHU Xinping， TANG Xinmin， HAN Songchen. Avoidance strategy for head-on conflict on taxiway based on supervisory control theory of DES[J]. Journal of Southwest Jiaotong University， 2011， 46（4）： 664-670.

[5]黄圣国，孙同江，吕兵. 运输网络的最短有向路Petri网仿真算法[J]. 南京航空航天大学学报，2002，34（2）： 121-125.

HUANG Shengguo， SUN Tongjiang， LU Bing. Petri net simulation arithmetic of the shortest directional path in transportation net[J]. Journal of Nanjing University of Aeronautics and Astronautics， 2002， 34（2）： 121-125.

[6]张威，谢晓妤，刘晔. 基于Petri网的机场场面路径规划探讨[J]. 现代电子工程，2007，4（1）： 59-61.

ZHANG Wei， XIE Xiaoyu， LIU Ye. Petri-net based airport surface routes planning[J]. Modern Electronic Engineering， 2007， 4（1）： 59-61.

[7]GARCIA J， BERLANGAA A. Optimization of airport ground operations integrating genetic and dynamic flow management algorithms[J]. AI Communications， 2005， 18（2）： 143-164.

[8]KEITH G， RICHARDS A， SHARMA S. Optimization of taxiway routing and runway scheduling[C]∥Proc. of AIAA Guidance， Navigation， and Control Conference and Exhibit. Honolulu： [s. n.]， 2008： 1-11.

[9]MARN G. Airport management： taxi planning[J]. Annals of Operations Research， 2006， 143（1）： 191-202.

[10]王化冰. 一种基于同步合成Petri网的FMS建模方法[J]. 系统工程理论与实践，2001，21（2）： 35-42.

WANG Huabing. A Petri net synchronous synthesis method for modeling flexible manufacturing systems[J]. System Engineering： Theory and Practice， 2001， 21（2）： 35-42.

[11]GEN M， CHENG R W. Genetic algorithms and engineering optimization[M]. New York： John Wiley and Sons， 2000： 297-340.

[12]刘长有，丛晓东. 基于遗传算法的飞机滑行路径优化[J]. 交通信息与安全，2009，27（3）： 6-8.

LIU Changyou， CONG Xiaodong. Taxing optimization for aircraft based on genetic algorithm[J]. Transportation Information and Safety， 2009， 27（3）： 6-8.

[13]刘兆明，葛宏伟，钱锋. 基于遗传算法的机场调度优化算法[J]. 华东理工大学学报：自然科学版，2008，34（3）： 392-398.

LIU Zhaoming， GE Hongwei， QIAN Feng. Airport scheduling optimization algorithm based on genetic algorithm[J]. Journal of East China University of Science and Technology： Nature Science Edition， 2008， 34（3）： 392-398.

[14]GOTTELAND J， DURAND N， ALLIOT J M， et al. Aircraft ground traffic optimization[C]∥Proc. of the Genetic and Evolutionary Computation Conference. San Francisco： IEEE Press， 2001： 1-9.

[15]GOTTELAND J， DURAND N. Genetic algorithms applied to airport ground traffic optimization[C]∥Proc. of the 2003 Congress on Evolutionary Computation. Canberra： IEEE Press， 2003： 544-551.

第2篇

关键词：路径规划；搜索区域；A*算法

中图分类号：TP306文献标识码：A文章编号：1009-3044(2008)21-30523-02

An Algorithm Based on Improved A* Restrictions on the Path to Search Regional Planning Approach

XU Zhan-peng, LIN Kai

(Qingdao Technical College Information Institute of Qingdao,Qingdao 266555,China)

Abstract: According to A* algorithm has been given an improved optimal path planning method, this algorithm in accordance with the actual situation of the road network of layered LO at the same time, according to the actual network topology of the region to search for reasonable Restrictions experiment proved that the algorithm in the path planning saving time

Key words: Path planning; Search region; A* algorithm

1 引言

路径规划是在车辆行驶前或行驶过程中寻找车辆从起始点到达目的地的最佳行车路线的过程[1], 它属于智能交通

系统中的最短路径问题的一个具体应用。

最短路径规划产生的路径分为两种：距离最短的路径和时间最短路径,其中前者相对比较易于实现，但是它容易忽略路径的具体情况和行车实际环境以及人为因素。因为在实际车辆行驶中要求不但在此路径上行车距离尽可能短，而且路径的行车环境尽可能好，即尽量走道路较宽、路面质量较好、红绿灯较少、红绿灯设置间隔较大、车流量较小的路径，避免走行车环境太差的路径。作者针对最短路径规划存在的不足之处 ,根据已有A*算法，给出了一种改进的最优路径规划算法，此算法在根据道路的实际情况对路网进行分层的同时，根据实际路网的拓扑特性对搜索区域进行合理的限制。

2 A*算法

A*算法是人工智能中一种典型的启发式搜索算法．也是路径规划算法中的常用算法，它通过选择合适的估计函数，指导搜索朝着最有希望的方向前进．以期求得最优解限制搜索区域的多层最优路径规划算法，A*算法评价函数的定义为[2]：

f(n)=g(n)+h(n) （1）

f(n)是从初始点通过节点n 到达目标点的估价函数；

g(n)是在状态空间中从初始节点到n节点的实际代价；

h(n)是从节点n到目标节点最佳路径的估计代价。它决定了搜索的效率和可采纳性。对于几何路网来说，可以取两点间欧氏距离（直线距离）作为估价值，即

其中，(xd,yd)、(xn,yn)分别为节点n 和目标节点在数字地图中的坐标。由于估价值h(n)≤n 到目标节点的距离实际值，算法具有可采纳性，能得到最优解。[3]

3 改进的A*算法球最短路径

本文在三个方面对传统的A*算法进行了更改：1)A*算法提到的权值会根据用户的不同查询条件来调用相对应的计算权值的公式；2) 添加了一个判断过程。当查询下一个临近边的时候首先查询交通控制策略，判断是否有管制信息并将相映的点从v中删除；3) 减少路径搜索的范围，以出发点与目的地点连线的中间点为圆心，以两点之间直线距离的二分之一再加上几公里为半径画圆，在圆范围内的路径参加搜索，在圆范围之外的路径不参加搜索。

具体实现如下：

创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点，设各个点的权值（也称为费用值）为g。遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,计算X的估价值[4]。

1)初始的OPEN表仅包含原节点．其费用值g为0，令CLOSED为空表，设其他节点的费用为∞ 。

2)若OPEN表为空．则宣告失败：否则，选取OPEN表中所有的节点移至CLOSED表，将此CLOSED表作为新的OPEN表。重复第二步，直到深度达到4。

3)对第二步在深度4时形成的OPEN表进行操作，若OPEN表为空．则宣告失败：否则，选取OPEN表中具有最小权值的节点，并叫做最佳节点NEXT．把NEXT从OPEN表移至CLOSED表．判断此NEXT是否是一目标节点。若NEXT为目标节点．转步骤3，若NEXT不是目标节点。则根据地图数据库包含的联接路段属性扩展并生成NEXT的后继节点。对于每一个后继节点n，进行下列过程：

①计算节点n的费用：g(n)= NEXT费用+从NEXT到n的费用

②如果n与OPEN表上的任一节点相同．判断n是否具有最小的g值。若是最低的g值，用n的费用代替OPEN表中相同的节点费用。且建立匹配节点的后向指针指向NEXT

③如果n在CLOSED表中与一节点相匹配。检查节点n是否具有最小的g值，如果n具有最小的g值，则用节点n的费用代替匹配节点的费用。并把匹配节点的后向指针指向NEXT。并把该匹配节点移到OPEN表

④如果n不在OPEN表。也不在CLOSED表上，则把n的后向指针指向NEXT。井把n放入OPEN表中。计算节点n的估价函数：f(n)=g(n)+h(n)

例如图1，为带权的有向图。

根据步骤三，针对图1，算法的具体实现如图2。

4)重复第三步：

若在深度为7的搜索中找到目标结点且仅有一条路径，则该路径为最终路径，返回；

若在若在深度为7的搜索中找到目标结点并且有多条路径则回朔，比较找到的路径费用，取权值最小的作为最终路径；

若在在深度为7的搜索中未找到任何目标点则跳转到第五步。

5)从深度为7的搜索中的所有的NEXT节点回朔，即从NEXT的后向指针一直到原节点遍历节点，最后报告若干条路径，比较个路径费用，取费用最小的前100条路径继续重复第三步、第四步。由于h函数在满足h下限得条件下，愈趋近于h效率愈高，因此实际应用中，我们取的是节点到目的点的直线距离保证满足下限的情况下，尽可能的趋近h。

4 结语

实践表明基于改进A*算法的限制搜索区域的路径规划方法不仅在进行路径规划时节省了时间，而且规划后的路径大部分道路位于高层路网上，路径长度与最短路径长度之比小于1.1,可以被人接受，是行车意义上的最优路径。

参考文献：

[1] 付梦印.限制搜索区域的距离最短路径规划算法[J].北京理工大学学报,2004(10).

[2] 赵亦林.车辆定位与导航系统[M].北京:电子工业出版社,1999:1-7.

[3] 王亚文.智能交通系统中路径规划算法研究与系统设计[D].陕西师范大学,2007.

第3篇

【关键词】神经动态规划 最优路径 子问题 Matlab仿真

为了减轻交通压力，人们越来越关心交通系统的智能化进程。智能交通系统主要的研究方向之一就是动态路径诱导系统，它可根据外出的人们的需求，为驾驶员提供最新的路况信息和最佳路径选择，以此避免交通拥堵现象的发生，从而优化交通状况，最终使交通时时地保持一个合理的动态分配。目前，最优路径选择的方法有很多，但是真正需要解决大型问题时，计算机需要搜索的选择范围太大，传统的动态算法基本上无法处理。1995年，神经动态规划算法被提出，该算法把复杂的问题分成若干子问题，这些子问题被拆分后更容易解决，使计算过程大幅简化，且更容易被计算机处理。采用这种方法，可准确、快速、实时、稳定地选择出最优路径，值得推广。

1 神经动态规划概述与核心思想

在解决多阶段决策问题时，动态规划大致思想为：将非常繁琐的原始问题分解为若干个阶段，这些阶段看似不相关，却是相互联系的子阶段，在找到上一阶段的解决方法以后才能处理下一个阶段，依次求出每个阶段的解，最后得到全局最佳的解。多阶段决策问题具备很强的顺序性，同时每个阶段所使用的解决方法也是随着阶段的变化而变化，所以“动态”意义就得以体现。其中交通网中最佳路径的求解就是典型的多阶段决策问题。

在路径优化中，动态规划是一种非常经典的计算方法，但在处理实际问题的时，我们肯定会遇到缺少一个完整信息或者维数灾等一系列问题，所以，引进神经网络对动态规划具有较大的解决实际问题的意义。神经动态规划如图1所示。

2 基于神经动态规划算法的最优路径实现

（1）将原来的问题分解成很多个小问题，即子阶段，并且找到每个子阶段的最优解决办法。求解多级问题的步骤为：根据每个问题的特点，划分子阶段。在划分子阶段时，必须按照一定的规则，比如根据执行决策的时间、空间的顺序等。本文用x来表示子阶段变量。

（2）求解状态和状态变量。每个子阶段具体的起始位置可以依靠自然状态来指导，其中客观条件阶段性数目的状态是自然状态中的一种，它传达每个子阶段的关键信息，此外，一组或者无后效性的变量同样可以用来表示状态变量。本文用Hx来表示第x级的状态变量。

（3）求解原问题决策变量和集合。从目前阶段到下一个阶段状态选择时，决策者需要做出恰当的决策，决策变量的范围称为集合。本文用Dx表示决策集合，用Ux表示决策变量。

（4）研究状态转移的方程。假设状态转移方程是：Hx+1=Tx（Hx，Ux）。次方程式中Tx不定，根据具体问题才能确定，如果Hx确定，一旦变量Ux确定，那么第x+1阶段状态变量（Hx+1）也将确定。

（5）研究指标函数。因为n和vi的递进性和可分离性，所以很容易找到指标函数n和vi之间的关系，显然，指标函数的求解也相对简单化。

（6）动态规划函数的基本方程。边界条件为；

，第x-m阶的最优动态规划函数是。

3 仿真结果

将上述模型，在Matlab仿真软件上进行模拟仿真，分解原始问题并确定各个子阶段的最佳方案，将这个问题用网格的形式如图2进行表示：A为起始地点，E为目标地点，从起始地点到目标终点有很多路径，假设经过每个节点需要一定的运输成本，在Matlab仿真软件上进行仿真后依据动态规则算法的要求，设定好相应的算法模型以及相应的计算公式，这样便可以找到最优路径。

由图2可以非常清楚的看出，成本最低的路线为：或者或者，成本都是110。仿真结果可以看出神经动态规划算法具有较多优点：得到清晰运算结果；很容易找到全局的最优路径；可以找到一组完善的解，有利进一步的分析。

4 结语

我们在使用神经动态规划算法来探索最优路径的时候，具有很多优势，首先其具有稳定、可靠的步骤，过程并不复杂，但是给予我们的结果十分清晰明确，且适用于现实生活。使用这种动态规划算法解决复杂的问题时，可以非常容易找到解决方案，而且效率很高。当然，该算法也有一定的局限，但只要我们不断地改进完善，日后继续研究神经动态规划算法，相信一定可以攻克更多的局限，能够使其更好地被应用。

参考文献

[1]谬慧芬，邵小兵.动态规划算法的原理及应用[J].中国科技信息，2006（23）：32.

[2]杨琰，廖伟志，李文敬，杨文，李杰.基于Petri网的顾及转向延误的最优路径算法[J].计算机工程与设计，2013（10）.

作者简介

杨超（1994-），男，广东省吴川市人。现在就读于长沙理工大学计算机科学与技术系。

第4篇

关键词：最短路径；动态规划；C 语言编程

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）09-2191-03

1 概述

数学源于生活，又服务于生活.它是一门研究现实世界中的数量关系与空间形式的学科.当今社会，随着物质水平的不断提高，生活需求的不断扩大，自然资源的不断开发利用.像天然气管道铺设问题，厂区布局问题，旅行费用最小问题等都已成为我们平时经济生活中的普遍问题.它们其实都可以化归为最短路线问题，而最短路问题实质上是一个组合优化问题[1]。

动态规划方法主要是研究与解决多阶段决策过程的最优化问题，它将求解分成多阶段进行，不但求出了全过程的解，还能求出后部子过程的一组解，在求解一些生活实际问题时，更显其优越性。为了快速、简单的计算最短路径，节约运输时间与成本，该文利用动态规划的思想编写了C语言程序，解决物流运输过程中多地点的最短路径的选择问题。

2 最短路径问题

2.1 最短路径问题算法的基本思想

在求解网络图上节点间最短路径的方法中，目前国内外一致公认的较好算法有迪杰斯特拉（Dijkstra）及弗罗伊德（Floyd）算法。这两种算法中，网络被抽象为一个图论中定义的有向或无向图，并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时，以该矩阵为基础不断进行目标值的最小性判别，直到获得最后的优化路径[2]。

Dijkstra算法是图论中确定最短路的基本方法，也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径，通常采用两种方法。一种方法是每次以一个结点为源点，重复执行Dijkstra算法n次。另一种方法是由Floyd于1962年提出的Floyd算法，其时间复杂度为[On3]，虽然与重复执行Dijkstra算法n次的时间复杂度相同，但其形式上略为简单，且实际运算效果要好于前者。

2.2 最短路径问题算法的基本步骤[3]

这样经过有限次迭代则可以求出[v1]到[vn]的最短路线。

（2）Floyd算法的基本步骤

（3）动态规划算法基本步骤

我们将具有明显的阶段划分和状态转移方程的规划称为动态规划[1]。在解决多个阶段决策问题时采用动态规划法是一个很有效的措施，同时易于实现。

根据动态规划的基本概念，可以得到动态规划的基本步骤：1）确定问题的决策对象。2）对决策过程划分阶段。3）对各阶段确定状态变量。4）根据状态变量确定费用函数和目标函数。5）建立各阶段状态变量的转移过程，确定状态转移方程。

根据动态规划的基本模型，确定用动态规划方法解题的基本思路，是将一个[n]阶段决策问题转化为一次求解[n]个具有递推关系的单阶段的决策问题，以此来简化计算过程.其一般步骤如下：

用于衡量所选决策优劣的函数称为指标函数.指标函数有有阶段的指标函数和过程的指标函数之分.阶段的指标函数是对应某一阶段状态和从该状态出发的一个阶段的某种效益度量，用[vkxk，uk]表示。在本文里用[dkxk，uk]来表示某一阶段的决策的最短路径。过程的指标函数是指从状态[xn（k=1，2，...，n）]出发至过程最终，当采取某种子策略时，按预定的标准得到的效益值。这个值既与[xk]本身的状态值有关，又与[xk]以后所选取的策略有关，它是两者的函数值，记作[dk，nxk，uk，xk+1，uk+1，…xn，un]。过程的指标函数又是它所包含的各阶段指标函数的函数。本文研究的过程的的指标函数是其各阶段指标函数的和的形式.当[xk]的值确定后，指标函数的值就只同k阶段起的子策略有关。对应于从状态[xk]出发的最优子策略的效益值记作[fkxk]，于是在最短路问题中，有[fkxk=mindk，n]。动态规划求解最短路径程序流程图如图2所示。

3 最短路径态规划实际应用举例

设某物流配送网络图由12个配送点组成，点1为配送中心起点，12为终点，试求自终点到图中任何配送点的最短距离。图中相邻两点的连线上标有两点间的距离[4]。

首先用动态规划法来讨论图3的最短路径，由图可知：

1）集合[ξ4]中有点9、10、11，它们在一步之内可到达点12；

2）集合[ξ3]中有点6，7，8，它们不超过两步就可达到点12；

3）集合[ξ2]中包括点 2、3、4、5，不超过三步就可到达点12；

4）集合[ξ1]中包括点1，不超过四步可到达点12；

按照动态规划法类推，得到最优路径长为16，径路通过点为1，2，7，10，12和1，3，6，10，12。

根据动态规划算法编写C语言计算程序[5] [6]，计算得到实验结果如下图4所示：

由图4可以看出程序得到的结果与本文推出的结果一样。证明了本文编写的C语言程序是正确的。

4 结束语

综上所述，用动态规划解决多阶段决策问题效率高，而且思路清晰简便，同时易于实现.我们可以看到，动态规划方法的应用很广泛，已成功解决了许多实际问题，具有一定的实用性。此种算法我们用动态规划思想来编程，并解决相应的问题，其在 VC 环境下实现，能方便快速的计算出到达目的地的最短距离及路径，节省更多的运输时间与成本。不过，该文只考虑了动态规划算法在生活中的简单运用，在实际生活中可能存在多个目的地或者更复杂的情况.因此我们可以考虑将其进行改进或者结合启发式算法，使之更好的运用在实际生活中，这有待于以后的继续研究。

参考文献：

[1] 杜彦娟.利用动态规划数学模型求解最短路径[J].煤炭技术，2005（1）：94-95.

第5篇

关键词:移动多智能体;全局规划;局部规划

中图分类号:TP393文献标识码:A文章编号:1009-3044(2010)16-4487-03

Research on Path Planning for Mobile Multi-Agent

CHEN Cui-li, GAO Zhen-wei

(Henan Normal University, Xinxiang 453007,China)

Abstract: A path planning method based on both the benefits of global and local path planners is proposed for mobile Multi-Agent path planning in dynamic and unstructured environments. The global path planner uses A*algorithm to generate a series of sub-goal nodes to the target node, and the local path planner adopts an improved potential field method to smooth and optimize the path between the adjacent sub goal nodes. Taking into full consideration the kinematical constraints of the mobile robot, this method cannot only effectively generate a global optimal path using the known information, but also handle the stochastic obstacle information in time. and is simulated on simulation platform developed by using Visual Studio 2005 software, simulation result presents the validity and utility of the algorithm.

Key words: mobile Multi-Agent; global path; local path

在移动智能体相关技术研究中,路径规划技术是一个重要研究领域。移动智能体路径规划问题是指在有障碍的环境中,寻找一条智能体从起始点到目标点的运动路径,使智能体在运动过程中安全、无碰撞地绕过所有的障碍物。这不同于用动态规划等方法求得最短路径,而是指移动智能体能对静态及动态环境下做出综合性判断,进行智能决策。在以往的研究中,移动智能体路径规划方法大体上可以分为三种类型:其一是基于环境模型的路径规划,它能处理完全已知的环境下的路路径规划。而当环境变化时(出现移动障碍物)时,此方法效果较差,具体方法有:A*方法、可视图法、栅格化和拓扑图法等;其二是基于传感器信息的局部路径规划方法,其具体的方法有:人工势场法、模糊逻辑法和遗传算法等;其三是基于行为的导航行为单元,如跟踪和避碰等,这些单元彼此协调工作,完成总体导航任务。随着计算机、传感器及控制技术的发展,特别是各种新算法不断涌现,移动机器人路径规划技术已经取得了丰硕研究成果。

一个好的路径规划方法需要满足如下性能[1]:合理性、完备性、最优性、适时、环境变化适应性和满足约束。有些方法没有高深的理论,但计算简单,实时性、安全性好,就有存在的空间。如何使性能指标更好是各种算法研究的一个重要方向。

在未知的(或部分已知的),动态的非结构的环境下,多智能体利用传统的路径规划方法很难满足前面的性能要求,本文提出了一种将全局路径规划方法和局部规划方法相结合,将基于反应的行为规划和基于慎思的行为规划相结合的路径规划方法,其思路如下:多智能体分别采用A*算法进行全局路径规划,各自生成到达目标点的子目录节点序列,同时采用改进的人工势能对子目录节点序列中相邻节点进行路径的平滑和优化处理,该方法不但能够充分利用已知环境信息生成全局最优路径,而且还能及时处理所遇到的随机障碍(其它智能体)信息,从而提高了多智能体整体的路径规划的性能。

1 路径规划方法

1.1 相关研究

1) A*算法

在最佳优先搜索的研究中,最广范围应有的方法为A*搜索,其基本思想[2]是:它把到达节点的代价g(n)和从该节点到目标节点的代价h(n)结合起来对节点进行评价:f(n) = g(n) + h(n)(1)。A*算法用于移动多智能体的路径规划时,多智能体分别按照已知的地图规划出一条路径,然后沿着这条生成路径运动,但智能体传感探测到的环境信息和原来的环境信息不一致时,智能体重新规划从当前位置到目标点的路径。如此循环直至智能体到达目标点或者发现目标点不可达[3]。重新规划算法依旧是从当前位置到目标点的全局搜索的过程,运算量较大。而且由于采用A*方法规划出的最优路径并没有考虑到机器人的运动学约束,即使机器人可以采用A*方法规划出一条最优路径,机器人也未必可以沿着这条路径运动。

2) 人工势能法

人工势能法由 Khatib 提出的一种虚拟力法[4]。人工势场方法结构简单,便于低层的实时控制,在实时避障和平滑的轨迹控制方面得到了广泛的应用,但根据人工势场方法原理可知,引力势场的范围比较大,而斥力的作用范围只能局部的,当智能体和障碍物超过障碍物影响范围的时候,智能体就不受来自障碍物引起的排斥势场的影响。所以,势场法只能解决局部空间的避障问题,他缺乏所在的全局信息,,这样就造成产生局部最优解不能进行整体规划,智能于局部最小点的时候,智能体容易产生振荡和停滞不前。

1.2 路径规划方法描述

鉴于A*算法全局路径搜索的全局性与改进人工势场算法局部路径搜索的灵活性,通过一定的方法把两者结合起来,其思路如下:多智能体分别采用A*算法进行全局路径规划,各自生成到达目标点的子目录节点序列,同时采用改进的人工势能对子目录节点序列中相邻节点进行路径的平滑和优化处理,该方法不但能够充分利用已知环境信息生成全局最优路径,而且还能及时处理所遇到的随机障碍(其它智能体)信息,从而提高了多智能体整体的路径规划的性能。由于A*方法采用栅格表示地图,栅格粒度越小,障碍物的表示也就越精确,但是同时算法搜索的范围会按指数增加。采用改进人工势场的局部路径规划方法对A*方法进行优化,可以有效增大A*方法的栅格粒度,达到降低A*方法运算量的目的。

2 环境构造

目前主要有三种比较典型的环境建模方法:构型空间法、自由空间法和栅格法,本文仿真实验采用的环境建模方法是栅格法,栅格法将机器人路径规划的环境划分成二维网格,每格为一个单元,并假设障碍的位置和大小已知,且在机器人运动过程中不会发生变化。栅格法中的网格单元共有三种类型,即障碍网格、自由网格和机器人所在网格。目前常用的栅格表示方法有两种,即直角坐标法和序号法。这两种表示方法本质上是一样的,每个单元格都与(x, y)一一对应。本文采用序号法表示栅格,设栅格的中心点坐标为栅格的直角坐标,则每个栅格编号都与其直角坐标一一对应,地图中任意一点(x,y)与栅格编号N的映射关系为:N=INT(xGs)+xmaxGs×INT(yGs),(1)式中,xmax表示x轴的取值范围,Gs表示栅格尺寸的大小,INT函数表示取整,而栅格中心点的坐标为(xG,yG),它与栅格编号N之间的关系为:xG=(N%M)×Gs+Gs/2,yG=INT(N/M)×Gs+Gs/2,(2)式中,M=xmax/Gs,符号%表示取余操作。本文中根据机器人的尺寸来确定栅格的粒度,假设一个栅格能容纳一个智能体,这里选择栅格的大小为40cm×40cm[5]。本文的仿真环境为800cm×800cm,栅格号N=0~399,机器人的初始位置的栅格号为N=42,目标位置的栅格号为N=314。在Visual Studio 2005中进行仿真,仿真结果如图1所示,长方形和椭圆图形代表障碍物栅格,小圆圈所代表的栅格为机器人的起始栅格和目标栅格,剩下的是自由栅格。在路径规划中机器人可以选择自由栅格作为它的路径点。

建立栅格后,对栅格进行初始化。设置变量G_Obstacle为0表示自由栅格,G_Obstacle为1表示障碍网格包括机器人栅格。若障碍物或智能体占当前位置栅格面积大于1/3则设置变量G_Obstacle为1.

3 数据的采集

对于简单地形,我们将实际地形就行考察并进行测量、量化,转化为平面坐标数据最后转换相应的栅格编号。对于复杂地形在没有航摄资料的情况下,本实验以地图为数据源的DTM数据获取方法在,可利用已有的地形图采集地形数据,用手扶跟踪式数字化仪将平面图形转化为平面坐标数据,最后转换相应的栅格编号。

4 实现过程

第1步:对环境信息进行数据采集并转化成相应的平面坐标数据。

第2步:确定各个智能体的初始位置和目标位置。

第3步:建立栅格,对栅格进行初始化。

第4步:智能体S(i)首先根据已知信息规划出各自的一条目标序列S(i)n。

第5步:智能体S(i)利用测试传感器探测到临界危险区L范围内的信息与原有信息是否一致,当智能体利用传感器探测到临界危险区L范围内的信息与原有信息一致时,利用改进后的人工势能算法搜索相邻目标点之间的轨迹,否则智能体搜索从当前序列点S(i)n到S(i)n+4路径。定义临界危险区L、目标序列点S(i)n(n>=1)。

第6步:智能体一旦移动到达目标栅格,则程序终止;否则返回第5步。系统的工作流程如图2所示。

5 仿真结果及结论

在Visual Studio 2005平台上进行了仿真,,首先根据已知环境信息,进行数据采集量化并进行栅格化处理,设置障碍和智能体的大小及位置(为了简单化,本实验所有障碍都设置为圆形),再进行初始化操作,采用0、1二元信息数组存储栅格化的地形。

智能体运用A*算法进行全局路径规划,图3显示两个智能体的运动过程,显然两个智能体的路径相交可能会发生碰撞,智能体为了避免碰撞应重新规划算法依旧是从当前位置到目标点的全局搜索的过程,运算量较大。而且显然只用A*算法规划出二维路径点序列,相邻两点之间的夹角一定是π/4的整倍数,机器人很难按照所生成的序列点运动。智能体采用改进后的人工势场进行目标序列点之间的局部路径规划,图4显示智能体的运动过程。显然智能体的整条运动轨迹显得比较平滑同时又实现实时避障的目的。

6 总结

本文对多智能体在动态环境下路径规划技术进行了研究探索,提出了一种能够将全局路径规划方法和局部路径规划方法相结合,通过仿真取得了很好的结果,证明A*和人工势场算法的结合可行。

参考文献:

[1] 刘华军,杨静宇,陆建峰,等.移动机器人运动规划研究综述[J].中国工程科学,2006,8(1):85-94.

[2] Nilsson N J. Princip les of Artificial Intelligence[M].Berlin, Ger2 many: Sp ringer,1980.

第6篇

关键词：快速搜索随机树；汽车局部路径规划；高斯分布；路径跟随

中图分类号：TP242 文献标志码：A

An Improved RRT Algorithm of Local Path Planning for Vehicle Collision Avoidance

SONG Xiaolin，ZHOU Nan，HUANG Zhengyu，CAO Haotian

（Stake Key Laboratory of Advanced Design and Manufacturing for Vehicle Body， Hunan University，Changsha 410082，China）

Abstract：The original Rapidly-exploring Random Trees（RRT） algorithm has a rapid exploring-speed and short required time in path planning though it has large randomness and lacks of constraints. Thus， an improved RRT was proposed where the expected paths were built in both straight and curved roads. The random points were accorded with normal distribution around the expected paths. Heuristic search method that led the random points to the goal with a certain probability was also used for improvement. Compared with the original RRT algorithm， it performs quite well in both time-efficient and path quality in the simulation. Meanwhile， the effectiveness of the improved RRT algorithm was verified in Prescan. The path can be followed well and the secure lateral acceleration was satisfied. In conclusion， the improved RRT is effective in the path planning for vehicle collision avoidance.

Key words： rapidly-exploring random trees； vehicle path planning； Gauss distribution； path following

近年来随着汽车向智能化的不断发展，无人驾驶汽车技术引得越来越多人开始关注.路径规划作为其中一项关键技术，许多学者开展了有益的探索，并取得了一些研究成果.比如A*算法[1]、D*算法[2]等启发式搜索算法，在复杂环境下有着很好的规划速度，但是路径并不理想；人工势场法[3]是一种虚拟力算法，其优点是规划的路径平滑，但是容易陷入局部最优解；人工势场法与弹性绳模型结合[4-6]在车辆局部路径规划时有理想的路径，但由于模型比较复杂，搜索效率低；此外蚁群算法、遗传算法、神经网络算法、水滴算法等智能仿生算法[7-10]，在理复杂动态环境信息时有较好表现，但由于需迭代计算，时效性不够好.

快速搜索随机树算法（RRT）[11]由Lavalle于1998年提出，是一种基于树结构的典型算法，在移动机器人路径规划中有着较早应用.由于算法在进行路径规划时是随机采样，不需要预处理，因此有着很快的搜索速度.路径点之间可以经过运动学、动力学仿真生成可执行曲线，因此该方法可用于解决含有运动学约束的路径规划问题.但RRT算法存在一些不足：1）重现性差，对同一环境进行多次路径规划结果不同；2）寻找最优或者次优路径能力较差；3）随机采样点在整个可行域内随机寻点的搜索方式，存在很多不必要的运算，影响算法速度.

随着RRT算法的应用和改进，一些学者也提出了不同的方法.偏向RRT[12]以及双向RRT[13]的提出使得算法的搜索效率得到了提高；DRRT[14]与MP-RRT[15]原算法在搜索路径的稳定性上做出了改进.但上述改进之后的结果并不适用于汽车行驶路径.针对以上不足，本文将建立道路模型，考虑路径约束，改进RRT算法，使其规划出的路径能够适用于汽车运动.

1 道路环境建模

在环境已知的情况下，建立道路环境模型.直道环境模型根据道路长度以及车道宽即可得到，弯道环境模型如图1所示，位于道路上的惯性坐标系的原点选取在道路中心线上，道路宽度为W，规划起始点即主车位置A，目标点C，障碍车位置为B.高速路直线之间的缓和曲线通常采用回旋线来实现平滑过渡，回旋线的特征是其曲率变化为常数.假定长度为l的回旋线线段起始曲率为C1，终止曲率为Cf，变化常数为C2，则有C（l）=C1+C2×l成立，C2=（Cf-C1）/l.回旋线常采用多项式逼近的形式表示：

式中：R0为道路中心线初始横向偏移；C0为初始的方向角.根据图1，结合边界条件R（0）=0，R′（0）=0可以将R0和C0消除掉.

为了保持车道宽度一致，弯道的左右边界是通过中心线上点向着其法线方向上下平移单个车道宽度来得到.在道路坐标系下中心线上的点可由式（2）表示.

中心线上一点的切向量和法向量则可以表示成：

因此道路左右界则可以由（4）来表示

2 RRT算法原理

基本的RRT算法如图2所示，RRT算法以给定的起始点为随机树根节点，根据当前环境快速有效地搜索可行域空间，通过随机采样点，将搜索导向空白区域并增加随机树的叶节点直至目标点区域，从而生成从起始点到目标点的路径.

算法的一般步骤如下：

1）首先通过environment（）函数建立环境数据模型，初始化各项参数；

2） 通过while循环来判断树节点是否达到目标点goal范围内，若没有，则开始扩展点.先生成随机采样点Prand，在树节点上通过函数Nearest（）选择距离Prand最近的树节点作为扩展节点Pnear，通过扩展函数New得到新的树节点Tnew，并将其添加到随机树上，直到循环终止.

3）通过getpath（）函数来得到生成的路径path.

原算法主体程序如下：

如图3所示，传统的RRT算法应用到车辆路径规划中存在以下问题：

1）由于随机采样点随机性大，导致搜索空间中有过多的冗余搜索，表现为搜索树布满了道路环境空间；

2）搜索出来的路径曲率变化过大，甚至出现小范围内直角变化，这样的路径并不能满足汽车行驶的正常状态；

3）路径在靠近障碍时才开始避障，对于运动中的汽车会造成失稳或者与障碍物发生碰撞.

道路长度/m

3 RRT算法的改进

3.1 期望路径模型

针对原RRT算法表现出来的问题，提出了一种随机采样点高斯分布的改进RRT算法.根据汽车行驶环境不同，设计了两种期望路径模型.

3.1.1 直道模型

驾驶经验丰富的驾驶员期望的避障路径模型如图4（a）所示.期望路径以函数Epz表示，其中各段均为直线段，start为起始点，goal为目标点.

提前避障在车辆避障路径规划中是必要的，故在模型中需要添加提前避障距离S，并根据车速调整大小.设V为当前车速，tc为换道时间，通常完成换道时间tc为1～2 s，ΔS为自定义安全提前量.

对于车速为V的汽车其刹车距离

则提前避障距离

图4（a）中fz2表示提前避障区域，区间长度为S，fz4区间长度也为S.

期望路径只是粗略的路径模型，在此基础上进行平滑得出的路径并不能满足汽车安全稳定行驶的要求.因此采用RRT算法进行路径寻优搜索.为了使随机采样点分布在期望路径周围，利用高斯分布函数生成的点集中在其均值周围的特点，结合期望路径函数则可以实现这一目的.在道路坐标系下随机采样点的高斯分布概率函数为：

令μ=Epz（x），则可以得到如图4（b）所示的随机采样点分布趋势图.

道路长度/m（a）期望路径模型

道路长度/m（b）随机采样点高斯分布

σ的大小决定了随机点在Epz（x）周围的集中程度，σ越小越靠近Epz（x）.特别地，对于fz2与fz4周围的随机采样点，如图4（a）以fz2为例，通过相应水平范围的随机点高斯分布旋转处理得到，即对

旋转角度：

3.1.2 弯道模型

将弯道分为多段，采用直线代替弯道曲线的形式来完成期望路径模型的建立.如图5（a）弯道的期望路径以函数Epw来表示.

随机采样点在fw各段函数区间的分布同直道的处理相同，从而可以得到如图5（b）所示的分布趋势图.

3.2 约束条件

要使一条规划出来的路径有效地应用于汽车运动，即路径可跟踪，则规划路径时必须满足道路环境约束.首先，随机树节点的生成要满足道路环境约束，设Bleft，Bright分别为道路的左右边界，则树节点位置坐标要满足：

考虑到汽车是具有几何形体的，设其车宽为D，则上述y方向的约束变为：

假定汽车质心沿着规划的路径运动，为了保证行驶过程中的稳定性，规划出的路径的曲率变化不能过大.若在实际情况下前轮最大转角为θmax，则路径中子节点与其父节点的连线和父节点与其父节点的连线之间的夹角β必须满足β

其中：K1为直线TaTb的斜率；K2为TcTb的斜率.βT为夹角限制值.

为了保证所扩展的点不与障碍车有交集，即树节点不与障碍车碰撞的要求，采用安全椭圆包络障碍车，并适当放大安全椭圆以保证避障要求.若新节点与其父节点的连线不与安全椭圆相交，则所扩展的新点满足避障要求.取连线上的五等分点Pi（x，y），则约束方程表现为：

其中（xob，yob）为障碍车的位置，半车长a=2 m；半车宽b=1 m；s为安全椭圆放大系数，当s=2时，安全椭圆正好包络矩形的障碍车，因此从安全避障考虑，s≥2.

3.3 启发式搜索

原算法在扩展随机树时，由于缺乏导向机制，算法的收敛速度在一定程度上受到了影响，为了提高算法计算速度，引入启发式机制来对随机采样点以及随机树节点的选择进行处理.采样点Prand在随机生成过程中会以一定概率ρ0选择目标点，从而将随机树节点向目标点引导，通常ρ0=0.1.

其中，GaussRand（）为随机采样点生成函数.

另外，在选择Pnear时不再单独以距离Prand最近作为选择标准，而是以随机树节点的择优系数Ch来决定，Pnear确定为Ch值最小所对应的树节点.

其中ωi，ωj为权重系数，且ωi+ωj=1；Dpr为树节点到Prand的距离，Dg为树节点到目标点goal的距离.当ωj>ωi时，选择出的Pnear具有向目说憧拷的趋势.通过以上启发式的处理，使得算法更快地收敛，减少计算时间.

3.4 平滑处理

RRT算法规划出来的路径通常会存在小范围内的曲折现象，路径并不连续.为了使得路径能够满足汽车在运动时的稳定性和安全性要求，需要对规划出来的路径进行光滑处理.B样条在处理路径光滑时能够不改变整个路径形状而进行局部调整[16]，利用B样条这一特性，来对算法所规划出来的路径进行插值拟合，从而达到光滑路径的目的，通常所采用的为3次B样条曲线.

当有m+1个控制顶点Pi（i=0，1，…，m）时，3次B样条曲线表示为：

3.5 算法流程

随机树节点的扩展受到随机采样点的影响，通过以上方式的处理，随机采样点不再是在可行域内随机分布，而是具有一定的趋向性.这样使得随机树节点的分布也具有趋向性，算法的随机性得到了改善，所规划出来的路径质量得到提高.主体程序如下：

算法的实现过程如下：

1）初始化阶段，首先通过environment（）函数建立道路环境模型，根据现有的环境模型，以expect（）函数建立期望路径模型.

2） 路径求解阶段，进入while循环来判断树节点是否达到目标点goal范围内，若没有，则开始扩展点.随机采样点Prand通过Pick（）函数在goal和GaussRand（）函数所生成的点之间进行概率选择；根据当前Prand计算树节点的择优系数Ch，并由Fitbest（）函数得出Pnear；通过函数New在Pnear的基础上扩展出新节点Tnew，当新节点满足约束函数constraint（）时，新节点则添加到整个随机树Tree上，否则，返回循环重新寻点直到其终止.

3）路径处理阶段，getPath（）函数从所得的Tree中获取最短路径，最后通过函数smoothing（）对所得路径path进行光滑处理，得到一条平缓的路径.

4 仿真实验验证

改进的RRT在应用于信息多变的不确定环境时会存在建模困难的缺陷，本文主要对确定车道环境下的改进RRT开展研究.由于条件有限，不能在实际车辆中进行试验验证.而Prescan软件能够对实际场景进行建模，并且有根据实车建立的车辆模型数据库，能够模拟实际车辆行驶过程.因此，为验证改进RRT算法的有效性，在Prescan软件平台中搭建直道和弯道场景如图6所示，仿真实验硬件平台Win10+Core-i7@3.6Hz+ARM@8G.仿真参数如表1～表3所示.

4.1 规划时间的影响参数分析

影响算法计算效率的重要参数主要包括搜索步长ΔL、约束夹角βT.步长越小，为了搜索到目标点所需要的节点数目也就越多，计算时间越长；约束夹角βT越小，规划路径也越平缓，但计算时间也越长.改变步长以及约束夹角并进行大量仿真实验，统计表明：在ΔL=3，βT=15°时，改进RRT算法在规划时间以及路径效果上的综合表现较好.图7为ΔL=3时，不同角度下计算时间的统计，以20次计算时间平均值做一次统计.

4.2 规划路径对比

为说明改进RRT算法的效果，在直道场景中，采用了其余2种规划算法来进行对比.一种是蚁群算法[7]，另一种是弹性绳算法[5].直道仿真对比结果如图8所示，改进前后的算法规划效果在弯道中的对比如图9所示，路径效果参数对比如表4所示.由图和表的结果对比可知：

1）相对于蚁群算法和原RRT算法，改进RRT算法与弹性绳算法规划的路径都更为平滑，不存在频繁的大曲率变化，且路径较短.

2）从直道的规划时间上看，传统的蚁群算法用时最长，而弹性绳算法平均计算时间为1.42 s.改进后的RRT算法平均计算时间0.25 s，相对于原RRT计算时间略有增加，这是由于增加了模型处理过程以及各约束条件所导致的.但与其余2种算法相比，改进RRT算法依然保持其在计算时间上的优势.

3） 原RRT算法在靠近障碍时才开始避障，改进RRT算法能够实现提前避障，并且根据车速不同自动调节避障提前量，这对安全行驶很重要.

4.3 路径跟随验证

对一条规划出来的路径，需要验证其有效性，即路径的跟随性，本文采用路径跟随时主车的侧向加速度曲线监测路径的稳定性，跟随速度20 m/s.直道和弯道仿真结果分别如图10、图11所示.

由图10（a）（b）可知，直道跟随路径基本和目标路径一致，跟随误差在0.2 m以内，误差较小；车辆保持稳定行驶时的最大侧向加速度由地面附着力决定，通常为0.8g.由图10（c）可知，跟随时的侧向加速度在0.4g以内，说明整个过程中都能够保证主车按照路径行驶时的稳定性.弯道仿真结果如图11所示，跟随误差都在0.1 m以内，跟随效果好；侧向加速度都在0.5g范围内，满足稳定性要求.

5 结 论

本文在将RRT算法应用到汽车避障局部路径规划时，针对原算法在随机性以及路径曲率变化上的不足，建立了直道和弯道的期望路径模型，使随机采样点在期望路径模型周围近似呈高斯分布，采用启发式搜索方式使采样点和随机树节点向目标点靠近，从而降低算法的随机性；并且在路径规划时加入约束，使得所规划出的路径更为合理.仿真实验结果表明：改进RRT算法不仅规划出的路径质量高、实时好、跟随性强，而且车辆的稳定性也满足要求.因此，改进RRT算法可以应用于实时汽车路径规划.

参考文献

[1] YAO J， LIN C， XIE X， et al. Path planning for virtual human motion using improved A* algorithm[C]//Proceedings of the Conference on Information Technology： New Generations （ITNG）.Washington， DC： IEEE Computer Society， 2010： 1154-1158.

[2] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik， 1959， 1（1）： 269-271.

[3] KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots[J]. The International Journal of Robotics Research， 1986， 5（1）： 90-98.

[4] SONG X， CAO H， HUANG J. Vehicle path planning in various driving situations based on the elastic band theory for highway collision avoidance[J]. Proceedings of the Institution of Mechanical Engineers， Part D： Journal of Automobile Engineering， 2013， 227（12）： 1706-1722.

[5] SONG X， CAO H， HUANG J. Influencing factors research on vehicle path planning based on elastic bands for collision avoidance[J]. SAE International Journal of Passenger Cars-Electronic and Electrical Systems， 2012， 5（2）：625-637.

[6] 肖浩， 宋晓琳， 曹昊天. 基于危险斥力场的自动驾驶汽车主动避撞局部路径规划[J]. 工程设计学报， 2012，19（5）： 379-384.

XIAO Hao， SONG Xiaolin， CAO Haotian.Local path planning for autonomous vehicle collison avoidance based on dangerous repellant fields[J]. Chinese Journal of Engineering Design，2012， 19（5）： 379-384.（In Chinese）

[7] 康冰， 王曦辉， 刘富. 基于改进蚁群算法的搜索机器人路径规划[J]. 吉林大学学报：工学版， 2014， 44（4）：1062-1068.

KANG Bing， WANG Xihui， LIU Fu. Path planning of searching robot based on improved ant colony algorithm[J]. Journal of Jilin University：Engineering and Technology Edition， 2014， 44（4）： 1062-1068.（In Chinese）

[8] HU Y， YANG S X. A knowledge based genetic algorithm for path planning of a mobile robot[C]//Proceedings of the Conference on Robotics and Automation. Washington，DC： IEEE Computer Society， 2004： 4350-4355.

[9] 吴乙万，黄智.基于动态虚拟障碍物的智能车辆局部路径规划方法[J].湖南大学学报：自然科学，2013，40（1）：33-37.

WU Yiwan， HUANG Zhi. Dynamic virtual obstacle based local path planning for intelligent vehicle[J]. Journal of Hunan University： Natural Sciences， 2013，40（1）：33-37.（In Chinese）

[10]SHAH-HOSSEINI H. Problem solving by intelligent water drops[C]// Proceedings of the Conference on Evolutionary Computation.Washington，DC： IEEE Computer Society， 2007： 3226-3231.

[11]LAVALLE S M.Rapidly-exploring random trees： A new tool for path planning[J]. Algorithmic & Computational Robotics New Directions， 1998：293-308.

[12]LAVALLE S M， KUFFNER J J. Rapidly-exploring random trees： progress and prospects[J]. Algorithmic & Computational Robotics New Directions， 2000：293-308.

[13]KUFFNER J J， LAVALLE S M. RRT-connect： An efficient approach to single-query path planning[C]// Proceedings of International Conference on Robotics and Automation.Washington，DC： IEEE Computer Society， 2003：995-1001.

[14]FERGUSON D， KALRA N， STENTZ A. Replanning with rrts [C]//Proceedings of International Conference on Robotics and Automation.Washington，DC： IEEE Computer Society， 2006： 1243-1248.

[15]ZUCKER M， KUFFNER J， BRANICKY M. Multipartite RRTs for rapid replanning in dynamic environments[C]//Proceedings of International Conference on Robotics and Automation.Washington，DC： IEEE Computer Society， 2007： 1603-1609.

第7篇

关键字：最优路径选择；A-Star算法；贪婪算法；模拟仿真

中图分类号：TP301.6 文献标识码：A DOI：10.3969/j.issn.1003-6970.2013.06.012

0 前言

物流与国民经济及生活的诸多领域密切相关，越来越多得到重视，甚至被看作是企业“第三利润的源泉”，而在物流成本方面，运输费用占大约50% ，比重最大[1]。因此，物流配送中最优路径选择的研究具有巨大的经济意义。物流配送中的最优路径选择问题的研究和应用都相当广泛，近几十年，国内外均有大量企业机构、学者对该问题进行了大量而深入的研究，取得丰硕的学术成果。如1953年，Bodin，Golden 等人便撰文综述了该问题的有关研究进展情况，列举了几百余篇相关文献，这些文献成为了早期车辆路径问题研究资料，随后随着该问题不断研究深入，约束模型及条件不断变化，车辆路径问题研究的最新进展可见Alt- inkerner 和 Oavish，Laporte，Salhi 等人的综述性文章[2]。围绕该问题的解决也极大推动了计算机学科的发展，不断有新的模型和算法推出。针对物流配送车辆路径优化问题的求解方法很多，根据算法原理的不同大致可分为两大类：精确算法和智能式启发算法。精确算法是指可以车辆路径问题的数学模型可求出其最优解算法，但由于算法存在诸多缺陷，所以在实际中应用并不广泛。目前，启发式算法是解决物流配送中最优路径选择的主要方法和主向[3]。近年来，随着科学的发展，一些新的启发式方法被用在求解物流路径选择及优化问题上，可以通过使用启发式方法获得较快的收敛速度和较高质量的全局解，常用的算法有模拟退火算法、GA 算法等[4]。A*算法是人工智能中一种典型的启发式搜索算法，被广泛应用于最优路径求解和一些策略设计的问题中[5、6]。本文结合贪婪算法的思想，深入研究A-Star（A*）算法，在QT Creator平台上，采用Visual C++编程对物流配送问题进行模拟仿真，同时考虑最短时间和最短路径两个方面，以此来解决物流配送中最优路径选择的问题，达到物流配送最优线路规划的目的。

1 需求分析

1.1 总体框架

在物流配送时，物流车装载当日需要配送的货品从仓库出发，按照事先规划好的最优配送路径为每一个客户进行配送，最后返回仓库。这就涉及在配送时配送路线的选择问题，而在配送之前，IT系统需要根据客户的配送地址间线路间距和经验路况分析计算出一条最优配送路径。并且在配送过程中，如果某路段发生堵车状况，需要动态调整配送路线，以达到最优配送的目的。为此，在QT Creator平台上，以面向对象的设计方式来开发最优物流配送的功能软件。通过再现交通运输环境，模拟物流运输中的突发事件，优化物流配送的路线，分别根据需求，设计出最短路径和最少时间两种配送方式，并通过二维动画的效果显示出来。通过此软件呆模拟解决物流配送中各种情况，从而降低运输成本。设计本软件的总体思路如图1所示。

1.2 功能设计

设计的软件从功能上来说，主要包括以下几点：

（1）载入一张已有地图（*.map的文件）或生成一张空白地图。用户可以在这张空白地图上操作，通过障碍物的增删来设置城市的道路。

（2）道路突发事件设置。

a.用户可以根据实际情况或主观意愿对地图进行规划。在地图中添加障碍物，设置道路前方的暂时封闭或者道路施工等未知路况。

b.也可以模拟城市人流量大的地方，通过在地图上，设置易堵车而导致前行速度下降的未知路况。

（3）设置仓库及客户点。

a.随机生成仓库及客户点。在地图中，用户可随机生成若干个客户点和仓库点。

b.指定生成仓库及客户点。在已生成或者模拟的地图上，根据用户的不同需求，可在地图上任意位置生成客户点和仓库点。

c.可以对仓库及客户点进行增删。

（4）计算路径及优化。

a.根据用户之前模拟的各种情况，计算其最短路径。根据用户载入或者自己规划的地图，模拟计算出最短路径，在界面的左上角显示其时间，并在地图上显示其路径。

b.根据用户之前模拟的各种情况，计算其最短时间。根据用户载入或者自己规划的地图，模拟计算出最短时间，在界面的左上角显示其时间，并在地图上显示其对应路径。

软件的大致功能如下图2所示。

图2 功能模块图

2 算法描述

2.1 贪婪算法

贪婪算法（Greedy algorithm）又叫登山法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但适用范围有限的策略[7]。

贪婪算法是基于邻域的搜索技术，它在计算过程中逐步构造最优解[8]。在构造解的过程中，每一步常以当前情况为基础根据某个优化测度（greedy criterion，贪婪准则，也称贪婪因子）作最优选择，而不考虑各种可能的整体情况，选择一旦做出就不再更改，这省去了为找最优解要穷尽所有可能而必须耗费的大量时间。它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，一般情况下只是近似最优解[9]。虽然贪婪法不是对所有问题都能得到整体最优解，但对范围相当广泛的求最优解问题来说，它是一种最直接的算法设计技术，通过一系列局部最优的选择，即贪婪选择可以产生整体最优解[10]。

对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择（贪婪选择）来达到。根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。它是一种改进了的分级处理方法。

2.2 A-Star算法

A*算法是人工智能中一种典型的启发式搜索算法，它是一种静态路网中求解最短路最优算法，其公式可表示为：

（1）

其中，是从初始点经由节点到目标点的估价函数；是在状态空间中从初始节点到节点的实际代价；是从到目标节点最佳路径的估计代价[11、12]。

在A*算法中，找到最短路径（最优解的）的关键在于估价函数的选取。当估价值到目标节点的距离实际值时，搜索的点数多，搜索范围大，效率低，但能得到最优解；当估价值到目标节点的距离实际值时，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解[13、14]。

A*算法的难点在于建立一个合适的估价函数，估价函数构造得越准确，则A*算法搜索的时间就越短[15]。A*算法的估价函数可表示为：

（2）

这里，是估价函数，是起点到节点的最短路径值，是到目标的最短路径的启发值。由于这个其实是无法预先知道的，所以我们用前面的估价函数做近似。当时，可以代替（大多数情况下都是满足的，可以不用考虑），但只有在时，才能代替。可以证明，应用这样的估价函数能有效地找到最短路径。

本文综合贪婪算法和A*算法的思想来求解决物流配送中最优路径选择的问题。图3为综合算法的流程图。

3 实验仿真设计

3.1 软件概述

开发的软件要具有实用性，这就是说，能给企业带来效益，这就包了两方面的内容：企业能获得的利润和客户的满意程度。也就是说采用所建立的模型要设计出合理的物流配送路线，保证在较短的路程或时间内遍历所有的节点，从而保证货物按时送到。

从算法角度来看，为了保证算法的有效性和高效性，结合软件的功能，则该软件的设计目标[16]为：①路径最短或时间最短， ②满足实际中遍历节点的要求， ③算法高效性， ④软件的普度适用性。

软件操作流程具体步骤如下：

第一步.用户载入一张已有地图或生成一张空白地图。

第二步.设置相关参数及约束条件。

第三步.显示计算结果和最优路径。

该软件可运行于Windows 7操作系统，主要包括3个部分：地图文件的读取部分、算法部分和用户界面部分。

3.2 软件模拟实现

1.初始化

根据软件的需求分析，本软件初始产生一个空白的二维平面图，在该模块用户可以根据实际情况模拟出实际路况，提供两种方式来实现该功能：

（1）通过点击工具栏上面的初始化按钮自动初始化。

（2）通过鼠标右键选择初始化选项。

图4 系统初始化界面

2.道路的参数设置

在视图界面中，用户可以点击鼠标右键，选择生成障碍物或删除障碍物来模拟现实生活中城市道路可能发生的各种情况，如：

（1）用户可以根据实际情况，点击鼠标右键，在出现的下拉菜单中，选中添加障碍物，设置道路前方的暂时封闭或者道路施工等未知路况。

（2）也可以在地图上，点击鼠标右键来设置易堵车而导致前行速度下降的未知路况。

在地图中浅黄色的区域是模拟人流量大的闹市区。深褐色方块模拟障碍物。

图5 道路模拟图

3.仓库点及客户点的生成

客户点和仓库点的生成包括两种情况：

（1）随机生成客户点和仓库点。在视图界面中，通过顶端的输入框，输入生成客户点或仓库点的个数，点击生成客户点或仓库点按钮来随机生成客户点或仓库点。

（2）在指定位置生成客户点和仓库点。在已生成或者模拟的地图上，根据用户不同的需求，在地图指定位置生成客户点和仓库点。

在如图5的道路设计下，在地图上随机添加了10个客户点和1个仓库点，如图6所示。

图6 场景界面图

4.路径最短和时间最短的配送路径

根据图6所设计的场景，通过贪婪算法和A*算法，分别计算出路径最短和时间最短的配送路径，并在地图上显示其路径。图7依据最短路径实现物流配送的最优方案，主要从距离这个方面进行考虑；图8根据最短时间实现物流配送的最优方案，主要考虑的是在道路有突发状况发生时物流配送的时间最少。

图7 路径最短的配送路径

图8 时间最短的配送路径

4 认识与结论

通过对物流配送中的实际问题进行模拟研究，在QT Creator平台上采用Visual C++编程开发出针对物流配送中最优路径选择问题的软件，从最短时间和最短路程两方面考虑，为物流配送公司提供可靠有效的参考信息，使配送方案符合实际情况。同时，深入研究了贪婪算法和A*算法，从算法的角度对物流配送中的时间和路程进行分析，设计实现了物流配送中最优数学模型，以期达到最优路径的目的。通过本研究的结果来看，开发的模拟软件能解决物流运送过程中的时间、路径等实际问题，同时实现了二维图形的可视化，更加直观地体现了物流配送中存在的问题和解决方式，对物流配送企业提高运营效率、降低运营成本等具有重要意义。

参考文献

[1]黄中鼎. 现代物流管理学[M]. 上海： 上海财经大学出版社， 2004， 1-37.

[2]谢秉磊， 郭耀煌， 郭强. 动态车辆路径问题：现状与展望[J]. 系统工程理论方法应用， 2002， 11（2）： 116-120.

[3]邹挺. 基于蚁群和人工鱼群混合群智能算法在物流配送路径优化问题中的应用研究[D]. 苏州： 苏州大学， 2011， 3-7.

[4]吴云志， 乐毅， 王超， 等. 蚁群算法在物流路径优化中的应用及仿真[J]. 合肥工业大学学报（ 自然科学版）， 2009， 32（2）：211-214.

[5]王海梅， 周献中. 直线优化A*算法在最短路径问题中的高效实现[A]. 全国第计算机技术与应用（CACIS）学术会议论文集（下册）[C]， 2008， 932-936.

[6]陈和平， 张前哨. A*算法在游戏地图寻径中的应用与实现[J]. 计算机应用与软件， 2005， 22（12）：94-96.

[7]晏杰. Matlab 中贪婪算法求解背包问题的研究与应用[J]. 赤峰学院学报（自然科学版）， 2012， 28（9）：23-24.

[8]刘纪岸， 周康渠， 宁李俊， 等. 基于贪婪算法的摩托车生产物流配送规则优化[J]. 制造业自动化， 2010， 32（5）：97-99.

[9]蒋建国， 李勇， 夏娜. 一种求解单任务Agent联盟生成的贪婪算法[J]. 系统仿真学报， 2008， 20（8）：1961-1964.

[10]江朝勇， 陈子庆， 谢赞福. 基于优先级贪婪算法的排课系统排研究与实现[J]. 信息技术， 2008， 24（7）：173-176.

[11]徐伟， 孙士兵. 基于A-Star算法警用地图查询系统的设计与实现[J]. 信息安全与技术， 2011. 5-2：52-56.

[12]王敬东， 李佳. A*算法在地图寻径中的实用性优化[J]. 电脑开发与应用， 2007， 20（7）：24-25.

[13]（美）Stuart Russell，（美）Peter Norvig. 人工智能——一种现代方法[M]. 姜哲，译. 北京：人民邮电出版社， 2004， 76-83.

[14]王文杰， 叶世伟. 人工智能原理与应用[M]. 北京：人民邮电出版社， 2004， 115-121.

第8篇

关键词： B样条曲线； 无人车； 路径规划； 碰撞检测； 最大曲率约束； 最优路径

中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2016）26-0235-03

B-spline Curve based Trajectory Planning for Autonomous Vehicles

QU Pan-rang，LI Lin ， REN Xiao-kun ，JING Li-xiong

（Institute of Aeronautics Computing Technique Research， Xi’an 710065， China）

Abstract：Path planning is an important research topic in the field of the unmanned vehicle motion planning， and it directly affects the performance of unmanned vehicles in a complex traffic environment. Taking the requirement for smoothness into account， this paper proposed a method based on B-spline curve and built a planning model which can be divided into four steps， including path clusters， constraint of maximal curvature， collision detection and optimal path. This method works efficiently and simulation results show efficiency of the method.

Key words：B-spline curve； autonomous vehicle； path planning； collide detection； constraint of maximal curvature

1 引言

近年来，无人驾驶技术备受关注，各大研究机构和企业争相推出各自的无人驾驶平台。无人车作为未来智能交通的主要主体也逐渐融入到我们的日常生活中，比如自主巡航[1]和自动泊车等等。然而，为了使其更好地服务于我们，需要进一步提高其智能化水平，而路径规划作为连接环境感知和运动规划的桥梁，是无人车智能化水平的重要体现[2]。

由于受到自身动力学和运动学模型的约束，车辆的路径规划问题除过要严格满足端点状态约束之外，还要求其中间状态满足运动系统的微分约束。由于实现简单，并且高阶多项式曲线能够很好地满足运动系统的微分约束，生成高阶平滑的路径，所以很多路径规划系统选择使用基于多项式曲线的方法生成路径。B样条曲线是一种典型的多项式曲线，且因为其所有的中间状态均是由控制点加权生成，所以其能够完全满足端点状态约束。综合考虑无人车路径规划的要求和实现复杂度，在仅已知初始位姿和目标位姿的情况下，本文选择B样条曲线生成路径，重点讲述分步规划模型，即路径簇生成、最大曲率约束、碰撞检测以及最优评价四个过程，并通过Matlab仿真对本文方法进行了验证。

2 问题描述

本节分别描述了无人车路径规划问题和B样条曲线。

2.1 路径规划问题描述

路径规划得到的是一条从初始位置到目标位置的路径，即二维平面内一条从初始位置点到目标位置点的曲线，曲线上的每一个点表示车在行驶过程中的一个状态。考虑到实现方便，本文将路径描述成离散点序列[Sstart，S1，???，Sn，Sgoal]，如图1所示，序列中每一个点[Si（xi，yi，θi）]表示车的一个状态，其中[（xi，yi）]表示此时刻车辆的位置，[θi]表示车辆的航向，[Sstart]和[Sgoal]分别表示车辆的初始状态和目标状态。图1中的圆[（xobs1，yobs1，robs1）]表示环境中的障碍物，[（xobs1，yobs1）]表示障碍物的位置信息，[robs1]表示障碍物的半径。

2.2 B样条曲线

如果给定[m+n+1]个控制点[Pi（i=0，1，???，m+n）]，就可以构造[m+1]段[n]次B样条曲线，其可以表示为公式1：

[Pi，n（t）=k=0nPi+k?Fk，n（t） ，t∈[0，1]Fk，n（t）=1n！j=0n-k（-1）j?Cjn+1?（t+n-k-j）n ， t∈[0，1] ， k∈0，1，???，n] （1）

其中，[Pi，n（t）]表示第[i]个[n]次B样条曲线片段，[n]表示B样条曲线的次数，[t]为控制参数，其取值范围为[[0，1]]，[Pi+k]为控制点，[Fk，n（t）]为B样条基。依次连接全部[n]阶B样条曲线段就组成了整条B样条曲线。

3 本文算法

本节重点讲述基于B样条曲线的路径规划方法和基于该方法生成路径的过程。

3.1 基于B样条曲线的路径规划方法

选择三阶B样条曲线生成几何路径，即每四个控制点生成一个路径片段，然后通过片段的拼接就可以实现从初始状态到目标状态的路径规划，下面着重讲述基于六控制点的三阶B样条曲线生成满足车辆端点位姿约束路径的方法，如图2所示。

l 依据初始状态选择控制点[P0，P1，P2]。当[P0，P1，P2]三个控制点共线，并且[P1]为线段[P0P2]的中点时，生成的B样条曲线与线段[P0P2]相切于点[P1]。所以选择无人车的初始位置为控制点[P1]，将控制点[P0]和[P2]选在初始航向角[θstart]所在直线上，并关于控制点[P1]对称。如是，即能满足车辆的初始位姿约束；

l 依据目标状态选择控制点[P3，P4，P5]。当[P3，P4，P5]三个控制点共线，并且[P4]为线段[P3P5]的中点时，生成的B样条曲线与线段[P3P5]相切与点[P4]。所以选择无人车的目标位置为控制点[P3]，将控制点[P3]和[P5]选在目标航向角[θgoal]所在的直线上，并关于控制点[P3]对称。如是，即能满足车辆的目标位姿约束。

（a） 路径簇

（b） 最大曲率约束

（c） 碰撞检测

3.2 分步路径规划

本小节将以图3所给定的场景为例，讲述最优路径生成的过程。

3.2.1 路径簇生成

在选定控制点[P1]和[P4]之后，通过选择不同的控制点[P2]和[P3]，从而得到多组控制点，进而得到多条路径。将控制点选择的极限定为线段[P1P2]、[P3P4]与[P1P4]相等，但是[P1P2]和[P3P4]不能出现交叉。将这个范围等间隔量化，各取四个点，共组成16组控制点，得到16条路径，如图3（a）中的蓝色曲线所示。

3.2.3 最大曲率约束

理论上，车辆的最小转弯半径[Rmin=Lsin（θmax）]是其本身属性[3]，只取决于车辆的轴距[L]和最大前轮转角[θmax]。那么，车辆可行驶路径的最大曲率[κmax=1Rmin]也是固定的，假设无人车可行驶路径的最大曲率[κmax=16]，以此为约束条件，在路径簇中选择满足最大曲率约束的路径，如图3（b）所示，图中绿色曲线表示不满足最大曲率约束的路径。

3.2.4 碰撞检测

碰撞检测的目的是保证车辆在规划路径上行驶而不与障碍物发生碰撞。采取的碰撞检测的方法很简单，因为环境中的障碍物采用圆来描述，所以只要判断路径上每一点到圆心的距离与障碍物半径的关系，就能确定其是否发生碰撞。由两点间距离公式：

[d=（x1-x2）2+（y1-y2）2] （2）

如果[d]大于障碍物半径，则不发生碰撞；如果[d]小于障碍物半径，则发生碰撞。图3（c）中的蓝色曲线表示既满足最大曲率约束，又不与障碍物碰撞的路径。

3.2.2 最优路径

路径要求的侧重点不同，优化的目标函数也可以有多种选择，常用的目标函数有最短和最平滑等。其中，路径最短可以抽象成优化问题：

[traoptimal=arg mintraids] （3）

路径最平滑可以抽象成优化问题：

[traoptimal=arg mintraiκ2] （4）

式中，[traoptimal]为最优路径，[traids]为第[i]条路径的长度，[traiκ2]为第[i]条路径上所有点处的曲率平方之和。图3（d）中的红色曲线即为得到的最短可行驶路径。

如是，就能得到满足车辆运动学约束，并且无碰撞的最优路径。

4 结论

本文选择使用B样条曲线解决无人车路径规划问题，并建立了基于B样条曲线的分步规划模型。仿真结果表明，使用基于B样条曲线的路径规划方法能够很好地解决简单障碍物场景中无人车的路径规划问题，并且因为路径生成过程简单，所以该方法常常表现得十分高效，能够完全满足无人车路径规划系统对算法实时性的要求。

参考文献：

[1] Vahidi A， Eskandarian A. Research advances in intelligent collision avoidance and adaptive cruise control [J]. IEEE Transactions on Intelligent Transportation Systems， 2003， 4（3）：143-153.

第9篇

关键词： 最短路径； A*算法； Dijkstra算法； 路径优化

中图分类号： TN911.1?34； TP312 文献标识码： A 文章编号： 1004?373X（2017）13?0181?03

Abstract： The path optimization is an important way to solve the traffic congestion and blocking. The traditional Dijkstra algorithm based on monophyletic shortest path can find the shortest path information from the starting point to other points， but its search time is long in the situation of various map obstacles. The A* algorithm with heuristic function in the field of artificial intelligence can select the optimum path by itself because of its memory function. With the increase of obstacle information and location information， the search efficiency of A* algorithm becomes higher. The A* algorithm and traditional Dijkstra algorithm were simulated and compared with experiments， and their search speed and search efficiency were compared. The simulation results show that the search effect of A* algorithm is more effective in the actual road network.

Keywords： shortest path； A* algorithm； Dijkstra algorithm； path optimization

最短路轿侍[1]是图论中网络分析的经典问题，近年来，随着路径搜索技术的不断发展，已经涌现出很多成熟的路径规划算法，比如，基于图论的Dijkstra算法[2?3]，以及关于人工智能领域的启发式搜索算法和动态规划算法等。A*启发式搜索算法作为人工智能领域的重要组成部分，其针对网格数据有着更高的运算效率，而且利用启发信息大幅度提高了搜索速度。这种全新的启发式搜索算法[4]将会极大地改变现有的交通管理与服务模式。

1 A*算法原理

传统的BFS算法的评估函数只考虑当前点与终点的距离，其策略是选择与终点最近的点进行搜索。而Dijkstra算法则只关注当前点与起点的距离，选择与起点最近的点开始搜索。A*算法[5]则是将二者结合起来，其启发函数采用如下的计算公式：

式中：就是A*算法[5]对每个节点的评估函数[2]，其包含两部分信息：是从起点到当前节点的实际代价，也就是从起点到当前节点的移动距离；相邻的两个点的移动距离是1，当前点距离起点越远，这个值就越大。是从当前节点到终点的距离评估值，这是一个从当前节点到终点的移动距离的估计值。

A*算法的搜索过程需要两个表：一个是OPEN表，存放当前已经被发现但是还没有搜索过的节点；另一个是CLOSE表，存放已经搜索过的节点，具体的算法流程图如图1所示。

1.1 常用的距离评估函数

是A*算法的距离估计值[6]，A*算法需要一个距离评估函数来计算这个值。常用的距离评估函数有曼哈顿距离、欧式几何平面距离和切比雪夫距离。在没有障碍物的地图上，这三种距离评估函数得到的效果是一样的，但是在有障碍物的情况下，这三种距离评估函数的效果略有差异。当距离评估函数总是0时，A*算法就退化为Dijkstra算法[6]的效果。

1.1.1 曼哈顿距离

从数学上描述，曼哈顿距离是两个点在各个坐标轴上的距离差值的总和，维几何空间中曼哈顿距离的数学描述为：

对于二维平面上的两个点和，其曼哈顿距离为：

即欧式几何平面距离为在直角坐标系中两个坐标轴上的投影距离和。

1.1.2 欧式几何平面距离

欧式几何平面距离（Euclidean distance）又称为欧式距离或欧几里得距离[7]，其数学定义是维空间中两个点之间的真实距离（几何距离），其数学符号可以描述为：

对于二维平面上的两个点和其欧式几何平面距离为：

即平面几何中两点之间的几何距离。

1.1.3 切比雪夫距离

切比雪夫距离（Chebyshev Distance）是由一致范数（或称上确界范数）衍生的度量，从数学角度上理解，对于两个向量和其切比雪夫距离就是向量中各个分量的差的绝对值中最大的那一个，用数学符号可以描述为：

特别情况下，对于平面上的两个点和，其切比雪夫距离为：

距离评估函数与A*算法的结果之间存在很微妙的关系，如果令始终为0，相当于一点启发信息都没有，则A*算法[5]退化为Dijkstra算法，这种情况即为最差的A*算法。的值越小，启发信息越少，搜索范围越大，速度越慢，但是越有希望得到最短路径；的值越大，启发信息越多，搜索的范围越大，但是其有可能得不到真正的最短路径。当大到一定程度时，公式中的就可以忽略不计，则A*算法演化成为BFS（广度优先搜索算法），速度最快，但是不一定能够得到最短路径。所以通过调整和函数，可以使得A*算法[6]在速度与准确性之间获得一个折中的效果。

1.2 A*算法的实现

A*算法实现的关键在于维护OPEN表和CLOSE表，其中对于OPEN表的主要操作就是查询最小的节点以及删除节点，因此考虑在算法实现时将OPEN表[7]设计为有序表。这样在OPEN列表存储数据时就可以自动将数据按照距离进行排序，这样算法的执行效率比较高。A*算法的参数设置见表1，参数的迭代次数见图2。

通过仿真实验分析可以得出，A*算法[5]在有障碍物的情况下中和了BFS算法和Dijkstra算法的优点，能够更有效地找到最终的最短路径。

2 A*算法与Dijkstra算法效率的比较

Dijkstra算法是典型的单源最短路径算法，其适用于求解没有负权边的带权有向图的单源最短路径问题。由于Dijkstra算法[2?3]使用了广度优先搜索的策略，它可以一次得到所有点的最短路径。但是，它只是简单地做广度优先搜索而忽略了很多有用的信息。盲目搜索的效率很低，耗费很多时间和空间。考虑到实际地图上面两点之间存在位置和距离等信息，A*算法既能够像Dijkstra算法那样搜索到最短路径，又能像BFS（广度优先搜索算法）一样使用启发式函数进行启发式搜索，是目前各种寻径算法中最受欢迎的选择。

将A*算法同Dijkstra算法[6]进行仿真比较，用于比较性能的主要指标有：时间复杂度分析；搜索到最短路径的成功率分析。利用C++语言编制了三种算法的最短路径搜索程序，运行在本地计算机上，并得出仿真模拟图。

搜索效率的对比结果如表2所示。

由表2可以看出：当地图节点的个数和弧的条数比较多时，A*算法[5]的搜索效率比Dijkstra算法快很多，当节点数不断增多时，其搜索最短路径的效率更高。在相同路网和位置信息的条件下进行仿真实验的结果如图3所示。

由图3可以看出，两种算法在相同障碍物条件下进行模拟仿真时，A*算法的搜索效率和时间复杂度要明显优于Dijkstra算法，并对不同实验场景下的效率进行对比，结果如图4所示。

3 结 语

从Dijkstra算法和A*算法[2]的实现可知，Dijkstra算法的时间复杂度是其中是有向图中顶点的个数。对于不含负权边的有向图来说，Dijkstra算法是目前最快单源最短路径算法。A*算法兼有Dijkstra算法和广度优先搜索算法的特点，在速度和准确性之间有很大的灵活性。除了调整和可以获得不同的效果外，A*算法还有很多可以提高效率的改进方法。比如，在地图比较大的情况下使用二叉堆来维护OPEN表以获得更好的运算效率。

参考文献

[1] WORBOYS M. Event?oriented approaches to geographic phenomena [J]. International journal of geographical information science， 2010， 19（1）： 1?28.

[2] NARAYANASAMY V. Game programming gems 6 [EB/OL]. [2015?05?12]. /data.

[3] DYBSAND E. A finite state machine class [J]. Game programming gems， 2000（1）： 237?248.

[4] 周郭许，唐西林.基于栅格模型的机器人路径规划快速算法[J].计算机工程与应用，2006，42（21）：197?199.

[5] 李大生，刘欣，吴明华，等.基于动力学约束的机器人无碰运动规划[J].机器人，1990（5）：14?19.

[6] VIDALVERD? F， BARQUERO M J， CASTELLANOSRAMOS J， et al. A large area tactile sensor patch based on commercial force sensors [J]. Sensors， 2010， 11（5）： 5489?5507.

[7] 李得伟，韩宝明，韩宇.一种逆向改进型A*路径搜索算法[J].系统仿真学报，2007，19（22）：5175?5177.

[8] 林丹.一种室内清洁机器人返回路径规划算法[J].重庆科技学院学报（自然科学版），2009，12（1）：110?113.

[9] 赵真明，孟正大.基于加权A～*算法的服务型机器人路径规划[J].华中科技大学学报（自然科学版），2008（z1）：196?198.