viple模拟器使用（四）：unity模拟器中实现两距离局部最优迷宫算法

首页
互联网
正文

本文介绍: unity 模拟器中实现两距离局部最优迷宫算法

名字解读

两距离：指的是左侧距离和右侧距离

局部最优：对当前状态来说最好的选择，至于整体能不能达到最优，是无法确定的。

从节点1到节点5，一共有3条路

第1条路线：1→2→4→5，对应的花销是：2+3+4=9；

第2条路线：1→3→4→5，对应的花销是：1+5+4=10；

第3条路线：1→3→5，对应的花销是：1+6=7；

所以，可以看出，花销最少的是第3条路线，对应的花销是7，即：该路线是最佳路线，开销最小。

如果采用的是贪心策略来实现从顶点1到顶点5。当站在顶点1的时候，看到前面有两条路，分别是去顶点2和去顶点3，对应的开销分别是2和1，此时，认为去3开销小，于是选择下一步走到顶点3。

同样的道理，当来到顶点3后，面前也有两条路，去顶点4和顶点5，分别对应的开销是5和6，此时会认为去顶点4开销小，所以下一个顶点去顶点4

由于顶点4到顶点5，只有一条路，所以就直接选择该条路径即可。

所以最终选择的路线是：1→3→4→5，对应的开销是1+5+4=10。

从该案例中可以看出，贪心策略是一种局部最优，也就是说，每一步的选择，都是根据当前拥有的资源选择对自己来说最好的选择，至于整体是否最优，有可能是，有可能不是。

综上所述，两距离局部最优迷宫算法，也就是一种贪心策略，可能最终也会走出迷宫（要根据迷宫的形状才能确定是否能走出迷宫），走的路径按照原理给定的策略进行选择，整体路径不一定是最短的路径。所以调整参数的时候，能使得机器人使用该策略走出迷宫且行走路径不要出现转圈等增加行走路径的值则为比较恰当的参数。

观察现象

两距离局部最优迷宫算法

注意：右转完成后，进行了测量。然后本视频中显示的是右转180度，应该是左转180度，制作PPT的能力有待提高，后期有时间进行更新。

总结出原理

初始化为直行状态，当前侧检测到前方有障碍物时，机器人右转90度；
右转完成后，进行测量。测量出来的值赋值给变量，用来保存右侧距离；
测量结束后，左转180度，再次进行测量，此时，测量出来的值对应的是左侧距离；
如果左侧距离大于等于右侧距离，则表示左侧更加宽敞，应该往左侧走，由于车头此时已经在左侧，所以只需要直行即可；
如果左侧距离小于右侧距离，则表示右侧更加宽敞，应该往右侧走，由于车头此时在左侧，所以需要右转180度，使得车头朝右，再直行。

有限 状态机

回答几个问题再考虑 如何写程序

1、为什么刚开始运行是直行前进？

答：使用前方的距离传感器进行测量，测量值大于等于设定的危险值，此时机器人认为前方有路，所以直行。

2、为什么机器人会右转90度？

答：使用前方的距离传感器进行测量，测量值小于设定的危险值，此时机器人认为前方无路，所以进行转弯，此时，机器人想要测右侧距离，由于只有前方才有距离传感器，所以，将机器人朝向先调整到右侧，再进行测量，所以右转90度。【右转90度，就是为了使用前方的距离传感器测量右侧距离，所以才会右转90度】

3、为什么右转90度后，测量完右侧距离，然后左转180度？

答：机器人想要测左侧距离，但是由于上一步骤后，机器人朝向是右侧，所以，需要先将朝向调整到左侧，再进行测量，由于从朝右改为朝左，可以左转180，也可以右转180度，所以没有特别要求非要从那边，建议选择左转180度。

4、两边都测量完了后，再进行比较，判断哪边更宽敞，就往那边走。情况就有两种：

1）如果左边≥右边，接下来直行（这是因为第三步过后，机器人已经朝左，此时选择直行，实际上就是往左边走了）

2）如果左边＜右边，接下来右转180度，然后再直行（这里因为第三步选择左转180度，现在想要把机器人的朝向改到右边，就右转180度进行恢复。第三步“建议选择左转180度”，实际上的目的就是想要在恢复的时候，选择右转180度，机器人看起来有点探测路的感觉）

总结：该算法策略，只使用了一个传感器，是前方的距离传感器。

算法 实现

unity线控模拟中，已经发现一个规律，想要机器人运行，使用的是移动动力控制和转动角度控制。现在加入算法后，模拟器环境没有改变，所以，主机配置应该和线控模拟是一致的，其次，想要让机器人动起来，还得是移动动力控制和转动角度控制。

接下来进行一种参考程序编写方法

前进自定义活动：做两件事，分别是：机器人前进以及前进状态的记录（由于没有设置定时器，先记录状态还是先运动，都可以，如果希望并行，还可以设置为两条工作流也行）

右转90度自定义活动：做一件事，右转，由于右转需要时间，所以不仅要右转，还要给一定的时长

左转180度自定义活动：主要做左转工作，和右转一样，都需要一定的时间，需要注意的是：左转是逆时针运动，所以，角度的符号为负数。

右转180度和左转180度相似，只需要将参数值符号改为正数即可，暂停和前进类似，只需要将驱动功率值设置为0即可。

Ma in 程序

第一个条件，表达的是直行过程中，发现前方无路，进行右转；第二个条件，表达的是右转完成后，进行测距，此时测出来的距离是右侧距离，然后进行左转180度。第三个条件表达的是左转完成后，进行测距，此时测出来的是左侧距离，只需要判断左侧距离和右侧距离的关系，即可做出后续往那边走的动作即可。

效果 展示

后记：理解原理，对整个运行过程很熟悉，编程实现，并进行参数调整，观察运行效果是否正确即可，当然，如果非常用心做，应该把参数调整到接近于整体最优的效果最佳。

unity 模拟器实验两距离局部最优迷宫算法效果

注意：需要对状态进行锁定，状态改变，要及时更新新状态，再做动作。

可能出现的问题：

1、没有进行状态锁定，导致转弯的时候，还在判断前方是否有障碍物

2、设置的时间不合理，例如：右转90度还没有完成动作，就进行测量右侧距离；同样的道理，左转180度还没有完成，就开始测量左边的距离，这也是不对的。其次，右转180度进行恢复的时候，还没有恢复到右侧，就开始前进，也是不合理的，这些问题都是因为设置完成动作的时间不合理造成的。

3、机器人刚运行的时候就开始右转90度，说明符合了右转90度的条件，状态是直行且测量值小于设定值，如果想要机器人刚开始能够直行，就要破坏右转条件，状态是无法改变了，那就只剩下测量值小于设定值，测量值来自传感器，传感器中的值只能读取，不能修改，所以，只能修改设定值，此时，应该将设定值改小一些，从而来使得测量值大于等于设定值，认为前方有路，才能直行，就防止了右转。