编程机器人探索网格
Programming a robot to explore a grid
在我的项目中，我只是想制作一个机器人，它可以尽可能多地探索网格，而无需两次走相同的路径。此外，它还有一个传感器，可以查看是否有物体挡在路上（物体只能在走廊上）。但是我在尝试让机器人避免走相同的路径时遇到了问题。
我尝试通过创建一个二维数组来为网格中的每个正方形存储一个整数值来解决这个问题。值为 0 表示机器人还没有在网格中的那个方格上，值为 1 表示方格在网格中被阻塞，值为 2 表示机器人之前已经在那个方格上。如果机器人看到其当前航向前方的方格值为 2，则它会继续旋转以寻找值为 0 的方格，但如果机器人周围不存在值为 0 的方格，则它开始回溯。
这个例子可以更清楚地解释我的问题：
三角形代表机器人和它的起始位置，左下角假设是我网格中的位置（0,0）。绿色圆圈代表阻挡其路径的项目。红色方块是机器人的目标。机器人只能移动到网格中的白色方块上。
当我启动我的程序时，机器人会向前移动（向东，因为这是它当前的航向），直到它到达绿色圆圈之前的路口。它向前看并检测到路上有物体，因此它逆时针旋转 90 度并检查是否有另一个堵塞物，再次发生因此它再次逆时针旋转。所以现在机器人在位置 (0,2) 向西行驶。它只能向西移动以避免离开网格或撞到物体，所以它回到了它的初始位置但仍然向西移动。它现在将继续顺时针旋转 90 度，直到它找到一个将其保持在网格上的方向，即直到它再次面向东方。所以网格现在看起来像：
但现在我想通过忽略该方向并再次逆时针旋转 90 度以面向北方来忽略继续前进并走上同一条路径，这样我的机器人就可以向北移动到一条新路径上。我可以简单地忽略方向并继续旋转以找到一条新路径，但是如果我被之前的路径包围并且我希望我的机器人回溯到它的最后一个路口怎么办。我怎样才能有效地做到这一点。还有我怎样才能有效地检测到我什么时候需要回溯。
谢谢
解决图 2 中的困境就像在移动之前检查机器人周围的其他 white 方块一样简单。在图 2 中，机器人会看到他面对的正方形是 "greyed out" 并决定检查所有其他方向，最终发现他的北面有一个空的白色正方形。
编辑：没有意识到这是一个真正的机器人。
由于了解单元格中内容的唯一方法是转向该单元格并使用传感器，因此无论您做什么，机器人都必须进行一定程度的转动。当它遇到墙壁或绿色物体时，它必须转弯，直到找到新的行进路径。您可以通过忽略外壳的墙壁来优化它。例如，当机器人返回起始位置面向西时，你已经知道南面有墙，因为它的坐标位置是(0,-1)，这是无效的。这使您可以确定打开的瓦片在北边，因为您已经访问过东边的瓦片，只需要转一圈。
此外，当机器人最终一路向北行驶时，瓦片 (0,6) 因为它的位置，您知道北面和西面有一堵墙。然后您可以智能地猜测空位必须在东边，因为西边的瓷砖 (-1,6) 无效且 (0,7) 也无效。
如果不更改传感器以查看 2 个块或在机器人上安装更多传感器（即每侧一个），由于可用信息有限，无法进行更多优化。
在我的项目中，我只是想制作一个机器人，它可以尽可能多地探索网格，而无需两次走相同的路径。此外，它还有一个传感器，可以查看是否有物体挡在路上（物体只能在走廊上）。但是我在尝试让机器人避免走相同的路径时遇到了问题。
我尝试通过创建一个二维数组来为网格中的每个正方形存储一个整数值来解决这个问题。值为 0 表示机器人还没有在网格中的那个方格上，值为 1 表示方格在网格中被阻塞，值为 2 表示机器人之前已经在那个方格上。如果机器人看到其当前航向前方的方格值为 2，则它会继续旋转以寻找值为 0 的方格，但如果机器人周围不存在值为 0 的方格，则它开始回溯。
这个例子可以更清楚地解释我的问题：
三角形代表机器人和它的起始位置，左下角假设是我网格中的位置（0,0）。绿色圆圈代表阻挡其路径的项目。红色方块是机器人的目标。机器人只能移动到网格中的白色方块上。
当我启动我的程序时，机器人会向前移动（向东，因为这是它当前的航向），直到它到达绿色圆圈之前的路口。它向前看并检测到路上有物体，因此它逆时针旋转 90 度并检查是否有另一个堵塞物，再次发生因此它再次逆时针旋转。所以现在机器人在位置 (0,2) 向西行驶。它只能向西移动以避免离开网格或撞到物体，所以它回到了它的初始位置但仍然向西移动。它现在将继续顺时针旋转 90 度，直到它找到一个将其保持在网格上的方向，即直到它再次面向东方。所以网格现在看起来像：
但现在我想通过忽略该方向并再次逆时针旋转 90 度以面向北方来忽略继续前进并走上同一条路径，这样我的机器人就可以向北移动到一条新路径上。我可以简单地忽略方向并继续旋转以找到一条新路径，但是如果我被之前的路径包围并且我希望我的机器人回溯到它的最后一个路口怎么办。我怎样才能有效地做到这一点。还有我怎样才能有效地检测到我什么时候需要回溯。
谢谢
解决图 2 中的困境就像在移动之前检查机器人周围的其他 white 方块一样简单。在图 2 中，机器人会看到他面对的正方形是 "greyed out" 并决定检查所有其他方向，最终发现他的北面有一个空的白色正方形。
编辑：没有意识到这是一个真正的机器人。
由于了解单元格中内容的唯一方法是转向该单元格并使用传感器，因此无论您做什么，机器人都必须进行一定程度的转动。当它遇到墙壁或绿色物体时，它必须转弯，直到找到新的行进路径。您可以通过忽略外壳的墙壁来优化它。例如，当机器人返回起始位置面向西时，你已经知道南面有墙，因为它的坐标位置是(0,-1)，这是无效的。这使您可以确定打开的瓦片在北边，因为您已经访问过东边的瓦片，只需要转一圈。
此外，当机器人最终一路向北行驶时，瓦片 (0,6) 因为它的位置，您知道北面和西面有一堵墙。然后您可以智能地猜测空位必须在东边，因为西边的瓷砖 (-1,6) 无效且 (0,7) 也无效。
如果不更改传感器以查看 2 个块或在机器人上安装更多传感器（即每侧一个），由于可用信息有限，无法进行更多优化。