定义
蒋新松[1]在文献中为路径规划作出了这样的定义:路径规划是自治式移动机器人的一个重要组成部分,它的任务就是在具有障碍物的环境内按照一定的评价标准,寻找一条从起始状态(包括位置和姿态)到达目标状态(包括位置和姿态)的无碰路径。障碍物在环境中的不同分布情况当然直接影响到规划的路径,而目标位置的确定则是由更高一级的任务分解模块提供的。
[1]蒋新松著.机器人学导论[M].辽宁科学技术出版社,1994:511-554
分类
路径规划分为依据已获取的全局环境信息,给机器人规划出一条从起点至终点的运动路径的全局路径规划方法(GlobalPath Planning)和侧重考虑机器人探知的当前局部环境信息,这使机器人具有较好的避碰能力的局部路径规划方法(LocalPath Planning)。
全局路径规划
全局路径规划规划方法的精确程度取决于获取环境信息的准确程度。通常可以寻找最优解,但需要预先知道准确的全局环境信息。
局部路径规划
局部规划仅依靠传感系统实时感知的信息,与全局规划方法相比,局部规划更具实时性和实用性;对动态环境具有较强适应能力;但是由于仅依靠局部信息,有时会产生局部极值点或振荡,无法保证机器人能顺利地到达目标点。
方法
传统规划算法
人工势场法
最初是1986年出Khatib提出,其基本思想是将移动机器人在环境中的运动视为一种虚拟人工受力场中的运动。该法结构简单,便于低层的实时控制,在实时避障和平滑的轨迹控制方面,得到了广泛应用,其不足在于存在局部最优解,容易产生死锁现象,因而可能使移动机器人在到达目标点之前就停留在局部最优点。
1990年,Warren[2]利用人工势场法,在二维和三维的C空间中,实现陆地移动机器人和水下机器人全局路径规划。为解决局部极小值问题,已经研究出一些改进算法,如2002年,Wang Y J[3]采用最优化理论,将人工势场和障碍约束结合起来,把路径规划问题转化为求解约束或半约束的最优化问题。张禹[4]提出的基于数字海图的水下机器人路径规划算法,克服了传统人工势场法的局部极小点,消除了路径的振荡和摇摆。焦鹏[5]设计了一种改进型虚拟势场局部规划算法,当AUV陷入局部极小时通过调用相应的逃避算法来摆脱局部极点。
[2]Warren C W.A technique for autonomous underwater vehicle route planning[J]. IEEE Journal of Oceanic Engineering,1990,15(3):P199-204
[3]Wang YJ, Lane D M, Falconer G J. Two novel approaches for an-manned underwater vehicle path planning: constrained optimization and semi infinite constrained optimization[J]. Robotica,2000,18(2):P123-144
[4]张禹,徐红丽,韦茵,封锡盛.基于数字海图的自主水下机器人路径规划研究.机器人,2006,Vol.28(No.3):321-325页
[5]焦鹏,王宏健,丁福光.基于虚拟势场理论的AUV局部路径规划方法.中国造船,2007,Vol.48(No.1):76-81页
解析法
用一个依赖于位形空间参数的不等式组来表示机器人躲避障碍物的要求。路径规划由起始位形到终止位形寻找路径时最小化一个标量函数而转化为一个数学优化问题。出于这种优化是非线性的,并有很多限制条件,故往往需要使用离散化的方法来找这个最优解。
激活值传播算法
激活值传播算法(Activity Propagation)是一种基于栅格类环境表示的并行路径规划方法。一个二维平面,划分成N*M个大小相等的正方形小方格。这些小方格称为栅格节点,每个栅格节点都对应于一个变量a,称为该栅格节点的激活值(Activity)。激活值传播算法是利用此激活值进行搜索的一种方法。
董笑菊[6]采用激活值传播算法来解决海流影响下的AUV全局路径规划问题,在算法的启发式搜索过程中,所用的评价函数同时考虑能量和路径长度两个因素。徐治非[7]采用激活值传播算法的基于电子海图AUV全局路径规划取得了良好的效果。
[6]Dong Xiaoju,Gu Guochang.AUV Global Path Planning Allowing for Ocean Current.Proceedings of the 3d World Congress on Intelligent Control antomation June 28-July 2,2000,Hefei,P.R.China
[7]徐治非.基于海图数据的AUV全局路径规划方法研究,哈尔滨工程大学硕士论文.2004.
搜索算法
基于微积分的搜索技术
使用由优化问题的解来满足的一组充分必要条件。包括像Newton、Fibonacci和“爬山”法等,这些技术一般只能用于解较简单的问题。
有指导的随机搜索技术
有指导的随机搜索技术以枚举技术为基础,附加些指导搜索过程的信息。其两个主要的子集是模拟退火算法(Simulated Annealing)和进化算法(Evlutinary Algorithm)。遗传算法(Genetic Algorithm)是其特例之一,90年代以后,使用有指导的随机搜索技术,尤其是遗传算法进行路径规划的文献呈逐步增多的趋势。
枚举技术
枚举技术是搜索目标函数的域空间中的每一个节点。实现简单,但需要大量的计算。常用的深度优先搜索、广度优先搜索、\(A^*\)搜索和Dijkstra搜索都是其特例。徐宏根[1]就是利用栅格建模获取环境的数据结构后,运用\(D^*\)算法搜索每个机器人的动态无碰路径。
徐宏根.多水下机器人编队协调问题研究.哈尔滨工程大学硕士论文.2005
智能规划算法
遗传算法
遗传算法(GeneticAlgorithxn,简称GA)最先是由JohnHofland于1975年提出的。从那以后,它逐渐展成为一种通过模拟自然进化过程解决最优化问题的计算模型。
目前,基于遗传算法的全局路径规划主要是针对二维平面规划问题,文献[12]利用遗传算法与激活值传播算法相结合对水面艇的全局路径规划做了研究;Zonghu Chang[13]基于前视声纳在未知环境中采集的信息,采用遗传算法进行路径规划研究,有效完成了海洋环境下动态路径规划;Kazuo Sugihara[14]在水下机器人模型SAUVIM的基础上,也提出了一种用遗传算法进行实时路径规划的方法;DongJia[15]探讨了进化算法在AUV路径规划中应用,在算法中几个种群同时进化并且互相竞争,增强了规划器的搜索能力;管乐乐[16]在标准遗传算法基础上加入新操作一复原、重构和录优,改进后的遗传算法收敛于全局,解决了局部寻优差和早熟的问题。
也有将遗传算法与已有的其他规划方法相结合,取二者之长,提高路径规划问题求解质量和效率的。例如,付岩[17]提出一种基于分层模型的遗传模拟退火算法路径规划方法,利用模拟退火算法的突跳性,解决遗传算法局部爬山能力差的问题;另外模拟退火算法的概率接受新个体的策略又保留了个体的多样性,解决了遗传算法交配时丢失最好解的问题和收敛过快的问题。
12--饶森.水面无人艇的全局路径规划技术研究.哈尔滨工程大学硕士论文.2007
13--ZongHu Chang,ZhaoDong Tang,HeGao Cai,XiaoCheng Shi.XinQian Bian.GA Path Planning for AUV to Avoid Moving Obstacles Based on Forward Looking Sonar.IEEE.2005(1):P1498-1502.
14--Kazuo Sugihara.GA-based On-line Path Planning for SAUVIM.http://www.ics.hawaii.edu/-sufihara/.
15--Dong Jia.Parallel Evolutionary Algorithms for UAV Path Planning.AIAA.2004:P30-62
16--管乐乐.某型AUV全局路径规划技术研究.哈尔滨工程大学硕士论文.2007
17--付岩.智能水下机器人全局及局部路径规划技术研究.哈尔滨工程大学硕士论文.2004
模糊逻辑算法
模糊逻辑是研究模糊命题的逻辑,它是二值逻辑的推广,是对经典的二值逻辑的模糊化。模糊逻辑方法最大的特点是参考经验,计算量不大,易做到边运动边规划,能够满足实时性要求。同时存在复杂环境中规则库构造难度大,调整和修改已构成的规则库不容易和适应能力差等缺点。
Ji Junjie[18]采用了模糊逻辑的方法,与强化学习方法相结合解决了AUV三维局部路径规划的问题;Lars Henriksen[19]将环境信息用栅格模型表示,对AUV MARTIN 采用类模糊逻辑方法寻求平滑且安全的航线;Ge Yang[20]等人采用模糊逻辑方法研究了水下机器人在海流中的局部路径规划方法;王岚[2l]采用模糊神经网络技术作局部规划中绕过障碍控制器,并用遗传算法对模糊神经网络的隶属度函数参数进行了离线优化,实时规划路径。鲁燕[22]在水下机器人实时运动规划中提出了考虑海流影响的基于模糊决策的避障规划方法,取得了良好的效果。
18--Ji Junjie, Li Bacquan, Cui Wei, Yuan Jianing. Design Three-Dimensional Local Path Planner for AUV. Proceedings of the 1999 IEEE Canadian Conference on Electrical and Computer Engineering Show Conference Center, Edmonton, Alberta, Canada May 9-121999
19--Lars Henriksen, Anders Bjerrum, Anders Ishoy. Sea Trials of MARTIN A European Survey AUV.
20--Ge Yang, Rubo Zhang, Guochang Gu, Yizun Guo, Xiaoning Feng.Research on Local Path Planning of AUV under Ocean Environment. Proceedings of the Sm World Congress on Intelligent Control and Automation, June 15-19.2004, Hangzhou.P.R. China
21--王岚.拱泥机器人的控制系统及路径规划研究.哈尔滨工程大学博士论文.2006
22--鲁燕.海流环境中水下机器人实时运动规划方法研究.哈尔滨工程大学硕士论文.2006
神经网络算法
人工神经网络开始于1952年Hodgkin和A.F.Huxley的研究,主要是模拟人脑结构的模型,将障碍物均假设为多面体,对一系列的路径点进行规划,使得整个路径的长度尽量短,同时又尽可能远离障碍物。主要优点是其隐含的并行性,具有并行处理、容错性和知识分布存储,但是较难找到三维物体的不等式表达式。
Gordon DeMuth[23]等人采用的人工神经网络方法应用于AUV的实时路径规划,取得良好效果。Xuemin Liu[24]提出了把模糊规则作为样本,对神经网络进行离线训练学习的方法,可有效缩短神经网络学习时间,并且控制器能根据变化的海洋环境作出调整。
23--Gordon DeMuth, Steve Springsteen. Obstacle Avoidance Using Neural Networks.
24--Xuemin Liu, Liang Peng, Jiawei Li, Yuru Xu. Obstacle Avoidance Using Fuzzy Neural Networks. IEEE.1998(9):P282-286.
基于群智能的方法
近几年模仿自然界中生物的一些群体行为,诞生了群智能算法,包括粒子群算法,蚁群算法等。
粒子群算法(ParticleSwannOPtimization,简称PSO)是由Eberhart博士和Kennedy博士于1995年提出的一种模拟鸟群飞行的仿生算法,有着个体数目少、计算简单、鲁棒性好等优点。
蚁群算法是上世纪90年代由意大利学者M.Dorigo,V.Mnaiezoz等人提出的,基于生物界群体启发行为的一种随机搜索寻优方法,隐含的并行性更使其具有极强的发展潜力,在解决优化组合的问题上有良好的适应性。伍祥红[25]利用蚁群优化的方法在线做路径决策操,并证明了该决策方法有效且可行,具有搜索时间短、路径优化且安全等优点。文献[26]提出一种分步路径规划方法,采用用Dijkstra算法求得链接图空间模型中的最短路径,然后用粒子群算法对此路径进行优化。文献[27]在粒子群算法中,加进了突变算子,避免算法在执行过程中陷入局部极小值。文献[28]将遗传算法的交叉操作结合到蚁群系统的路径寻优过程中,提高了蚁群系统的路径寻优能力。
25--伍祥红.基于蚁群优化的自主水下机器人路径决策方法研究.哈尔滨工程大学硕1论文.2006
26--秦元庆,孙德,宇等基于粒子样算法的移动机器人路径规划.机器人,2004,26(3):222-225页
27--Ning Li,Yuanqing Qin,Debao Sun.particle Swarm Optimization with Mutation Operator.Proeeeding of the Third lniernational Conference on Machine Learing and Cybemetics,Shanghai,China,2004:P2251-2254
28--张汝波,郭必祥,熊江.基于蚁群算法的机器人全局路径规划研究.哈尔滨工程大学学报,2004,25(6):724-727页
基于案例学习的规划方法
基于案例的学习方法(case-based learning)具有类比学习的功能,它依靠过去的经验进行学习及问题求解。优点是适合较难发现规律性的知识,因果关系难于用确切的模型或者规则来表达,而且实际的案例通常比规则提供的信息更多的领域;难点是案例库的建立以及组织、管理案例库,检索到匹配的案例,根据匹配结果的好坏去扩充案例库等,而且可能产生曲折的路径。
尚游[29]首次将基于案例的类比学习方法引入到水下机器人的全局路径规划中,构造了有学习功能的全局路径规划策略及应用框架,方法对空间维数及障碍物形状没有要求,可对海流等环境影响因素进行合适处理。
尚游,刘百顺.基于案例的自主式水下机器人全局路径规划的学习算法.哈尔滨工程大学学报,1998,Vol.19,No.5P1-10
强化学习算法
Q-学习算法是由瓦特金斯在1989年提出的类似于动态规划算法的一种方法,它提供Agent在马尔可夫环境中,利用经历的动作序列执行最优动作的一种学习能力。Q-学习算法实际是马尔可夫决策过程的一种变化形式。进一步又研究了几种改进的Q-学习算法,如Q(\(\lambda\))算法、SARSA(0)算法及其收敛性、SARSA(\(\lambda\))算法等。
刘和祥[30]综合Q-学习算法、BP神经网络法和势场法对AUV进行局部路径规划。徐莉[31]利用基于CMAC神经网络的Q-学习算法成功解决了复杂障碍物环境下基于强化学习的自主机器人的局部路径规划问题。
30--刘和祥,边信黔,李娟,王宏健.基于前视声纳信息的AUV局部路径规划研究.机器人技术,2007,243-345页
31--徐莉.Qlearning研究及其在AUV局部路径规划中的应用.哈尔滨工程大学.2004
基于规则的规划算法
规则表示法又称为产生式表式法是当前专家系统最常用的知识表示方法之一见文献,他将人类的知识表示成为IF<条件>THEN<结论>的形式,应用于路径规划首先依据条件制定好规则,最后算法实现时匹配相应的规则。褚刚秀[32]根据基于规则的路径规划算法来规划机器人接近最短的路径设计出基于规则的避碰控制系统。
褚刚秀.未知环境的基于传感器AUV三维实时路径规划.哈尔滨工程大学硕士论文.2003
免疫算法
最早的免疫学说是1897年Ehrclih提出的侧链学说,而最著名的是1973年Jeme 提出的独特型网络模型。免疫算法是一种确定性和随机性选择相结合并具有勘测与开采能力的启发式随机搜索算法,它被认为是对自适应免疫应答中体液免疫的简单模拟。
文献[33]设计了基于免疫网络理论的路径自主发现与规划算法,该算法有很强的空间搜索能力和规则的发现与再学习能力,能够较快地从机器人的环境空间到命令空间做出满意规划解集。文献[34]定义了两个新概念:趋同半径和异化半径,并在此基础上提出了基于思维进化的人工免疫算法,构建了机器人的数学模型和亲和力函数,应用于足球机器人的路径规划取得了很好的效果。
33--王孙安,庄健.移动机器人路径发现与规划的免疫算法[J].系统仿真学报,2002,14(8):995-997页
34--王立军,基于人工免疫思维进化算法的足球机器人路径规划,太原理工大学硕士论文.2006
其他新方法
Shinji[35]等人在AUV UMIHICO的基础上,提出了采用Dijkstra的算法和全顶点(all-pairs)成本算法在连通图中进行寻优(最小成本)计算,寻找最优路径的全局规划算法,以及用双向运动规划方法在全局规划的基础上进行局部路径规划的方法。
陈永明[36]通过改进的空间搜索方法,模拟传感器对障碍物的探测过程,获取障碍物的方位及位置信息,在海流环境下水下机器人全局路径规划算法。
张巧荣[37]提出了一种分层路径规划的算法,通过包含路径的长度以及能量消耗因素的评价函数,解决大范围全局路径规划问题。
Hiroshi KAWANO[38]基于东京大学研发的AUVR-One,提出采用可用于有任意形状障碍物的训练算法,在多层结构的基础上Q-Learning和教学法相结合的算法,加速学习算法的进程。
Liu Shuzhong[39]在可视图的基础上,将垂直面和水平面的规划相结合,用路径的长度作为评价函数,研究探讨了三维环境中的动态和静态路径规划方法。
35--Shinji Arinaga,Shoji Nakajima,Hideo Okabe,Akira Ono and Yutaka Kanayama.A Motion Planning Method for an AUV.IEEE.1996:P477-484
36--陈永明.智能水下机器人的实时避碰策略和全局路径规划研究.哈尔滨工程大学硕士论文.2007
37--Qiaorong Zhang,Guochang Gu.A Hierarchical Global Path Planning Approach for AUV.Roceedings of the 4h World Congress on Intelligent Contml and Automation line 10-14,2002.Shanghai,P.R.China
38--Hiroshi KAWANO,Tamaki URA.Motion Planning Algorithm for Non-Holonomic Autonomous Underwater Vehicle in Disturbance using Reinforcement Learning and Teaching Mcthod.Proccedings of the 2002IEEE International Conference on Robotics&Automation WashingtonDC.May2002.
39--Liu Shuzhong,Song Guoning.Three Dimcnsional Path Planning for AUV.IEEE.1992(6):P91-94
环境表示方法
二维情况下
环境表示问题:指环境中障碍物的表示和自由空间的表示。环境建模就是对机器人活动空间的有效描述。机器人在规划前首先要做的就是将环境的描述由外部的原始形式通过一系列处理转化为适合规划的内部的世界模型,这个过程称为环境建模,其中主要是障碍物的表示方法。合理的环境表示才能有利于规划中搜索量的减少,才能有利于时空开销的减少。不同的规划方法是基于各种不同的环境建模来进行的。
栅格法
黑格代表障碍物,在栅格数组中标为1,白格代表自由空间,标为0。最短路径是通过搜索这张栅格图得到的。栅格法的特点是简单,易于实现,可应用于不同算法,具有表示不规则障碍物的能力,适用于大规模并行处理机的实现。其缺点是表示效率不高,存在着时空开销与求解精度之间的矛盾,并且对工作区域的大小有一定的要求,如果区域太大,将使栅格的数量急剧增加,使搜索存在组合爆炸的问题。
单元树环境表示法
为了克服栅格法的缺点,设计出了单元树法,如图2.1中的(c)。这种方法把机器人工作空间划分成了几个较大的单元cell,每个单元三种情况之一:都为自由空间:都为障碍物空间;混合型空间。对于混合型空间类型的单元按照前面的方法继续进行划分,直到一个预先设定好的精度为止。四叉树法和八叉树法都属于单元树法的范畴。
该算法对各种维数的姿态空间原则上都适用,但它基本上都是盲目的、穷举的方法,对于高维的情况,计算量很大。缺点是其所找到的安全路径也比较靠近障碍物,并且计算单元之间的邻接关系时的损失较大。
多边形环境表示法
如图2.1中(d)所表示的是多边形法,多边形表示法也是常用的方法之一。该方法用多边形来逼近障碍物,并使用了很多成熟了的诸如求叉点和测距等方面的解析几何算法。还有用障碍物的边缘函数来表示环境的方法,不过应用这两种环境表示方法的路径规划算法较少。
章小兵[41]针先采用四边形轮廓图作大体上的粗略规划,随后对最优路径采用沿边的方法连接得到真实路径点集合,大大减少了路径规划的时间。
章小兵,宋爱国,唐鸿儒·基于四边形的移动机器人全局路径规划方法[J].制造业自化,2006,28(8):46-49页
Roadmap环境表示法
Roadmap法的主要思想是将自出空间连接关系转化为所谓Roadmap的线性曲线网。Roadmap作为规则化的路径集合建立起来之后,路径规划就简化为寻找Roadmap中起始点和终点之间的路线问题。用这种方法构建环境模型后适用搜索的规划方法寻路。Roadmap法又可以分为可视图法(The Visibility Graph),V氏图法(The Voronoi Diagram),其中V氏图法较多的应用于UAV火力威胁网下的路径规划中。
C空间环境表示法
C空间法(位姿空间Configuration Space)通常是按比例扩大障碍物,而把机器人缩小成一点,然后采用预先定义的凸多边形等基本形状构造自由空间来描述机器人及其周围的环境,并将自由空间表示为连通图,然后通过搜索连通图来进行路径规划。其实质是根据运动物体的大小和姿态,把周围的障碍物向外扩展一定的距离,而运动物体则缩小为一个点,得到了一个位姿空间。此方法比较灵活,即使起始点和目标点改变,也不必重构连通图。
切线图环境表示法
切线法是一种将障碍物的顶点相连,使最终围成的切线轮廓完全包裹住障碍物的几何建模方法,切线图的构造可以分解为三个子问题:一是将复杂的障碍物多边形转化成简单凸多边形;二是寻找公切线;三是将探测到的切线与障碍物进行碰撞检测。优点是能非常有效地利用稀疏环境和处理较大的规划空间,并且能够适应未知和动态的环境。
拓扑环境表示法
拓扑法基本思想是降维法,即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。步骤是:将规划空间分割成具有拓扑特征一致的子空间,根据彼此连通性建立拓扑网络,在网络上寻找起始点到目标点的拓扑路径,最终由拓扑路径求出几何路径。优点在于利用拓扑特征大大缩小了搜索空间。但在障碍物较多的情况下,空间的划分算法极其复杂。对于不太复杂的网络结构,可采用宽度优先、深度优先等简单算法,复杂网络结构可采用人工智能中的各种有效算法,如\(A^*\)算法、\(S^*\)算法等。
三维情况下
可扩展到三维情况的:
栅格环境表示法
在空间扩展到三维情况时,cell就变成了一定大小的小立方体,将一个一定大小的三维空间平均划分为若干小立方体,对于每个小立方体黑色代表障碍物,在栅格数组中标为1,白色代表自由空间,标为0,优点是简单,易于实现,具有表示不规则障碍物的能力。但是这样的空间划分将是一个数据量超大的工作非常占用系统资源,其缺点要比二维栅格更加明显。但是由于易于实现性且适用于各种传统或智能规划算法,还是较多的用于移动机器人和水下机器人的路径规划中。针对大范围环境王宏健[42]教授将三维空间简化处理为二维空间基于栅格法进行环境建模,采用遗传算法和\(A^*\)算法进行全局路径规划,取得了良好的效果。
王宏健,边信黔,唐照东等大范围环境下自主式水下潜器两种全局路径规划方法的研究[J].中国造船,2004,45(3):78-83页
八叉树环境表示法
八叉树法只在障碍物(图中的黑色区域)的边缘处,八叉树才需要分解成小的栅格,从而克服了均匀划分栅格法的缺陷。八叉树结构是2D四叉树结构在空间的扩展,用层次式的3D空间子区域划分来代替大小相等、规则排列的3D栅格,能够较好的表示三维环境。
丑强利用八叉树的理论解决了虚拟环境中的碰撞检测问题[43];Robert J.Szezerba[44]的框架子空间法,将栅格法和八叉树法相结合用于解决三维空间的路径规划问题:Kevin p[45]等人在基于四叉树的海洋环境模型下,采用\(A^*\)算法在深海环境中生成一条无碰的路径。陆军[46]利用八叉树法进行三维环境模型的建立,再利用\(A^*\)算法搜索出水下机器人在静态环境下的路径,完成了水下机器人三维路径规划仿真。高涛[47]介绍了八叉树环境模型,讨论了应用距离值传递法进行路径规划的算法,结合前述的八叉树环境模型和路径规划算法编程实现了水下机器人的三维路径规划并给出了仿真结果。
但是应用八叉树的前提是建立一个高效的构造算法,以便把三维图形图像转化成相应八叉树结构,它是一个非原始的表示方法,必须由其它表示(如3D栅格)转换生成。
43--丑强.虚拟环境中基于八叉树的碰撞检测问题,吉林大学硕士学位论文.2007
44--DannyZ. Chen, Robet J. Szezerba. Using Framed-Qctrees to Find Conditional Shortest Pathsinan Unknown 3-D Environment. IEEE Trans. Robotics and Automation. 1995, RA-4(1): P15-25
45--Kevin P. Carroll, Stephen R. McClaran, Eric L. Nelson, David M. Barnett, Donald K. Friesen, and Glen N. Williams. AUV Path Planning: An A* Approach to Path Planning with Consideration of Variable Vehicle Speeds and Multiple, Overlapping, Time-Dependent Exclusion Zones. IEEE. 1992(6): P79-84
46--陆军,华克强.水下机器人三维路径规划黑龙江自动化技术与应用
47--高涛基于八叉树模型的水下机器人的三维全局路径规划研究.哈尔滨工程大学硕士学位论文.2003.3:35-39页
切线图环境表示法
王磊[48]在读取海图数据的基础上,针对智能水下机器人建立了切线图环境模型,并利用分层思想将三维空间分成几个Level上的二维空间来考虑,在图2.4中,三维空间的规划问题就转化为Levell,Level2,Level3,Level4四个平面上的规划问题,再得到这些平面的规划结果之后,就可以将不同路径上的关键点进行两两互连,经过碰撞检测之后,留下来有效连接搭建起来的就是三维搜索空间。
王磊.海洋环境下水下机器人快速路径规划研究哈尔滨工程大学硕士论文
基于海面区域分割环境建模的规划方法
毛宇峰[49]介绍了一种基于海面区域分割环境建模的规划方法本方法,采用图搜索法实现仿真环境三维路径规划。这是一种基于四叉树的海面区域分割环境建模方法,有效的解决了海底环境的表示问题,在此基础上,通过动态扩展搜索点的思想,实现了智能水下机器人仿真海洋环境中的三维路径规划,有效解决了水下复杂多样的地形描述问题。
毛字峰,智能水下机器人路径规划技术研究,哈尔滨工程大学硕士论文.2006
其他方法
祖伟[50]研究AUV在真实海图数据环境中的三维海底地形路径规划问题,设计了优化路径的遗传算法实现方案,通过使用提出的惩罚函数及启发性知识实现三维路径规划;Joao Sequeira和Maria Isabel Ribeiro[51]提出了分两层规划的方法,并针对海流环境下的机器人能量消耗最小化得到从起点到终点的一系列中间关键点,并给出相邻关键点间的机器人位姿的变化序列;肖秦現
[52]在原有基于平面Voronoi图的路径规划基础上“将Voronoi图的概念进行了推广,又提出了“空间改进型Voronoi图”的概念,将平面无人机的的感知模型框架中推广到三维空间。
将水下机器人工作环境中的障碍物设定为台、棱柱和圆锥等规则形体,运用一种新的方法,将垂直面建模和水平面建模结合起来对水下机器人进行三维空间建模,得到的路径为垂直和水平线组成的折线[53]。
50--祖伟,郝燕玲,曾海涛基于海图数据的AUV三维海底路径规划方法研究全国博士生学术论坛(2007)
51--Joao Sequeira,Maria Isabel Ribeiro.Robot team control:A geometric approach Robotics and Autonomous Systems,Volume 53,Issue 1,October31,2005:P59-71
52--肖秦昆,高晓光.Voronoi图的无人机路径规划研究.计算机工程与应用2005(26):240-207页
53--LiuShuzhang, SongGuoning. Three dimensional PathPlaning for AUV.Autonomous Underwater Vehiele Teehnology, 1992, 12(7): 156-159 P