algorithm - 机器人如何规划迷宫？

Question

首先 - 我浏览了类似的问题，但它们没有解决我的问题，这不是重复(我希望)。
我正在使用 Arduino Nano 构建和编程一个机器人，该机器人应该可以解决迷宫问题。它被放在迷宫的某个地方，然后必须找到一个项目。下次它应该直接到达该项目(它不一定是最短的路，但不允许有死角)。
没有必要知道整个迷宫，因为只要他有一条通往元素的路就很好。正如我所说，我不需要最短路线。
迷宫是二维的，我只是把黑色胶带放在白色 table 上，机器人应该使用线传感器来跟随线。
没有其他传感器可以定位自己。首先，我想到制作一个二维数组，迷宫的每个区域都在其中。但是因为它只是一个普通的线传感器，所以机器人不知道直线是一个还是两个字段长，所以整个事情都不起作用。
我也尝试过 DFS 或类似的东西，但这里有类似的问题。迷宫是圆形的，机器人怎么知道之前已经找到了节点并且它是相同的？
如果有人有想法，那就太好了!

Answer 1

虽然方向有点模糊，但可以使用决策。一个决定必须是可重复的。它可以用一个类来表示:

public class Decision {
    boolean[] directions = new boolean[2]; // 0 = left, 1 = straight, 2 = right
    // at least 2 of them should be true or it is no decision
    int path; // 0-2 to mark the current path
}

1. 创建一堆决策。

2. 如果一开始只有一个可能的方向(后退不算，后面处理)，则继续前进，直到遇到第一个决定。

3. 将包含所有可能方向的决策推送到堆栈。

4. 将路径设置为第一个可能的方向并朝那个方向移动。

5. 如果您最终做出另一个决定:在 3 点继续。

   如果您找到 token :中止，则您找到了一种没有死胡同的可重现方法。

   如果是死胡同:回到上一个决策节点(返回的第一个)继续6。

6. 弹出决定并尝试下一个可能的方向(设置新路径并插入决定)并在 5 处继续。

   除非你已经尝试了所有方向，然后退回另一个决定并继续6。

   如果没有更多的决策(上面提到的特殊情况，我们一开始就走错了方向):继续前进，直到遇到第一个决策，然后从3继续。这意味着你需要另一个 bool 变量来指示是否你应该从头开始倒退。

   从左回来时要小心，然后想尝试直行，接下来您将不得不向左转，而不是直行。所以这里涉及到一些计算。

如果您从一开始就以错误的方式开始，该算法就会出现循环决策问题。我认为这可以通过设置上限来避免，例如如果您仍然没有找到 token 并遇到 30 个决策节点(继续)，那么您可能在原地打转，所以回到开始，现在不要按递增顺序尝试方向，而是按递减顺序尝试。