学文网路径规划第1篇
关键词：最小生成树；Floyd；规划模型
中***分类号：TB文献标识码：A文章编号：1672-3198（2013）08-0189-02
1基本假设
（1）不变更各区内交通线路及节点设置，新增平台和“围堵点”均不设在节点之外。（2）市内6城区各点不会在同一时间出现突发事件。（3）交巡警在赶往案发地的路途中保持60km/h匀速前进且没有发生道路拥堵。（4）平台警力集中使用，不能分散。（5）管辖范围的划分以及任务的分配可以最优化。（6）接到各类报案，交巡警决策部门的决策用时均为零。（7）尽管各区面积、人口数、人口密度分别与报案率完全不成比例，从题目要求中的任务的性质，警力部署看，可以肯定：各区人口数、面积与警力空间配置与优化无关，所以此二列数据不在本模型中使用。
2参数符号说明
i――A区各出入口标号；t――时间；j――节点标号；m――方案标号；ti――警力封锁第i个出入口所需要的时间；tjm――交巡警从平台出发到达j节点所需要的时间；xα――节点横坐标；yα――节点纵坐标；xb――与所求节点相邻节点的横坐标；yb――与所求节点相邻节点的纵坐标；Emm――距离矩阵。
3模型的建立和求解
3.1模型Ⅰ：规划模型
minmmaxj{tjm|j=1，2，…，92，tjm≤3}
交巡警平台管辖范围的大小取决于他到周围节点所需要的最长时间（尽量不超过3分钟）即maxtj，所以要求出各平台到j点需要的最长时间（由于某平台到某节点有若干种方案，所以将maxtj用maxtjm代替，m代表方案），为了能保证交巡警以最快速度到达案发平台，我们从各方案的maxtjm中筛选出maxtjm最小的一个方案，即合理分配辖区的最优方案。
我们用excel软件对数据进行了大量处理，从而将时间问题转换为路径距离问题：交巡警3分钟内能走过的最长路径距离为3min*60km/h，即30mm，同时用Matlab绘制出了A区各点的关系***（如***1）。我们分别以A区中的每一个平台为起点，在C++6.0的环境中连续20次运用最小生成树法，初步确定出每一个平台所能管辖的最大范围（如表1）。
***1A区各点关系***表1中存在如下问题：（1）许多平台的管辖范围有重复。（2）个别节点没有被划分到任何一个平台的辖区（28、29、38、39、61、92号点）。（3）个别平台没有发挥作用（10、14号点）。为了解决这些问题，我们考虑以各平台的业务量为新标准优化辖区范围的分配（此处我们用各点发案率的高低衡量各点业务量的大小），尽量使各平台的业务量均衡。另外，对于那些没有被划分到任何一个辖区的点，我们实行“就近原则”使之有主可依。分配情况见表2。
相邻节点间距离=（xa-xb）2+（ya-yb）2
为确定交巡警的全力逮捕范围，即在案发后一段时间（大概是6分钟）后罪犯逃亡的路线。因涉及全市的交通要道，所以要先用最小生成树确定P点逃亡的区域。则在案发一段时间后，第一种情况是：罪犯仍在A区范围内，则动用一切交巡警服务平台的警力资源全面封锁路口，以确保可以及时的逮捕罪犯。第二中情况是不在A区内，通过C++语言可以知道罪犯只能向B区逃亡。在B区内，可以用最小路径的方法求得罪犯逃亡的最大范围，再利用就近原则给这个区间分配交巡警服务平台，然后快速地进行全面封锁，以达到逮捕罪犯的目的。***2是我们根据数据用MATLAB绘制出的包围圈（绿色线所包围的范围）。其中空白区域的顶点即是B区域中的237号节点，也是罪犯逃亡路线中唯一位于B区域中的点。
***2包围圈我们再次运用Floyd算法，找出包围圈各顶点与临近交巡警服务平台间的最短路径，形成我们的最优围堵方案。特别需要指出的是，由于案发三分钟后才接到报警，所以此处所说的最短路径必须能在三分钟内到达。我们得到的最优围堵方案（如表4）。
表4新增平台后的最优方案
服务平台节点最优方案所需时间（分钟）583（新增）2922到29必然小于3584（新增）2821到28必然小于3101010到100161616到160585（新增）3923到39必然小于3232到31.23543到55到542.275535到49到531.176596到591.6586（新增）6124到61必然小于37487到30到481.29173237（C区点）173到235到2371.181参考文献
[1]阳明盛，等.最优化原理、方法及求解软件[M].北京：科学出版社，2006.
[2]施继红.数学建模与计算机应用的融合[J].信息系统工程，2011，（05）：14-15.
[3]马莉.MATLAB语言实用教程[M].北京：清华大学出版社，2010.
路径规划第2篇
关键词：分层路网；拓扑结构提取；路径规划；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分层路网拓扑结构提取
路径规划第3篇
关键词：移动机器人；路径规划技术；综述
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.
路径规划第4篇
关键词 路径规划;全局规划;局部规划
中***分类号 TP242 文献标识码 A 文章编号 1674-6708(2009)10-0067-02
路径规划是指机器人从起始点到目标点之间找到一条安全无碰的路径,是机器人领域的重要课题。移动机器人技术研究中的一个重要领域是路径规划技术,它分为基于模型的环境已知的全局路径规划和基于传感器的环境未知的局部路径规划。本文综述了移动机器人路径规划的发展状况,对移动机器人路径规划技术的发展趋势进行了展望。
根据机器人工作环境路径规划模型可分为两种:基于模型的全局路径规划,这种情况的作业环境的全部信息为已知;基于传感器的局部路径规划,作业环境信息全部未知或部分未知,又称动态或***路径规划。
1 全局路径规划
全局路径规划主要方法有:可视***法、自由空间法、栅格法、拓扑法、神经网络法等。
1.1 可视***法
可视***法视移动机器人为一点,将机器人、目标点和多边形障碍物的各顶点进行组合连接,并保证这些直线均不与障碍物相交,这就形成了一张***,称为可视***。由于任意两直线的顶点都是可见的,从起点沿着这些直线到达目标点的所有路径均是运动物体的无碰路径。搜索最优路径的问题就转化为从起点到目标点经过这些可视直线的最短距离问题。
1.2 拓扑法
拓扑法将规划空间分割成具有拓扑特征的子空间,根据彼此连通性建立拓扑网络,在网络上寻找起始点到目标点的拓扑路径,最终由拓扑路径求出几何路径。拓扑法基本思想是降维法,即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。
1.3 栅格法
栅格法将移动机器人工作环境分解成一系列具有二值信息的网格单元,多采用四叉树或八叉树表示,并通过优化算法完成路径搜索,该法以栅格为单位记录环境信息,有障碍物的地方累积值比较高,移动机器人就会采用优化算法避开。对栅格的改进采用以障碍物为单位记录的信息量大大减少,克服了栅格法中环境存储量大的问题。
1.4 自由空间法
自由空间法应用于移动机器人路径规划,采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间,并将自由空间表示为连通***,通过搜索连通***来进行路径规划。自由空间的构造方法是从障碍物的一个顶点开始,依次作其它顶点的链接线,删除不必要的链接线,使得链接线与障碍物边界所围成的每一个自由空间都是面积最大的凸多边形。连接各链接线的中点形成的网络***即为机器人可自由运动的路线。
1.5 神经网络法
可视***法缺乏灵活性,且不适用于圆形障碍物的路径规划问题。神经网络法用于全局路径规划可以解决以上问题。算法定义了整条路径的总能量函数,相应于路径长度部分的能量和相应于碰撞函数部分的能量。由于整个能量是各个路径点函数,因此通过移动每个路径点,使其朝着能量减少的方向运动,最终便能获得总能量最小的路径。
2 局部路径规划
局部路径规划包括人工势场法、模糊逻辑算法、神经网络法、遗传算法等。
2.1 人工势场法
人工势场法基本思想是将移动机器人在环境中的运动视为一种虚拟人工受力场中的运动。障碍物对移动机器人产生斥力,目标点产生引力,引力和斥力周围由一定的算法产生相应的势,机器人在势场中受到抽象力作用,抽象力使得机器人绕过障碍物。
2.2 模糊逻辑算法
模糊逻辑算法基于对驾驶员的工作过程观察研究得出。驾驶员避碰动作并非对环境信息精确计算完成的,而是根据模糊的环境信息,通过查表得到规划出的信息,完成局部路径规划。模糊逻辑算法的优点是克服了势场法易产生的局部极小问题,对处理未知环境下的规划问题显示出很大优越性,对于解决用通常的定量方法来说是很复杂的问题或当外界只能提供定性近似的、不确定信息数据时非常有效。
2.3 神经网络法
模糊控制算法有诸多优点,但也有固有缺陷:人的经验不一定完备;输入量增多时,推理规则或模糊表会急剧膨胀。神经网络法则另辟蹊径。路径规划是感知空间行为空间的一种映射,映射关系可用不同方法实现,很难用精确数学方程表示,但采用神经网络易于表示,将传感器数据作为网络输入,由人给定相应场合下期望运动方向角增量作为网络输出,由多个选定位姿下的一组数据构成原始样本集,经过剔除重复或冲突样本等加工处理,得到最终样本集。
2.4 遗传算法
遗传算法以自然遗传机制和自然选择等生物进化理论为基础,构造了一类随机化搜索算法。利用选择、交叉和变异编制控制机构的计算程序,在某种程度上对生物进化过程作数学方式的模拟,只要求适应度函数为正,不要求可导或连续,同时作为并行算法,其隐并行性适用于全局搜索。多数优化算法都是单点搜索,易于陷入局部最优,而遗传算法却是一种多点搜索算法,故更有可能搜索到全局最优解。
3 移动机器人路径规划技术的发展展望
随着计算机、传感器及控制技术的发展,特别是各种新算法不断涌现,移动机器人路径规划技术已经取得了丰硕研究成果。从研究成果看,有以下趋势:首先,移动机器人路径规划的性能指标要求不断提高,这些性能指标包括实时性、安全性和可达性等;其次,多移动机器人系统的路径规划。协调路径规划已成为新的研究热点。随着应用不断扩大,移动机器人工作环境复杂度和任务的加重,对其要求不再局限于单台移动机器人。在动态环境中多移动机器人的合作与单个机器人路径规划要很好地统一;再次,多传感器信息融合用于路径规划。移动机器人在动态环境中进行路径规划所需信息都是从传感器得来。单传感器难以保证输入信息准确与可靠。此外基于功能/行为的移动机器人路径规划,这是研究的新动向之一。
总之,移动机器人的路径规划技术已经取得了丰硕成果,但各种方法各有优缺点,也没有一种方法能适用于任何场合。在研究这一领域时,要结合以前的研究成果,把握发展趋势,以实用性作为最终目的,这样就能不断推动其向前发展。
参考文献
[1]陈陈.优化方法与最优控制[M].北京:机械工业出版社,1993.
路径规划第5篇
关键词：智能交通 A*算法 静态路径规划
中***分类号：P285 文献标识码：A 文章编号：1007-9416（2013）09-0117-02
1 引言
城市交通道路的复杂性，固定意识的出行路径引发的严重交通堵塞，使出行者迫切需要获得正确的出行路径；出行过程中，对不熟知地理环境和周围交通状况的把握和了解；车辆及出行者对社会服务的急迫需要；荒野作业过程中的道路迷失。我们可以得出一个重要的结论，就是随着出行者活动范围的不断扩大，人们迫切需要对车辆自身所处的位置及周围环境有更有效的认识，并作出理性的判定[1]。有效调高出行车辆行驶过程中的路径规划效果是解决城市交通堵塞的重要方法。
2 建立静态路径规划数学模型
对于最优道路路径规划策略的研究上来说，道路口节点和路径就可以对智能交通网进行数学逻辑上的描述，这一个基本的数字路网模型***可以表示为：
（2.1）
式中：G为智能交通道路的基本电子路网模型；N为道路网络路口节点的集合，ni为表示道路路网的任意一个节点，xi， yi为该任意节点的横和纵坐标；R为道路路网层路径的ri集合，为道路路网任意一段路径，为两个道路口节点之间或任意一条道路径的权重值。
依据智能交通原始电子地***，创建交通路网的空间拓扑结构相***G，以此为基础建立静态路径规划数学模型，模型具体描述如下：
2.1 定义智能交通路网的权值变量
实际智能交通中的两道路口节点，相关的任意道路径都含有一个权值，依据电路的常用定义规则，称为道路阻抗，描述了车辆行驶过程中通过该道路路径所要消耗的能量变量值，该值可以定义：道路路径的空间距离、通过该道路路径所需时间、车辆行驶路程缴费，依据用户所关心的目标函数可以采用不同的权值测量方法。
最优路径规划的目标函数为：车辆行驶过程中的始末道路最短路径DistanceMin。设，式中为车辆行驶过程中的路径值，。
最优路径规划的目标函数为：车辆行驶过程中的始末道路最短时间DistanceMin。设，式中为道路路径的宽度和等级，，为系数。假设车辆的平均速度与道路路径的宽度和等级成正比。
此外，据用户所关心的目标函数可以采用不同的权值测量方法，最优路径规划的目标函数为车辆行驶路程缴费最小的情况时，需要考虑车辆行驶过程中的道路的收费和油耗，并忽略车辆其他损耗。
2.2 最优路径规划的目标函数T
依据用户所关心的目标函数T，可以采用不同的定义方法。通常在最优路径规划策略考虑，始末道路节点的路径最短、及车辆耗时最小等。
车辆在智能交通网络的行驶过程中，始末道路口节点之间的道路径，分为m条路径，车辆通过每条路径的时间为。最优路径规划的目标函数T定义为：
标函数T为最小路径：
； （2.2）
标函数T为最小路径：
， （2.3）
因为：
（2.4）
则：
（2.5）
3 A-star算法设计
A-star算法是一种路径规划过程中比较经典的预测方式的搜索算法。采用智能交通网的全局信息变量，通过选择合理的预测估计评价函数，预设置优先查询的到路径方向，以减少搜索的道路口节点及路径的路段个数，实现查询的最优效率。以道路口节点之间的欧式距离及道路等级为A-star算法预测启发式的评价指标，定义如下所示：
（3.1）
其中，是始点到当前节点之间实际所产生的通过道路路径的费用，即是始末两节点之间的，每段路径的道路等级乘以道路的路径长度相加的代数和，是当前节点到目的地节点的最小代价值，本文取当前节点到目的地节点的欧式距离，为表智能交通道路分类序号值，取值为0、1、2；选择道路等级作为算法价值的评价指标，主要是考虑智能交通网中的高等级路，道路的路况及安全系数较高，虽然不是车辆行驶过程中的最短路径，但是可以给行车者带来精神放松，提升交通安全指标。A-star算法主程序框***如***3.1所示。
4 实验研究
车辆的静态最优路径轨迹规划，以复杂情况较大的北京市东城区的三环和四环之间的道路网数据为路径规划源。东西距离10KM，南北距离4KM。技术平台支持：Inter Pentium 4 1.8GHz，512M内存，Microsoft Windows server 2003操作系统。采用道路网道路功能的两层分类：略***层和详***层，细线为略***层网络结构，粗线为详***层网络结构。交通网略***层包含道路的路径段178条，道路口节点数53个，交通管制的转向限制为8条；详***层包括道路路径段2031条，道路口节点1419个，交通管制的转向限制为2307条。在路径规划仿真平台中，任意选择车辆行驶路径的始末点，A*实验结果统计如表4.1所示。
5 结语
在智能交通网中的静态路径规划算法研究中，具有启发式的A*算法能够实现车辆的静态最优路径规划，最优路径规划策略能够直接有效的提高道路的使用效率。减少城市交通堵塞情况的产生，可以做到节能减排的效果，产生更多的经济和社会效益。
参考文献
[1]常青，杨东凯，寇艳红，张其善.车辆导航定位方法及应用[M].北京：机械工业出版社，2005.
[2]陆化普.智能交通运输系统.北京：人民交通出版社，2002.
[3]G.A.Giannopoulos The application of information and communication technologies in transport. European Journal of Operational Research 152（2010）：302-320.
路径规划第6篇
【关键词】移动机器人 最优路径规划 栅格法 A*算法
自从有移动机器人这一概念以后，*成为长期以来研究的最热门的内容之一。移动机器人可研究的领域相对较多，其关键技术有传感器信息结合、创建地***、定位导航、路径规划等。其中核心技术之一是路径规划技术，从起始点到终点，快速在环境地***中找到最短或最佳的无碰撞路径，这是路径规划的主要任务。本文是以“探索者-1”移动机器人作为研究平台。它由多个CPU控制，通过扫描式超声波传感器探测周边环境。当机器人接收到超声障碍信息后，可生成栅格环境地***，并基于迷宫八方向搜索的思想找到最佳路径。
1 机器人路径规划环境模型建立
在有障碍的环境中，移动机器人根据传感器发出的信息，生成环境地***，才可以实现路径规划以及导航，而栅格地***、拓展地***、几何三维特征地***是移动机器人生成的环境地***的三种表示方法。当移动机器人在获得信息时，会在一定程度上存在较多的不确定性，这是由传感器差异造成的。由于获得的信息不确定导致处理数据方法也不确定。解决这一问题，概率法，灰色理论，模糊理论等起到一定的作用。
1.1 栅格地***的创建
在栅格地***模型中，移动机器人所接收的每个栅格的信息直接与地***中的每个区域相匹配，这样移动机器人就可以根据栅格地***进行定位甚至导航。
“探索者-1”得到环境障碍信息主要途径依托于扫描式超声传感器，但是这种传感器具有盲区、多次反射等缺陷，所以超声信息存在很大的不确定性。因此可采用灰色系统理论来创建完善的栅格地***模型。
1.2 栅格地***创建实验结果
以“探索者-1”移动机器人作为实验对象进行实验，实验环境和实验结果如***1所示。
实验结果：采用栅格法，有一定的辨别真伪能力，能够有准备地描绘所需要的环境地***。
2 A*路径规划算法与传统算法的比较优势
传统算法生成的相邻子节点的作用是相同的，且不分先后顺序。如果不利用优先级的子节点生成策略，会产生许多问题，比如没有考虑机器人的宽度，而生成越过障碍物顶点栅格顶格的路径规划。A*路径规划算法是一种非常经典的启发式搜索算法，它的估计函数计算式为：f（x）=g（x）+h（x），其中f（x）为节点x的估价函数；g（x）为实际代价；h（x）是最佳路径的估价，在函数中作用最大。另外，估价函数决定着A*算法的正确与否。取g（x）在状态空间到x节点的深度，如***2所示。其中h（x）的计算方法为：h（x）=|Xd―Xs|+|Yd―Ys|。式中：（Xd，Yd）表示目标点坐标，（Xs，Ys）表示当前点坐标。
3 改进A*路径规划的算法
机器人定位前，A*算法已规划好最佳的路径，但路径中夹杂了多余的点坐标，当移动机器人到达拐点处时，不能自行地调整姿态。因此，我们对A*算法提出两个方面的改进：
（1）简化坐标点，除去冗余的坐标点，只剩下起点、拐点和终点。
（2）解出拐点处的旋转方向和最小角度，当机器人到达拐点处时，根据角度和方向自行处理自己的位态。用A*规划任意路径，通过实验证明它的正确性，如***3中A所示。
改进A*算法后的路径规划如***3中B所示，路径只包含起点1、拐点3、6、8、9和终点11。
4 仿真分析
为了验证A*算法的可靠性，在不同环境下，可选用编译工具Matlab 7.0对移动机器人进行路径规划仿真。其结果表明：采用改进的A*路径规划算法，使得要计算的路径点减少，且当机器人到达拐点处时，能够自动调节位态，使移动机器人更好地自主定位。
5 结语
基于A*路径规划算法移动机器人，找到的最优路径要满足几何长度的最短与时间最短的条件，只有这样的无碰路径才是最优路径。在栅格环境下，采用A*算法的移动机器人其实并不能完美满足实际应用，为了使其路径更加完美，则需要继续地实验论证，期待未来的移动机器人不但可让路径简单化，而且还能找到其在拐角处旋转的方向和角度，满足定位要求。
参考文献
路径规划第7篇
关键词:移动多智能体;全局规划;局部规划
中***分类号: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.