瞎猫找小鱼 傻子都看得懂的RRT随机扩展树算法

1、一佯镧诱嚣只猫眼睛瞎了，鼻子也不好使，它非常饿，小明又看它可怜，又给了它一只鱼，但是小明又很顽皮，又没有把鱼直接放小猫嘴巴底下，而是放在固定的位置，要让小猫自己去找。假设下图框起来的区域为这只猫可以寻找的所有范围，框里面各种黑的灰的红的绿的黄的橙的都是不能走的，现在猫在左下角，鱼在右上角，猫很胆小，每次都只向前尝试走一步。因为看不见，又闻不到，小猫每次都只能随机的去碰。因为小明每次都把鱼放在那个位置，而它平时每次都在现在的位置休息，所以这一次，小猫准备记住自己走的每一步，以便找到一条最近的路，下一次小明再给鱼，就不用乱碰，可以抄近路去找了。可怎么找呢？它眼睛瞎了，鼻子不好使了，不过耳朵还挺灵，刚好它这个区域再一颗果树底下，果树现在每隔一段时间就向下掉一个果子，位置当然完全随机，小猫通过听声辩位，能听出果子落到那个位置，于是它决定，以果子落地位置为参考，随机去找。小猫现在准备出发了，它记住自己当前所在位置为Xstart，鱼所在位置为Xgoal

3、第2颗果子，落在了它身后，小猫没有立即行动，而是回想了下，它已经走过的路中，距离这个果子落常挢傣捅地点最近的点在哪里，嗯因为它才走了两步，所以只有Xstart 和“1”这个点，第二颗果子落地的点，距离Xstart更近，于是小猫回到Xstart，又向第二个果子落地的方向前进一步，没碰到墙或者石头啥的，于是它记住了，第2点也是可以走的。

5、第4颗果子，落在了小猫起始位置的后面，距离这个点最近的当然是起始点了，于是小猫又跑回来从起始点向第四颗果子落地的地方前进了一步，咦，也没碰到什么障碍物，得到了“4”号可以走的点。

7、第6颗果子落在了黑色石头后面，距离这个落地点最近的曾经走过的路是“5”点，小猫从5号点向着第六颗果子落地点前进，结果碰到大石头，嗯这个方向是不可行的，这一次没能得到新的可以走的点，等待下一颗果子。

9、第8颗果子落在了黑色与灰色石头的左边，小猫掐指一算，在曾经走过的路中，“1”点距离这个落地点最近，于是小猫跑到“1“点，向着第8颗果子落地点前进一步，成功，得到了“7”号点，这个点也是可以走的。

11、经过很多很多次的类似的尝试，小猫终于碰到了鱼。

13、小猫起始的位置，就是Xstart,鱼的位置就是Xgoal，每次果子落地的位置是Xrand,小猫每鸱远忡绑次向前探索的那一步，叫做搜索步长ρ，足饶戽沸每次在已走过的路中，距离果子落地点最近的那个点叫Xnear，每次探索到的最新的点叫Xnew。以上这些就是有关RRT算法的所有参数。Xnew=Xnear+ρ*（（Xnear-Xrand）/|Xnear-Xrand|）