多机路径规划学习日记

1、2018.11.13 周二 成都阴天阅读哈尔滨工程大学蒋龙杰的硕士论文多水下机器人协同信息采集路径规 划方法研究。文中简单介绍了 Dijkstra算法，这是多机路径规划的基础算法， 有必要明白该算法的思想，在百度上搜索到一篇文章每天一个算法一一最短路 径之Dijkstra0文章内容如下：今天为大家分享的算法是为解决最短路径算法的Dijkstra算法（简称D算法），这是一个解决从点到点之间最短路径的问题，看下面这张图：这里，我们想要得出节点a （节点1）到节点b （节点5）的最短路径，就是 怎么走可以使得权重值的和最小，每一条边都有一个权重。今天我们介绍的D算法就是解决这类问题的，这是一种贪心算

2、法，每次只 取权重和最小的点，通过不断加入节点，来更新源节点a到各个节点的最短路径， 直到所有节点遍历完。算法步骤：.定义，遍历过的节点集合为 S,集合U为其余节点（即未遍历）。初始 时，S只包含源点vS=v ”的距离为0U包含除v外的其他顶点，即:U=其 余顶点。若v与U中顶点u有边，则正常有权值，若u不是v的出边邻接点， 则权值为8注：这里集合S、U,是为了判断哪些节点已经遍历过， 如果U为空了，就不继续执行。.从集合U中选取一个距离v最小的顶点k,把k加入到S中。.以k为新考虑的中间点，修改v到U中各顶点的距离；若从源点v到顶 点w的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改

3、v到w的距 离值。例子：.重复步骤2、3直到所有顶点都包含在S中。上面就是D算法的处理步骤，可能大家第一次看和我一样很迷茫，不要紧， 我们结合上面这个图，使用D算法来详细介绍每个步骤：.初始化步骤用一个一维数组DIS来表示节点1到各个节点的最短路径(即权重)，没有 连线的用一表示。除此之外，为了防止节点重复计算，我们把节点分成两组，一 组已经遍历的节点集合S,另一组还没遍历集合U。初始化的时候，节点1在集 合S中。注：节点1到自己的权重为 0。.从集合U中获取离节点1最近的点(参考U在数组中的最小值，是节点 2),加入到集合S,并重新计算DIS数组。(1)节点2有到节点3和4的边，所以数组DI

4、S的3和4位置的值可能会 变动。2到3的权重为10,所以1到3的权重为17 (7+10), 17大于9,所 以不用变动。3至I 4的权重为15,所以1至I 4的权重为22 (7+15), 22小于无穷， 所以DIS4=22。(这里数组角标大家注意下，DIS4表示第四个位置，起始位置 为1)3.重复步骤2,获取U里面距离最近的点(这里为节点 3),重新计算DIS 数组。(1)节点3这里和4、6有边，所以DIS的位置4、6可能需要修改值。(节 点2在S中，只考虑U中没遍历过的节点)。(2)3到4的权重为11,所以1到4的权重为20 (9+11),小于22 (DIS4), 所以 DIS4=20。(3

5、) 3到6的权重为2,所以1到6的权重为11 (9+2),小于14 (DIS6), 所以 DIS6=11 。DIS I 口 I T 1 m 【如 18 1n4.重复步骤2,取节点6加入S,重新计算DIS节点6只有到5的边了，所以只修改DIS6的值。这里节点1到节点5的权 重为 20 （11+9）,小于无穷（DIS5）,所以 DIS5=20。5,继续重复。这次获取到节点4,从DIS数组可以知道1到4的权重（20）已经大于等于1到5的权重（20）,所以无论如何也无法从节点 4取到权重更小的路径了，（现 在已知的1到5最小距离是20，且1到4的最小距离是20，若想要找到1-4-5 的距离小于20 ,

6、则4-5的距离应该是负的，但是4-5的权值不是负的。）所以 可以舍弃（D算法是无法解决负权重问题，所以图的权重必须为正）。由于节点1到节点5没有边连接，所以权重为无穷，大于20。所以，算法的最终结果就是：节点1到节点5的最短路径是20,顺序是1-3-6-5。有了算法，必须要有代码才有说服力，这里我用 C语言实现了 D算法的代 码，大家有兴趣慢慢看，慢慢研究。我贴的是部分代码，其他不重要代码省略。预定义变量：数据初始化：门用处隆表可.点和点、之的校里I R-上1次示节幅。到3的陀中用11intI 1 C ）（ TOC o 1-5 h z EfrrINFINITEINFINITE,I -；f,rr

7、tINFINITE,INFINITE,I,，,INFINITE,I.（IMFLWITE,.,i.INFINITE,1NF1M1TEIWFXHITI：fIMFIMITE,INFINITE ,f/.t-,INFTWITE,INFINITE,1 ；咐，匕口工困加期心内节1J. .到齐T 区点的权,ROwwxLjhL 1 0 J ）int dis = （, r 1M6LINIIE r INFINITE *）;“S利U的野:合明微组衣小表不在S中r 3表？在中/初始化为M只科 附点,3隹与中】D算法具体逻辑方法：、/三城北若招呼9弓驾班H 一；、/用雪半况DHS辱亩indU.2U ;BOK( ； 0 n

8、ahnodeinumber ； J 2+二、价U4力涝者怖分邱占3廿此HHC 二Su) S6 weighc(G21 AINFINHTM二 Z/6口加、/用DJS库济a呼51,建袖率DI9 disJ+WQighrrJ2Adis【j2J( disGZJ disv:dght:s【j 2 J ;、甜柜前559C5今之2)eoHi= ;iANODplINUMBER;十二、/僚风U去dts ME行压货目处年昌d处寻亩2MV、/番小U法窿3宙4s濒假好呼/0int minnghc H INFINITE;int v H 。 inctjlutrtlOH (； j iahnode n JMBWR; jM+II wu. CJ.d i 5 3 i2018.11.14 周三成都阴天阅读文章哈尔滨工程大学徐宏根的多水下机器人编队协调问题研究。文章的主要研究内容：.首先研究了多机器人协调的环境建模与路径规划问题。本文基于栅格法对动态水下环境进行建模，并提出用 D*算法搜索出机器人在动态环境下的无碰路 径，完成机器人的路径规划。其次设计了多水下机器人的混合控制体系结构。.在多水下机器人编队问题上，本文提出了一种基于分解策略的多机器人编 队控制方法，将复杂的多机器人编队问题分解为