1.3　国内外路径规划技术的研究现状

1.3.1　环境建模技术研究进展

水下钴结壳机器人属于自主式机器人的一种。近年来，有关自主车辆导航研究越来越多，多数集中在室内或者结构化的环境中，环境建模相对简单。国内外有关室外的环境建模研究主要集中在无人驾驶车辆和星球车辆（月球车、火星车等）上。

利用外部环境的三维地形信息，评估地形的可通行性，判别不可通行区域是自主车导航的核心问题之一，也是机器人环境建模的核心内容。因此，通过对运用于Rocky7上的路径规划方法进行总结，S.L.Laubach[38]提到：地形的通行性问题是未来路径规划的关键，即规划车体的运动路径应该更好地结合地形信息。

目前地形通行性方面的研究主要集中在运用人工智能的统计学和模糊方法分析地形物理信息，国际上卡耐基梅隆大学（CMU）与美国喷气动力试验室（JPL）的研究者分别提出了环境建模的两种解决方案。

CMU的方法是沿着候选路径计算地形通行性，候选路径根据车体舵轮的转向角度生成。通行性指数通过路径上单个栅格的相关权值的累加而得到。R.Simmons[39]、S.Singh[40]使用的相关参数是横滚角（roll）、俯仰角（pitch）和粗糙度（roughness）。首先将地形分成小块区域，然后利用最小二乘法将区域拟合到一个平面上，俯仰角和横滚角的计算是通过此平面的两种角度来表示该区域的俯仰角和横滚角，拟合平面和实际区域表面的残差表示粗糙度。

JPL中比较有代表性的方法是基于语言描述和模糊逻辑的方法。H.Seraji[41，42]将地形柔软度、坡度、地形粗糙度等地表信息通过语言描述进行模糊分类，之后计算地形通行性指数，最后通过地形的通行性指数（代表不同地形中机器人的通行能力）指导机器人路径规划。通行性指数依据传感器测量范围的不同分为区域、局部和全局指数。区域通行性指数是通过地形粗糙度和坡度（slope）进行模糊分类而得到；局部通行性指数是由对地形表面柔软度（surface softness）和局部障碍物进行模糊分类而得到。如图1-5是H.Seraji获得的火星环境通行性地图，图中不同颜色代表区域的不同通行性。

此外，还有一些基于地形参数的通行性计算方法，如A.Shirkhodaie[43]通过纹理设计，神经网络分类器、规则分类器和模糊分类器分辨地形的种类并确定其可通行性。D.Gennery[44]使用平滑插值方法计算高度、坡度（smoothed and interpolated height），得到地形的通行性指数。

在国内，徐璐[45]提出一种基于障碍物分类的通行性计算方法，首先计算出障碍物的高度变化，面积等信息，然后对障碍物进行二次分类，分离出可以克服的障碍（可越过的沟和可攀越的土丘等），得到着色障碍分类图。在以上过程的同时将地形栅格化，计算每一栅格的平均坡度等参数，得到通行性指数，作为机器人三维路径规划的评价函数。

史美萍[46]提出了一种新的多约束环境建模方法——MCWM方法，它综合考虑了运动的平稳性、系统的不确定性、人机协同性和月面地形的可通行性等四个因素，最后产生支持路径规划的综合代价地图——MCWM模型（图1-6），达到了地表通行性的合理和鲁棒性建模。

刘华军[47]提出了越野高程地形的相对不变性概念，并利用越野地形的这种性质，提取出了在地形具有的相对不变特征，如地形粗糙度等，利用基于模糊规则的方法，评估各特征对地形的可通行性。最后通过自主车越野导航实验表明算法能满足自主车越野导航的需要，稳定有效。

但总的来说，以上通过通行性研究确立环境建模的方法，适合于在环境中寻找通行性最优的行走路径，而机器人则需要对全矿区的遍历式采集；而且以上方法并没有针对性的考虑环境中不同底质对地形通行性的影响，对于采矿区这种含有三种不同类型底质的特殊环境，不能直接应用。因此，本书提出了针对水下不同底质进行环境建模的方法。

1.3.2　遍历路径规划技术的研究进展

关于机器人遍历（覆盖）路径规划问题，Sylvia[48]认为，覆盖是机器人必须遍访工作环境中的可达表面。Zheng[49]定义已知环境信息情况下机器人覆盖问题为：遍访已知环境的所有位置，同时完成某项任务。Enrique等[50]认为，覆盖路径必须尽可能短，重复路径尽可能避免；覆盖问题转化为两个子问题：首先是寻找能遍历简单区域的运动方式，其次是寻找一条连接区域的可靠途径，用来保证全区域覆盖。

在国外，关于覆盖算法，Howie[51]首先研究基于生成树的机器人覆盖算法，文献[52]对算法本身作了较详细的总结。而覆盖算法在水下机器人上的应用方面，文献[53]采用水下机器人覆盖技术对水下进行地形测绘。但现有的覆盖技术大部分局限于二维环境中，仅Ercan等在文献[54]中提到简单三维物件表面的覆盖问题，绝大多数覆盖问题尚未涉及三维地形的覆盖。

Grossberg[55]根据生物学家Huxley和Hodgkin提出的描述细胞膜的动力学模型（H-H模型）和神经细胞膜的电路模型[56]，提出了神经动力学网络模型。Yang和Meng又将这种基于生物激励的神经网络应用到机器人的环境建模和遍历路径规划[57]。将区域划分成的栅格作为一个神经元，通过生物激励神经网络模型中的动力学激励公式确定栅格的激励值大小。这种方法考虑转弯最少，遍历最短的路径，能避开障碍物和跳出死角，达到了完全遍历，不足是重复率较高。通过启发式模板和生物激励结合的方法能够得到较好的改善性能指标。

Carvalho[58]等人在已知环境地图的前提下，在真实机器人平台上进行了基于行为模板的遍历路径规划研究，把机器人行为划分成多种固定的模板，依据实际位置选择适合模板，最后实现规划路径的遍历。该方法需要预先获知环境地图，通过让机器人首先沿着区域边界行走完成对环境地图的总体构建，然后再根据实时环境信息依靠合适模板进行启发式行走，缺点是此法的实现较困难。

Quine和McCluskey提出Q-M法，该方法开始是用于电路上寻找最大素蕴含的方法。该方法通过提取给定环境中所有基本矩形自由区域，并用这些自由区域作为节点构造连通图，完成对区域的覆盖。

在国内研究中，Qiu等[59]提出了利用生物激励神经网络对环境进行建模，计算环境信息，并采用滚动规划技术和启发式搜索算法进行路径规划。

蔡自兴[60]认为，机器人覆盖就是利用移动机器人，遍历目标环境区，尽可能地满足重复路径少、时间短和未遍历区域小的优化目标。

李开生[61]首先提出遍历规划的数学描述和概念，包括全遍历规划的设计方法，设计了常用的几个性能评价函数；并且在此基础上，给出了基本遍历运动序列的全遍历规划器，该规划器是基于综合性能评价指标的。

张赤斌[62]采用全局运动规划和局部区域遍历相结合的方法。该方法首先定义了遍历空间中子区域间的综合连通距离，再由一个完全赋权连通矩阵表示整个遍历空间中的连通关系。采用群智能算法优化子空间遍历距离，得到最短全局遍历顺序，证明了算法的有效性。

谢斌[63]提出了基于改进的Node Counting在线图搜索方法。算法通过扩大遍历时的局部搜索空间，使移动机器人工作空间的搜索加快。设计仿真系统主要模块，并编制相应的仿真程序。该算法具有良好的遍历性能，同时在机器人被“绑架”或信息素被破坏的情况下，算法仍具有较好的鲁棒性。

邱雪娜[64，65]提出了改进的生物激励神经网络法（图1-7）。该方法集成了模板模型，启发式搜索和障碍物逼近算法；移动机器人的工作环境建模使用“分流合作—竞争反馈”网络的生物激励神经网络；能够实现不规则形状障碍物周边区域的遍历。

在我国钴结壳调查区内主要分布的是相对平坦地形，机器人的遍历路径设计，是在满足最大覆盖率、最小重复率和最小消耗的前提下，一种综合的优化设计。在采矿遍历路径规划中，针对平坦地形环境，设计综合评价准则，并以此指导遍历路径规划，是本书研究的特点。

1.3.3　全局静态规划技术的研究进展

静态路径规划是在全局环境信息已知的情况下，机器人按照某种优化准则，在环境中从一点行走到的另一点的可行通路。

在国外研究方面，S.M.LaValle提出快速随机搜索树算法[66]（RRT）算法，该算法是一种增量式前向搜索算法。搜索树构造阶段，从初始位姿点出发构造搜索树，在位姿空间中随机选择一个位姿点，遍历搜索树，找到距离最近的节点，后在控制输入集里选择一个控制输入作用在该节点上，机器人沿着节点间连线，依照状态转换方程产生满足约束的候选路径集，到达一个新状态集，依据节点间距离，选择距离最近的控制输入作为最佳控制输入。并且依次产生新状态，直到到达目标状态，完成搜索树构造。算法从目标状态点出发，找寻父节点，直至到达状态起始点，就规划出满足全局约束的路径。

Barraquand和Latombe设计了随机路径规划算法[67]（RPP）。该算法以人工势场法为基础，通过执行随机步骤使其脱离局部极值。RPP定义启发式势函数和三种模式：DESCEND，ESCAPE和BACKTRACK。初始时刻，规划器在DESCEND模式下，从起始节点开始依照梯度下降的原则产生新的节点。在该节点邻域内，且使得势函数最小方向上产生一个新节点。如果陷入局部极值，规划器转入ESCAPE模式，执行一个随机步骤创建新节点。如果在ESCAPE模式中，随机产生新节点失败，规划器转入BACKTRACK模式。在此模式下，从上次产生的新节点起始节点间随机选择一个节点，从而完成完整路径规划。

Orlin.J[68]应用经典最短路径搜索算法Dijkstra算法解决静态路径规划问题。该算法可在显式图中找到从目标节点到图中任意节点的最短路径，或从起始节点到任意节点的最短路径。若该算法在到达目标节点时结束，那么一定可以找到一条从起始节点到目标节点的最短路径。算法复杂度是O（n2）。

Papadatos.A[69]解决静态路径规划问题时使用A*算法，该算法是一种隐式图启发式搜索算法，其距离函数的定义具有启发性。其距离函数的定义为f（c）=g（c）+h（c），即某个节点c处的距离f（c）定义为从起点至c的距离g（c），与从c到目标点距离的估计h（c）之和。启发式估计是真实路径费用的下界，只要h（c）存在，A*算法一定可以得到一条最优路径。

Stentz发展了D*算法[70]，D*算法还可在动态图上搜索到最短路径。该算法能够在搜索动态图目标节点的过程中处理变弧的代价，假设弧的代价在遇到障碍时可能会发生变化。D*在静态图中的搜索情况将转化为Dijkstra算法，时间复杂度为O（n2）。D*算法代价参数可以随搜索过程改变的情况下，它可以处理任意的路径优化问题；当参数的变更发生在起始点附近时，算法效率最高。

而在国内，张钹[71]提出用状态空间的连通性分析解决路径规划问题，它根据环境和机器人的几何特点，将空间划分成若干拓扑一致的子区域，根据彼此的连通性建立拓扑网，在图中搜索一条拓扑路径。这种方法的优点是利用拓扑特征缩小了搜索空间，算法复杂性仅依赖于障碍物数目，理论上是完备的。

吴峰光[72]采用移动线和扫描线相结合的方法构造切线图。采用移动线算法检测障碍物顶点之间的公切线，然后利用扫描线算法测试公切线与障碍物之间交叉点的存在性，如果存在，则滤除这些公切线，那么剩下的公切线构成的图被称为切线图。构造切线图在的时间复杂度为O（[M+R]N+M2lgM），式中N为障碍物顶点数，M是N点构成的凸曲线的条数，R为开凸曲线的滚动数。最终，搜索最优路径问题转化为从起点到终点，经过障碍物切线的最短距离问题。

朱庆保[73]描述了机器人静态路径规划的仿生算法，该算法利用栅格法对环境进行建模，并模拟蚂蚁觅食行为，最终由多只蚂蚁完成最优路径搜索。采用了目标导引函数、最近邻居策略和概率搜索策略，使搜索过程迅速高效。最后通过仿真表明：即使在非常复杂的障碍物环境中，算法也能迅速规划出最优路径。

而在水下自主车静态路径规划方面，为了提高机器人的集矿效率，达到最优路径规划的目标，王随平[74]建立了从起始点到终点，自主车耗能最少、耗时最短的多目标优化问题模型；利用对子目标加权将单目标优化问题取代多目标优化；采用了将蚁群算法与遗传算法相融合算法——GAAA算法，对机器人作业路径进行了寻优控制；并通过仿真验证了算法用于机器人路径寻优是有效的和可行的，并且规划路径的效果较蚂蚁系统更好（图1-8，图1-9）。

机器人进行全局路径规划的基础是水下三维环境模型，在每个已获知精确环境信息的滚动窗口内，机器人利用在环境模型中规划出的路径逐步向目标点方向行走采集。本书采用群智能算法[75～80]规划滚动窗口内的静态路径，并对算法进行改进，提高算法实时性；并按照不同的原则设置算法启发函数和适应度函数，以满足机器人运行中存在的采集路径和连接路径的不同要求。

1.3.4　动态路径规划技术的研究进展

动态路径规划的前提是机器人无法获得先验的全局环境信息，只能依靠当前获得的信息，以在线的形式规划机器人的路径。

关于动态路径规划的方法研究，Gerke M[81]使用遗传算法（Genetic Algorithms）解决机器人动态路径规划问题。遗传算法利用简单的繁殖机制和编码技术来描述复杂的现象，由于作为并行算法其隐性并行性适用于全局搜索，而且算法本身的优化计算和整体搜索策略不依赖于梯度信息，所以解决了其他一些算法难以解决的问题。因此，在移动机器人局部路径规划中有着广泛的应用。遗传算法是一种多点搜索算法，具备固有的并行性，不必要求导数存在、连续性、单峰等假设，不受搜索空间限制性假设的约束，因此与传统优化算法相比具备突出的优点。

Nelson H C[82]使用模糊逻辑算法（Fuzzy Logic Algorithm）。模糊逻辑是基于实时传感信息的一种在线规划方法，它利用包含模糊概念的参照物的位置和运动信息，动态环境模型构造二维隶属度函数；采用反射式导航机制，将当前环境障碍信息输入模糊推理机，把机器人期望转向角和速度作为推理机输出；通过模糊评价综合考察各个方向，获得搜索结果。该方法运用近似自然语言方式，在包含动态障碍物的局部环境中能有效地实现机器人避碰导航；可以处理数据的非精确性和不确定性，克服误差和噪声，实现输入输出之间的映射关系。

Jang D[83]采用神经网络（Artificial Neural Net Work）算法规划机器人在线路径。基本原理是将传感器测得的障碍物信息等作为神经网络的输入层信息，经过神经网络的并行处理；由多个选定位姿下的数据构成原始样本集，经过剔除冲突或重复样本等处理，得到最终样本集；再由输出层输出由人给定场合下期望速度和转向角，引导机器人导航避障，最后到达目的地。作为一个高度并行的分布式系统，神经网络可以实时解决机器人在线路径规划问题。

模拟退火算法（Simulated Annealing）[84]是一种基于蒙特卡罗（Monte Carlo）迭代求解法的一种启发式随机搜索算法，Kastella K将其应用到机器人在线规划领域。算法模拟固体的退火过程，按照Metropolis准则接受新解，并以一定的概率接受恶化解，因而能够获得全局最优解。算法将搜寻空间内的每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有能量，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个邻居，然后再计算从现有位置到达邻居的概率。

Fukuda T[85]通过免疫算法（Immune algorithm）解决机器人在线规划问题。免疫算法是一种具有勘测与开采能力，随机性和确定性选择相结合的启发式随机搜索算法。它通过抗体学习抗原来完成应答，完成自适应免疫中体液免疫的简单模拟。将免疫概念在保留原算法优良特性的前提下，力图有选择、有目的地利用待求问题中的一些特征信息或知识来抑制其优化过程中出现的退化现象。

Mallot H.A[86]把基于行为的方法应用到机器人在线路径规划领域。该方法将导航问题分解为相对独立的行为单元[87]，比如跟踪、避碰、目标导向等。这些行为单元是完整的运动控制单元，由传感器和执行器所组成，具有相应的导航功能，单元之间通过相互协调来完成导航任务。

在国内，相关文献也分别就遗传算法、模糊逻辑、神经网络算法、模拟退火算法、免疫算法和基于行为的算法应用到机器人局部路径规划领域，并提出了相应的改进算法，取得了不错的研究成果[88～93]。

而在水下自主车的局部路径规划上，张菁[94]探讨了基于模糊决策的自主车实时路径规划方法。首先，通过测距声呐水下机器人对其前方180°的范围实时探测，获得环境信息，利用模糊决策进行实时路径规划，得到避障所需转动角度及方向，对于特殊情况参照连续转角记录仪来修正转角，实现特殊环境中的运动避障。

刘海滢[95]研究了水下多金属结核集矿车作业过程中的局部路径规划，旨在解决水下特殊复杂环境下集矿机自适应实时路径规划问题；利用了基于强化学习的自调整和自学习算法实现了水下集矿机的实时运动规划，实现模糊控制规则；设计了集矿机实时运动规划器操作过程、规划器结构以及相应的算法的整套实时规划方案，样机池试试验表明该方法的有效性。

王随平[96]针对水下底履带机器车复杂、未知的工作环境，提出了一种履带机器车避障和导航算法（图1-10）。该算法首先利用声呐传感器实时检测障碍物的位置，然后用D-S理论推算障碍物更精确的位置，最后运用改进人工势场法决策行走方向，规划履带机器车的实时作业路径，实现了水下履带机器车的避障和导航。仿真结果表明，该算法适应未知动态复杂环境下水下履带车的实时避障和导航。

李鹏英[97]结合水下集矿机实际作业环境，建立了基于神经网络的集矿机实时避障模型。该模型利用多传感器融合技术，将传感器采集到的环境信息数据处理后作为BP神经网络输入；把车体的速度、转向角和注视向量作为为网络输出；依据集矿机实际运行情况，综合人行走经验，设置能实现实时避障网络导师训练信号。为克服局部极小值问题，引入遗传算法对BP避障模型进行改进。仿真实验表明该算法能够通过有效训练达到预期的目标，并很大程度上克服了BP网络的局部极小问题。

席裕庚、张纯刚等[98～102]借鉴预测控制中的滚动优化原理，在全局环境信息未知或不完备的情况下，利用机器人实时探测的局部环境信息提出了基于滚动窗口法的机器人路径在线规划方法。该方法以滚动的方式进行在线规划，实现了优化与反馈的合理结合。建立了环境中存在静态和动态障碍物情况下，滚动规划的算法模型，具有良好的适应性，并分析了算法的安全性和可达性。该算法不追求全局情况未知的路径最优，而是通过滚动的方式获得局部较优路径，通过对环境的不断更新最终得到次优结果。

本书以寻找遍历路径上的对应转向点为目的，建立动态路径规划的改进滚动窗口法模型。随着机器人的不断行走，滚动窗口内的环境信息也不断获得更新，机器人通过在窗口边界上不断需找新的子目标点的方式，逐步向转向点靠近，并最终在滚动窗口内找到转向点，完成单次动态规划。机器人重复上述过程，最终达到对全区域的遍历采集。