机器人最快的迷宫算法

#1 楼

除非您被允许先探索或事先了解迷宫，否则您不能对迷宫作过多的介绍。否则，很容易建立一个迷宫，使用墙面跟随法要花很长时间才能解决，但是解决方法很简单。请参见以下示例。



在这种情况下，随机选择转弯平均速度更快。所以也许这是一个棘手的问题，需要更多的思考。
在某些情况下，迭代加深的方法也不错。在这里开始您的研究，并在遇到特定问题时返回。

#2 楼

墙跟踪算法将从侧面的传感器中受益更多。因为您一直跟踪到找到一个间隙，所以您变成了那个间隙。然后，当您撞到前面的墙壁时，可以使用加速度计来感应碰撞。但是，不确定如何确定自己不在迷宫中（以防您需要这样做）。只是一个主意...

#3 楼

对于任何给定的算法（事先不知道迷宫），都有一个特定的迷宫，其中算法没有在第一次尝试中选择最快的方法。首先在迷宫中记录道路，然后找到最佳方式，然后再尝试以最快的方式将其驱赶到目标。 ，它的移动方式只是机器人可以移动的宽度，而不能太宽，并且如果它具有直角（许多简单的迷宫都可以），那么您可以使用一些技巧第二次更快地解决它：


侧面传感器会很有帮助，因此，如果不可能的话，您将不会被迫不断转弯
，并且您拥有距离传感器（通常是超声波），而只有障碍物传感器（也许是保险杠） ，您可以将其限制为窄波束，然后选择稍微波动一下，看看距离是否一直在变化，或者是否有孔（这表示侧面），以及如何洞远了。然后，您可以在靠近交叉路口处快速行驶，然后仅缓慢行驶并进行全程旋转以精确找到侧向路。
将传感器安装在“坦克状”旋转底座上也可以使您直行并旋转比旋转整个机器人更快的sensosr
，如果方法狭窄，则可以考虑在侧面添加保险杠，而只是撞击到侧面以感觉到它们，而不是原地旋转以正确检测它们。如果您可以拥有像虫子一样的天线同时感觉到两侧，则可以加分（但是它们需要灵活而不破损，并且您至少需要3个状态传感器（2位）-无触摸-轻触摸-硬触摸：无触摸表示侧向，轻度触摸表示您正好位于中间的直行上，硬触摸则表示障碍物或向侧弯太多。

无论如何： />您沿惯常的“右手踩墙”方式前进，直到找到目标，然后继续以相同的风格开始运动，这样您就第一次走遍了整个迷宫。
在路上标记任何交叉点并计数它们种类的地图（如果测量距离，则为奖励），然后，当您从起点回到地图时，请在内存中旅行；返回十字路口时，您知道可以跳过第一种方法，因为您选择了那里，因为它没有达到目标并返回。继续，直到找到目标并且您已经解决了一半的地图。然后从头开始以相反的方式进行操作，并求解地图的另一半。您应该得到相同的结果-否则，您犯了一个错误或者迷宫不是一棵树。
第二次尝试时，您可以知道可以跳过哪一侧的方式，以及必须在哪种交叉方式上选择哪种方式，因此，您可以走更短的路线来瞄准目标。
如果您还标出了距离，那么您就知道下一转弯应该走多远，并且您可以在几乎所有距离上真正快速行驶，然后才需要精确扫描转弯（并且可能会更慢）。
如果您的机器人构造允许，您甚至可以忽略墙壁，让墙壁轻轻地将您撞回中心，这样您就不需要很多精致的导航，因此甚至可以运行快点。
转弯时也一样，在您认为要接近转弯的时候，您可以一直贴在墙上并稍微推一下，直到它允许您进入，这样您就知道了转弯在这里。再次简化了导航，减少了要评估的数据量，从而可以实现更快的速度。
如果您想要超快，也可以记录此运行并将其用于第三次运行，在此情况下您知道有多长时间可以在转弯前运行，已经考虑了快速运行与谨慎和缓慢探索之间的所有加速度和不规律性。