蚁群算法的动态路径规划学习笔记_部分动态障碍物路径规划蚁群

蚁群算法的动态路径规划学习笔记

《基于蚁群算法的动态路径规划及其在编队中的仿真应用》-赵峰，作为学习路径规划算法的参考资料，并决定从这篇论文开始着手进行路径规划及算法的学习。十分感谢本篇论文的作者，如有任何不合适的地方，请联系我，我将第一时间删除。

1、静态路径规划与动态路径规划的区别
  以区域分割为指标的动态路径规划以区域分割为指标的动态路径规划 静态路径规划是在已知的静态环境中，规划一条从起点至终点的路径。一旦在规划好的路径途中出现了未知障碍物，则放弃已规划好的路径，从起点重新规划。浪费时间，浪费资源。

  动态路径规划有效应用于未知环境中规划一条从起点至终点的路径，路径中中出现未知障碍，不必从起点重新规划，而是在障碍点处重新规划，避过障碍物后回到原来路径。通常动态路径规划是基于静态路径规划的局部路径规划，即先进行静态路径规划，无人车沿着静态路径行驶，若途中遇到位置障碍物，则在障碍物的两端重新进行规划，绕过障碍物回到原始路径中。效率高，但可能会出现不必要路径变长的情况。
2、从分析一篇论文开始

基于蚁群算法的动态路径规划及其在编队中的仿真应用-赵峰

一、核心：改进的局部信息动态路径规划算法（边走边规划）。以定半径路径规划算法为基础，使用了两种方法：（1）以区域分割为指标;（2）以时间步长为指标。

说明：运动半径：机器人每一步行走的距离。
定半径：在一次完整的路径规划过程中每一步行走的距离保持不变。
G：机器人在二维平面内的运动区域。
机器人沿栅格内的中心点行走。
二、算法过程：
1、栅格编号转换为坐标点，计算公式如下：

a:每个栅格边长；MM：横纵坐标的最大栅格数值；（xi,yi）:每个栅格的坐标；i:每个小正方形的栅格编号；mod(a,b)取余计算,即(a/b)结果取余数；ceil(a,b) ：(a/b)的结果向正方向取整。
2、边走边规划策略流程图：

流程图解释：左边为T-ACA（传统蚁群算法），会选择最大概率最大的点作为下一可行节点，未避免陷入局部最优，则调用C-ACA（被调用蚁群算法）采用轮盘赌进行概率选择，解决此问题。T-ACA与C-ACA组成LD-ACA(改进的蚁群算法)
1：在C-ACA种，如何判断该点是最优局部目标点？
答：
最优局部目标点的指标设定，有2种解决方法：（1）二次轮盘赌算法，（2）最小值选择策略算法（借鉴贪婪算法思想）。
（1）二次轮盘赌算法：

其中，i:目标点集合；allowed：排除已经走过的节点后可以前往的目标点集合；Pi:被选择概率，如下式P:第k只蚂蚁t时刻从城市i到城市j的概率。
解释过程：1、计算从当前位置到局部目标点集合中所有点的Pij；2、将每一个Pij对应生成一个随机数rand，两者比较，将pij>rand的局部目标点保留下来组成i‘，以避免陷入局部最优点，3、加入传统轮盘赌算法，选择最优的局部目标点。

其中： α：信息启发式因子，反映信息素对蚂蚁选择路径的影响力，β：期望启发式因子，反应启发式信息在指导蚁群搜索过程中的相对重要程度。

问题：此处，**轮盘赌法原理，轮盘赌算法如何用编程实现？（未解决）**在4中详细解释。
（2）最小值选择策略算法：确定全局目标点（终点），在所有可行的局部目标点中）选取距离全局目标点最近的点为最优局部目标点。（当前位置一步长的周围邻域终点）距离计算公式如下：

（ex,ey）:全局目标点的坐标；Z：局部目标点到全局目标点距离集合的最小值，取Z为所在节点位置为最优局部目标点。
2、C-ACA中哪些节点为可行节点？
答：可行节点的选取依据主要有两方面：（1）当前节点到可行节点路径上的残留信息浓度（对应信息素更新策略）。（2）可行解点的启发式信息ηij，公式如下。

ij:每个栅格中心坐标，dij:当前节点i到可行节点j之间的距离。
3、C-ACA信息素更新策略只发生在从起点到最优局部目标点的道路上，更新规则公式如下：
tao
Tij(t)：t时刻，即当前从i到j的信息素浓度；（1-R）:信息素持久性系数，R是信息素蒸发系数；▲Tij:信息素从t-1到t时刻的增加值，计算公式如下：

Q：信息素强度，正常数；Lk: 第k只蚂蚁在本次迭代中所走的路径长度长度。
4、轮盘赌策略
作用：在保证最大某节点有最大被选择概率的同时，其他效率较低概率的节点也会被相对低概率选择。
基本思想：个体被选中的概率与其计算出的概率值大小成正比。
几个概念：
各点被选择概率P(i),即为

积累概率如下，即为在[0,1]的横轴上，每个点的概率即为Pi依次写在横轴上方，轴下方将概率依次相加，为累积概率


在这里插入图片描述
具体操作：
（1）产生一个[0,1]的随机数r
（2）若r<=q1,则allowedz中，节点1被选中
（3）若qs-1<r<qs,(2<=s<=N),则在allowedz中，s被选中
参考连接https://blog.csdn.net/u010807846/article/details/51088750；
https://blog.csdn.net/zheng_zhiwei/article/details/23209729
三、动态环境变化规则（该文中）
文中设计了两种动态环境变化过程：
（1）以区域分割为指标的动态路径规划；
（2）以时间步长为指标的动态路劲规划。
1、以区域分割为指标的动态路径规划（到达了G2区域，G2区域地图变化）
思想：全局分成若干个子区域，并假设机器人坐所在位置的子区域行走时，该子区域的障碍状况不变，机器人所在子区域外的信息与机器人本次路径规划无关。子区域数目越多，机器人对动态路径障碍适应性越强。
信息获取方式，设计了两种局部信息获取方式:(1)一步范围视野（2）两步范围视野。
地图变化状态步骤：地图整体为G,分为3部分G1,G2,G3,机器人从G1起点开始行驶，在一步范围内获取障碍信息，直到到达各部分交界时，地图中的G2部分障碍物发生变化，以此类推直到G3变化。但需注意机器人行驶至环境交接区域时，由于G2部分地图的变化，由G1进入G2时的一步可能会不可行驶，因此用边界返回思想。即机器人进入G2部分时判断该步是否为可行使区域，如不可行驶则返回G1部分重新进行规划。
2、以时间步长为指标的动态路径规划(第5步走完，地图即发生变化，第5步到第6步属于连贯的正常路径寻优，不需要边界返回)
地图变化以机器人行走的步数为指标，如，机器人行走在5步内为G1,6到10步为G2，以此类推直到到达终点。
四、Matlab编程实现在下一篇中讨论。