关键词：遗传算法；智能机器人；路径规划
前言
现阶段，在现代社会中，各领域生产智能化发展速度不断加快，与此同时，智能机器人成为了国内外该领域的研究人员的重点科研对象，并且针对智能机器人的路径选择问题进行深入探究。在研究过程中，为了能够令机器人帮助人类做更多的实际工作，则开发了智能机器人来辅助实践，在各项指令的操作和影响下下，机器人能够完成人类赋予它的任务。
一、遗传算法概述
（一）简析遗传算法
早在上个世纪中叶，世界范围内的少数计算机科学家开始探究遗传算法的雏形，而后，在一段时期内，遗传算法成为了一种进化计算的分支策略，填补了编码方案设计领域的空白。实际上，遗传算法在实践过程中的应用策略较为简单，在该算法支撑下的搜索能力以及躲避障碍物的能力都较强。
（二）遗传算法的实践优势
应用遗传算法来对智能机器人的路径进行科学规划的过程中，可以将其与直角坐标法结合起来应用，这样一来，便可以简化数据计算以及编码过程的复杂程度，保障机器人在行进的过程中的大部分时间处于环境的中心位置，从而避免遇到障碍而停止行进[1]。
二、基于遗传算法的智能机器人的路径规划
要想令智能型机器人顺利地游走于各类静态与动态环境之中，不被各种障碍物体所碰到，并能够完成一定的任务，并不是一件容易的事。因此，需要利用遗传算法这一科学研究内容来完善智能机器人的路径规划方案，使其达到既定行进目标。
（一）智能机器人研究项目概述
在智能机器人的研究领域中，机器人的路径规划指的是机器人在它的工作范围内，根据系统内部的指令来进行最优化的选择，包括行走路径最短或行走时间最少等决策都是通过路径规划指令来引导，甚至在智能机器人的行走过程中遇到障碍物时，则也同样需要路径规划指令操作来判断最优的行动路径[2]。
（二）在遗传算法影响下的智能机器人路径规划的特征与优劣势研究
1.基于遗传算法的智能机器人行进路径的特点分析
遗传算法是以自然遗传机制为前提，在某种程度上以生物进化过程为基础来构建的一种数学模型，在其中利用变异编制控制机构等计算程序。基于遗传算法的智能机器人路径规划需要占据大量的存储运算空间，因此，智能机器人的路径规划速度较为缓慢，在复杂动态环境下的路径规划实效不佳，需要在未来研究过程中对其进行改进。
2.基于遗传算法的智能机器人路径规划的优劣势分析
就从基于遗传算法的智能机器人路径规划来看，尽管这一模式能够在一定程度上为机器人提供可行的行进方案，但其行进速度较为缓慢，即使受到局部选择极小的障碍，也会令智能机器人在动态环境中步履维艰。研究发现，基于遗传算法的智能机器人路径规划具备一定的研究价值，推进了智能机器人项目的研究进展。
通过分析遗传算法的特征及其演进过程，运用遗传算法或其它模拟形式来优化智能机器人的路径规划，则可以在一定程度上增强智能机器人的性能。但是，无论何种方法，都或多或少的存在一定的问题，不能达到智能机器人最优路径选择的要求[3]。相对而言，尽管存在一定的不足，但基于遗传算法的智能机器人路径规划相对还是较为可行。目前，在各项技术支撑下的智能机器人已经具备一定的实践能力。
在遗传算法的推进下，智能机器人项目的研究有了新的进展，且在机器人的路径规划方面有了极大的突破，但就目前的研究成果来看，智能机器人的行进路线并不完美，成功完成某一既定的行进任务的概率并不高，因此，相关的技术科研人员还需针对路径规划问题做深入的探讨与研究。未来的主要研究方向有以下几项内容：其一，全局路径规划与局部路径规划的有效整合；其二，多传感器信息融合技术的引入；其三，智能算法以及相关改进研究等[4]。相信在多元化的智能算法影响下，智能机器人的行进路径规划则会更加准确，并且，能够完成更为高级的指令任务，为人类社会各领域的生产建设提供优质的服务。
结束语：
通过研究智能机器人路径规划可以了解到，不同策略方式的选择应用都可以充实到智能机器人研究成果之中，尤其是遗传算法的实践应用，令智能机器人路径规划更加合理。从以往的研究资料中可以了解到，智能机器人路径规划是机器人研究领域中的一项重要分支，同时也是智能机器人用以执行各种指令的基础条件。在研究智能机器人的路径规划过程中，遇到了诸如易陷入局部最优等问题，进而提出应用改进遗传算法来改善这一状况，并且取得了良好的实效。总之，基于遗传算法的机器人路径规划能够在一定程度上推动该研究项目的发展，从而积累更多的研究经验。■
参考文献
[1]崔瑾娟.基于遗传算法的机器人路径规划[J].洛阳师范学院学报，2013，02（02）：35-36.
[2]谭艳.基于遗传算法的机器人路径规划问题[J].现代计算机，2013，08（15）：23-24.
关键词：白车身；机器人焊接；路径规划
我国目前白车身焊接机器人焊接路径规划方面仍处于落后水平，相关路径规划也极为不完善，机器人工作的过程中经常出现作业顺序不合理的状况，导致生产周期增长，影响整个焊接线路的发展。所以如何制定出一条合理的路径规划是当前首要目标，本文立足实际就针对这个问题提出一些有效性策略。
一、路径规划的意义
白车身焊接机器人焊接中制定出一条合理的路径规划可以有效缩短机器人生产时间，进而缩短整个工期，提高整个生产效率，某种程度上降低了生产成本。另一方面，白车身焊接机器人焊接路径规划具有一定的典型性，在自动驾驶、服务机器人、挖掘机器人等路径规划研究方面具有重要的借鉴意义，具有较高的社会价值和经济价值。
二、白车身焊接机器人焊接路径规划
（一）路径规划的基本任务
现代化工业生产的主要目标是为了获得较高的制造质量、取得较高的生产率，而付出较低的生产成本，这是现代企业提高自身竞争力的重要手段，也是路径规划中的主要任务之一，而在路径规划的过程中要想保证焊接质量主要取决于以下两点：
第一，最大程度的使用机器人工位。使用机器人工位能够有效降低工人的劳动强度，减少人为错误几率，提高焊接的准确性，保证焊接的顺利进行，从而保证焊接的稳定性。
第二，要完成所有的焊接点，保证焊接的工艺参数。
要想实现较低的制造成本就是最大化的利用现有资源，提高机器人的工作效率，缩短机器人工位的生产周期，减少机器人的使用数量。路径规划的重要方向就是提高生产率，保证生产环节的顺利进行，缩短生产周期，提高生产率。
（二）路径规划
白车身焊接机器人焊接路径规划主要有两个分支，一是改变工艺参数，使用新的工艺方法和辅助设备。二是要提高分配的合理性、提高焊接顺序的合理性，提高合理性的目标是为了减少机器人工位的生产周期。第二个分支实现的途径主要是通过提高机器人焊接路径的合理性，从而提高单个机器人的生产效率，最终缩短整个生产周期。
（三）遗传算法
遗传算法是进化算法中产生最早、应用最广泛的一种基本算法，在工程技术和经济管理领域都有广泛的应用。遗传算法有群体搜索和遗传算子两个基本特征，所谓的群体搜索打破了领域的限制，使信息可以广泛分布于整个空间。而遗传算子就是使染色体进行随机操作，以降低人机交互的依赖。两个特征保证了遗传算法具有最优的搜索能力、最简明的操作能力以及信息处理的隐秘能力。
白车身焊接路径规划主要问题如下：
第一，白车身中所需要焊接的焊接点众多。
第二，在生产的过程中常常追求没有意义的高精度。
第三，在解答相关问题时需要运用数学方法。
第四，因为方案最终应用于企业，所以数学方法最好要简洁明了，便于学习。
综上，在路径研究时需要运用遗传算法，主要优势在于：
第一，遗传算法的计算步骤比较简单明了，在实际操作时便于学习和使用。在计算时大大减少了计算量，从而节约时间。
第二，能够在很大程度上优化焊接作业顺序，减轻焊接的工作量。
第三，减少定量分析与定性分析的工作量。
第四，能够很好的掌控全局，在全局中找到最优解。
三、路径规划的仿真
（一）仿真系统的各要素
路径仿真系统一般要具有以下几个基本要素：
第一，对仿真问题的描述。模型和仿真运行控制共同组成了一个仿真系统，而一个特定的模型又是由一个参数和一组参数值构成。例如白车身点焊机器人焊接路径的参数模型一般包括家具模型、机器人模型、侧围模型，在这基础之上还加入了具体的参数值，就形成了特定的模型。
第二，行为产生器。模型确定以后就要对模型进行试验，这是一套试验的软件，行为产生器可以生成一组根据时间变化的数据，这类数据是仿真的物资基础。
第三，模型行为及对行为的处理。
模型行为可以大致分为三种：轨迹行为、结构行为以及点行为。
仿真系统中都要获取轨迹行为，这些行为的获取主要是根据时间的推移而产生的。
（二）仿真软件的选择
一个完善的机器人仿真系统可以依据机器人的运动学、动力学、行为轨迹等多项内容进行仿真计算，并可以根据机器人的实际操作内容进行仿真操作过程，并不依赖于真正的机器人。但目前最主要的工作是对机器人的路径规划做一个仿真方案，而不是设计出一个机器人的仿真系统。在进行机器人路径规划时需要一定的条件，在现实生活中可以有多个选择，最好的选择就是使用一些类似CAR这种专业软件，如果条件不允许可以选择VC++或者使用CATIA等软件进行仿真。VC++自主编写的优点在于针对性比较强，在做路径时可以考虑多方面因素，然而缺点是不能建立详细的三维模型，在实际操作时不能全方面的展现白车身焊接工位情况，且工作量较大。CATIA与VC++相比最大的优势就是可以建立详细的三维模型，能够全方位展现工位情况，仿真轨迹最为真实，在仿真过程中还可以检查是否干涉。而缺点也是比较明显的，在仿真的过程中不能将动力学和控制算法考虑在内。
四、小结
白车身主要是以钢结构为主的支架，是汽车中重要组成部分。而车身制造是整个环节中比较复杂又极为重要的一环，影响整个汽车的质量。我国研究白车身焊接机器人焊接路径仍处于落后阶段，为了提高综合竞争力需要加大技术投资，提高我国白车身制造综合竞争。
参考文献：
[1]王立东.基于Christofides算法的白车身焊接机器人路径优化[J].河西学院学报，2011，27（2）：96-100.
关键词:路径规划; 地标; 预处理; 层次缩减算法; 三角启发算法
中图分类号: TP312.8文献标志码:A
Landmark.oriented heuristic routing algorithm in traffic network
MENG Ke*, ZHANG Chun.yan
School of Computer Science and Technology, China University of Mining and Technology, Xuzhou Jiangsu 221008, China
Abstract:
To improve the query efficiency of road routing algorithm in large-scale traffic network, a landmark-oriented algorithm based on A* algorithm was proposed. Select the most important vertexes and edges as landmarks during preprocessing, choose appropriate landmarks as the reference parameters and calculate in sections in point-to-point routing. Experiment results indicate that it has higher query efficiency and more reasonable results in long-distance road routing.
To improve the query efficiency of road routing algorithm in large.scale traffic network, a landmark.oriented algorithm based on A* algorithm was proposed. Select the most important vertexes and edges as landmarks during preprocessing, choose appropriate landmarks as the reference parameters and calculate in sections in point.to.point routing. The experimental results indicate that it has higher query efficiency and more reasonable results in long.distance road routing.
Key words:
path.planning; landmark; preprocessing; Contraction Hierarchies (CH) algorithm; A* Landmarks Triangle (ALT) algorithm
0 引言
对于大规模交通网络，Dijkstra算法［1］需要花费长时间进行计算，不符合实时性的要求。目前相关的优化算法有启发式算法和预处理算法两种。启发式算法(A*)［2］使用合适的启发函数减少搜索空间以获得较高的查询效率，启发函数会直接影响最后的计算结果；预处理算法使用点或边标记法、快捷路径法、区块分割法等对网络中的边进行合并和标记以迅速求出最短路径，但需要大量的辅助存储空间。
根据实际交通网络的特点：在主干道上通过的最短路径最多，存在重要的边和点；对于长距离的路径规划，出发点和目标点的中间节点有可能成为最短路径上的点。本文以A*算法为基础，将地图中关键的节点选为地标，并将地标作为启发函数的启发参数来求得路径规划的合理解。为提高长距离路径规划的查询效率，使用分段处理的思想将查询分割为若干子查询，并给出相关的优化方法。
1 相关研究
对于静态网络图G=(V,E)，大多数优化算法需要经过充分的预处理。三角启发算法（A* Landmarks Triangle，ATL）［3］39算法将图G按中心点划分为若干区域，每个区域选取一个标志点(LandMark)，根据三角不等式使搜索路径趋向于目标节点，大幅度减少搜索空间，从而提高查询效率。
文献［4］提出一种分层合并的预处理算法CH，对原始图G的边进行迭代合并，产生一组生成图{G1,G2,…,Gh}，生成图和原始图的边使用标号对应，以便求解后还原原始路径。这种预处理算法非常消耗存储空间，不适合于大规模网络，但是可以快速求出最短路径。经过预处理的CH算法时间复杂度可以达到O（N log H），N为合并图的平均边数，H为合并图的层数。
Arc.Flags［5］基于区域划分的思想对图进行预处理。将图划分为K个区域，每一条边(v,w)存储一个K比特的参数，第i位代表从点v到区域i的最短路径中包含此边。ARC.Flags可以精确求出最短路径，但预处理时间较长。Chase算法［6］综合CH和ARC.Flags的特点，对ARC.Flags划分的区域使用CH算法进行合并处理，加快预处理时间。
Bauer等［7］提出一种混合算法SHARC，对CH和ARC.Flags进行了多项改进，提出分层标记的思想，可以缩短预处理时间和减少额外空间。分层的ARC.Flags提供搜索方向，CH加速区域内的路径搜索，在单向搜索环境中SHARC可以提供非常高效的精确最短路径。经过修改的SHARC可以进行时变最短路径问题的搜索，文献［8］对此有详细描述。
2 地标导向的启发式算法
2.1 地标的选取
交通网络图一般拥有层次关系，乡镇与城市之间有干道相连，城市与城市之间有高速相连，在路径规划中这些连接线路被通过的次数最多。对于具有这一特点的图G，地标集的定义如下：
设r为一个搜索半径，点u为中心，2r为半径的G的子图记为Bu,2r，选取满足以下条件的最短路径P，PBu,2r并且Len(P)>r（Len(P)为P的欧拉长度）；如果存在点集Cu对于所有的P满足Cu P，则Cu为Bu,2r的地标集，并且设h=max(|Cu|)为G的地标度数（|Cu|为Cu的节点个数）。显然h越大地标对最短路径的贡献越大，在路径规划时可利用的地标节点越多。
计算大规模交通网络的地标集，采用以下几个步骤。
1)选择节点密集型的区域，将图分割为搜索半径为r的不同区域。在实验中会讨论r在不同取值时地标集获取情况以及启发式算法的查询速度。
2)对于区域Bu,2r，使用CH算法进行预处理以便于快速计算最短路径。
3)为Bu,4r中的每一个点对计算最短路径，获取最短路径集合P={Pv,w|v,w ∈Bu,4r ,|Pv,w|>r}。
4)对P中所有的路径取交集获得地标集Cu。
2.2 启发式算法设计
本文将地标节点作为启发式搜索的启发节点，求解思想如下。
对于点对（s,t）如果属于同一分割区域，由于使用了CH算法进行预处理，可以快速求得精确的最短路径。如果（s,t）属于不同区域则使用以下启发式规则。
1)从s所在区域的地标集中选取距离t最近的地标c作为下一跳的启发节点，s到c的最短路径使用CH求得。如果s所在区域没有地标集，则设c=s，转向第2）步。
2)从邻近区域的地标集中选取距离t最近的地标c′作为启发点，使用ALT算法求出（c,c′）的最短路径。
3)重复以上步骤直到c′与t在同一分割区域，使用CH算法计算（c′,t）最短路径。
4)对最短路径进行合并输出。
CH算法在区域内进行快速搜索，同时对于不同区域采用ALT算法控制搜索方向，使搜索始终沿着目标进行，这是一种分段搜索的思想，对于长距离的最短路径求解由于有地标集提供搜索参考，搜索线路比ALT更加精确，耗时更短。
2.3 算法分析与优化
CHALT算法的地标集预处理比较耗时，但可以在多项式时间之内完成计算。对于G的一个稠密子图，从空集开始， 使用CH算法从所有待处理的路径中选取一个覆盖所有路径的点，然后将此点从图中移除，对剩余路径迭代计算，直到不存在满足条件的点为止，在有限次迭代后算法会终止。对子图预处理的时间复杂度为O(n log nO(CH))，其中n为子图的节点个数，O（CH）为CH算法的时间复杂度。
对于ALT算法，双向搜索的收敛速度一般比单向搜索快［9］，因此使用双向CHALT查询可以获得更好的时间效率，具体执行步骤如下：
1)使用前向搜索计算(s,t)的最短路径获取一个启发点cf;
2)使用后向搜索计算(t,s)的最短路径获取一个启发点cb;
3)设s=cf , t=cb 重复1)，2)两步，最终搜索会在同一个节点相遇;
4)合并前向搜索和后向搜索的最短路径后输出。
对于地标集，可以使用TNR［10］的思想进行最短路径索引，TNR计算并存储所有地标之间的最短路径并存储在一张|C| × |C|的表格中，其中|C|为图G中地标节点的个数。如果s和t分别在不同的分割区域，并且存在地标，则根据索引表查询地标之间的最短路径，否则执行启发式搜索。对地标的查询可以在常数时间之内完成。大规模网络图使用CHALT+TNR算法可以在牺牲少量存储空间的前提下提供最优的性能。
3 实验
使用Intel Pentium CPU 2.5GHz、2GB RAM完成本算法和其他算法的比较实验，算法采用C++编写。实验数据选用北京市交通路网（包含81534个路段和34219个节点）。最短路径的度量标准为距离最短，在实验中使用欧拉距离完成路径计算。
表1为不同的最短路径算法在1000组随机查询中的平均时间比较。预处理的时间使用分钟计算，预处理每节点所占用的额外空间单位为字节，额外空间为负说明预处理后的搜索图比原图规模小。从表1中可以看出ARC.Flags和SHARC虽然执行效率比较高，但需要长时间的预处理，并且节点变更对算法的影响大，不适用于大规模网络；CHALT算法执行时间属于中上等，但预处理时间短，在经过TNR优化后的执行时间接近SHARC算法的查询时间；双向CHALT算法在时间上比单向快一些。由于CHALT使用地标节点作为启发参数，地标节点仅占所有节点的小部分，不容易受到节点变更的影响。
在CHALT算法中，划分区域的大小将影响地标集的选取和路径规划结果。表2表示不同搜索半径r对查询速度的影响，r的单位为km。从表2中可以看出在r=3km和r=4km时候在预处理时间少的情况下依然可以获得不错的查询效率，极端情况下r=0时算法变为ALT算法；r=∞时算法将仅使用CH算法，地标节点个数接近于0，启发函数不可用，也就失去了地标的参考价值。在实际应用中需要根据实验来确定合适的搜索半径，来达到效率与合理性的权衡。CHALT算法获取的解为近似解，但接近最优解，如图1(图1中黑色路径为CHALT算法，白色路径为Dijkstra算法)。CHALT算法优先选择重要的节点和边，在地图上表现为主要的街道和路口；Dijkstra算法对所有与(s,t)相关的路径计算以获得最优解，而不会考虑节点的重要性，在实际应用中存在不合理性。CHALT算法获取的路径比Dijkstra更平滑并且更合理。
4 结语
为解决大规模长距离的最短路径规划问题，本文根据分
段计算的思想，使用地标集将启发式搜索限制在靠近最短路径的方向。实验证明CHALT算法在保证预处理和查询效率的基础上，得出更合理的计算结果，优化后的算法查询效率更高，可以应用在大型交通网络中。下一步研究方向为以地标为导向的启发式算法在离散变权网络中的应用。
参考文献:
［1］
DIJKSTRA E W. A note on two problems in connexion with graphs ［J］. Numerische Mathematik, 1959(1):269-271.
［2］
GOLDBERG A V, KAPLAN H, WERNECK R F. Reach for A*: Efficient point.to.point shortest path algorithms ［C］// Proceedings of 7th International Workshop on Algorithm Engineering and Experiments. Miami: SIAM, 2006:129-143.
［3］
GOLDBERG A V, KAPLAN H, WERNECK R F. Better landmarks within reach［C］// WEA07: Proceedings of the 6th International Conference on Experimental Algorithms. Berlin: Springer.Verlag,2007:38-51.
［4］
GEISBERGER R, SANDERS P, SCHULTES D, et al. Contraction hierarchies: faster and simpler hierarchical routing in road networks［C］// WEA08: Proceedings of the 7th International Conference on Experimental Algorithms. Berlin: Springer.Verlag,2008:319-333.
［5］
KHLER E, MHRING R H, SCHILLING H. Fast point.to.point shortest path computations with arc.flags［C］// The Shortest Path Problem: Ninth DIMACS Implementation Challenge. Piscataway: IEEE, 2009:41-72.
［6］
LAUTHER U. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background［EB/OL］.[2011-07-02].gi.days.de/archive/2004/downloads/gitage2004/vortraege/lauther.pdf.
［7］
BAUER R, DELLING D. SHARC: Fast and robust unidirectional routing ［J］. ACM Journal of Experimental Algorithmics, 2009, 14(12):12-26.
［8］
DELLING D. Time.dependent SHARC.routing ［J］. Algorithmica, 2009, 60(7): 60-94.
［9］
GOLDBERG A V, HARRELSON C. Computing the shortest path: A* search meets graph theory, #MSR.TR.2004.24 ［R］.USA: Microsoft Research, 2004.
［10］
BAST H, FUNKE S, SANDERS P, et al. Fast routing in road networks with transit nodes ［J］. Science, 2007,316(5824):566-593.
［11］
HILGER M. Accelerating point.to.point shortest path computations in large scale networks［R］. Berlin: Technische University, 2007.
关键词： 增维启发式搜索； 智能车； 路径规划； 高效率； 平衡
中图分类号： TP311 文献标识码：A 文章编号：1009-3044（2016）36-0188-04
Increment-dimensional Heuristic Search Motion Planning Algorithm
WU Hong
（Department of Computer Science and Technology， Tongji University， Shanghai 201804， China）
Abstract： For intelligent vehicle motion planning， effective enough is always an important issue. The huge statue-space， high time complexity of the high dimensional search approach is always the bottle-neck of the algorithm. To solve this problem， this paper proposes a new method， increment-dimensional heuristic search algorithm. This method is a stepped-up heuristic search to reduce the searching status and improve the search algorithm execution efficiency. In experiment， the result shows that this algorithm reduces 87% of searching status and executes time is nearly 1/10 of that of the traditional heuristic search method. It is a very good trade-off between execution efficiency and trajectory quality.
Key words： increment-dimensional heuristic search； intelligent vehicle； motion planning； effective； trade-off
1 引言
在智能无人车领域，智能车无人车的行驶安全以及驾驶舒适度一直是一个非常重要的研究问题。而智能无人车的路径规划是这一问题的核心。智能无人车路径规划算法需要在有限的时间内，输出高质量高精度的路径，传输给智能无人车的控制模块、执行模块加以执行。一般的移动机器人路劲规划算法研究的是在高维度的空间里探索出一条路径，相比之下，智能无人车的路径规划则需要考虑车辆动力学模型约束，通常我们需要考虑四维状态。二维状态（x， y），表示车辆的地理坐标，车辆的航向角θ，以及行驶速度v。在四维状态空间里搜素出一条可行路径，是一个计算密集型的任务。与此同时，智能无人车的行驶速度可能很高，因此要求规划算法能够在一个非常有限的时间里给出搜索的结果。
为了解决这一问题，本文给出一种增维启发式路径规划搜索算法。该算法采取一种分阶段，逐步增加搜索维度的方法来生成路径。在每一个阶段，增维搜索算算法选择离车辆当前位置附近的一个区域，增加状态空间维度，进行启发式搜索。因此该算法的输出轨迹是多精度的轨迹。在车辆附近位置，输出轨迹为高维度高精度，充分考虑车辆动力学模型，驾驶舒适度，能耗以及可靠性。而在远处，低维度低精度的轨迹依然可以引导智能无人车的行驶方向正确，充分考虑的地图信息，障碍物信息。从人类正常的驾驶习惯上来说，驾驶员总是对近处的驾驶精度较高，而远处相对较低。该算法充分利用了这一点原理，牺牲了远处的轨迹精度，极大地提高了算法的运行效率。在频繁联系的反复规划中，车辆会一直执行高精度部分轨迹。因此，该算法在运行效率以及输出轨迹质量方面，取得一个非常好的均衡。
为了展示该算法的性能，本文进行了仿真实验。在实验中，智能无人车刚刚进入一个停车场，需要在目标停车位泊车。实验结果表明，相比传统的高维度启发式搜索算法，该算法减少了超过87%的搜索状态，运行性能提高了近10倍。
2 研究现状及文献综述
从20世纪70年代开始，欧美的西方国家开始无人驾驶汽车方面的研究工作，并在智能无人车的控制和商用化方面取得一定进展。在汽车工业非常发达的德国，各大汽车公司都资助或者联合高等院校以开发可在普通道路上行驶的智能无人车。目前，欧盟已启动一个名叫CyberCars的智能无人车项目，以推动智能无人车的研究和各国间智能无人车技术的信息共享。
在20世纪的80年代，我国部分大学开始智能无人车的研究工作，虽然起步较晚也取得一定成果。目前，从事这方面研究工作的 主要是国防科技大学、军事交通学院及清华大学等科研机构。[1-6]
在智能无人车决策模块的相关研究中，最核心的部分是路径规划算法的研究。文献[7]提出一种快速扩展随机树生成算法―RRT （Rapid-Exploring Random Tree）算法。RRT是一种多维空间中有效的路径规划算法。它以一个初始点作为根节点，通过随机采样增加叶子节点的方式，生成一个随机扩展树，当随机树中的叶子节点包含了目标点或者进入目标区域，便可以在当前随机树中找到一条从初始点到目标点的路径。文献[8]在RRT算法在自动驾驶汽车以及宇宙空间探测器路径规划上的应用。文I[9]对RRT算法提出优化方法并通过实验，解决了基本RRT算法存在的动态环境中规划路径不稳定的问题，同时提出双向RRT生成算法以及动态步长等优化方法，提高了RRT算法生成初始点到目标点路径生成的速度。然而RRT算法在规划路径的过程中产生的是可行解，而非最优解。文献[10]提出了RRT*算法，RRT算法进行了改进，保证了RRT算法生成解是渐进最优解。然而RRT*算法在时间复杂度上远高于朴素的RRT算法。文献[11]提出了一种RRT*算法加速的方法，通过使用预生成RRT随机树，在使用RRT*_S算法优化当前随机树，构造出与RRT*算法生成随机树本质相同的RRT*_S随机树，从而实现RRT*算法的加速。文献[12]为麻省理工学院将RRT*算法运用于叉车移动路径规划的一次应用实践，并对RRT算法与RRT*算法在实际应用中的结果给出对比分析。
文献[13][14][15][16]给出了2007年美国DARPA智能无人车比赛麻省理工学院（MIT）参赛智能无人车的整体架构，MIT智能无人车的轨迹生成算法，主要是用RRT算法生成可行路径，并对该路径进行平滑，以此为基础生成智能无人车运动轨迹。
文献[17][18][19][20][21][22]主要阐述了状态空间搜索算法，通过估价函数进行启发式搜索以及状态空间搜索剪枝。文献[23]提出了ARA*（Anytime A*）算法，对短时间间隔内连续反复用A*搜素算法进行空间状态搜索这一类状态空间搜索应用场景进行优化。
3 增维启发式搜索算法
增维启发式搜索是一种两阶段的启发式搜索算法。在算法的第一阶段，搜索出一条从车辆当前位置到目标位置的几何最短路的轨迹。在第一阶段的搜索，我们只考虑二维的搜索状态空间（x， y），即车辆的地理坐标。第二阶段，选取第一阶段的路径中的一个点作为本阶段目标点，搜索状态加入车辆的航向角θ，以及行驶速度v，总体状态空间提升到四维，并且考虑车辆动力学模型，在此状态空间下，搜索出一条高精度可执行的车辆行驶轨迹。
3.1 第一阶段搜索
在这一阶段，因为我们只考虑二维状态空间（x， y），即车辆的地理坐标。如果将状态空间离散化，这一搜索问题会退化成一个图论的最短路问题。虽然图论的最短路问题有很多经典成熟的算法。但是在这里还是有一些值得讨论的问题。
3.1.1 栅格随机化
一般地，在执行最短路算法之前，会把状态空间离散化成栅格，然后对栅格做4联通或者8联通处理，但是这种离散化方法会使最短路失去最优解，如图1a、1c所示。
图1 a. 离散化使得几何最短路失解；b. 随机化18联通栅格法；c. 8联通栅格法几何最短路（黑），随机化18联通栅格法几何最短路（红）。
a b c
为了解决这一问题。如图1b所示，算法使用一种随机化18联通的栅格法来离散化空间。即在栅格之间连边的时候，每个栅格除了相邻向相邻8个栅格联通，同时随机向其他10个栅格联通。选取的10个栅格满足与该栅格曼哈顿距离小于7，满足条件的格子约为100个，足以随机化，同时连边长度小于两个栅格长度，也方便计算是否与障碍物碰撞。
3.1.2 最短路算法
在离散化为栅格之后，采用单源最短路算法来计算车辆当前位置到其他位置的几何最短路，虽然单源最短路算法非常的经典成熟，但依旧有值得讨论的地方。
最短路的经典算法是堆优化的Dijkstra算法，该算法时间复杂度为 [O（eloge）]，其中[e]代表离散化后边的数量，然而在稀疏图中，SPFA算法的实际时间复杂度约为[O（e）]，在18随机联通结构的图中效率比价高，因而在本阶段中，我们采用SPFA算法计算单源最短路。
3.2 第二阶段搜索
在第二阶段的搜索中，我们选取第一阶段结果，几何最短路上的一个点来作为目标点，在搜索状态加入车辆的航向角θ，以及行驶速度v，在搜索中充分考虑车辆动力学模型，搜索出一条高精度可执行的车辆行驶轨迹。
3.2.1 启发函数
在启发式搜索过程中，一个强力有效的启发式函数对搜索效率来说至关重要。启发式函数不仅为搜索的实际代价提供了一个下界，同时也是实际代价的一个良好估算，可以引导搜索往正确的方向扩展，并且实现搜索剪枝，在第二阶段的搜索中，使用以下启发式函数。
动力学约束无障碍启发函数，[hnh（x，y，θ，v）]，该函数忽略障碍物信息，考虑车辆动力学模型，在此条件下求出最优的路径。这一启发式函数因为忽略了障碍物信息，只考虑动力学模型，所以可以离线计算、存储，在真实路径规划的过程中查询，计算速度极快。该函数极大的消除接近目标点航向角错误的搜索分支。
地图信息非动力学模型启发函数，[hh（x，y）]，该启发函数是上一启发函数的对偶函数，忽略车辆动力学模型，以几何最短路作为启发函数。该启发函数充分考虑的地理信息，消除了错误行驶方向的搜索分支。
结合二者，选取启发函数[h（x， y，θ，v）] = max（[hnhx，y，θ，v， hh（x，y））]，
fxyv） = g（x， y， ，v） + h（x， y， ，v） （1）
fxyv） Fxyv） （2）
f 为状态[（x， y， θ， v）]的估价函数， g为当前搜索状态[（x， y， θ， v）]的实际代价， [F]为实际搜索代价。
在该启发函数的引导下，第二阶段启发式搜索可以高效地计算出四维高精度路径。
4 仿真实验以及实验结果
为了展示该算法的性能，本文进行了仿真实验。在实验中，智能无人车刚刚进入一停车场，需要在目标停车位泊车。实验环境为Ubuntu 12.04 Linux系统，Intel i5处理器， 8GB内存。停车场大小为长80米宽50米，栅格离散化精度为10厘米，车辆采用72个不同的航向角，同时采用两个速度，最大的前向速度以及最大的后向速度。
图2 a朴素四维启发式搜索；b增维启发式搜索；c朴素四维启发式搜索输出路径；d增维启发式搜索输出路径
a
b
c
d
表1 算法性能比^
[ 阶段 朴素四维启发式搜索 增维启发式搜索 搜索状态数量 第一阶段 400000 第二阶段 10808634 408773 共计 10808634 808773 算法运行时间
（毫秒） 第一阶段 142 第二阶段 2844 141 共计 2844 283 ]
如图1b，对于每一次路径规划，增维启发式搜索算法可以有效地减少搜索状态的数量，因为高维度高精度部分的搜索集中在离车辆较近的区域，而从全局的角度，二维的几何最短路依旧引导着轨迹往正确的方向。相比之下朴素的四维启发式搜索搜索量极大（图2b）。从输出轨迹上看，两者的输出轨迹质量几乎相同（图2c、2d）。
5 结论
本文展示了增维启发式搜索路径规划算法。该算法分为两阶段。第一阶段在全局考虑二维的搜索状态空间，得出起始点到目标位置的几何最短路。在第一阶段几何最短路基础上选取一个目标点作为第二阶段目标状态空间，进而得到考虑了车辆动力学模型、四维的高精度可执行轨迹。仿真实验结果表明，在现实场景下，该算法极大地减少了搜索状态数量，提高了算法执行效率，同时输出高质量的智能无人车行驶轨迹。
参考文献：
[1] 杨明.无人驾驶车辆研究综述与展望[J]..哈尔滨工业大学学报，2006，38（增刊）：1259-1262.
[2] 孙振平.自主驾驶汽车智能控制系统[D].国防科技大学，2004.
[3] 杨森森.基于GPS/INS/激光雷达的无人车组合导航[D].上海交通大学硕士学位论文，2013.
[4] 钱钧，杨汝清，王晨，等，基于路标的智能车辆定位[J].上海交通大学学报，2007，41（6）：894-898.
[5] 王曦鸣.军用无人车的路径规划与仿真研究[D].北京交通大学硕士学位论文，2010.
[6] 曹玉芬，张国斌.美国无人地面车辆计划[J].国外坦克，2004（5）：25-27.
[7] Rapidly-exploring random trees： A new tool for path planning. S. M. LaValle. TR 98-11， Computer Science Dept.， Iowa State University， October 1998
[8] RRT-based trajectory design for autonomous automobiles and spacecraft. P. Cheng， Z. Shen， and S. M. LaValle. Archives of Control Sciences， 11（3-4）：167--194， 2001.
[9] Rapidly-exploring random trees： Progress and prospects. S. M. LaValle and J. J. Kuffner. In Proceedings Workshop on the Algorithmic Foundations of Robotics， 2000.
[10] S. Karaman and E. Frazzoli， Sampling-based algorithms for optimal motion planning，I. Robotic Res.， vol. 30， no. 7， pp. 846C894， 2011.
[11] Yun-xiao Shan Bi-jun Li Jian-Zhou Yue-Zhang，An Approach to Speed Up RRT* ，2014 IEEE Inteligent Vehicles Symposium （IV） June 8-11
[12] Karaman S， Walter M R， Perez A， et al. Anytime motion planning using the RRT*[C]//Robotics and Automation （ICRA）， 2011 IEEE International Conference on. IEEE， 2011： 1478-1483.
[13] Leonard J， How J， Teller S， et al. A perception-driven autonomous urban vehicle[J]. Journal of Field Robotics， 2008， 25（10）： 727-774.
[14] Kuwata Y， Fiore G， Teo J， et al. Motion planning for urban driving using RRT[C]//Intelligent Robots and Systems， 2008. IROS 2008. IEEE/RSJ International Conference on. IEEE， 2008： 1681-1686.
[15] Leonard J， Barrett D， How J， et al. Team MIT urban challenge technical report[J]. 2007.
[16] Kuwata Y， Karaman S， Teo J， et al. Real-time motion planning with applications to autonomous urban driving[J]. Control Systems Technology， IEEE Transactions on， 2009， 17（5）： 1105-1118.
[17] Barbehenn， M. and Hutchinson， S. （1995）. Efficient search and hierarchical motion planning by dynamically maintaining single-source shortest path trees. IEEE Transactions on Robotics and Automation， 11（2）： 198C214.
[18] Gaschnig， J. G. （1979）. Performance measurement and analsis of certain search algorithms. Ph.D. Dissertation， Carnegie Mellon University.
[19] Stentz， A. （1995）. The Focussed D* Algorithm for real-time replanning. Proceedings of the International Joint Conference on Artificial Intelligence （IJCAI）， pp. 1652C1659.
[20] Pearl， J. （1984）. Heuristics： Intelligent Search Strategies for Computer Problem Solving. Boston， MA： Addison-Wesley
关键词 GPS导航仪；算法优化；路权选定优化；Dijkstra算法
中图分类号：TP3 文献标识码：A 文章编号：1671—7597（2013）021-063-02
1 前言
随着我国经济的发展、城市化水平的提高、遥感技术（RS）、地理信息系统（GIS）、全球定位系统（GPS）的发展成熟，出现了以GPS接收机为载体，以GIS（主要是指电子地图）为数据，以路径规划算法为核心的GPS导航仪，使得用户仅需要输入目的地，就可以进行实时路径规划导航。这项技术可以为出行者提供出行路线信息，并在出行过程中对驾驶员适时地做出路线指导，是智能交通系统（ITS）的重要组成部分，它不仅极大地方便了出行者，使他们可以按照自己选定的目标获得路线信息。而且可以从宏观上降低城市交通拥堵情况，提高出行效率，对优化交通流在整个路网的分配方面产生积极的影响。
但是，由于GPS导航系统对路径规划求解的快速性有很高的要求，因此以往研究人员更加注重于提高速度而忽略了对求解的最优性。现阶段，GPS导航系统在实际使用上，由于成本、技术原因，存在着路径规划不准确、道路权值确定不准确的问题，导致用户使用GPS导航系统进行路径规划时未能选择最优路径，引导出行时效率不高，未能充分发挥其作为交通流量调节器的作用。这不仅影响使用者的出行效率，也不利于城市交通体系的高效运作。本文将会分析该问题产生的原因，并提出一种切实可行的解决方案。
2 GPS路径规划中的一些性质
2.1 GPS导航与图论
GPS导航中的路径规划是以储存在GPS导航仪中的地理信息系统——主要是其中的电子地图为数据的。因此，从计算机的观点出发，地图实质是一张带权有向图，而路径规划实质就是寻找两点之间的最优路径。这使我们可以联想到图论（Graph Theory）的一些性质和定理来寻求最优路径的寻找方法。
2.2 道路网络的数学模型
在数字地图中，定义一条道路的交叉点或端点作为道路网的节点，节点有相对的经度、纬度地理坐标；两节点间的路段定义为网络的边，路段的距离定义为边的权值，从而构成了一张描述城市道路的数学意义上的“图”，对于道路的通行代价，对应图论的概念“权”，我们称之为“路权”。
这样，城市中的路径规划就转换了一个经典的图论问题——最短路径问题。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图中两结点之间的最短路径（最小代价路径）。算法具体的形式包括：Dijkstra算法、SPFA算法、Bellman-Ford算法等。
3 传统Dijkstra最短路径算法运用的可行性分析
对传统算法最短路径算法能否运用于GPS导航仪的关键就在于其时间复杂度能否为GPS导航仪所需的快速性相适应。因此，本文选择最为经典的Dijkstra算法进行分析。
我们以深圳为例，在个人电脑上制作了一张简易电子地图并使用Dijkstra最短路径算法进行测试。
经过统计，深圳市存在上万个节点。通过实际测试，我们发现即使使用个人计算机，需要计算出15000个节点的图的单源最短路径，需要3379 ms，通过简单线性回归分析，我们得出了经典Dijkstra算法在GPS导航仪上运行时的耗时估计值，其中加粗字体部分为较为接近实际的耗时情况。
（注：本表数据有计算机随机产生，所用计算机配置：
CPU：Intel（R）Core（TM）2Duo CPU E7400 @2.80Ghz 2.80Ghz；RAM：3.25G可用；Windows 7 32位操作系统，下同）
可以看出，如果在GPS导航仪上使用经典的Dijkstra算法在深圳市区内进行路径规划，用户将需要等待70余秒，甚至有可能需要5分钟。显然，这不足以满足用户实际需求，这也是GPS导航仪厂商没有采用经典Dijkstra算法来解决最短路径问题的原因。
4针对经典Dijkstra算法的优化
4.1 一种特殊的数据储存方式
经过思考，我认为，由于需要计算单源最短路径，可以使用如下的数据储存方式：
定义一个数列a和一个变量sign。集合a中储存的是集合S中未被标记的顶点，sign记录的是数列a的项数。初始时，a中只有1项，记作a[1]其值为初始顶点v的编号，sign等于数列a中的项数，初始时，sign的值为1。稍后，我们将使用数列a及其一些特殊操作来储存集合S中的顶点，这种数据储存方式的具有如下的性质：
对于数列a中的任意一项a[n]，均有a[n]≤a[n*2]（n*2≤sign）、a[n]≤a[n*2+1]（n*2+1≤sign）。即保证a[1]为整个数列中的最小一项。
4.2 几种特殊操作的定义与分析
使用4.1提出的这种数据储存方式，需要定义四种操作：
1）加入数列：令sign增加1，将集合S中未被输入数列a的顶点中的一个顶点S[i]放入a[sign]。
2）维护加入（n）：本操作中n为参数。比较a[ ]（为对n向下取整），a[n]的大小。
如果a[ ]>a[n]则将它们交换位置并进行“维护加入（ ）”
3）取出第一项：先取出a[1]，然后令a[1]=a[sign]，sign减少1。
4）维护取出（n）：本操作中n为参数，比较a[n]，a[n*2]，a[n*2+1]，三个数的大小，令其中最小的与a[n]交换位置。
如果a[n*2]>a[n*4]或a[n*2]>a[n*4+1]则进行“维护取出（n*2）”
如果a[n*2+1]>a[（n*2+1）*2]或a[n*2+1]>a[（n*2+1）*2+1]则进行“维护取出（n*2+1）”。
4.2.1 操作“加入数列”的时间复杂度分析
上述例子展示了n个数加入到数列a的完整过程。通过此实例，可以看出，不论数的大小如何，我们总是只需进行一次“加入数列”操作，因此“加入数列”操作与数据大小无关，操作“加入数列”的时间复杂度为O（1）。
4.2.2 操作“维护加入（n）”的时间复杂度分析
对于“维护加入（n）”的操作次数，我们设想，如果数列a中已经有sign个元素，现在我们通过操作“加入数列”在a[sign+1]处多放入一个元素k，令k的位置为loc（此时loc=sign+1），假定a[sign+1]比数列a中所有项都小，则此时4.1所述的性质已经被破坏，需要通过执行操作“加入维护（n）”来维护，其维护顺序为：
调整a[sign+1]的位置，将a[sign+1]与a[]，交换位置，此时k的位置loc= 。如果此时的a[]比a[]还小，则再次进行调整，直到符合4.1所述的性质为止。
操作“维护加入（n）”实际是每次把小的项a[n]前调整到a的位置，如果将位置为a[n]项调整到a[1]，例如调整a[256]到a[1]，其过程为：a[256]->a[128]->a[64]->a[32]->a[16]->a[8]->a[4]->[2]->a[1]。可以看出，其过程类似二分法，时间复杂度为（LogN）。
4.2.3 操作“取出第一项”的时间复杂度分析
显然，操作“取出第一项”其操作仅一项，因此时间复杂度为O（1）。
4.2.4 操作“维护取出（n）”的时间复杂度分析
操作“维护取出（n）”的执行过程为：将最小的元素取出，并将数列中最后一项元素放到第一项，然后进行与操作“维护加入（n）”相反的操作。显然，实质上，操作“维护取出（n）”为操作“维护加入（n）”的逆向操作，因此，其时间复杂度亦为O（LogN）。
4.3 特殊数据储存方式与Dijkstra算法的结合
本章节我们将具体地将上文介绍的特殊出具储存方式与Dijkstra算法相结合，使得Dijkstra算法可以用于GPS路径规划。
算法时间复杂度分析对比：
上述说明的数据储存方式，是用于在O（LogN）的时间复杂度下，找到整个集合中的最小值，如果将其用于改进Dijkstra算法，则将使算法的时间复杂度由O（N2）下降到O（NLogN）。可以看出，O（NLogN）相对于O（N2）是巨大的进步。
4.4 改进型算法适用性测试
如上所述，时间复杂度从O（N2）降低到O（NLogN）是一个巨大的进步。最后我们实测了原数据于改进型算法的实际耗时，并根据简单回归分析，预测算法用于GPS导航仪的时间，如下表：
上表中加粗字体部分为接近实际情况的耗时。可以看出：
1）使用改进型算法，其最大耗时不超过6s（实际使用中一般不会出现最长耗时的情况），完全适用于GPS导航仪所进行的路径规划。
2）通过对比第1、2、3、4、5组数据，可以发现，随着点数、边数的增加，Dijkstra改进型算法的时间优化倍数更加明显。
综合上述，该改进型算法可以运用于GPS导航仪上进行的路径规划并给出最短路径。
5 结论
本文的研究通过图论路网建模、算法分析、应用程序编写、算法性能检验等工作。根据深圳市的城市形态环境建立图论模型，找到了GPS导航仪为用户进行路径规划是路径规划不准确的原因，并提出了了改进方案，即“基于特殊数据储存方式的路径规划算法改进方案”，此方案使得经典路径规划算法的时间复杂度从原来的O（N2）大幅下降为O（NLogN），使算法在GPS导航仪上运行的平均最长等待时间不超过6秒并得出最短路径，完全满足了用户体验，可以用于改进GPS导航仪。
本文对GPS存在的问题进行了一些探讨。但是，由于水平限制，本研究存在一些问题。研究仅考虑了Dijkstra算法一种情况，未针对其他最短路径算法如SPFA，Floyd进行研究比较。同时，也未对更多的优化方法进行讨论，未对数据结构的改进进行讨论，这些问题希望可以在以后的学习中可以做进一步的研究。
参考文献
[1]中国社会科学院城市发展与环境研究中心，中国城市发展报告[M].社会科学文献出版社，2009.
[2]李罗明，武汉市交通拥堵问题研究[D].武汉理工大学硕士学位论文，2005.
[3]彭飞、柳重堪、张其善，车辆定位与导航系统中的快速路径规划算法[J].北京航空航天大学学报，2002.
[4]毕军、付梦印、周培德，一种适于车辆导航系统的快速路径规划算法[J].北京理工大学学报，2002.
关键词：新型城镇化；路径；江都区
中图分类号：TU984文献标识码： A
1引言
随着我国经济建设的快速发展，我国的城镇化率不断提高。作为国家经济发展先进地区的长三角，更是处于城镇化转型升级的重要阶段。新型城镇化是我国经济得以长足健康发展的的必由之路和强大引擎，是我国产业结构升级转型的重要抓手，是解决农业农村农民问题的重要途径，更是促进社会全面进步的必然要求。[1]
2新型城镇化研究背景
2.1世界城镇化发展的趋势
随着全球经济的进一步发展，各个国家面对的经济情况和社会情况也越来越复杂多变。同时，伴随着全球经济格局的整合和重组，对各国的经济社会发展都提出了新的要求。特别是20世纪80年代后，发展中国家的城市化增长尤其迅速。随着信息和知识的发展，城市化的发展开始进入以人为中心，呈现出分散化与集聚化并存的局面。同时由单纯的生产性转向生产、生活和生态和谐共存的局面。城市与乡村、人与环境进入了共生、共享和共荣的状态。[2]
2.2新型城镇化是我国经济发展的必然选择
我国已经进入全面建设小康社会的决定性阶段。在这样的背景下，我国的城镇化转型升级显得尤为迫切。我国城镇化的发展过程具有农业经济向工业经济、计划经济向市场经济转型的“双重转型”背景；表现为人口城市化(异地转移)和农村城镇化(就地转移)“双熏城镇化方向”；是在“政府推动”和“市场拉动”双重动力驱动下的城镇化；是在制度变迁方面自上而下的城镇化和自下而上的城镇化的“双重发展模式”。[3]认为如何在此关键时期把握机遇，妥善地应对城镇化过程中的风险和挑战，走出具有中国特色的城镇化道路，是需要城市规划专业深入去研究和探索的。
本文将结合扬州市江都区的新型城镇化规划研究，对如何在规划方面去引导控制新型城镇化的有序发展提出一些观点建议。
3研究区域概况
扬州市江都区位于长三角腹地 ，交通优势明显，是重要的区域交通枢纽城市。位于扬州泰州大都市圈连绵区。是扬州市的副城，承担了扬州发展的一部分城市职能，是扬州重要船舶产业及港口物流基地。2012年GDP达到639.1亿元。江都区2012年的总人口为106.9万人，其中城镇人口和乡村人口的比例基本已达到1:1,2012年的城镇化率达到52.2%。根据江都区总体规划，预计在2030年要达到80%的城镇化率。
江苏省的城镇化率已经超过60%，苏南城镇化率超过70%，南京城镇化率80.23%江都区的城镇化率为52.2%，。相较于其他地区，如下图所示，江都区的城镇化率属于低水平。此外，江都区各个城镇的城镇化水平不平衡。
表1：江都区人口与城镇化率
江都总人口（万） 城镇人口（万） 乡村人口（万） 城镇化率（%）
现状2012年 106.9 56.1 50.8 52.5
规划2020年 120 81.4 39 67.8
规划2030年 138 110 28 80
可知，江都区在未来的发展中面临的机遇与挑战并存。本文将从多个方面探讨如何更好的结合本区的情况更好的推进新型城镇化。
4江都区在城镇化进程中面临的问题
4.1土地利用呈现分散、粗放的特点
江都区2010年人均城镇建设用地为116m2，村庄建设用地为296.76m2，土地集约化空间很大。但是居民点布局分散，集约程度较低，土地利用效率不高，浪费较严重。
同时，江都区的工业虽然发展迅猛，至2012年突破了1782亿元，形成了医药化工、特钢生产加工、车船制造及配套件、机械电子四大支柱核心产业。但是现状的乡镇工业布局分散，村镇之间产业集群效益不高。园区容积率偏低，土地利用集约化程度相对较低。未来江都区在集约化利用方面仍然有较大的提升空间。
4.2产业发展与环境保护协调不足
在城镇化的过程中，应妥善处理环境与产业发展的关系，彰显生态价值。新型城镇化建设是一项非常复杂的系统工程 ，强调的是经济、社会、环境的协调发展。 这要求长三角地区小城镇在保持经济、社会健康发展的同时，必须以节能、环保、生态、和谐概念为基础 ，积极构建生态型小城镇。[4] 而目前江都区的发展，虽然已经有产业发展和生态环境相互协调的意识，但并未形成具体的规划。
4.3城镇特色有待进一步彰显
城镇职能雷同，特色不明。城镇经济结构雷同，城镇间缺乏分工协作，横向联系少，出现经济同构、相互掣肘、恶性竞争的问题，一方面恶化了相互之间的经济关系，另一方面也扭曲了各自的城镇职能，加剧了资源供给紧张和环境负荷加重的局面。[6]
江都区目前沿江开发进程不够快。沿江地区建设未成气候，基础设施相对薄弱，沿江区位优势、资源优势发挥利用不够充分，以港兴市的发展战略实施不够到位，载体作用不够突出，带动作用不够明显。各个村镇未能因势利导的利用本地资源，产业布局点分散，规模较小，许多城镇产业同构性大，主要以蔬果园、花卉、渔业和部分工业为主，未能将自身的资源优势加以发掘，因地制宜的发展特色产业。
4.4城镇规模偏小，结构欠佳 城镇化质量不高
江都区现状的城镇规模偏小，结构欠佳。镇区人口规模和用地规模普遍偏小，部分镇建成区面积不足1平方公里，城镇体系缺少中间层次的城镇群，5万人以上的城镇廖廖无几。如图8所示，除仙女镇、大桥镇外，其他各个乡镇的镇域人口和镇区人口普遍较低。
此外，“旧城镇、旧街区、城中村”等问题广泛存在。江都区人均城镇建设用地达到116m2。农村人均建设用地高达297m2，各镇之间差异明显，区域经济发展不均衡。各镇人均GDP差距大：水平最高的仙女镇达到168830元，是最低水平镇的4.4倍。
5江都区新型城镇化的规划路径探索
图1：江都区产业分布图
为了把江都区打造成为长三角重要的城乡统筹和新型城镇化示范区，江都区通过从体制机制创新、城市功能系统升级、产业升级、设施支撑提升、生态可持续及多层次统筹发展等方面探索了江都区的新型城镇化路径。包括：
5.1引导土地利用转型：从粗放经营到“产城融合”
产业结构方面， 江都区现状的产业存在效率地，转型慢和三产内部结构不优化等问题，调整现状产业发展的方向为以都市服务型、消费型为主导，乡村生态生活环境为主导。都市区强化服务乡村的支撑产业，反哺广大乡村区域。乡村发展高效集约、现代综合、生态环保型产业。对工业整合现有工业布局体系，集中发展发展具有特色化、规模化，现代高效的农业，第三产业则采取：①强化城市产业体系，大力发展服务业； ②邵伯湖和渌洋湖水乡风貌旅游度假区；③水产养殖加工基地与水乡风貌旅游区结合中部扬泰机场；④打造空港物流园区农业观光区、生态农业体验区、5个现代高效农业园区；⑤丁伙花木种植基地、郭村蔬果种植基地。
通过这些产业调整和促进措施，增加就业岗位。依托于不同区域现状特征与产业基础，突出优势，打造品牌。
5.2引导城镇形象转型：从千城一面到特色城镇
图2：江都区区域空间结构
在江都区新型城镇化过程中，通过构建新型中心，以提供更好的支撑条件，提高区域统筹发展动力；通过打造高品质生态文化特色城镇空间，美誉度提高，提高城镇吸引力。
在具体规划中，通过规划乡村聚落形成生态社区、特色村两级体系，以达到特色城镇建设的目标。主要措施有划定在区域中具有特定意义的保留村落，同时弱化其他村落，逐步形成向生态社区和特色村集聚的趋势。
5.3根据不同的空间特征，有针对性的制定差异化的城镇化路径
2012 年 3 月 14 日， 国务院总理答记者问时指出“制定并出台农村集体土地征收补偿条例”是本年度一项重要工作任务，这意味着农村集体土地流转将面临着更为宽松的制度环境。江都区以在本次规划中，也探索了农村集体土地流转的新方式。通过发展以多样化产业为支撑，引导农民逐步向城镇或社区集中。同时在管理上进行探索，建立、健全城镇居民的社会管理体制。在具体实施中，主要是通过统计区内各个村镇产业、经济发展和村庄形态等特征，提出基本的聚落模式，有序引导各个乡镇进行差异化的城镇化路径。结合公共服务设施的系统分级配建，和农民的再教育再培训。在精神文明方面同样提升农民的素质，达到物质和文明的同步前进。
根据区内现状村镇聚落的分布，结合规划目标，主要将聚类分为下面三种类型：
表2：带状分布型聚落
涉及城镇 吴桥，浦头，大桥，仙女，宜陵
特征 聚落规模较大、连绵成条带状
镇-村规模差异较小
城镇化目标 “离土不离乡”以周边城镇和规模较大的乡村聚落作为乡村人口集聚目的地
就业目标 现代农业和乡村旅游、乡村休闲产业相结合
公共服务 分级配置
表3：点式分布型聚落
涉及城镇： 樊川，真武，丁伙
特征 ① 聚落规模较小
② 散点式分布
城乡差异较大
城镇化目标 “离土又离乡”
主要以城市和大型城镇为乡村人口集聚目的地，少量人口向周边大型生态居住社区集中
就业目标 现代农业和乡村旅游、乡村休闲产业相结合
公共服务 分级配置
表4：块状聚集型聚落
涉及城镇 邵伯，小纪，郭村，丁沟，武坚
特征 聚落规模中等、大分散，小集聚、
城乡差异较大
城镇化目标 “离土又离乡”与“离土不离乡”相结合
主要以城市和大型城镇为乡村人口集聚目的地，部分人口向周边大型生态居住社区集中。
就业目标 现代农业和乡村旅游、乡村休闲产业相结合
公共服务 分级配置
5.4构建乡镇生态体系
经济的发展不应以牺牲生态环境为代价，应该走长久的可持续的发展路径。江都区素有“苏中粮仓”、“鱼米之乡”的美誉，区内拥有一百多万亩的耕地 ,占总面积49%，河网密布，水资源充沛，水质条件优越。江都区境内江淮冲积平原，土壤对作物适应性广；适宜种植多种粮食作物和经济作物。全市优质稻米种植面积65万亩，水产养殖面积15万亩，年产稻谷40万吨；拥有如此良好的生态环境基地，在本轮规划中，通过生态体系的建立，培育和发展生态斑块。
通过研究区分规划区内不同类型的生态基质，划分为坑塘水网农田基质、低洼平原农田基质、高沙平原农田基质、城市建设基质。在此基础上培育和发展生态斑块。主要措施包括：保护独特的自然与文化景观特征的生态斑块，包括渌洋湖生态斑块、邵伯湖生态斑块、丁伙花木种植园斑块、宜陵规模农业生态斑块、大桥镇湿地、规模农业生态斑块、武坚、小纪规模农业生态斑块。重点提升、补充建设的生态斑块，包括小纪生态核心斑块、郭村生态核心斑块、浦头、吴桥生态核心斑块，构建网络生态廊道。
表5：构建“区域―地方―场所”3个层次的城乡绿道网络体系
类型 主要绿道 衔接层次 连接节点
区域层次 由渌洋湖生态保育区向南沿运河至城镇连绵带廊道至长江夹江形成的绿道 衔接区域高速路廊道，主要道路，规模农业产业带、主要河流廊道、旅游观光区等 区域湖泊、水库等大型水面、特色生态旅游区、规模农业区等
地方层次 沿宜陵镇-樊川镇的规模农业产业带、小纪镇-吴桥镇的规模农业产业带、安大公路 主要各片区衔接次要道路、河流廊道等 片区主要的公园、开敞空间、广场等
场所层次 以乡道、村道为主的农村风貌观光运动休闲绿道 与乡道、村道、旅游观光区、规模农业产业内部道路衔接 场所内街头绿地、坑塘水面、休憩服务设施点等
通过不同层级不同层次的生态网络，保证江都区在经济建设发展的同时，生态不受破坏甚至想更好的趋势发展。使得经济与生态能协调发展。
5.5构建合理多元城乡产业发展体系，形成互助互利的产业发展模式
在江都区的产业发展中，构建都市以服务型、消费性为主导，乡村以生态生活环境为主导的模式。都市区强化服务乡村的支撑产业，反哺广大乡村区域。乡村发展高效集约、现代综合、生态环保型产业。
规划包括：邵伯湖和渌洋湖水乡风貌旅游度假、水产养殖加工基地与水乡风貌旅游区、结合中部扬泰机场，打造空港物流园区、农业观光区、生态农业体验区、5个现代高效农业园区、丁伙花木种植基地、郭村蔬果种植基地。
规划充分利用现有文化自然等资源，发展青少年启智产业发展。结合历史和教育、农业和教育、体育与教育相结合的多种教育基地。
5.6完善城乡公共交通体系
采用多种方式，构建完善的城乡联系通道，包括规划方面完善县道网布局，加强城区和产业园区、城区和乡镇、乡镇和乡镇之间等的联系，形成六纵六横五联的县路网格局，实现公交线网江都区全域覆盖。在运营管理方面，则不断的推进城乡的公交化。采用低票价和优惠免费政策、加密公交班次、加密公交站点布置。采用定线、定班、定点和定时的运营模式，使得公交的服务更加人性化。
5.7区内探索机制体制创新，提高城镇化水平和质量
在江都区内从户籍制度、土地政策和人口政策三方面进行政策创新的探索。在不放弃农民既有土地以及宅基地权益为前提下加强区内劳动力的自由流动。同时，加大城镇化保障性住房建设力度支撑，促使区内福利一体化。不断的扶持新型产业，保证区内持续的活力和竞争力。具体措施包括：
（1）加强农民权益保护。要逐步弱化农业户口和非农业户口的差异，弱化附加在户籍关系上的福利供给（住房、教育、医疗等）的差别，消除农民进城的身份障碍。
（2）促进农民城镇化就业。促进农民工创业以推动二次转移，让农民工成为小城镇建设的真正主体，同时加强农民技能培训和教育。
（3）探索土地收益分配体系。“三集中”――通过农户向社区集中、承包耕地向规模经营集中、工业企业向园区集中通过资源整合，实行节约用地、集约用地的重大措施来优化城乡布局。
（4）促进空间层级的简化和优势资源的城镇聚集和政府资源投入与合理分配。
6结语
城镇化是随着工业化而产生发展的，其发展过程同时也带来了诸多负责的问题和矛盾。我国的城镇化正处于快速发展的关键时期。在此其情况下，作为我国城镇化发展先进的长三角地区，江都区通过从政策创新、生态体系构建、管理体系优化、产业整合互助及公共交通系统构建等多个层面多个角度去共同推进新型城镇化，妥善的解决当前的问题和矛盾，走可持续发展的道路。
参考文献
[1] 国家新型城镇化规划（2014―2020年），国务院,2014
[2]当代世界城市化的特点及发展趋势，窦金波《经济研究导刊》[J]. 2010, 05
[3]辜胜阻等.中国特色城镇化道路研究 [J].中国人口・资源与环境，2009, 19(1)
[4]赵莹,长三角小城镇新型城镇化建设的理性思考[J].当代经济研究，2012,9
关键词：多目标优化；遗传算法；记忆算子；空间多自由度路径规划
中图分类号：TH 213.1 文献标识码：A
虚拟场景中起重机无碰撞吊装路径规划属于环境信息已知的全局路径规划问题.全局路径规划方法根据已获知的环境信息，对环境进行建模，为起重机规划出一条满足约束条件和目标的吊装路径.目前，国内外的研究机构、学者对吊装路径规划做出了大量的研究成果，比如Morad[1]等人基于人工智能的方法开发出一款PathFinder系统，该系统在Walkthru环境中运用主动干涉检测盒启发式搜索方法来确定真实作业空间中的最优吊装路径.Reddy[2]等人采用了C空间的原理和启发式搜索算法对起重机的无碰撞吊装路径规划过程进行研究.
起重机空间无碰撞吊装路径规划本质上是一个多性能指标的NP完全问题，这其中需要满足多个优化参数，例如最短距离、最小时间和最低耗能等，很难为其求解单一的优化解.传统路径规划方法有可视图法、栅格法和A*等启发式算法[3-5].在解决空间多自由度的路径规划问题时，上述算法的搜索速度、精度和解空间不足.近年来，遗传算法在复杂多目标优化问题中的应用已成为研究的热点，然而，多数文献仅对平面路径规划问题进行优化[6-7]，针对空间多自由度路径规划这一类多关节多约束多目标优化问题的研究较少.Kazuo Sugihara and John Smith[8]用遗传算法进行路径规划的研究具有一定的可行性和有效性，然而该文提出的路径空间栅格划分法不能解决规划速度与规划精度之间的矛盾：栅格密度小，则搜索精度差；若密度大，则数据计算量大，计算速度低.因此进化较多的搜索过程需要占据较大计算时间和存储空间.
本文将遗传算法应用于起重机多目标路径优化问题，通过分析作业场景模型和起重机位姿空间模型，将路径空间分割成多个路径平面，然后对路径平面进行栅格化处理，建立平面路径规划模型，最后应用遗传算法原理建立吊装物的路径点信息模型来确定起重机的多个吊装路径.该算法通过为场景模型添加包围盒属性来保证路径空间的搜索精度和路径的可行性，并添加新的记忆算子来提高计算效率和收敛速度，对于运用遗传算法求解空间多自由度的路径规划问题有一定的指导意义.
1路径规划模型的建立
1.1作业场景模型
全地面起重机臂架组合形式有主臂、主臂+辅助臂（副臂、塔臂或动臂）两种，吊装运动有回转、变幅和卷扬3种方式[9].根据起重机的吊装运动特点，将吊装场景划分成两个路径空间，为便于表述将其投影至XOY平面上（如图1所示）.定义r，R分别为起重机最小和最大的工作半径，吊装幅度Fd∈[r， R]，S和T分别为吊装物的起吊点和目标点，O为起重机回转中心，OS和OT分别为起始边和终止边，其中，Q1为自起始边沿逆时针（左转）方向指向终止边的扇形区域，角度范围为W1；Q2为自起始边沿顺时针方向（右转）指向终止边的扇形区域，角度范围为W2.
4结论
针对起重机空间多自由度的吊装路径规划问题，提出了一种基于多目标遗传算法的路径规划方法.该算法根据起重机吊装运动特点，设计了三维空间的路径点编码机制和适合于路径规划的具有启发作用的遗传算子，且综合考虑了起重机吊装路径的多个目标，能够同时提供不同特点的多条路径.最后通过实例验证，表明了该算法的有效性.
参考文献
[1]MORAD A A，CLEVELAND A B，BELIVEAU Y J，et al. Pathfinder： Albased path planning system[J]. Journal of Computing in Civil Engineering，1992，6（2）：114-128.
[2]REDDY H R， VARGHESE K. Automated path planning for mobile crane lifts[J]. ComputerAided Civil and Infrastructure Engineering，2002，17（6）：439-448.
[3]杨淮清，肖兴贵，姚栋. 一种基于可视图法的机器人全局路径规划算法[J]. 沈阳工业大学学报，2009，31（2）：226-229.
[4]朱磊，樊继壮，赵杰，等. 基于栅格法的矿难搜索机器人全局路径规划与局部避障[J]. 中南大学学报：自然科学版，2011，42（11）：3421-3428.
[5]贾庆轩，陈刚，孙汉旭，等. 基于A*算法的空间机械臂避障路径规划 [J]. 机械工程学报，2010，46（13）：109-115.
[6]刘旭红，张国英，刘玉树，等. 基于多目标遗传算法的路径规划[J]. 北京理工大学学报，2005，25（7）：613-616.
[7]申晓宁，郭毓，陈庆伟，等. 多目标遗传算法在机器人路径规划中的应用[J]. 南京理工大学学报，2006，30（6）：659-663.
[8]KAZUO SUGIBARA， JOHN SMITH. Genetic algorithms for adaptive motion planning of an autonomous mobile robot[C]//Computational Intelligence in Robotics and Automation：1997 IEEE International Symposium， Monterey，USA，1997.
[9]杜海岩. 工程机械概论[M]. 成都：西南交通大学出版社，2004.
动态环境移动机器人遗传算法路径规划
1绪论
移动机器人在进行工作时，往往要求根据某一准则（如路线长度最短、能量消耗最少等），在结构化空间中沿一条最优（或次优）的路径行走。为寻求这条行走路径，人们提出了路径规划的可视图法、人工势场法等。但是，可视图法搜索路径的算法复杂，效率不高；而人工势场法有可能产生极小路径点，使得机器人停滞不前，从全局上把握不了路径的质量。近来随着遗传算法等新的全局最优化方法的发展和应用，也有文献利用遗传算法来规划机器人路径。但文献所介绍的方法产生的无效路径太多，使得计算效率太低，甚至找不出最优路径。
针对这种动态环境的特点，本文从系统的观点提出一种路径规划新方法。整个系统包括两个层次，全局规划层采用改进遗传算法根据整体环境信息决策出初始全局优化路径，而局部规划层采用基于行为的方法根据局部高分辨率信息实时修正初始全局优化路径.基于行为的方法，是一种简单、实时性强的控制机器人运动的方法。该方法根据任务的不同将机器人的运动分解为几个基本行为，通过传感器和通信信息对环境做出快速反应，以利于机器人迅速完成任务。设计了三个基本行为，即跟踪全局路径的行为、避碰的行为和目标制导的行为。其中，避碰的行为采用强化学习得到。
2模型的建立
2.1遗传算法
遗传算法是基于自然选择和遗传学原理的搜索算法。它将“适者生存”这一基本的达尔文进化理论引入串结构，并且在串之间进行有组织但又随机的信息交换。伴随着信息交换的进行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体。遗传算法的基本思想是：在问题的求解过程中，把搜索空间视为遗传空间，把问题的每一个可能解看作一个个体，个体里面有基因，所有的个体组成群体。依据某种评价标准对每一个个体进行评价，计算其适应度，并根据适应度对每一个个体进行选择、变异和交叉操作，淘汰适应度小的个体，留下适应度大的染色体，从而得到新的群体，新的群体优于旧的群体。对新的群体再施加自然选择法则，结果一代胜过一代，直到达到预定的优化标准。以上就是遗传算法的基本原理。
2.2路径规划建模
本文在对移动机器人路径规划时采用栅格法来表示，即用大小相同的栅格来划分机器人的工作空间。首先，移动机器人通过势场生成一个障碍物地图，然后机器人利用障碍物地图来规划一条安全的路径，该路径是使机器人由起点运动到终点的一条无碰路径。
障碍物的位置一旦被传感系统如视觉传感器探测到，则赋给与那些位置相对应的栅格一定的初始值，并根据规定的减函数向相邻栅格传播，这样就得到一张障碍物地图。在地图中，用“0”来代表开放的空间，“1”代表障碍物或墙壁，“8”为起始点，“5”为出口。整数表示的地图数组如图1所示：
（1）将环境空间划分为独立的栅格空间；
（2）首先将环境空间的每个栅格初始化为0；
（3）探测障碍物所占据的部分栅格；
（4）把1赋给障碍物所占据的栅格；
3基于遗传算法的路径规划实现
3.1问题定义
3.2算法参数选择
在遗传算法中，个体的长度、种群的长度、遗传操作概率等都是影响算法优化性能和效率的因素之一。交叉概率（CROSSOVER_RATE）用于控制交叉操作的频率。概率太大时，种群中串的更新很快，进而会使高适应度的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前。变异概率（MUTATION_RATE）是加大种群多样性的重要因素。概率太小则不会产生新的个体；概率太大则使遗传算法成为随机搜索。
3.3算法的终止条件
本文使用种群长度作为终止条件。被优选后的群体储存在m_vecGenomes种群中，用NewBabies记录群体的长度，如果其长度不小于给定的种群长度m_iPopSize，则退出循环，否则继续循环。
4动态环境仿真试验
图3所示为机器人向出口运动过程中，出现运动障碍物的情况下，利用算法不断寻找到通向出口的路径。图中分别作出最优个体的路径规划图和种群适应值及最优路径仿真过程图。需要说明的是，路径规划是寻找满足安全的最短路径，这是求最小值的问题，因此以下各图中适应值（或称路径代价）越小，则该路径越好。随着进化代数的增加，适应度值逐渐减少，路径长度也减少。参数同前三次试验的结果作比较可知，迭代次数同适应度成正比，同路径长度成反比。可以看出，本文所进行的仿真试验能够成功地利用遗传算法找到了近似最优路径，并且具有很强的实施性、实用性。
