算法改进思路.md · zhouhua_8/monte-carlo-AGV

# 1 修改思路

## 1.1 修改评价函数

>  1、a=10，b=0.5，c=0.5  第一个迭代-30，二-40，三-60  距离：运算10次的时候是32，运算20次的时候是40  结论：未见明显提高

>  2、a=20,b=1,c=-1  所有用于评价的指标都做归一化（并引入了模拟策略的1）  距离：10次-40  结论：未见明显提高

>  3、修改评价参数，改成只考虑当前AGV的三个参数（总步数，完成标志，与终点距离），让与终点距离参与到评价中，看能否使得算法走得更远  距离：10次-40

>  4、修改评价参数，只考虑所有AGV与终点距离，并让当前AGV与终点距离具有最大的权值  距离：10次-30

4次实验总结：之前的评价函数忽略了当前AGV与终点距离这一项评价，导致了始终不能向着终点行进，第四次实验加大权值，可以明显看到有提高

> 5、将1，2，3，4的评价指标结合起来，设置四个评价指标，分别是当前走至终点的总步数，当前已完成的目标数，当前AGV距离目标的远近，其余所有AGV距离目标的远近。 参数设定为1，1，-1，-0.15，  距离：10次-36 20次-38  结论：虽然有提高，但并不显著，说明问题不在这上面（这个还不够细致和准确，还需要改善）

## 1.2 修改模拟策略

> - 都选择通过最佳趋向路线进行模拟   距离：10次-40  20次-30
>
> - 若无限制，初始可选择分叉有五类（停止，倒退，前进，左走，右走）
>
> - 更新限制后，对可选择分叉做筛选，如果有靠近目标点的走法将其记录，并与前一步所走策略比对，优先选择与前一步相同的走法
>
> - 若不存在靠近目标点的走法，判断造成不可靠近的原因，若原因是由AGV或者突然出现的障碍导致，则原地等待可作为候选策略，若原因是由于一直存在的障碍导致，则原地等待不可做为候选策略。

>应用跳点的蒙特卡洛树模拟策略：
>
>- 转折点设置：转折点事件包括（1）第一次发现除模拟方向和反模拟方向外的靠近目标点的走法；（2）触碰到静态障碍物（包括边界和长期堆放在仓库的物体）；（3）触碰到动态障碍物（包括AGV和随机生成的运动障碍物）

## 1.3 修改模拟迭代次数

> 1、增加模拟迭代次数 由60次变化为100次，并与（1）.2进行对比  距离：36

## 1.4 其他修改

>1、由于考虑到在扩展时很可能会发生由于其他AGV随机走，当前AGV固定而堵死的情况，这里对这种情况做出如下限制：
>
>如果是刚走了三步进入后立马堵死，认定本次行走的第三步是失败的，从第二步删除第三步，也就是永不考虑从第二步走到这个第三步的情况
>
>如果不是上述情况下发生堵死，认为是有偶然因素的，这时候不应该永不考虑某一条路不走，而是适当减少这条路的权值（这里选择的是反向传播-1价值）

# 2 天生的缺点

要说明应用蒙特卡洛算法在AGV这种全面信息里是必要的，我们就必须要对AGV的工作场景做特化，之前构思的一开始就固定位置静态障碍物就不可行，必须要是随机产生的可静态可动态的障碍物，才能够让蒙特卡洛树的一步步决策有用武之地，比如是一个人突然出现，使得AGV本来决定要前进的，现在必须针对突发情况重新进行新的蒙特卡洛树决策，想要沿引之前的决策是不可行的，因为可行区间会因为自己的停止和其他AGV的行走发生变化。而由于我没有做全局规划，也不会造成后续计算无用武之地的时间浪费。所以算法更适用于应用在随机障碍产生可能大的工作场景，算法的价值只有在避障的时候才最大限度地体现了。

# 3 文献综述

## 3.1 针对模拟策略的修改文献

>《结合跳点引导的无人机随机搜索避撞决策方法_李安醍》 - 跳点引导也就是沿着一个方向一直走，直到要转折了才停止，将当前节点沿着所有可能方向走完后的所有转折点放入open集合，并从中选取下一次模拟行走的起始点，直至选取的点是我们设置的目标点
>
>跳点搜索的适应度计算公式  F(n) = G(n) + H(n)，G(n)代表从起始点走到n来的实际代价，H(n)代表从你设定的目标点到n来的估计代价
>
>此外，文献中还为我们提供了一种动态避障之后如何再次利用蒙特卡洛树搜索的思路：首先，参考计算机网络的TCP传输窗口，设置蒙特卡洛树保存的最大运行步数为n（窗口SIZE为n），所有AGV每走出一步，窗口滑动并计算下一步放入窗口中存起来，如果发生突发障碍并且对AGV的下一步造成了影响，重计算窗口保存的第一步（假设剪枝的树可恢复，利用已遍历的条件快速完成避障路线计算），并将改变后的第一步辐射到后n-1步，重新形成新的路径规划树。
>
>如果做这样一个假设，AGV运行一个身位的时间是长于蒙特卡洛树做一次决策的时间（即决定出下一步怎么走），这样就不会存在实时性的问题。
>
>那么设置窗口也就没有必要了，可以实时的计算下一步。
>
>**算法的优势在于避障的反应时间短，算法的计算压力小（这是比起群体智能算法的优势）。**
>
>**其次，相对于贪婪这种启发算法，优势在于它进行了多次模拟，比起直接根据一个规则决定望着什么方向走，更具有反应最优路径的参考价值。**
>
>**由于算法是平行跑在每个AGV的电脑上，所以所需要的计算时间只是一个蒙特卡洛树的生成时间+从其他AGV接收它的下一步计划的时间+接收之后的剪枝操作时间，最后一个剪枝时间非常短可以忽略不计。**

>《改进平滑A*算法的多AGV路径规划_胡蔚旻，靳文舟》 -  这篇文章讲了针对李强的文章的改进，但是作者显然没有将自己的改进描述清楚

>《基于改进 A*算法在 AGV 路径规划中的应用_李强》 - 这篇文章讲了对A~算法的改进，也就是引入了筛选概念，认为相对于目标点运动的时候，有些方向是没必要去讨论的

> 《Applying hybrid Monte Carlo Tree Search methods to Risk-Aware Project Scheduling Problem》- 文章在资源约束的项目调度问题上，定义了一个新的问题：考虑风险避免的资源约束的项目调度问题，这类问题有着较大的决策空间，同时又满足马尔可夫决策过程，文章证明了UCT方法是解决动态决策的非常重要的方法，进一步论证了基于UCT的蒙特卡洛树搜索算法在本文定义的RAPSP问题上可能会有比较好的表现。
>
> <u>文章提到，in-memory tree在马尔可夫决策问题中，前一步生成的in-memory tree经常是被保留以用在下一次快速决策中（前一步的演算结果可以被继承），这是用空间换时间的思想</u>
>
> 为SRCPSP问题生成解决方法，生成的schedule必须要具备较强的鲁棒性，鲁棒性体现在两个方面，一是应对实际环境的不确定性时，可以很快的恢复，二是恢复所需要的计算时间越少越好。
>
> 将求解器应用在MCTS的选择（或扩展）过程中，因为是与UCT过程进行了一定的重合，所以是和UCT进行组合命名
>
> 在实验结果展示上，因为外部的干扰，无法得知最优的完工时间，因此采用的相对最优时间(relative makespan)和获胜率(win rate)，相对最优时间即是相对于本次所有策略中有最少完工时间的那位的比例，获胜率即给定方法的所有模拟策略达到最少完工时间的比率
>
> estimate	execute	partial	element

# 4 模拟策略思路详解

经过考虑，还是决定采取跳点法结合蒙特卡洛树来作为模拟策略，具体的步骤将在之后的内容里进行详细说明，以方便编程实现，这里仅说明采用跳点法比起之前采用单步前进法的优势所在：

1. 跳点法可以在一次模拟中生成多个有用的扩展，可以更快的拓展到叶子节点（这是最重要的提高）
2. 跳点法用在其他AGV的随机策略中，保障了其他AGV转向频率的降低，有效避免了很多不必要的模拟方案被纳入影响因子
3. 至于跳点法对于寻找到目标点的能力，我认为其是和单步法差不多的，之前的单步法不能成功，原因在于很多不必要的因素没有考虑，导致很多分支是无效的（比如说选择了一个方向后，下一步又选择反向走，这是无效的行为；又比如说遇到了静态障碍物仍选择等待，这是无效的，等待再久静态障碍物也不会移开），所以这些因素应该作为考量放入我们的模拟策略设计中。

>算法步骤：
>
>1. 初始化地图，目标集，并根据AGV是否分配任务来将未分配任务的AGV设置成静态障碍物
>2. 初始化Plan_Rude用于存储所有AGV小车的行驶路径，首先应将AGV小车的初始位置存入
>3. 根据当前AGV小车位置生成n个根节点（过程中不生成子代）
>4. 初始时选择根节点作为扩展开始节点
>
>- 如果是Plan_Rude中属于当前AGV的计划只存入了一个点，代表着AGV还没有开始行驶，由根节点做扩展的时候，四个方向不应受到限制，除非对应方向上有障碍物存在，排除障碍物后，将可以选择的方向存在available_rude中，如果存在动态障碍物，且动态障碍物阻挡了通向目标点的两个方向，那么在可选择方向中，还应加入等待选项（如果不是这种情况，那么等待带来的收益一定是小于向着目标点行驶带来的收益的）。并随机选择一个方向进行跳点（选择谁并不重要，对于根节点来说，之后都需要完全遍历，目的是保证每个方向都做了模拟），跳点停止时的下一步作为本次模拟的起始点，如果选择的等待选项，则不进行跳点，只扩展出等待一步。无论是跳点还是等待，其他AGV都应根据模拟规则补足相对应的模拟步骤后才开始本轮真正的模拟
>- 反之，如果AGV已经开始了行驶，那么可扩展的方向就应去除原路返回方向（因为原路返回选项是一定没有意义的绕路，这种情况应直接剪除），之后存入available_rude的规则与3.1完全一致。
>- 跳点方法：（跳点方法是选择出了所有方向上具有最大可能找到最短路径的所有行驶方法，这将启发着我们的模拟过程，同时减少蒙特卡洛树的运算时间）
>  - 首先，沿着选定方向扩展出所有下一跳点可能（即遇转折或障碍（障碍又分静态障碍与动态障碍）），下面所述，是一个递进关系
>    - 沿路前进一步
>    - 判断当前形势（同时还必须要保证以下条件：如果是向着目标点前进，当前进至最远的可扩展方向（再前进就不是靠近目标点了）后，停止跳点；如果是背着目标点前进，当遇第一个转折就停止跳点）
>      - 如遇转折，此优先级最高，扩展转折下一跳，返回第一步
>      - 如遇障碍，判断障碍形式
>        - 如障碍为静态障碍，向着除逆原路方向的另一方向扩展一步，退出扩展
>        - 如障碍为动态障碍，扩展停止于当前节点，退出扩展（因为动态障碍是运动的，如此多步骤后动态障碍早已换了位置，不应于当前情况做出下一步的确定判断）
>	    - 如到目标点，立标志，退出
>	    - 返回第一步
>	- 如果选定方向是与目标点背道而驰的，我们希望转折来得越早越好，所以首次模拟的起始点选定为第一个转折；而如果选定的方向在趋近目标点，我们希望转折来得越迟越好，所以首次模拟的起始点会选定为最后一个转折。
>	- 在根节点每个方向都进行了第一次模拟后，再根据UCT原则选择接下来的模拟方向（只针对根节点下一层做UCT），选择了模拟方向后，从上到下，优先选择还没有模拟的节点进行模拟，若所有节点都模拟完一次，停止（**另一个思路是扩展完的节点模拟完后不停止，根据UCT向下选择，选择到某个未将所有可行方向扩展完的节点后，对它利用一般方法做扩展，然后再做模拟**，这个思路应该是更好的，**它贴合了较大概率收益最大的方向消耗较大算力，较小概率收益最大的方向消耗较小算力**，停止的条件就变成了达到固定的迭代次数，这样也可以保证算法每一步的时间是相对确定的）
>	- 停止后，根据最优子代计算方法选出第二层最优的节点，作为下一步
>4. 在根据3做好扩展步骤并指定了模拟的开始节点后，第4步首先需要补足其他AGV从根节点到相同深度的模拟步骤：（或许模拟也用跳点法？）
>
>- 首先，原则上一切以本轮AGV为优先，所以本轮AGV的扩展步骤是率先完成的，其余AGV开始做扩展时，在可扩展方向上需要剪除的内容有（逆前一步方向行驶，静态障碍物，本轮AGV的当前位置以及本轮AGV的下一步位置以及本轮AGV的下下步位置，优先度在我之前的AGV的当前位置和下一步位置，优先度在我之后的AGV的当前位置，随机生成的动态障碍物），剪除后，按如下判断优先级筛选纳入available_rude的方向：
>
>  if   可扩展方向包括向着目标点行驶的方向：
>
>  	if	向着目标点行驶方向与前一步行驶方向一致：
>
>  			直接放入available_rude，停止判断
>
>  	else	不一致：
>
>  			都放入available_rude，停止判断
>
>  else	不包括：
>
>  	if	前一步行驶方向存在于可扩展方向中:
>
>  			available_rude中加入前一步行驶方向
>
>  	else	:
>
>  			available_rude中加入等待
> 
> - 然后，本轮AGV根据available_rude做选择（若长度为1，是单选，若为2，多选，每个概率为0.5），并根据做出的选择对相应的树进行扩展。
>
> - 当补足相同深度后，进入第五步，也就是真正的模拟开始
>
>5.	第5步与第4步一脉相承，本轮AGV仍具有最高的模拟优先度。做扩展时，剪除的内容有所变化（逆前一步方向行驶，静态障碍物，优先度在我之前的AGV的当前位置和下一步位置，优先度在我之后的AGV的当前位置，随机生成的动态障碍物），剪除后，按第4步的优先级筛选判断纳入available_rude。
>6.	如果4、5步中某一AGV在模拟的过程中到了目标点，则根据其目标集更新起终点，如果目标集更新完了，说明这个AGV在本次模拟过程中完成了自己所有的任务，那么这个AGV将不再参与之后的模拟运算，**而自己由动态障碍转为静态障碍**（这也是很关键的一个点，这将对跳点产生影响）。
>

# 5 选择节点策略

怎么选择节点？

1. 刚开始的时候，根节点下一层所有的方向都是没有权重的，这个时候先随机选择一个方向，然后找到这个方向的最深处，如果它不是叶子节点，选择结束，从此点开始进行模拟。（因为这个位置是当前具备最大可能找到最优路的，先访问掉）
2. 第二次后，根节点下一层有些节点具有了权重，接下来的选择首重权重还为0的方向（若有多个也是随机选择），直到根节点下一层所有的方向都进行了一次模拟。
3. 再之后，根据UCT原则选择根节点下一层的节点，再根据2的规则对根节点下一层的节点同样的进行选择（即首重那些下方还不具备权重的，但如果都具有了权重，则根据UCT选择）
4. 如果选中的这个开始模拟的节点具备权值，说明它不应再作为模拟的节点，对它进行一步扩展，原则依据不返回，无特殊情况不停止，优先去往靠近目标点方向，再把扩展出的点作为模拟的起点。
5. 当到达最大迭代次数，不能再进入选择，或者是某次选择到达了叶子节点，也不再进行选择。

# 6 模拟策略

怎么开展模拟，当前模拟的AGV和其他的AGV要怎么看待

1. 首先，因为障碍是随机生成随机移动的，其轨迹我们难以确定，所以对于其他AGV造成的影响是很难度量的，我们无法完全确定其他AGV的下一步行驶方向，因为这会随着障碍物的移动发生改变，但是我们可以知道其他AGV的倾向，因为走出下一步的策略对于每个AGV来说都是相同的，因此我们可以假设一个$\lambda$参数来表征当前区域AGV会与障碍物相遇的统计学概率，以这个概率作为AGV拓展自己行驶方向的依据，当随机数大于（1-$\lambda$）的时候，可以选择较差的躲避方向（当然，原路返回不管在什么时候都是排除的）
2. 因此，我们对模拟策略做出如下的设计规范：
   - 首先由当前模拟车辆根据跳点的规则从当前扩展节点开始模拟出一条（或到达目标点，或到达最大迭代次数）的路径，在这个过程中，其余AGV的行驶被忽略;
   - 依次对其他AGV从根节点展开单步模拟，模拟的策略分为两个部分
     - 首先，假如本次产生的随机数小于或等于$\lambda$，表示本次单步看作是无动态障碍可能的模拟，因此本次前进方向需排除原路返回、远离目标点。在此种方法下的优先级顺序：靠近目标点且承接前一步>仅靠近目标点。若以上优先级均不存在，且不可行的原因又不是因为动态障碍造成的，那么强制转化到大于$\lambda$的情况，反之呢，则将等待作为下一步
     - 假如本次产生的随机数大于$\lambda$，表示本次单步看作是有动态障碍可能的模拟，因此本次前进方向仅排除原路返回。在此种方法下的优先级顺序：靠近目标点且承接前一步>仅靠近目标点>仅承接前一步。若以上优先级均不存在，且不可行的原因又不是动态障碍造成的，那么就选择不承接前一步且远离目标点，否则选择等待。
     - 若AGV下一步与目标点重合，则更新目标点，若目标点不再能继续更新，那么此AGV转化成静态障碍输入地图中，并更新可达信息。同时遍历的树的数量发生改变（这个可以通过将for循环做如下改进实现,  for node in tree，这样每次node就从tree中取一棵树出来，而完成任务的tree就del掉，下一次循环就不会有了）
     - 而重要的是，我们将本次模拟的AGV重要性提到了最前面，因此本次模拟的AGV，其当前位置，下一步位置，下下步位置都是其他AGV下一步模拟时的动态障碍

3. 很重要的一点是，在模拟的过程中，不去计数在回溯阶段score需要用到的一些统计变量，以模块化模拟，方便后续的改进，而统计变量在模拟结束后再在score函数进一步计算（随增加了时间复杂度，但代码可读性大大增加）

zhouhua_8/monte-carlo-AGV

简介

发行版

贡献者

近期动态

zhouhua_8/monte-carlo-AGV .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

zhouhua_8/monte-carlo-AGV