路径规划篇（1）

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.

路径规划篇（2）

自从有移动机器人这一概念以后，*成为长期以来研究的最热门的内容之一。移动机器人可研究的领域相对较多，其关键技术有传感器信息结合、创建地图、定位导航、路径规划等。其中核心技术之一是路径规划技术，从起始点到终点，快速在环境地图中找到最短或最佳的无碰撞路径，这是路径规划的主要任务。本文是以“探索者-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）

移动机器人路径规划就是移动机器人从初始出发点，在一个有障碍物的环境中，找到一条从初始点到目标点的无碰撞最优路径。本文在分析了目前各种路径规划方法优缺点的基础上，采用遗传算法来解决动态环境下移动机器人的路径规划问题。首先针对路径规划问题的特点，对遗传算法的各个环节进行了细致的分析，包括地图环境的建立，染色体的表示和编码、适应度函数的设计，遗传操作算子的设计，算法参数的分析和选取等。然后基于MATLAB和VC++可视化编程语言，开发了基于遗传算法的机器人的路径规划仿真系统。并在动态环境下开展了移动机器人的仿真实验，分析了实验结果。

一、遗传算法

遗传算法是基于自然选择和遗传学原理的搜索算法。它将“适者生存”这一基本的达尔文进化理论引入串结构，并且在串之间进行有组织但又随机的信息交换。伴随着信息交换的进行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体。遗传算法的基本思想是：在问题的求解过程中，把搜索空间视为遗传空间，把问题的每一个可能解看作一个个体，个体里面有基因，所有的个体组成群体。依据某种评价标准对每一个个体进行评价，计算其适应度，并根据适应度对每一个个体进行选择、变异和交叉操作，淘汰适应度小的个体，留下适应度大的染色体，从而得到新的群体，新的群体优于旧的群体。对新的群体再施加自然选择法则，结果一代胜过一代，直到达到预定的优化标准。以上就是遗传算法的基本原理。

二、移动机器人路径规划建模

本文在对移动机器人路径规划时采用栅格法来表示，即用大小相同的栅格来划分机器人的工作空间。首先，移动机器人通过势场生成一个障碍物地图，然后机器人利用障碍物地图来规划一条安全的路径，该路径是使机器人由起点运动到终点的一条无碰路径。障碍物的位置一旦被传感系统如视觉传感器探测到，则赋给与那些位置相对应的栅格一定的初始值，并根据规定的减函数向相邻栅格传播，这样就得到一张障碍物地图。在地图中，用“0”来代表开放的空间，“1”代表障碍物或墙壁，“8”为起始点，“5”为出口。整数表示的地图数组如图1所示：将环境空间划分为独立的栅格空间；首先将环境空间的每个栅格初始化为0；探测障碍物所占据的部分栅格；把1赋给障碍物所占据的栅格；在障碍物地图中，被占栅格上、下、左、右的四个相邻栅格的值neighbor通过规定的减函数decrease来计算，直到计算值小于或等于0，即neighbor [Edirection]=decrease（s，dtreclion），其中direction为0，1，2，3，表示赋值为0的左右四个相邻栅格，s为当前栅格的值，在屏幕上显示的仿真效果图如图1～2所示：

三、基于遗传算法的路径规划实现

（1）问题定义。本文研究的移动机器人运动环境为二维平面空间，环境中的静态障碍物已知，动态障碍物可以探测。这样使得问题便于着手，有利于把重点放在探索遗传算法在这类问题的实际应用上来，为今后研究三维空间内机器人的运动路径规划打下基础。本文将移动机器人视作一个质点，即不考虑机器人的尺寸。本文的目标是要在静态环境和具有少量动态障碍物出现或运动的环境里，为机器人找到一条从当前位置到目标位置的行动路线，要求这条路径满足以下条件：该路径不与任何障碍物发生冲突；该路径应尽可能短；该路径应与障碍物保持一定的安全距离；该路径应尽可能平滑。（2）遗传算子设计。优胜劣汰是设计遗传算法的基本思想，它应在选择、交叉和变异等遗传算子中得以体现，并考虑到对算法效率与性能的影响。一是赌法选择。赌法是把种群中所有个体适应度的总和比作一个轮子的圆周，每一个个体按其适应度的大小占轮子不同大小的扇区。轮子随即旋转后停在哪个扇区，对应的个体就被选中。具体步骤如下：计算每一个个体的适应度值f（xi）；累加所有个体的适应度值SUM=∑f（xi），并记录每一个个体的中间累加值S_mid；产生一个随机数N，0

三是变异算子。变异运算模拟生物在自然界中因各种偶然因素而引起的基因突变。它提供了种群中遗传基因类型的多样性，当交叉操作产生的适应度值不再进化且没有达到最优时，就意味着算法的早熟收敛。这种现象的根源在于有效基因的缺损，变异操作在一定程度上克服了这种情况，有利于增加种群的多样性。

其程序如下所示：Mutate（vector &vecBits）；{for（int curBit=0；curBit

四、路径规划仿真研究

移动机器人的动态环境路径规划是个相当困难的问题。本文所研究的动态环境限于机器人运动空间里一直存在一个或多个不断移动的障碍物。与A*算法进行比较图4（a）为A*算法的仿真结果。图4（b）为本文所用的遗传路径规划方法的仿真结果。由图4和表1数据可得，本文所研究的路径规划方法具有时间短，路程优，可视性强的特点，并能有效的实现路径规划。

本文在分析比较目前各种移动机器人路径规划算法的优缺点的基础上，对采用遗传算法解决静态和动态环境里路径规划问题的方法作了进一步的分析研究。通过在多个复杂程度不同的环境下，分别进行静态和动态情况下的仿真，仿真结果表明，该算法能够成功地规划出近似最优的路径。

参 考 文 献

[1]徐国华，谭民．移动机器人的发展现状及其趋势[J]．机器人技术与应用．2001，20（2）：45～51

[2]龚进峰．数字势场和遗传算法的机器人路径规划的方法[J]．天津大学学报．2002，10（2）：75～78

[3][美]Mat Buckland.Ai Techniques for Game Programming[J]．北京：清华大学出版社，2006

[4]赵翊捷，陈卫东．基于地图的移动机器人定位技术研究[D]．上海：上海交通大学．2002

[5]王仲民，岳宏．一种移动机器人全局路径规划新型算法[J]．机器人．2003（2）：152～155

[6]王醒策，张汝波，顾国昌．基于势场栅格法的机器人全局路径规划[J]．哈尔滨工程大学学报．2003，24（4）：170～172

路径规划篇（4）

关键词：多机器人；路径规划；强化学习；评判准则

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

路径规划篇（5）

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

1 引言

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

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

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

2 问题描述

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

3 路径规划原理

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

根据几何学园外两点到园的四条切线,其切线与两点连线夹角小的两条线段之和小于切线与两点连线夹角大的两条线段之和。如图2所示。设A和B两点坐标分别为(XA,YA)和(XB,YB),如果角α

由(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的最短路径

根据角α

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

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.

路径规划篇（6）

【Abstract】Intelligent transportation has a very wide range of applications in modern industry. Inproving route planning algorithm is one of the important ways to increase the efficiency of intelligent transportation. Based on Intelligent Transportation Project in China Robocup competition，an adaptive route planning algorithm is designed. The proposed algorithm can be applied to the intelligent classification of garbage and the automation of logistics. Compare with the exist algorithms， it can change the route and destination before the start of transportation.

【Key words】Route Planning； Adaptive； Intelligent Transportation

0 引言

智能搬运机器人主要指按设定的路线，或者使用视觉、磁线、激光导航的自动行驶的机器人。智能搬运机器人是一种自动导向车（Automated Guided Vehicle，简称AGV）[1]， 也称自动导向搬运车、自动引导搬运车。随着AGV的性能逐渐提高，智能搬运机器人被广泛用于工业、农业、医学、国防等领域[2]。路径规划是提高智能搬运机器人性能的一个重要方向[3]。

路径规划指的是根据既定的标准，如何规划一条从起始点到终点的最优路径[4]。根据环境信息的知情情况，路线规划又分为局部路径规划和全局路径规划[5-6]。本文讨论的路线规划以中国机器人大赛中的智能搬运项目为蓝本，利用颜色识别技术设计了一个自适应的路径规划算法，它可以应用于工业自动化过程中自动化物流、垃圾智能分类等领域。

1 可适应的路径规划算法

在描述本文提出的可适应的路径规划算法之前，首先介绍机器人大赛智能搬运项目的比赛规则，在1.2节将介绍根据算法设计的机器人。

1.1 路径规划规则

图1所示为中国机器人大赛智能搬运项目中的使用的场地图。图中黑字A、B、C、D、E、F、G为待搬运的色块所在地，其中A、B、C、D、E可随机放置3-5个色块，F和G点每点可随机放置不超过5个色块。O点所在为起点及终点，图中a、b、c、d、e为目标所在地，机器人要识别待搬运色块的颜色，并搬运到相应的颜色目标所在地，机器人的路径除点a、b、c、d、e外只能为图中黑色的线条。根据要求，设计的机器人必须有颜色识别、路径识别存储等功能。色块共用5种颜色：绿色、白色、红色、黑色、蓝色。本文假设图中目标点a、b、c、d、e 的颜色在搬运前是可以随机调整的，但搬运过程中是固定的，这种假设与生活中的情形比较相符。现有比赛中用到的算法都是固定了目标点的颜色、每个夹角的度数和每段路径的长度，应用性低，因此本文提出自适应的路径规划算法。

1.2 智能搬运机器人设计

本文设计的智能搬运机器人包括如下几个模块：（1）路径检测；（2）转向控制；（3）电机驱动；（4）车速检测；（5）电源管理；（6）物体检测（7）物体抓取；（8）路径规划。主控制器是51单片机，它负责接收赛道数据、赛车速度等反馈信息，并对这些信息进行恰当的处理，形成合适的控制量来对舵机与驱动电机进行控制，采用红外传感器控制小车沿着预设的轨道黑线及时调整车身姿态，使之准确、快速地跑完全程，采用四驱差速来进行原地转向与前进，使用稳压芯片7805稳定电压，用颜色传感器准确识别要抓取物块的颜色，超声波传感器定位需抓取物块，测算出距离出来以便接下来准确的搬运至目的地。实现这些功能共包含电机模块，超声波模块，颜色传感器模块，红外模块，伺服电机抓手模块，电源稳压模块。智能车的设计主要体现在电路板和机械结构上面，车的前部携带着超声波探头，与颜色传感器，用于识别物体，在颜色传感器与超声波探头下面是红外模块用来循迹，来到车身是双层的结构，在上层前端固定着有三个伺服电机控制的抓手，上层的中间是红外驱动模块，车的尾部则是放置电池及电源模块，由一根铜柱支撑着51的最小系统外加电机驱动的模块。而车的下层则是装载着四个电机驱动四个轮子。

本文设计的智能搬运机器人在行驶过程中通过不断地向地面发射红外光来进行路径检测，当红外光可遇到白色地面时发生漫发射，反射光被装在小车上的接收管接收；如果遇到黑线则红外光被吸收，则小车上的接收管接收不到信号，再通过比较器来采集高低电平，从而实现信号的检测，最终形成路径。

1.3 自适应的路径规划算法

所谓的自适应指的是没有完全掌握整个搬运路径，包括目标点a、b、c、d、e的颜色、两点间距离，弧线间角度等，这样，机器人在搬运前必须遍历路径并记录下来。a、b、c、d、e的颜色可在搬运前任意更改，在搬运当中目标颜色不变，每次搬运前机器人都需要自己检测目标点的眼神。为方便描述，假设E和F并无任何块。算法令1代表绿色，2代表白色，3代表红色，4代表黑色，5代表蓝色，用数字来记录颜色，这样如果算法涉及加权，例如aA是一段斜坡，则预算aA可能更花费时间。算法首先要判断障碍色块及目标点a、b、c、d、e的颜色。

该算法如下：

如果点E、F也存在色块，算法类似。算法可以加入权值。

2 结论

本文针对中国机器人大赛智能搬运项目的路径规划算法进行改进，提出自适应的智能路径规划算法，同时开发上位机软件和搬运部件接口。经实验证明，该算法有效可靠，有较高的效率。

【参考文献】

[1]陈书光.机器人路径规划算法探讨[J].商，2012（15）.

[2]宁志刚.一种高效的机器人路径规划算法[J].科技致富向导，2011（18）.

[3]周嵘，张志翔，翟晓晖，闵慧芹，孔庆杰.机器人室内路径规划算法的实用性研究[J].机械与电子，2016（8）.

路径规划篇（7）

中图分类号：P208 文献标识码：A 文章编号：1007-9599 （2013） 02-0000-02

1 概述

物流产业随着基础工业的不断壮大及消费市场的蓬勃发展而快速兴起。而中国的物流企业不论从技术装备还是管理水平与国外仍存在较大差距，概括起来有一下几个方面：对现代物流理念上的差距，企业规模方面的差距，社会需求方面的差距，管理体制方面的差距，专业手段方面的差距，专门人才方面的差距。据对美国物流业的统计与分析，以运输为主的物流企业年平均资产回报率为8.3%（irr），仓储为7.1%，综合服务为14.8%。在中国大部分物流企业的年平均资产回报率仅为1%。这一数据，不仅说明了中国物流效率低下，同时企业仍有很大的空间通过物流来降低成本。

如何应用先进的技术手段来提高物流业的经营效率，及时高效、经济地将商品配送到客户手中，成了大家探讨的话题，这也就是现代物流领域中备受关注的车辆路径问题（vehicle routing problem，VRP）。物流配送路径规划的优化与否，对物流配送效率、费用和服务水平影响较大。而此类问题都涉及如何处理大量的空间数据与属性数据而缩短物流时间、降低成本的问题。

地理信息系统作为不仅具有对空间和属性数据采集、处理和显示功能，而且可为系统用户进行预测，监测、规划管理和决策提供科学依据。它可以有效的结合最优路径、各种VRP模型、车辆行驶成本等要素，在可视化分析以及物流规划路径分析等方面具有不可替代的作用。GIS技术与现代物流工程技术相结合，给现代物流行业提供了巨大的发展空间，为物流企业完善管理手段、减低管理成本、提高经济效益、最终提升核心竞争力提供了机遇。

2 技术实现途径研究

物流配送车辆路线优化问题由Dautzig和Ramser于1959年首次提出，该问题一般定义为：对一系列给定的顾客（取货点或送货点），确定适当的配送车辆行驶路线，使其从配送中心出发，有序地通过它们，最后返回配送中心。并在满足一定的约束条件下（如车辆容量限制、顾客需求量、交发货时间等），达到一定的目标（如路程最短、费用最少等）。配送中心的每次配送活动通常面对多个非固定用户，并且这些用户分布在不同的地点，同时他们的配送时间和配送数量也都不尽相同。如果配送中心不合理规划车辆、货物的运输路线，常会影响了配送服务水平，还会造成运输成本的上升，因此对车辆及货物的配送路线进行规划是配送中心的一项重要工作。

车辆路线优化问题一般可根据空间特性和时间特性分为车辆路线规划问题和车辆调度问题。当不考虑时间要求，仅根据空间位置安排车辆的线路时称为车辆线路或车辆路径规划问题（VRP）。当考虑时间要求安排运输线路时称为车辆调度问题（VSP）。本文不考虑时间要求，主要针对第一类VRP问题，提出相应的技术实现方案研究。

典型的VRP具有以下特征：（1）所有车辆从仓库出发，并最终回到仓库；（2）所有车辆必须满足一定的约束；（3）多辆车负责多个客户；（4）每个客户由一辆车访问一次；（5）车辆的路线上可以取送货。目前研究的车辆路线规划的模型主要有两类，一类为网络图模型，另一类为数学模型。由于VRP难以用精确算发求解，启发式算法是求解车辆运输问题的主要方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式方法。

物流公司的业务一般具有配送范围广的特点，本文主要针对大范围跨省配送的案例进行智能路径规划，因此影响因素较多，主要包括：（1）大范围、跨省的配送交通网络图；（2）复杂的车辆运作规则，包括运行时间、运载能力、运行成本计算、驾驶员工作时间限制等；（3）复杂的道路选择优先级；（4）复杂的运输车辆优先级；（5）客户订单及运输车辆数据；（6）取货及分发过程；（7）繁杂的配送规则，如仓库、货物、客户的时间等；（8）运输车辆的重复利用，要求同一辆车在符合多个约束条件下尽可能多的参与到不同路线的配送中。

本文主要基于ArcObjects的网络分析和地图展示等组件进行二次开发，同时对其提供的车辆路径规划算法进行了拓展性研究。

3 功能模块设计方案

3.1 软件架构设计

系统建设遵循SOA架构，由数据资源层、组件层、服务层和表现层组成。数据资源层包括各种数据库、关系型数据库和空间数据库引擎ArcSDE，实现对物流业务数据的存储和管理；组件层包括接口协议、GIS组件、其他中间件；服务层实现计算功能，接受表现层的请求进行计算；表现层采用多种形式展现分析结果。

3.2 软件功能设计

本系统是物流业务管理系统的一部分，主要提供历史数据管理模块、线路优化分析模块、地图操作模块，同时提供与其他相关业务系统的扩展功能。

（1）线路优化分析模块

线路优化分析模块是系统的关键，提供两种分析结果：一种是基于AO自带的网络分析模块设计，计算分析结果；另一种是历次根据具体路况等信息的实际调度结果。

实际调度结果来自车辆GPS监控数据，并将实际调度结果作为输入，用来校正线路优化分析方法，最后生成最优路径规划。

（2）地图展示模块

地图展示模块，在配送交通网络图上展示道路基本信息、周边环境、仓库及客户地点、车辆位置信息等。同时将各种车辆路径规划分析结果以地图形式展示。基于ArcGIS提供的基础地图操作功能，实现地图缩放、浏览、鹰眼、图层控制、测量、选择、标注、信息查询等功能。

（3）历史数据管理模块

历史数据管理主要存储历史客户订单数据、实时路况信息、历史路径规划分析结果、实际运输路径等，可支持对历史数据的查询和修改。

（4）扩展功能模块

提供与其他相关业务系统、车载GPS设备、车辆监控设备等的接口，便于系统的扩展。

3.4 数据库设计

本系统中涉及的数据库主要包括元数据库、基础地理空间数据库、业务数据库、分析模型数据库、历史数据库等。

4 结束语

本文将物流车辆路径规划理论算法的研究与地理信息系统的网络分析模块相结合，经过二次开发，形成了用于实际的物流车辆路径规划信息系统。另外车辆路径规划设计约束较多，本文中不考虑时间要求，仅根据空间位置安排车辆的线路，同时不考虑装箱问题。

车辆路径规划问题是现代物流业的热点问题，但是基本停留在理论算法层面，随着技术的不断进步，必然出现考虑更多约束的先进算法，希望将这些算法真正与现代物流业结合，那将会是一个跨越式的进步。

路径规划篇（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.

作者简介

路径规划篇（9）

中图分类号：U116.2文献标识码：A

Abstract: In order to solve the vehicle routing problem and other extended problems, a modeling and solution method that is based on artificial intelligence planning of PDDL are put forward. Multifarious PDDL models of vehicle routing problem are designed and solved by using SGPlan6 and DaeYa planner. The experiment results indicate the algorithm can provide high quality scheduling scheme of vehicle routing in short time and has better extended capability.

Key words: PDDL; VRP; artificial intelligence planning; logistics

0引言

车辆路径问题（Vehicle Routing Problem，VRP）最早是由Dantzig和Ramser在1959年提出的，通过对车辆运输路线进行优化，在满足客户需求的前提下，达到诸如路程最短、成本最低、耗时最少等目的[1]。VRP自提出以来就一直是运筹学领域国内外学者研究的热点，围绕着问题建模和求解算法研究有大量的研究成果，在物流配送、交通运输等领域也获得了广泛的应用。

VRP存在多种扩展问题，而每种VRP都具有多种优化目标，国内外学者针对这些类型的VRP特点提出了一些特定的建模方法和求解算法。本文基于智能规划的PDDL（Planning Domain Definition Language）语言对VRP和扩展问题进行统一建模，再借助通用的PDDL规划器对VRP进行求解，最后给出一些改进方法以提升利用PDDL求解VRP的效率。

1VRP和扩展问题定义

基本的VRP可描述为：对一系列给定的客户（送货点或取货点），确定适当的配送车辆行驶路线，使其从车场（配送中心）出发，依次访问各客户点，最后访问车场，并在满足一定约束条件下（如车辆载货量、客户需求量）使用数目最少、车辆行驶路程或时间最短等。从定义上看，VRP是考虑多车辆的旅行商问题（TSP）。由于VRP过于简化模型，为了更贴近实际问题，在VRP基础上增加更多的特征形成了多种VRP扩展问题。

带时间窗车辆路径问题（VRPTW）在基本VRP基础上，对各客户点设置了服务时间窗，其中硬时间窗是指车辆对客户的服务必须在该窗口内完成，软时间窗是指当车辆服务超出窗口时，对目标函数给予一定惩罚。

带分割车辆路径问题（VRPSD）是指客户点的需求可以同时被几个车辆分割来服务，可以节约所需车辆数和总的行驶路程。

多车场车辆路径问题（MDVRP）扩展了基本VRP中只有一个车场的约束，多个车场分布在不同区域，但通常限制车辆必须返回出发时的车场。

开放式车辆路径问题（OVRP）中车辆在完成服务后不需要回到出发的车场，即车辆的行驶路线是开发式的，而不是闭合的。

带回程车辆路径问题（VRPB）是指车辆除了向某些客户提供配送服务外，可同时向另外一些客户提供收取货物的服务，这种VRP问题需要充分考虑到车辆载重量的限制。

带取送货车辆路径问题（VRPPD）是指车辆可同时向客户提供配送和收取货物的服务。

多车型车辆路径问题（HVRP）中所用车辆可为多种类型，每种车型的费用和载重量不同，允许限定各车型的数量。

此外，还包括多车程车辆路径问题（VRPMT）、带拖车车辆路径问题（VRPTT）、随机车辆路径问题（SVRP）、模糊车辆路径问题（FVRP）、非对称网络车辆路径问题（AVRP）等多种类型。通过对VRP增加新的属性和特征，这些新的VRP扩展问题更加符合实际需要，也逐步拓宽了VRP的研究广度和深度，但这同时也给VRP进行准确的建模和求解带来了新的挑战。基于智能规划的方法能够实现统一的VRP建模，而这种通用规划语言描述的VRP模型也为下一步统一的VRP求解奠定了基础。

2PDDL智能规划语言

智能规划是人工智能领域中应用性很强的一个研究领域，主要研究关于动作的推理，通过对预期动作的期望效果，选择和组织一组动作，其目的是尽可能好地实现一些预先给定的目标。对于一个智能规划求解系统来说，通常由三部分组成，知识表示、知识存储和知识推理，知识表示是知识推理的前提。PDDL是作为目前智能规划领域应用较多的规划语言，是完成知识表示的主要工具之一。

1998年，McDermott提出了规划领域定义语言PDDL[2]，并逐渐成为国际智能规划比赛IPC公认的标准，PDDL不仅给出了规划问题定义的语法，还从语义的角度给出了规划的定义。2002年，Fox和Long在第三届规划器比赛中提出了PDDL2.1[3]，增加了数值表达、规划尺度和持续动作等新的表达能力。PDDL2.2[4]新增了导出谓词和时间化初始文字这两种表达能力。PDDL3.0[5]在PDDL2.2的基础上进行了扩展，新增了软目标和状态路径约束，增强了对规划质量的表达。

可以将PDDL看作是一种表达动作的语法标准，每个动作的可用性和效果通过动作的前件和后件来描述，前件和后件又是利用由谓词、项和逻辑连接词组成的逻辑命题来表示。一个规划问题由一个域描述和问题描述组成，一个域描述可以对应多个问题描述，其中每个问题描述都表示不同的规划问题。

基本的VRP并不像一个通常意义上的规划问题，因为映射VRP车辆移动的PDDL动作之间只有很有效的因果关系，同时规划的多个目标之间也是一种松散关系。但随着VRP扩展问题不断引入新的属性和特征，如车辆载重能力限制、客户点上不同的需求、时间窗口的约束等，都使得车辆移动路线的选择更为复杂，在这种情况下，利用智能规划能够给求解VRP带来一定的帮助。

3PDDL建模

路径规划篇（10）

DOI：10.16640/ki.37-1222/t.2017.08.229

1 引言

伴随网络信息技术的迅猛发展，传统的基于Ethernet和TCP/IP的网络因为其设计的松散性和简单性的特征，使得其在Internet得到了规模化应用和快速发展，然而随着Internet的应用日益深入和广泛和使用规模的不断扩大，Internet的结构和功能日趋复杂，传统网络与生俱来的缺陷逐渐呈现并且爆发起来。

传统网络架构设计的数据中心网络中，由于传统网络的纯分布式控制特点，管理者无法从全局角度指定数据包的整体路径，只能通过包头标识符的方式对数据包进行有限约束或优化。SDN（Software Define Network 软件定义网络）作为一种新的网络架构概念，具有控制和转发分离实现了逻辑集中控制、开放式编程接口，从而解决传统网络中的问题，为这些路径控制不明确的问题提供了新的解决思路和方案。

本文的目的是通过在SDN新网络架构下使用OpenFlow技术来研究低负载条件的数据中心网络架构中的SDN实时路径规划问题。

2 基于SDN的实时路径规划的设计

2.1 网络拓扑

采用对称的Fat-Tree网络模型来分析问题，对称的Fat-Tree网络模型简便易行，胖树架构下，网络带宽不收敛，胖树网络则更像是真实的树，越到树根，枝干越粗，即：从叶子到树根，网络带宽不收敛，适合用来说明和解决问题。

2.2 系统设计思路

根据系统的功能性与非功能性需求分析，将本系统划分为4大功能模块：控制器交互模块、人机交互模块、路径选择模块、流量分析模块。

控制器交互模块：控制器交互模块分为三个子模块：Topo信息获取、Topo信息处理、转发控制。

人机交互模块：人机交互模块可分为图形界面设计、Topo显示、用户输入、转发路径输出共四个子模块。

路径选择模块：路径选择模块是本系统的计算核心，实现对数据包转发路径的计算。本模块可以划分为最短路径选择、最优路径选择两个子模块。

流量分析模块：流量分析模块必须具备如下两个核心功能：第一个是验证转发层是否在Ryu控制器的控制下按照路径选择模块计算出的转发路径转发数据包；第二个是监控整个Fat-Tree网络Topo中的流量。

2.3 软件体系结构

其中使用了跨平台的B/S结构，实现了PC/Mobile的平台兼容性，后台使用Flask作为Web框架，利用Nginx来进行py文件的渲染。在Ryu/Ryu和Mininet的环境下搭建拓扑，并读取数据，Application端的软件完全采用面向对象的方式来实现，极大的提高了`活性和可扩展性，为软件功能的扩充带来了方便。

2.4 应用场景介绍和特性总结

通过平台搭建和后台编程，最终实现了基于SDN的实时路径规划，总结起来应用场景有如下两个特征：

第一个是OpenFlow将控制功能从网络设备中分离出来，在网络设备上维护流表（flow table）结构，数据分组按照流表进行转发，而流表的生成、维护、配置则由中央控制器集中管理，灵活性和扩展性更高，从而加速网络部署周期。

第二个是可以通过中央控制器灵活地进行动态管理和配置，可在不影响传统网络正常流量的情况下，在现有的网络中添加规则，降低了网络复杂度。

综上所述，本文提出的实时路径规划需要加入动态路径规划（DP）模块的RYU控制器，DP模块可以读取整个网络的流量分布，并且可以根据策略对交换机进行流表配置。为交换机设置具有带宽控制的队列，每个队列可以设置经自己转发的包的最大最小带宽，以及对链路的占用时间。配置路径选择策略，控制器的DP模块根据策略建立每个交换机的流表配置，并写入交换机。

3 小结

本文分析和总结SDN相关的发展历程，分析基于SDN的实时路径规划中的各个核心问题，基于SDN的数据中心网络实现逻辑和控制分离，结合本文相关工作总结SDN有如下三个优点：1.集中高效的网络管理和运维维护；2.灵活的组网和多路径转发；3.智能虚拟机部署和迁移，解决当前数据中心网络集中自动化管理，多路径转发，绿色节能问题。

概而言之，SDN网络能力是开放和虚拟化有效实现数据中心容量提升，虚拟机智能部署和迁移，大规模虚拟租户需求，目前SDN技术还不成熟，多控制器控制机制的研究也将是下一个重要研究领域。

参考文献：

[1]范伟.软件定义网络及应用[J].成都：中国电子科技集团，2013.

[2]罗正华.可编程的网络――软件定义网络[D].成都：成都大学，2013.