连续环境下基于enhanced GA算法的多目标多机器人路径算法_基于遗传算法ga的机器人

10.1016/j.eswa.2018.08.008
https://doi.org/10.1016/j.eswa.2018.08.008

Abstract

连续环境多机器人路径规划，基于多种方法结合。
1.创新的APF在离散网格中找到起点到终点的所有可行路径。
2.EnhacedGA （EGA）改进初始路径，找到起点和终点之间最佳的路径。
文章提出的APF主要作用在于time-efficient的找到确定的一系列可行的路径，并且能够保证如果存在连通路径则一定能找到

这里说到了time-efficient和一定能找到两个概念。1.之前我的论文因为一开始就对所有的静态障碍物点进行计算，所以比较消耗时间，但是实际上只是拿周围的八个location进行计算最大的梯度，所以某种意义上来说，只是我代码的冗余计算很多导致的时间比较慢，可以说time-efficient；2.但是说实在APF都有陷入局部最优无法到达终点的可能性（我是自己调整了APF排斥力的作用范围才比较好的没有陷入局部最优），为什么文章说只要存在可行路径就可以找到呢？接下去看吧】

EGA使用了5种特定的crossover和mutaion操作来改进初始路径。并且在这篇文章当中，路径长度，光滑程度和安全性都作为多目标路径规划问题的objective function。
算法可以拓展到多移动机器人的路径规划问题中：objective function 加入一个新的损失项，即机器人之间的距离，并且EGA中加入一个新的collision removal operator 来移除可能的collision between paths。
为了检验算法的有效性，12 plannar environments with different size and complexities were examined（作者还和PSO，A*，PRM，B-RRT在12个环境里面做了比较）。结果表明EGA的表现并不会受control parameter的影响。
不仅如此，我们还将算法和其他已有算法（A* ,PRM,B-RRT和PSO）进行比较。比较实验表明，我们的算法比PSO以及确定性的算法A*以及概率算法PRM和B-RRT路径规划算法在路径长度、运行时间和成功率上 更outperforms。
最后，仿真表明在四机器人的路径规划算法上，我们的算法不仅给出来collision-free 的路径，还找到了所有机器人的近似最优解。

keywords：移动机器人；路径规划；遗传算法；APF；多机器人路径规划；多目标路径规划（Multi-objective path planning）

---

巴拉巴拉（related work）

Considering the affecting factors on PP like different kinds of robots and environments, static or dynamic obstacles, and multiple robots, finding the shortest path with the highest degree of smoothness which avoids collision with other robots and obstacles is still a challenging problem.
(Canny, 1998)说PP（path planning）问题是一个NP难问题。所以启发式或者进化算法被广泛用在寻找最优解上。GA、PSO和蚁群算法，artificial bee colony、bacterial forging optimization、shuffled frog leaping就是其中的一些。上面这些工作都将环境认为是网格地图，并且在这些grids中找到最优路径*【emmm，真的是这样嘛？表示怀疑】，比如Tuncer et al. (Tuncer & Yildirim, 2012) introduced a new mutation operator to find the path with the shortest length in a discrete gridded environment using GA。
基于网格的缺点是网格固定，PP规划出的路径被限制在这些网格中。并且A和Dijkstra算法早就在网格地图中能找到最优了。【D是A的动态变种，但是只是保证快速更改可行路径，并不能保证最优，而如果每时每刻计算A*，算力消耗巨大】
Feasible initial solutions can improve the performance of the evolutionary algorithms。之前他们都是随机初始化，初始化的路径不OK就一直初始化**（作者认为这样很蠢很没有效率，还diss了一波传统的GA的operators，作者为PP设计了自己的operators）**

【这里我想说一下俺的鄙见，俺认为GA只是一种被套上好听的Genatic字样的搜索方法，叫优化方法也行，实际上和粒子群等算法思想差不多，初始分布广，然后不断收敛找好的区域，有时候遇到局部最优是因为是概率算法，有时候没有找到就直接收敛到局部了，而搜索的方向根据不同算法，不一样，比如GA就是根据operaters，或者鸟群算法的群体速度的计算等等】

再者原来的GA在PP问题上只关注路径长度。而多目标的PP问题可以找到一个更不错的路径来适应现实中的工程需要。PP比较常用的三个 目标：1.长度2.路径平滑程度（更少的degree of direction change）3.路径安全：a path which always satisfies a predefined safety margin
(distance) with respect to obstacles
这里作者在吹嘘自己的算法比起之前的算法牛逼之处在于

1. 能够在continuous的环境下找到最优解 = =
2. innovative的APF方法用来构建一系列可行初始解(说这样对GA算法来说很高效）
3. 改进了五个operators所以把算法叫做EGA（Enhanced GA），These operators are modified such that they can minimize the path length and maximize the path smoothness at the same time while altering the solutions minimally to avoid generating infeasible paths

【什么意思，意思是不是说我的operators不像其他的变化那么大，一下子跳到其他不可行解了，所以你的operators就是类似于对初始结果进行fine-turn？】

4. 作者还提到这项PP工作的船新版本——multi-robot 的PP problem他也考虑啦：
   他在GA的objective function里面加了一个collision term，代表多机器人之间的 碰撞概率【之前不是说距离的嘛 = = 】，GA加collision-removal operator等等巴拉巴拉

【有主编怀疑了，你丫的是不是只是单纯的想用GA啊，干嘛不用用其他的进化算法或者确定的算法捏？不能APF初始+粒子群嘛 不能APF初始+蚁群算法嘛】
GA introduced in PP in 2013 by considering the linear combination of path length, smoothness, and safety as an objective function.作者觉得2013这篇文章牛逼，GA可以并行计算，并且这篇文章引入co-evolutionary mechanism，类似于每一个iteration每个机器人都规划自己的path然后会evaluated the collision between robots。不过作者说这种mechanism也有毛病，每一个slave GAs（robot的意思把）will continuously modify the paths without any knowledge about the collision between robots.【可能是之前这个工作，robots之间不知道其他人的路径，但是每个时刻会根据现在的位置进行evalute collision？这样避障效果可能比一开始大家就知道各自走哪里，然后对将要走的路径计算collision probability效果要差？】所以，作者就在这里说机器人之间的碰撞必须作为PP问题的附加约束，和obstacle一样

我滋瓷啊，当然作者也在后面MRPP中做了这样的工作，但是我还是感觉作者没说出为什么要用GA，可能要看2013的工作，看为什么要用GA把.只是有一句话我不知当说不当说：确定不是找一个已有算法APF然后fine turn说GA更好咩 = =

如果想看multi-object可以看A modified PSO-DE algorithm was introduced by Tang et al. (Tang et al., 2016) for for PP in a discrete environment with a combination of path length and safety as the objective function.作者diss说这个runtime太长，不过的确是MOPP（多目标PP）
也有人Han et al. (Han & Seo, 2017) selected selected a set of points in the obstacles’ neighborhood and used them as a guide to build an initial feasible path. Then, a modified PSO was adopted to optimize the position of the points and find the optimal piecewise linear path.They showed that the success rate of 100% could be achieved using a feasible initial path. Also, a modified operator could improve the path smoothness while the problem originally aimed at minimizing the path length.
作者在文章related work中指明2017年的时候就有人三步PP（proposed by Mac et al. (Mac et al., 2017):

1. 三角分解得到obstacle and free configuration space
2. utilizing the Dijkstra’s algorithm to find an initial collision-free path
3. adopting a new constrained multi-objective PSO for global PP.
   However, the mentioned study did not provide any comparison between the proposed algorithm and other PP algorithms in terms of objectives like path length and runtime to prove the efficiency of the introduced algorithm

Hidalgo-Paniagua et al. (Hidalgo-paniagua et al., 2016, 2015) proposed a multi-objective (path length, smoothness, and safety) Shuffled Frog-Leaping algorithm with three refiner operators to find the optimal path in a gridded environment.
【我这里是真的不明白作者为什么一直强调离散的环境，难道在计算机中仿真，连续环境不也是离散化，只不过间隔很小吗？】
Davoodi et al. (Davoodi et al., 2015) presented a multi-objective GA for PP in a continuous environment. The proposed algorithm initiates with random paths and uses simple crossover and mutation operator to generate feasible paths and optimize them. To compensate for the drawback of random initial paths and common genetic operators, new operators were introduced to correct collision with obstacles and self-intersection. However, using a multi-objective algorithm with an infeasible initial solution and several operators could result in long runtimes。
【哦吼，这几句话就很表面为什么作者要做这个工作了】
Instead of connecting the center of the grids in a discrete environment with linear segments to build a piecewise linear path,
【所以作者大概就是这个意思：你们啊 对大的地图都是连接grid中心，我不要，我直接对像素操作。那，我的工作，不也是一样的 = =，没有用grid 直接像素查看APF梯度】Song et al. proposed the application of Bezier Curve (Song &Wang, 2016) and a multimodal delayed PSO (Song et al., 2017) to build smooth paths. Using this method, the mobile robot will be able to follow a curve, instead of a piecewise linear path, which is desirable for many applications. 当然也有人A*之后再平滑的。

作者大招：

1. 你们都是grid based方法，效果受限于grid 大小。本仙子不一样，我的性能不受离散化大小的限制（略略略）
2. 你们跑evolutionary algorithm的时候啊，怎么都那么死脑筋random init 啊，给一个好的初始化咯，【那岂不是可以美名其曰，模仿学习？】大大加快收敛速度。【报告老师，有人作弊】
3. 我的GA不一样，是EGA，注意那个E！（多了五个我自己写的operators哦）
4. 我的优化目标不止一个哦，有三个哦
5. 我能MRPP

In this study, we consider the PP problem in 2-dimensional environments filled with arbitrarily-shaped static obstacles, which have no interaction (positive or negative attributes) with the free space . Moreover, the robots are considered as points, and their size will be added as a confidence radius around obstacles. Also, in the multi-robot PP case, we assume that all robots move with constant speed.

---

正片

【或许我不应该用PRM，而应该根据机器人的size对map进行grid化】
不过作者这里的工作很取巧，怎么说呢，地图的确是连续的（某种意义上），但是作者的obstacle是一个一个有R的圆的组合排列，这使得他在计算APF的时候就爽歪歪了。
all feasible paths between start and destination locations will be determined based on the pre-calculated potentials.
某种意义上，这种取巧也使得可通行区域变得很好计算。
Next, the coordinates of PBs related to each feasible initial path is coded as a solution.
Fig.2(b) shows the solution structure (chromosomes of the EGA) corresponding to the initial pat shown in Fig. 2(a).

As the initial paths obtained by the proposed APF might have a different number of PBs, the mentioned solution coding will result in an EGA with variable length chromosome
Using chromosomes with variable length could improve the flexibility of the path planner, as it can select the optimal number PBs automatically

Fig. 3(a) shows the potential map of the environment shown in Fig. 2(a)

怎么从APF中得到可行路径？
文中描述如何用三种list来构造APF，这个就不谈了，简单说就是从终点广播梯度，终点的梯度和下降的step
To determine the feasible initial paths, starting from the start location, at each iteration, an adjacent node with the highest potential should be selected.
Repeating this procedure, the potential of the path increases gradually till it meets the destination location, the point with the largest potential in the map. At this point, a feasible path between start and destination locations is found.
可以看到fig3（b）就能看到很多条根据梯度随机选择的路径。
就是因为这个原因所以说作者说
The proposed APF is guaranteed to find a feasible initial path if one exists.

个人估摸为什么说保证呢，因为你看这个形式 = = 不就是BFS嘛，全部遍历过去了，当然只要有连通区域就能保证咯 = =

EGA
我们EGA的特点是

1. 变长的基因序列
2. 五种船新的交叉变异方式
3. 改进的减少PBs数量的operators
   我们的终止搜索方式是到达固定的迭代次数

Selection Operators

we used the Roulette Wheel Selection (RWS) o select parents for crossover operator.

Crossover Operators

The first crossover operator finds a new offspring by calculating the mean of the two parents:

When the number of PBs of the two parents are not equal, first, the parent with the smaller number of PBs is selected,作为母亲
在一个父母选定了之后，另一个父母就从与他的这个母亲亲最近的另一条路径中选择，并且以一种全新的方式繁殖

Where $\alpha$ is a vector of random numbers in the range of [-1,+1].
While the first crossover operator is designed to generate shorter and smoother paths, the second crossover operator is adopted to search the environment in a random fashion and avoid premature convergence.

Mutation Operators和 Deletion Operator就不讲了，自己去论文里面看.

Objective Function

1. single objective:path length
2. multi-objetive:path length,path smoothness,path safety
   第一种single objective被作者用来和A*\PRM\B-RRT\PSO算法比较.
   第二种multi-objetive是用来在复杂的环境下规划路径的
   而且第二种捏,作者竟然是the objective function is calculated as the weighted linear sum of the three objectives
   

Multi-robot Path Planning

这里作者说如果是多个机器人,那么PP问题就变成动态的PP问题了,因为其他机器人算是动态障碍物.
【下面作者的观点我不同意】
three tasks should be handled simultaneously:
(i) the optimal path for each robot should be determined based on the position of static obstacles
【？？？动态非ROBOT的障碍物不要考虑了？】
(ii) the determined paths should be checked for possible collisions among robots, and
【yep，是这个道理，还有机器人和移动障碍物的collision 概率呢】
(iii) the optimal paths should be modified based on the collisions.

文中为了方面mobile robots with constant speed are considered.
也就是说相同时间走的路程是相同的，如何说这段时间移动的距离can be used to detect possible collisions between robots。
For PP of mobile robots with variable speed, only the distance calculation should be modified based on different speed values, and the rest of the algorithm can be applied in the same way.
在MRPP中有两个措施
The first one measures the closest distance between every two robots and increases the objective function value associated with their paths if they are closer than a predefined safety distance。The penalty of the objective function value is inversely related to the distance between two robots; if their distance is larger than the predefined safety distance, the penalty is zero, otherwise, the closer the distance, the greater the penalty.
【这 = = 不就是动态的APF，选取静态障碍物的APF+最近动态障碍物的APF】
The second mechanism modifies the paths which collide with each other.For this purpose,one of the paths is selected randomly, and one of its PBs is selected and moved in a random fashion. This modification will remove the detected collision; however, the new path should be checked for possible collision with all other paths again. If the new path is collision-free, it will be replaced by the old one. Otherwise, the collision removal process will be repeated.
【就，直说了，没看懂】

但是看图片大概能了解到就是原先得到的路径，根据其速度计算一下两个路径会不会发生碰撞，或者说计算在两个路径交叉点的位置，两个机器人的位置，然后他们的距离作为碰撞的概率可能性.