路径规划第1篇

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

0引言

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

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

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

1分层路网拓扑结构提取

路径规划第2篇

【关键词】移动机器人 最优路径规划 栅格法 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*算法的移动机器人其实并不能完美满足实际应用，为了使其路径更加完美，则需要继续地实验论证，期待未来的移动机器人不但可让路径简单化，而且还能找到其在拐角处旋转的方向和角度，满足定位要求。

参考文献

路径规划第3篇

关键词：遗传算法；智能机器人；路径规划

前言

现阶段，在现代社会中，各领域生产智能化发展速度不断加快，与此同时，智能机器人成为了国内外该领域的研究人员的重点科研对象，并且针对智能机器人的路径选择问题进行深入探究。在研究过程中，为了能够令机器人帮助人类做更多的实际工作，则开发了智能机器人来辅助实践，在各项指令的操作和影响下下，机器人能够完成人类赋予它的任务。

一、遗传算法概述

（一）简析遗传算法

早在上个世纪中叶，世界范围内的少数计算机科学家开始探究遗传算法的雏形，而后，在一段时期内，遗传算法成为了一种进化计算的分支策略，填补了编码方案设计领域的空白。实际上，遗传算法在实践过程中的应用策略较为简单，在该算法支撑下的搜索能力以及躲避障碍物的能力都较强。

（二）遗传算法的实践优势

应用遗传算法来对智能机器人的路径进行科学规划的过程中，可以将其与直角坐标法结合起来应用，这样一来，便可以简化数据计算以及编码过程的复杂程度，保障机器人在行进的过程中的大部分时间处于环境的中心位置，从而避免遇到障碍而停止行进[1]。

二、基于遗传算法的智能机器人的路径规划

要想令智能型机器人顺利地游走于各类静态与动态环境之中，不被各种障碍物体所碰到，并能够完成一定的任务，并不是一件容易的事。因此，需要利用遗传算法这一科学研究内容来完善智能机器人的路径规划方案，使其达到既定行进目标。

（一）智能机器人研究项目概述

在智能机器人的研究领域中，机器人的路径规划指的是机器人在它的工作范围内，根据系统内部的指令来进行最优化的选择，包括行走路径最短或行走时间最少等决策都是通过路径规划指令来引导，甚至在智能机器人的行走过程中遇到障碍物时，则也同样需要路径规划指令操作来判断最优的行动路径[2]。

（二）在遗传算法影响下的智能机器人路径规划的特征与优劣势研究

1.基于遗传算法的智能机器人行进路径的特点分析

遗传算法是以自然遗传机制为前提，在某种程度上以生物进化过程为基础来构建的一种数学模型，在其中利用变异编制控制机构等计算程序。基于遗传算法的智能机器人路径规划需要占据大量的存储运算空间，因此，智能机器人的路径规划速度较为缓慢，在复杂动态环境下的路径规划实效不佳，需要在未来研究过程中对其进行改进。

2.基于遗传算法的智能机器人路径规划的优劣势分析

就从基于遗传算法的智能机器人路径规划来看，尽管这一模式能够在一定程度上为机器人提供可行的行进方案，但其行进速度较为缓慢，即使受到局部选择极小的障碍，也会令智能机器人在动态环境中步履维艰。研究发现，基于遗传算法的智能机器人路径规划具备一定的研究价值，推进了智能机器人项目的研究进展。

通过分析遗传算法的特征及其演进过程，运用遗传算法或其它模拟形式来优化智能机器人的路径规划，则可以在一定程度上增强智能机器人的性能。但是，无论何种方法，都或多或少的存在一定的问题，不能达到智能机器人最优路径选择的要求[3]。相对而言，尽管存在一定的不足，但基于遗传算法的智能机器人路径规划相对还是较为可行。目前，在各项技术支撑下的智能机器人已经具备一定的实践能力。

在遗传算法的推进下，智能机器人项目的研究有了新的进展，且在机器人的路径规划方面有了极大的突破，但就目前的研究成果来看，智能机器人的行进路线并不完美，成功完成某一既定的行进任务的概率并不高，因此，相关的技术科研人员还需针对路径规划问题做深入的探讨与研究。未来的主要研究方向有以下几项内容：其一，全局路径规划与局部路径规划的有效整合；其二，多传感器信息融合技术的引入；其三，智能算法以及相关改进研究等[4]。相信在多元化的智能算法影响下，智能机器人的行进路径规划则会更加准确，并且，能够完成更为高级的指令任务，为人类社会各领域的生产建设提供优质的服务。

结束语：

通过研究智能机器人路径规划可以了解到，不同策略方式的选择应用都可以充实到智能机器人研究成果之中，尤其是遗传算法的实践应用，令智能机器人路径规划更加合理。从以往的研究资料中可以了解到，智能机器人路径规划是机器人研究领域中的一项重要分支，同时也是智能机器人用以执行各种指令的基础条件。在研究智能机器人的路径规划过程中，遇到了诸如易陷入局部最优等问题，进而提出应用改进遗传算法来改善这一状况，并且取得了良好的实效。总之，基于遗传算法的机器人路径规划能够在一定程度上推动该研究项目的发展，从而积累更多的研究经验。■

参考文献

[1]崔瑾娟.基于遗传算法的机器人路径规划[J].洛阳师范学院学报，2013，02（02）：35-36.

[2]谭艳.基于遗传算法的机器人路径规划问题[J].现代计算机，2013，08（15）：23-24.

路径规划第4篇

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

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

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

路径规划第5篇

【关键词】路径规划；电子地图；应用

所谓电子地图是一项结合计算机制图以及数据库处理和信息系统等学科为一体的图形表现形式。在现代社会中，电子地图在各个行业中应用广泛如在车载导航系统中，它已成为路径规划中一项较为重要的技术。但有关电子地图的详细应用主要在快速生成卫星影像和航空相片以及行数据的记录和新数据的派生方面。存在的问题是其技术的应用还不够广泛和深入。所以，本文结合实例对电子地图中的数据特点以及路径算法和算法的改进进行分析，同时对路径规划中电子地图的应用进行探讨。

1.实例应用

在计算机的相关软件的运行环境下，用VisualC++开发某市实验用地图上提取的300个道路所用点，同时添加附加信息，实施路径规划。在地图上制定路径的起始点和终止点之后，电子地图可在很短的时间内确定最优化的路径，同时该路径的各种辅助设备能够满足实际车载和各种应急需求。

2.电子地图的数据特征与路径算法

2.1数据特征

电子地图的数据特征是按照一定图层进行叠加的，在电子地图中的各种点、线、面等的集合就是图层。在电子地图中的数据分为两种：（1）空间数据。它主要是对空间对象的几何特征、位置关系以及拓扑关系进行存放。（2）属性数据。主要是对空间对象的类别、名称以及特征等进行确定。在本文所引用的Shape File中，属性数据主要以dbf的形式储存于数据库中，相对的空间数据则主要以Shape File所固有的格式进行数据的储存。这两种数据通过一定的形式联系在一起。电子地图中，将城市的道路网建设成一个图层，将其命名为道路网，同时在地图上实施路径规划，要对道路进行操作，那么就不涉及其它图层。

2.2电子地图的路径算法

在电子地图的路径规划中，路径算法是重要的工作过程之一。现在电子地图中最长用的算法是启发式搜索算法，其主要的模型为f（x） =g（x）+h（x）.（1）式中：g（x）表示从起点到搜索点的实际花费；h（x）表示从起点到终点的预估花费，称为启发函数；f（x）表是总花费。在采用启发模型之后，可以对驱动模型进行改进：（1）在每次新生成的节点展开之前，要对显示的同一位置两个节点的花费进行比较，在新生成节点大于已生成节点的前提下，可放弃已生成节点，反之用原节点。（2）将最小距离作为搜索信息，其花费的现实随节点的开展而增加。（3）在节点的数量增加后，综合代价增加，在每次新生成的节点的花费大于原来节点的情形下，可将新生成的节点淘汰用原来的路径。

3.路径规划中电子地图的应用

在路径规划过程中，电子地图重新定义了地图在人们心中的形象。在电子地图的帮助下，可以将现成的路径规划中出现的各种要素进行不同形式的组合最后连接成新的地图；同时交通部门可以根据电子地图在路径规划中的应用，对各种交通情况诸如交通事故、天气变化、不同路段的情况进行不同程度的监管；此外，路径规划中电子地图的使用为各种市民和公民进出入不同的城市提供便捷的服务，可以在现有的地址、地址范围和地理位置以及道路的交叉口等进行准确的定位，帮助人们在不熟悉路径以及路况的情况下正确的选择道路。

3.1起终点问题

在实际的生活过程中，电子地图上的起终点并不能代表实际路线中的出发点和结束点。在我们的日常生活中较为常见的是起点和终点都位于某一个路段的中间部分，在此时，必须将路段的出发点作为起点，目的地作为终点，在电子地图中输入该城市的行政规划图，通过电子地图对该路径数据的处理和分析，得出最佳路径区划图。

3.2最优路径模型的确立

电子地图在路径规划中的应用中所要解决的最优路径问题并不仅仅指最短的路途。它还包括利用电子地图在最短时间和最小花费内寻找到最合适的通向目的地的路径或者在电子地图的帮助下，将这几个问题全部综合在一起，最后使问题得到解决。同时在电子地图对路径的道路级别、人流量的大小以及转弯限制等做出详细的判断之后，确定最佳的路径模式。此时可将启发式模型中的g（x）进行一定程度的修改：g（x）=∑aijLij+∑bmnTmn。在该式中，Lij表示的是i和j之间的路径长度；其中aij表示的是相应的权值，这个参数与道路的级别和流量有关；Tmn表示的是从路段m到路段n之间所需要的花费（如时间等）；与之相应的bmn代表的是穿越的权值。若在该路段处禁止转弯则可将其设置为常数，g（x）则表示从起点到所要到达的地点之间的花费。在电子地图启用最佳模型的情况下，进行路径的选择。

3.3确立加权模型

电子地图的工作过程中如何利用启发式算法进行信息的启发也是关键工作之一，加权函数的常用表达形式是f（x）=λ1g（x）+λ2h（x），λ1+λ2=1 λ1>0，λ2>0。在该式中主要的调节系数是λ1和λ2。在λ1>λ2表示搜索过程准备好；在λ2>λ1时表示启发开始，搜索将沿着最佳路线进行搜索，这时搜索的速度较快，有利于降低完备性。在确定加权模型的情况下，电子地图可就本车中的车载以及前面的路线情况进行分析，最后计算出加权函数，得出行车的最佳路线，最终可帮助人们很快的实现快速到达的目的。

路径规划第6篇

关键词：白车身；机器人焊接；路径规划

我国目前白车身焊接机器人焊接路径规划方面仍处于落后水平，相关路径规划也极为不完善，机器人工作的过程中经常出现作业顺序不合理的状况，导致生产周期增长，影响整个焊接线路的发展。所以如何制定出一条合理的路径规划是当前首要目标，本文立足实际就针对这个问题提出一些有效性策略。

一、路径规划的意义

白车身焊接机器人焊接中制定出一条合理的路径规划可以有效缩短机器人生产时间，进而缩短整个工期，提高整个生产效率，某种程度上降低了生产成本。另一方面，白车身焊接机器人焊接路径规划具有一定的典型性，在自动驾驶、服务机器人、挖掘机器人等路径规划研究方面具有重要的借鉴意义，具有较高的社会价值和经济价值。

二、白车身焊接机器人焊接路径规划

（一）路径规划的基本任务

现代化工业生产的主要目标是为了获得较高的制造质量、取得较高的生产率，而付出较低的生产成本，这是现代企业提高自身竞争力的重要手段，也是路径规划中的主要任务之一，而在路径规划的过程中要想保证焊接质量主要取决于以下两点：

第一，最大程度的使用机器人工位。使用机器人工位能够有效降低工人的劳动强度，减少人为错误几率，提高焊接的准确性，保证焊接的顺利进行，从而保证焊接的稳定性。

第二，要完成所有的焊接点，保证焊接的工艺参数。

要想实现较低的制造成本就是最大化的利用现有资源，提高机器人的工作效率，缩短机器人工位的生产周期，减少机器人的使用数量。路径规划的重要方向就是提高生产率，保证生产环节的顺利进行，缩短生产周期，提高生产率。

（二）路径规划

白车身焊接机器人焊接路径规划主要有两个分支，一是改变工艺参数，使用新的工艺方法和辅助设备。二是要提高分配的合理性、提高焊接顺序的合理性，提高合理性的目标是为了减少机器人工位的生产周期。第二个分支实现的途径主要是通过提高机器人焊接路径的合理性，从而提高单个机器人的生产效率，最终缩短整个生产周期。

（三）遗传算法

遗传算法是进化算法中产生最早、应用最广泛的一种基本算法，在工程技术和经济管理领域都有广泛的应用。遗传算法有群体搜索和遗传算子两个基本特征，所谓的群体搜索打破了领域的限制，使信息可以广泛分布于整个空间。而遗传算子就是使染色体进行随机操作，以降低人机交互的依赖。两个特征保证了遗传算法具有最优的搜索能力、最简明的操作能力以及信息处理的隐秘能力。

白车身焊接路径规划主要问题如下：

第一，白车身中所需要焊接的焊接点众多。

第二，在生产的过程中常常追求没有意义的高精度。

第三，在解答相关问题时需要运用数学方法。

第四，因为方案最终应用于企业，所以数学方法最好要简洁明了，便于学习。

综上，在路径研究时需要运用遗传算法，主要优势在于：

第一，遗传算法的计算步骤比较简单明了，在实际操作时便于学习和使用。在计算时大大减少了计算量，从而节约时间。

第二，能够在很大程度上优化焊接作业顺序，减轻焊接的工作量。

第三，减少定量分析与定性分析的工作量。

第四，能够很好的掌控全局，在全局中找到最优解。

三、路径规划的仿真

（一）仿真系统的各要素

路径仿真系统一般要具有以下几个基本要素：

第一，对仿真问题的描述。模型和仿真运行控制共同组成了一个仿真系统，而一个特定的模型又是由一个参数和一组参数值构成。例如白车身点焊机器人焊接路径的参数模型一般包括家具模型、机器人模型、侧围模型，在这基础之上还加入了具体的参数值，就形成了特定的模型。

第二，行为产生器。模型确定以后就要对模型进行试验，这是一套试验的软件，行为产生器可以生成一组根据时间变化的数据，这类数据是仿真的物资基础。

第三，模型行为及对行为的处理。

模型行为可以大致分为三种：轨迹行为、结构行为以及点行为。

仿真系统中都要获取轨迹行为，这些行为的获取主要是根据时间的推移而产生的。

（二）仿真软件的选择

一个完善的机器人仿真系统可以依据机器人的运动学、动力学、行为轨迹等多项内容进行仿真计算，并可以根据机器人的实际操作内容进行仿真操作过程，并不依赖于真正的机器人。但目前最主要的工作是对机器人的路径规划做一个仿真方案，而不是设计出一个机器人的仿真系统。在进行机器人路径规划时需要一定的条件，在现实生活中可以有多个选择，最好的选择就是使用一些类似CAR这种专业软件，如果条件不允许可以选择VC++或者使用CATIA等软件进行仿真。VC++自主编写的优点在于针对性比较强，在做路径时可以考虑多方面因素，然而缺点是不能建立详细的三维模型，在实际操作时不能全方面的展现白车身焊接工位情况，且工作量较大。CATIA与VC++相比最大的优势就是可以建立详细的三维模型，能够全方位展现工位情况，仿真轨迹最为真实，在仿真过程中还可以检查是否干涉。而缺点也是比较明显的，在仿真的过程中不能将动力学和控制算法考虑在内。

四、小结

白车身主要是以钢结构为主的支架，是汽车中重要组成部分。而车身制造是整个环节中比较复杂又极为重要的一环，影响整个汽车的质量。我国研究白车身焊接机器人焊接路径仍处于落后阶段，为了提高综合竞争力需要加大技术投资，提高我国白车身制造综合竞争。

参考文献：

[1]王立东.基于Christofides算法的白车身焊接机器人路径优化[J].河西学院学报，2011，27（2）：96-100.

路径规划第7篇

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

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

    1 引言

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

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

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

    2 问题描述

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

    3 路径规划原理

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

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

    由(X-XB)/(XA-XB)=(Y-YB)/(YA-YB)得:(YA-YB)X-(XA-XB)Y+(XAYB-YAXB)=0

    (2)利用夹角求切线方程

    如果测出过A、B两点与园的切线和AB直线的夹角,则可求出切线方程。

    在图2中,直线AN的方程为:Y-YA=tanα(X-XA)

    直线AM的方程为:Y-YA=tanβ(X-XA)

    直线NB的方程为:Y-YB=tanα1(X-XB)

    直线MB的方程为:Y-YB=tanβ1(X-XB)

    (3)由四条切线求点A到点B的最短路径

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

    3.2 首先判断机器人和给定的目标位置之间是否存在障碍物

    如图1所示,以R代表机器人,坐标为(XR,YR),以G代表目标位置,其坐标为(XG,YG),障碍物为A、B、C、D、E、F等,坐标为 (XA,YA)、(XB,YB)、(XC,YC)、(XD,YD)、(XE,YE)、(XF,YF)等。Rr表示机器人半径、Ri(i=A、B、C、D、E、F)表示障碍物的碰撞半径,也就是说在其半径以外无碰撞的危险。要根据实际情况和控制要求来确定碰撞半径。碰撞半径Rp一般选择大于障碍物的半径Ri加上机器人半径Rr,即Rp>Ri+Rr。

    3.3 单障碍物情况

    机器人在任何时刻都能够测得机器人的位置坐标(XR,YR),目标位置是已知的(XG,YG),可测量出机器人与目标连线和机器人与障碍物碰撞圆的切线的两个夹角αi和βi(i=1,2,…)。若αi<βi,则选αi方向的切线作为行走路径;否则,则选βi方向的切线作为行走路径;则如图1所示。

    3.4 多障碍物情况

    对于多障碍物情况,可将移动机器人绕过多个障碍物最终到达目标位置作为一个总任务,每当绕过一个障碍物作为一个分任务。总任务就可分解为多个分任务,设第i个分任务的目标点为Gi和中途点为Bi,执行第i个分任务时,如果在到达Gi的路径上存在障碍物,则增加第i+1个分任务,此时目标点Gi+1就是Bi;以此类推,寻找切线路径直至到达给定的最终目标位置,计算所有分任务的最短切线路径之和即为所求的最优路径[4]。

    4 行路径算法

    (1)机器人朝着目标按直线方向行走,直到以下任一情况发生:

    ①已经到达目标,结束。

    ②在机器人与目标之间发现障碍物,转(2);

    (2)按路径规划的原理选择路径,转(1)。

    5 结语

    移动机器人路径规划的算法有很多,每一种算法能够适用于几种特定的场合。一个好的算法,不但理论简单,计算快捷,容易理解,便于实现,而且实现的效果好,能够提高运行效率。本文介绍的移动机器人的路径规划方法,容易理解,便于实现,可适用于某些特定的场合。

    参考文献

    [1] 李彩虹,李贻斌,范晨.移动机器人动态避障算法[J].山东大学学报,2007,5(37):60-64.

    [2] 陈刚.复杂环境下路径规划问题的遗传路径规划方法[J].机器人,2001,(3):230-233.

路径规划第8篇

【关键词】模糊控制 双足机器人 路径规划 超声波传感器

机器人路径规划一直是机器人研究领域的热点问题。路径规划是在有障碍物的环境下找到一条由给定点到达目标点的最优路径，使机器人能够绕过障碍物，在不与障碍物相碰撞的情况下到达目标点。机器人在移动过程中必须安全无障碍的绕过所有障碍物，寻求一条安全的运动轨线判断并自动躲避障碍物顺利抵达目的地并且尽可能使所走路径最短。目前，常用的局部路径规划算法有势场法、A* 算法、栅格法及模糊算法。其中模糊算法有效的减小了对环境信息的依赖性，具有良好的鲁棒性和实效性。

本文主要采用模糊算法解决直立行走机器人在静态未知环境中的局部最优路径规划问题，并通过MATLAB仿真实验验证了模糊算法的有效性和可行性。

1 超声波传感器

双足直立机器人实现避障行走，首先需要对外界环境进行感知，探测到障碍物的方位。而超声波作为一种距离探测传感器，以其质量可靠，成本低廉为特点，在机器人测距中得到了广泛应用。基于双足直立机器人在速度上有限制的前提条件，采用周期扫描模式进行距离检测是最可行的方案，即将机器人的视野范围均分为若干份，记录每个视角检测到障碍物的距离，进而获得完整的外界环境的知识。同时为了消除机器人在运动过程中的抖动对测距的影响，为测距模块搭建了云台系统，使测距模块在运动过程中始终保持水平状态。

2 模糊控制器设计

2.1 确定模糊控制器的输入变量和输出变量

模糊控制器的输入是超声波采集的距离信号和双足机器人与目的地方向的夹角信息，输出是双足机器人的转动角度。双足机器人的构成包括支架、舵机、目标传感器、超声波传感器等部分。超声波采集的距离信息是机器人当前位置与障碍物的距离，超声波在机器人前进方向的180度范围内采集与障碍物的距离信息，取其中最左、最右及正前方的距离信息为三个输入变量，定义最左侧距离为DL、正前方距离为DC、最右侧距离为DR。通过目标传感器，确定双足机器人当前位置与目的地方向的夹角D0为角度输入变量。利用这些条件推理出输出变量OUT，即双足机器人的转动角度，如图1所示。

2.2 输入变量及输出变量的模糊化

定义距离输入变量的模糊语言为DL={Near，Far}， DC={Near，Far}，DR={Near，Far}；角度输入变量C0的论域为C0={LB，LM，LS，ZO，RS，RM，RB}；输出变量OUT的论域为OUT={OLB，OLM，OLS，OZ，ORS，ORM，ORB}。各个变量的隶属度函数图形为对称三角形且模糊分割完全对称，DL、DR、DC、 C0及OUT的隶属度函数图形如图2中（a）-（e）所示。

2.3 确立模糊控制规则

模糊控制规则（控制策略）的选择是模糊控制器设计非常关键的一步。它是基于手动控制策略，是操作者经验和技术知识的集合 。模糊控制规则实际上是一系列模糊条件语句的集合，反映了输入量与输出量的关系。按照双足机器人的实际控制进行模糊逻辑推理，确定了四个输入信号，一个输出信号，构成一个多输入单输出的模糊控制系统。

双足机器人在行进过程中，根据与障碍物的距离信息及与目的地的夹角信息进行决策推理出转动角度，从而实现最佳的路径规划。当采集到障碍物信息时，双足机器人将转动一定角度，改变行进轨迹实现有效避障的功能。机器人行进规则如下：

（1）当目标点位于障碍物左（右） 侧时，则机器人左（右）转；

（2）当目标点在机器人正前方且障碍物距离机器人很近时，则机器人需根据它的左侧和右侧的障碍物信息来决定左转还是右转；

（3）当左侧障碍物距离大于右侧障碍物距离时， 机器人选择向左转，反之向右转。

根据确定的输入输出变量的论域，采用模糊规则的一般形式If（条件）then（结果）进行描述。模糊规则如表1所示。

2.4 模糊决策

模糊决策（模糊推理）是根据模糊逻辑的关系及推理规则来进行的 。根据模糊规则推出输出量的隶属度函数。下面将通过简单举例来说明模糊控制器的原理。

以双足机器人在DL=0 ，DC=2.5，DR=3，C0=8的状态为例，该状态对应模糊表中的第11、12、18条规则，由此状态下的模糊规则进行推理合成，得到输出量的隶属度函数。

第11、12、18条规则推理结果及合成隶属度函数结果如图3中（a）-（d）所示。

2.5 解模糊

经模糊推理得到的是一个模糊集合 。通过解模糊得到精确值，确定实际输出对双足机器人进行转角控制。MATLAB 提供5种解模糊方法：面积重心法、面积等分法、平均最大隶属度法、最大隶属度取小法和最大隶属度取大法 。本文模糊控制器采用面积重心法进行解模糊，将模糊输出量清晰化，得到精确值来控制双足机器人转动角度。

3 Matlab实验仿真

在Matlab中进行双足机器人路径规划仿真实验，实验中圆形障碍物的半径和位置随机设置，起点设定为原点，终点的位置任意设置， 进行路径规划的同时描绘出机器人的运动轨迹，仿真实验可以在任意环境下检验算法的正确性和可靠性。实验结果如图4所示。

由图4可知（a）图起点为（0，0），目标点为（500，550）；（b）图起点为（0，0），目标点为（300，350）。改变目标点位置，障碍物随机设定，机器人均可实时躲避障碍物，并规划出最短路径，验证了利用模糊算法进行双足机器人路径规划的有效性和可行性。

4 小结

本文介绍了基于模糊控制算法的双足机器人路径规划方法，系统的描述了模糊规则控制器的建立，利用MATLAB进行了仿真实验，实验结果表明模糊算法可以有效地减小双足机器人在路径规划中对于环境信息的依赖性，保证了实时性并提高了双足机器人路径规划的精确度。

参考文献

[1]曹宇杰，邓本再，詹一佳.基于模糊神经网络的RoboCup足球机器人局部路径规划方法研究[J].电子设计工程，2015（23）：141-144.

[2] 李庆春，高军伟，谢广明.基于模糊控制的仿生机器鱼避障算法[J].兵工自动化，2011，30（12）：65-69.

[3]孙大勇，苏庆宇.井下机器人路径规划中的模糊逻辑控制算法[J].电气技术， 2007（3）：47-49.

[4]霍迎辉，张连明.一种移动机器人的路径规划算法[J].自动化技术与应用，2003，22（5）：8-10.

[5]王妹婷，陆柳延，齐永锋，等.基于模糊算法的水下机器人路径规划研究[J].机床与液压，2014（3）.

[6]张营，鲁守银.基于模糊控制算法的变电站巡检机器人路径规划[J].制造业自动化，2015（11）：53-55.

[7]郝宗波，洪炳熔.未知环境下基于传感器的移动机器人路径规划[J].电子学报，2006，34（5）：953-956.

[8]刘丽萍.硒砂瓜温室种植模糊控制系统设计[J].电子设计工程，2012，（20）：62-64.

[9]高扬，孙树栋，赫东锋.部分未知环境中移动机器人动态路径规划方法[J].控制与决策，2010，25（12）：1886-1889.

[10]姚毅，陈光建，贾金玲.基于模糊神经网络算法的机器人路径规划研究[J].四川理工学院学报：自然科学版，2014， 27（6）：30-33.

[11]柳长安，鄢小虎，刘春阳，等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报，2011，28（5）：1220-1224.

[12]黄大志，张元良，陈劲松.基于模糊控制的自主寻迹机器人研究[J].机床与液压，2012，40（9）：35-37.

[13]朱兴柯，叶飞，李斌，等.变电站巡检机器人运动控制系统研究[J].现代制造， 2014（30）：122-124.

[14]陈卫东，朱奇光.基于模糊算法的移动机器人路径规划[J].电子学报， 2011（4）：971-974.

[15]肖瑛，董玉华.一种级联混合小波神经网络盲均衡算法[J].信息与控制，2009， 38（4）：479-483.

作者简介

鲁红权（1994-），男，河北省唐山市人。现为华北理工大学学生。研究方向为智能机器人控制。

路径规划第9篇

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

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