手抄报 安全手抄报 手抄报内容 手抄报图片 英语手抄报 清明节手抄报 节约用水手抄报

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

时间:2024-10-26 19:52:16

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

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

2、小猫侧耳一听,第1颗果子落在了12点方向,但在它的活动范围之外,这没关系,有方向就好,因为这是它的第一步,所以不用考虑,它径直向12点方向前进一步,没有碰到墙,也没碰到石头,所以它就走到了“1”点,小猫记住,这"1"点是可以走的。

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

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

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

4、第3颗果子,其实落在了鱼的附近,小猫回想了下第三颗果子落地的位置,已经知道的Xstart/"1"/"2"三个点中,2点距离最近,于是从2点向第三颗果子方向前进一步,得到了“3”点

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

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

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

6、第5颗果子落在了“3”号点的右上角一点点,距离这个落地点最近的无疑就是“3”号点了,于是小猫跑到3号点,又朝着果子方向前进了一步,嗯,因为第四颗果子落的太近了,小猫跨过了这颗果子,得到了“5”号点,这一点也是可以走的。

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

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

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

8、第7颗果子落在了活动范围之外,曾经走过的路中,距离这个落地点最近的是“1”号点,于是小猫返回“1”号点,向这第7颗果子落地点前进一步,成功了,于是获得了第“6”点。

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

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

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

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

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

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

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

12、它再次重新回顾下自己曾经走过的所有的路,然后找到了一条最近的道,图中紫色的那条路,于是小猫记住了这条路,下次就照这条路来找鱼

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

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

© 手抄报圈