路径规划范文

时间:2023-03-03 05:39:40

路径规划

路径规划范文第1篇

关键词 自动泊车;最佳泊车路径

中图分类号: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.

[3]何峰.自动泊车系统的研究及实现[J].广东工业大学,2009.

路径规划范文第2篇

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 本文的局限与进一步研究的方向

本文的研究更多地从实际运用和操作的便利角度出发,因而力求方法简便,运算效率较高,然而实际问题远比设想复杂,物流系统的优化应该是整体性的优化。本文只是做了配送区域的合理划分,在此基础上,对区域内配送路径进行优化,只是送货过程的优化,完整的过程还包括客户服务水平,合理的库存水平,以及配送中心选址,服务地点(卸货点)的设置等,只有这些因素都考虑到了,才能真正实现配送系统的优化。另外,还有静态分析和动态分析的区别,大区域划分保持相对静态,区域间根据每日具体的业务需求做必要的动态调整,这部分可借助人工安排,也可参考软件,保持一定的灵活性。整个配送系统的研究千头万绪,在进一步的研究中,首先需要把销售系统的优化结合进来,客户前端的需求和库存决定着后面的订单以及配送,业务员对零售网点的访销,一方面对接客户服务,体现公司的客户服务水平,另一方面,对接订单的处理以及最终的配送工作,业务人员访销作业的系统性安排,以及客户、配送中心信息的一体化都有赖于业务访销与配送作业的综合优化。

路径规划范文第3篇

关键词:分层路网;拓扑结构提取;路径规划;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分层路网拓扑结构提取

为完成最优路径规划,首先应构建路网间的拓扑结构。由于道路普遍存在的分级特点,以及驾驶者出行习惯走高级路段的心理,可以对路网进行分层处理。对于一个城市合理的层数是两层[12],常见的分层模型有两种模型[13],分别如图1和图2所示。

路径规划范文第4篇

关键词:移动机器人;路径规划技术;综述

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.

[5]邬再新,李艳宏,刘涛.多移动机器人路径规划技术的研究现状与展望[J].机械,2008(01):1-3+16.

路径规划范文第5篇

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

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

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).

[2]李晓梅,丁宁,朱喜林.基于DSP控制芯片的直流无刷电机控制系统研究[J].长春大学学报,2006(02).

路径规划范文第6篇

移动机器人遗传算法完全遍历路径规划

1引言

完全遍历路径规划( Complete Coverage Path Planning, CCPP)是一种特殊的路径规划,它要求移动机器人在满足一定的指标下完遍历目标环境中的可达区域。在机器人的许多应用领域,大都需要用到遍历路径规划算法,例如军事用的地雷探测、家居及办公环境的地面清洁、不同应用领域地图的创建等。在这些应用中要求机器人覆盖环境中所有未被障碍物占据的区域。按照对环境知识的了解,在已知环境覆盖算法中让清洁机器人规划出一条能走过环境中的所有地方并目.是代价最小路径,这个时候的问题就相当于旅行家问题,未知环境的覆盖要求清洁机器人必须借助身体上携带的不同类型的传感器来感知周围的环境并进行规划。

为克服上述路径规划中存在的问题,本文比较了基于遗传算法的完全遍历路径规划方法的优缺点,提出了基于遗传算法与单元分解法、启发式搜索和障碍物逼近算法结合的完全遍历路径规划新方法,将该方法应用于清洁机器人的完全遍历路径规划,与基于其他算法的路径规划方法进行比较,在多个性能指标上都得到了改善与提高。

2完全遍历规划性能指标

移动机器人的完全遍历路径规划常用的性能评价指标有遍历面积百分率,遍历重叠率。

(1)遍历覆盖率,是指机器人沿可行轨迹线遍历完成后,己遍历面积与可达区域面积的百分比。

(2)遍历重叠率,指所有遍历重叠面积之和与可达区域面积的之比的百分数。

为了保证相邻区域之间不留有遍历盲区,相邻遍历区域必须有一定程度的重叠,显然,

重叠区域越小越好,但因受机器人本身的系统误差,定位误差,控制精度以及环境状态的影响,重叠区不可能太小,如果一个机器人性能越高,则遍历重叠率能控制在很小的范围内。

从遍历重叠率,还可以推出未遍历面积百分率,它指机器人沿着可行轨迹线遍历完成后,未遍历面积与可达面积的百分比。

如果一个机器人性能越高,则遍历覆盖率越高,遍历重叠率越低,遍历效果越好,本文中主要结合遍历重叠率和未遍历面积来综合评价完全遍历路径规划。

3基于遗传算法的完全遍历路径规划

本文的环境地图采用几何表示法表示,即用点、线及其组合来表示环境中的特征,并用参数来表明各个特征在环境中的具置。将地图进行Boustrophedon单元分解后,地图将由若干障碍区和若干遍历区组成。电子地图则表示为各个区域信息的集合,而其中单个区域的信息包括区域的属性(障碍区属性或遍历区属性)及区域顶点的坐标。通过 Boustrophedon单元分解,环境可以分解为如图 1所示的若干遍历区和障碍区。

如图1所示,区域 2和区域 5之间的连通距离是不方便求解的,本文通过定义一个距离来表示两者之间的实际距离。虽然这个距离与实际距离之间有一定的差距,但距离值的大小趋势是一致的,而且距离的定义主要考虑了两个区域之间的直线距离、区域之间的连通关系、区域之间的障碍物情况。对于非毗邻关系的区域之间的距离,我们用D%= bDJN%来表示。其中, b是一个可调系数,可以通过仿真来调整该值以得到一个较好的数值;D为环境中两个区域之间的直线距离矩阵,对于该表达式中的各个参数, D、N可以根据划分后的区域的边界信息来确定,而J需要通过下面的算法实现。

由图2我们可以得到矩阵A

aij = 1表示遍历子区域i和j毗邻,aij = 0表示不毗邻。矩阵A为对称矩阵,其对角线的元素值为0,即不存在通过一次连通的路径连通区域1与它自身。aij = 1表示存在一条从区域i到区域j的一次连通路径,如a12 = 1,从图 2看出,区域1、 2存在一次连通路径。那么如何得到非一次连通的区域之间的连通关系呢?我们可以通过求矩阵 A的n次幂来得到两个区域之间的n次连通关系。对于i、j、k三个区域,如果区域i和区域j连通,区域j和区域k连通,则区域i和区域k连通,即当元素aij为非零值,ajk也为非零值,则通过计算

得到区域i和k的有几条连通路径。图2中各区域之间的连通关系矩阵如下:

在电子地图中两个遍历子区域的最近顶点分别为 A( x i , y i )、 B ( x j , y j ) ,判断两者之间的障碍物个数就是判断AB连线通过的障碍物个数。障碍物顶点在向量AB的顺时针方向还是在逆时针方向可以通过向量的叉乘来判断,即

电子地图中遍历子区域之间的障碍物数矩阵 N如下:

为了只保留对角线元素为 0,将矩阵 N的非对角线元素加1,得到规格化后的障碍物矩阵N。

距离矩阵 D表示遍历子区域之间的实际距离,其元素dij为子区域i和j的最近顶点之间的距离,对于毗邻区域的距离值定为a,非毗邻区域的距离值由电子地图根据区域坐标定出。图 1区域之间距离矩阵 D实测如下:

通过对障碍物矩阵、距离矩阵、连通矩阵的相同位置的元素相乘,再对非一次连通的区域距离乘以系数b,得到一个重新定义的综合距离矩阵D',其中

图1区域综合距离矩阵D'如下:

4仿真研究

基于本章提出的完全遍历路径规划算法,进行了大量的仿真实验。下面是对图3的仿真地图完全遍历结果。

经过大量地图的仿真表明,该遍历算法的覆盖率达到90%以上,有的甚至达到95%以上,而且重复率在10%以下。对于不同的地图覆盖率和重复率是不同的,不过对大多数地图而言,该算法是高效的、实用的,具有很强的适应性。该完全遍历算法特点是系统要处理的信息量很少,机器人实时性控制更强。特别是提出了基点这一重要概念,使得在未知环境中实现完全遍历更有效、更方便。

5结论

本文根据遍历环境内区域关系和区域连通图,将已有的连通图补充为完全连通图,并根据区域信息和连通信息定义一个区域之间的距离矩阵,赋予区域之间的连接权值。根据距离矩阵,采用遗传算法对区域的遍历顺序进行优化。仿真研究表明,该方法用于不确定环境下的移动机器人遍历路径规划,不但能保证遍历所有可达工作空间,并且规划的路径较短、路径重复率小,具有较高的规划效率。

参考文献:

[1]丁学恭.机器人控制研究[M].浙江大学出版社,2006.

[2]杨高波,元波.精通MATLAB7.混合编程[M].电子工业出版社,2006.

[3]张增圻.智能控制理论与技术[M].清华大学出版社,1995.

路径规划范文第7篇

摘 要:在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结,讨论了多机器人路径规划方法的评判标准,并阐述了研究遇到的瓶颈问题,展望了多机器人路径规划方法的发展趋势。?

关键词:多机器人;路径规划;强化学习;评判准则?

?abstract:this paper analyzed and concluded the main method and current research of the path planning research for multi?robot.then discussed the criterion of path planning research for multi?robot based large of literature.meanwhile,it expounded the bottleneck of the path planning research for multi?robot,forecasted the future development of multi?robot path planning.?

key words:multi?robot;path planning;reinforcement learning;evaluating criteria ??

近年来,分布式人工智能(dai)成为人工智能研究的一个重要分支。dai研究大致可以分为dps(distributed problem solving)和mas(multi?agent system)两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发,将智能体概念应用于多机器人系统的研究中,将单个机器人视做一个能独立执行特定任务的智能体,并把这种多机器人系统称为多智能体机器人系统(mars)。因此,本文中多机器人系统等同于多智能体机器人系统。目前,多机器人系统已经成为学术界研究的热点,而路径规划研究又是其核心部分。?

机器人路径规划问题可以建模为一个带约束的优化问题,其包括地理环境信息建模、路径规划、定位和避障等任务,它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点,且已经有许多成果[1~3],例如在静态环境中常见的有连接图法、可视图法、切线图法、voronoi图法、自由空间法、栅格法、拓扑法、链接图法、dempster?shafer证据理论建图等;动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而,多机器人路径规划研究比单个机器人路径规划要复杂得多,必须考虑多机器人系统中机器人之间的避碰机制、机器人之间的相互协作机制、通信机制等问题。?

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 multi?mobile 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 multi?agent learning:the state of the art[j].autonomous agents and multi?agent 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:high?level communication and control in a distributed problem solver[j].ieee trans on computer,1980,c-29(12):1104-1113.?

[34]陈伟,张铭钧,孟宪松.基于多目标决策理论的多机器人协调方法[j].哈尔滨工程大学学报,2003,24(3):308-312.?

路径规划范文第8篇

关键词:路径规划; 地标; 预处理; 层次缩减算法; 三角启发算法

中图分类号: 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.

[12]

路径规划范文第9篇

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

中图分类号: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.

[16]李t,郭孔辉,宋晓琳.基于样条理论的自动垂直泊车轨迹规划[J].湖南大学学报:自然科学版,2012,39(7):25-30.

路径规划范文第10篇

关键词: 车载导航系统; 电子地图; 拓扑结构; 路径规划; 限制搜索区域

中图分类号: TN96?34; TM417 文献标识码: A 文章编号: 1004?373X(2016)13?0133?04

Abstract: The increasing quantity of motor vehicles brings huge pressure for traffic, environment, energy, etc. An improved path planning algorithm is proposed, which is called capsule?like restricted searching area path planning algorithm. This method can greatly reduce the searching range of traditional path planning methods, and ensure the success rate of shortest path planning by means of setting the dynamic searching parameter. The ellipse restricted area algorithm and improved algorithm are deeply compared and studied by taking the road network data of the topology structure as the experimental platform. The high efficiency and stability of the improved algorthm were verified by experiment. The preliminary design scheme of the vehicle?mounted navigation system with center mo?nitoring is given, which is composed of monitoring center subsystem, vehicle?mounted subsystem and communication subsystem.

Keywords: vehicle?mounted navigation system; electronic map; topology structure; path planning; restricted searching area

仅仅通过道路基础设施建设来解决交通问题,已经不能满足快速增长的机动车数量对交通的需求,而智能交通系统的出现大大改善了交通状况,合理利用现有道路资源,就可以大幅度提高路网的使用率和使用质量,从而达到减少交通堵塞现象的目的。车载导航系统,作为ITS的关键组成部分之一,不仅能够为用户准确地提供一条前往目标地点的合理道路,还使得单个车体与城市交通系统网络有机融合,从而能够顺利避开堵塞的道路,使得外出效率大为提高。

1 车载导航系统电子地图的实现

1.1 电子地图中道路网络数据模型

道路网络的数据模型是生成具有拓扑结构道路网络的基础。车载导航电子地图是由点、线和面三个基本元素组成。整个道路网络的表示一般采用Arc?Node模型,该模型的特点是易于表达实际路网的拓扑关系,且形式简洁。考虑到实际电子地图的面是由弧段组成,故可以将路网归结为节点和弧段两个基本元素的组合。Arc?Node模型的基本原理是在一定的精度范围之内,采用以直代曲的思想,由连续的小段直线代替和逼近真实的道路曲线,这样就形成了Arc?Node数据模型,其形式化定义为:

式中:为路网;为路网的节点集;为路网的有向路段集;和为路段的起点和终点;为路段的属性集,可表示为距离、时间和花费等。

同时,根据实际交通网络的特点,做如下的分析假设:所有的边都是线段,对于弯曲弧度数较大的路段,可通过在该路段上插入一系列节点使该路段由一些弧度较小的路段构成,把弧度较小的路段假设为一条线段。如图1所示,节点1和2之间的路径弧度较大,在原路径上插入节点3和4,将原路段分割成弧度相对较小的三个路段。边长通常是双向可通的,边的权值为正值。

网络中有较多的节点和边,与节点相关联的边数为常数,且远小于网络中总的节点数。

1.2 导航电子地图中折线网络拓扑化算法实现

算法实现的原理可以简单的描述为:依据折线道路网络的组成特点及Arc?Node数据模型,由给定的折线道路网络生成表示其拓扑结构的Arc?Node数据模型。生成过程基本可以分成两个步骤:第一步是完善给定的折线道路网络数据,即对1.1节中介绍的道路网络的几个情况进行相应的处理;第二步是在第一步的基础上,由完善后的折线数据网络数据生成表示其拓扑结构的Arc?Node数据结构。整个算法流程如图2所示。

2 车载导航系统路径规划搜索算法

2.1 椭圆限制搜索区域路径规划算法

椭圆限制区域的最短路径算法思想如下:以起始点和终点为焦点,以为长轴长画一个椭圆,然后在椭圆区域内的站点间寻找最短路径。其中,为起始点到终点的欧式距离,是一个与城市路网信息有关的统计参数。所以,椭圆限制区域的最短路径算法是依赖于城市的统计参数的,统计数据表明对于北京路网的值为1.417。构造椭圆限制区域的方法如下:

(1) 建立直角坐标系:轴为轴为与其垂直的方向。

(2) 以起始点为圆心,的连线为半径,作圆该圆内的区域就是传统最短路径规划算法Dijkstra算法的搜索区域。

(3) 以起始点终点为焦点,作椭圆椭圆内的区域就是椭圆限制搜索区域路径规划算法的搜索区域。其中椭圆的长半轴与椭圆相交于点和点形成的椭圆阴影区域就是算法的搜索范围。

椭圆限制搜索区域路径规划算法的实现步骤比较简单,具体如下:输入起始点终点完成道路的网络数据加载及程序运行环境设置等;根据起始点构造椭圆限制搜索的区域;在构造的限制搜索区域内,调用Dijkstra算法进行最短路径计算;输出起始点和终点之间的最短路径。

2.2 改进的限制搜索区域路径规划算法

胶囊形限制搜索区域路径规划算法的原理与椭圆限制搜索区域路径规划算法类似,搜索起始点到终点的最短路径时,只需要考虑中间胶囊形阴影部分的路段和节点,该胶囊形限制搜索区域路径规划算法的搜索范围比Dijkstra搜索算法和椭圆限制搜索区域算法都大大缩小;并且以线段作为上下边界的限制,在一定程度上减少了判定节点是否落在限制区域内时椭圆算法需要进行的大量乘积和开方运算,从而提高了整个搜索过程的效率。具体的搜索区域设置方法如下:

(1) 轴为轴为与其垂直的方向,以起始点为原点建立一个直角坐标系;

(2) 以起始点为圆心,的连线为半径,作圆该圆内的区域就是传统最短路径规划算法Dijkstra算法的搜索区域;

(3) 以起始点终点为焦点,作椭圆椭圆内的区域就是椭圆限制搜索区域路径规划算法的搜索区域。其中椭圆的长半轴与椭圆相交于点和点

(4) 分别以起始点终点为圆心,线段AS(DK)为半径作两个半圆EAF和VKG,连接点和点形成了如图3所示的阴影的胶囊形限制区域,该区域即为改进算法的路径规划搜索范围。

由上面提到的道路路网统计参数可知,椭圆限制搜索区域路径规划算法搜索的成功建立在95%的置信水平之上,也就是还有5%的可能性,实际最短路径上的节点落在限制区域之外,这就可能导致搜索的失败,胶囊形限制搜索区域路径规划跟椭圆限制搜索区域路径规划存在同样可能导致搜索失败的情况,因此就必须通过调节半圆的参数半径扩大搜索范围,保证搜索成功,提高算法的可靠性。修正后的算法步骤如下:

第1步:输入搜索起始点和终点完成拓扑化路网数据加载及程序运行环境设置等;

第2步:根据起始点构造初始胶囊形限制区域算法的搜索区域,阈值半径为

第3步:在构造完成的胶囊形限制区域中调用Dijkstra算法,进行最短路径规划,若搜索成功则转步骤5,否则继续;

第4步:设置动态变化参数以起始点终点为圆心,以上一次搜索的阈值半径加上为半圆半径构造新的胶囊形限制搜索区域,如图4中虚线包围区域所示,构造完成后转第3步;

第5步:输出搜索得出的最短路径,算法结束。

3 中心监控式车载导航系统初步设计

3.1 中心监控式车载导航系统构成

中心监控式车载导航系统除具有导航功能外,通过借助通信网络,还能够采集信息、分析信息,路径规划在中心根据实时交通情况完成。实际应用时,通常需要根据车载终端的具体需要进行配置,通常至少应包含监控中心子系统、车载子系统和通信子系统三部分。

监控中心子系统:系统接收车载子系统发送的车辆速度、位置、报警等信息,然后在导航电子地图拓扑路网基础上对车辆状态进行实时显示、并且进行车载子系统的路径查询、数据分析处理要求。处理完成之后,并对系统和车载子系统进行参数设置及控制。

车载子系统:车载子系统负责与监控中心子系统通信,把车辆位置信息、报警状态发送给监控中心子系统,同时接收监控中心子系统的反馈指令对车辆进行相关控制。车载子系统结构组成如图5所示。

通信子系统:中心监控式车载导航系统的关键部分之一。选择正确的通信方式,连接车载子系统和监控中心子系统十分重要。首先必须考虑到通信系统网覆盖范围,其次还必须考虑车辆行驶过程中可能遭遇的恶劣环境影响。

3.2 中心监控式车载导航工作原理

车载GPS接收机接收定位卫星发来的定位数据,并且根据4颗不同卫星发来的星历数据计算出自身所处地理位置的坐标,该坐标数据通过符合GSM标准的无线模块,采用SMS形式,由车载终端将车辆的位置状态、报警器输入信息发送至GSM网,GSM网将接收到的车辆定位信息通过互联网或者通信接发设备送至中心控制子系统,以便监控中心及时掌握车辆的动态位置信息,进一步控制车载终端。其中的定位信息传输功能实现所需软件为通信服务器软件,主要完成车辆和监控中心之间的数据传输与通信,实现数据收发、编码、解码、数据入库等工作。监控中心则完成车辆位置信息的可视化、车辆行驶的最优路径规划及各种控制指令的发送等功能。基于GPS和GSM短消息业务的中心监控式车载导航系统的工作示意图如图6所示。

3.3 中心监控式车载导航软件实现

中心监控式车载导航系统的软件设计具有良好的人机交互界面和数据处理能力。首先构建一个客户端/服务器结构,数据库安装在控制中心子系统上,数据库管理采用结构化查询语言,客户端采用Windows操作系统,应用程序采用VC 2010进行开发。中心监控式导航监控中心软件设计通常要考虑5个功能模块组成:

地图显示模块:为达到对车辆监控的目的,能够显示车辆轨迹、车速等;

信息点管理模块:信息点被分类存储后,在管理用户界面中体现,用户可以对信息点数据库进行管理,如删除、添加或修改等;

数据显示模块:解码信息显示于终端;

指令下载模块:将路径导航指令实时下载到车载终端;

系统隐私保护模块:车辆管理数据库,存有车辆的电子编号用于计算机检索和处理,保证车辆信息的安全。

4 实验验证及结果分析

为了验证提出的胶囊形限制搜索区域路径规划算法的有效性和可靠性,使用125 000比例尺下MapInfo格式的北京2011年交通图作为电子地图数据源(该地图道路网络共有97 773个地理特征数量),在WIN 7平台Microsoft Visual Studio 2010编程环境下对椭圆限制搜索区域以及胶囊形限制搜索区域最短路径规划算法的性能进行测试。为了简洁,这里用SF1表示椭圆限制搜索区域路径规划算法;SF2表示胶囊形限制搜索区域路径规划算法。

为了保证两种算法的可靠性,反复给定不同的搜索起点和终点,对比各种算法的搜索时间和规划路径长度等实验数据。考虑到论文篇幅的限制,这里仅给出起点编号为797,终点编号为2 195情况下的算法的实际路径规划结果图。图7表示算法SF1路径规划结果,图8表示算法SF2路径规划结果。

两种算法的性能对比如表1所示。表中ST表示测试给定的起点,DT表示测试的目标终点;分别表示算法SF1,SF2在相同情况下所用的搜索时间(单位:s)。分别表示算法SF1,SF2在相同情况下所规划出的最短路径长度(单位:m)。

由表1可以看出,在相同的起点和终点下,在搜索的高效性方面,启发式搜索算法SF2明显比传统算法SF1优越很多,提出的改进路径规划方法比算法SF1的搜索效率有20%左右的提升;改进算法SF2,通过设置动态参数避免了此种情况的发生,很好的保证了搜索的可靠性。综上所述,可见本文提出的改进路径规划算法在搜索效率和搜索可靠性方面都具有相当的优越性。

5 结 论

本文在拓扑化路网数据基础上,提出了一种改进的路径规划算法――胶囊形限制搜索区域路径规划算法。该方法在很大程度上减少了传统路径规划方法的搜索范围,再通过设置动态搜索参数保证了路径规划的成功率。并且以拓扑结构路网数据为实验载体,对椭圆限制区域算法及提出的改进算法进行了深入的对比和研究,通过实验验证了改进算法的高效性和稳定性。最后,给出了中心监控式车载导航系统的初步设计方案。

参考文献

[1] 屈展.车载导航系统中路径规划问题的研究[D].兰州:兰州理工大学,2012:253?257.

[2] 高星.浅论车载导航系统的现状及发展趋势[J].计算机光盘软件与应用,2011(6):76?77.

[3] 陈圣,董林飞.Dijkstra和A*算法在智能导航中的应用分析[J].重庆科技学院学报,2010,12(6):159?161.

[4] 尹路明,张志恒,张小朋.一种新型GPS/DR组合导航系统[J].现代电子技术,2014,37(13):136?138.

[5] 罗国青.车辆定位导航系统动态路径规划研究[D].长沙:湖南大学,2011:321?323.

[6] CHEN Heping, LI Xianqin, GU Jinguan, et al. Research of path planning algorithms based on vector map data structure [J]. Computer engineering and applications, 2010, 39(19): 238?245.

[7] ZHAO Yilin. Vehicle location and navigation systems [M]. Boston: Artech House, 2010: 108?111.

上一篇:理财规划范文 下一篇:年度规划范文