机器人探索算法

Question

机器人探索算法

algorithmartificial-intelligencerobotics

21

我正在尝试为一个机器人设计一种算法，该机器人需要在包含障碍物的世界中找到旗帜（位置未知）。机器人的任务是捕获旗帜并将其带回他的家基地（代表他的起始位置）。在每一步中，机器人只能看到有限的邻域（他不知道世界的全貌），但他有无限的记忆来存储已经访问过的单元格。

我正在寻求关于如何以有效的方式执行此操作的任何建议。特别是第一部分；即到达旗帜的部分。

输入图像描述

- Daar

2

你目前想到了什么？ - Mitch Wheat

3

如果你处于机器人的位置，你会怎么做才能更有效地找到旗帜？ - Lucas Moeskops

3

@Lucasmus：我认为很难找到一些真正聪明的算法，因为机器人除了他有限的邻域之外不知道世界上的任何事情。 @Mitch Wheat：目前为止，我只列出了这样一个算法所应具备的期望特性列表：

尽可能少地重复访问已经访问过的单元格
全局目标：寻找旗帜
局部目标：避开障碍和无限循环

- Daar

所有这些答案都基于您了解搜索功能的前提。如果不清楚，请查看我的答案底部。希望这有助于澄清。 - T.K.

此外，许多答案都对知情搜索非常有效，而这是一种无信息搜索类型的问题。我试图在我的答案的下一个编辑中解决这个问题，在这里。 - T.K.

8个回答

3

其中一部分是路径规划，例如使用A*算法。

另一部分是探索。任何有未知邻居的单元格都值得探索。最好的探索单元格是离机器人最近且未探索邻域最大的单元格。

如果机器人能透过墙壁看到某些探索候选单元格，则有些单元格可能无法进入，即使标志已经可见也需要进行探索。

每次揭示新单元格时重新评估当前目标可能很有价值。只要在揭示新单元格时执行此操作，就可以始终取得进展。

- aaz

1

通过简单的DFS搜索，至少你会找到旗帜：）

- Petar Minchev

好的。当您获得有关基地位置的一些信息（例如，它与下界边缘的距离）时，您如何利用它来改进此算法？ - Daar

BFS怎么样？它也很简单。 - Micromega

1

这里有两个部分： 1）寻找旗帜 2）回归家园

对于寻找部分，我会每次完整绕圈时将家点向外圈。这样，您可以搜索每个方格并确定它是清晰的位置、障碍物、地图边界还是旗帜位置。这样，您可以创建环境地图。

一旦找到旗帜，您可以沿着同样的路线返回，或者找到更直接的路线。如果是更直接的路线，则需要使用您创建的地图找到最短路径。

- glowworms

0

你想要的是在机器人视口中找到所有的最小生成树，然后让机器人选择它想要走的最小生成树。

- Micromega

这将适用于知情搜索，其中机器人事先知道网格的情况。根据问题描述，机器人并不完全了解环境。 - Shamim Hafiz - MSFT

@Gunner：这已经超出了我的能力范围，但为什么不让机器人在下一步中玩欧拉回路游戏呢？ - Micromega

空间填充曲线怎么样？这样机器人就有一个+/-100的空间索引，或者他看到什么就让他通过找到每个最小生成树来随机选择一条路线？ - Micromega

0

如果你遇到了障碍物，可以绕过去确定它的精确尺寸，测量完后返回原来的路线。在视野范围内没有障碍物的情况下，你可以尝试直接朝最近的未检查区域前进。

这可能不是最快的方法，但我认为这是一个好的起点。

- Rafał Rawicki

0

我认为的方法是在机器人行进时构建图形。将有一个函数返回给机器人网格的特定状态。这是必要的，因为机器人事先不知道网格的状态。

您可以在搜索中应用启发式算法，以增加到达目标旗帜的概率。

- Shamim Hafiz - MSFT

你需要的是完全图的空间填充曲线，这样你就可以限制机器人的视野，并让它使用Prim或Kruskal算法探索视野，然后让它从众多MST中选择一个，或者让它探索最近的未知区域。 - Micromega

0

正如许多人所提到的，如果你知道自己在哪里和目标在哪里，A*算法是进行全局规划的好方法。但如果你没有这种全局知识，你应该了解一类叫做“虫子”算法的算法。

至于探索，如果你想尽快找到旗帜，根据你的机器人可以看到多少本地邻域，你应该尽量避免这种邻域重叠。例如，如果你的机器人可以在每个方向上看到一格，那么你应该探索每三列。（第1列、第4列、第7列等）。但如果机器人只能看到它当前占据的格子，那么最优的方法就是不要回到已经访问过的区域。

- Ben

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- T.K. · Accepted Answer

一个简单的广度优先搜索/深度优先搜索算法可以实现，但速度较慢。一定要防止机器人检查多次访问同一个方格的路径，因为这会导致这些算法在标准情况下运行时间更长，在无法到达旗帜的情况下无限期地运行。

A*是更优雅的方法，特别是如果你知道旗帜相对于自己的位置。通常情况下，Wikipedia 解释得很好。使用的经典启发式方法是到目的地的曼哈顿距离（假设没有障碍物的移动次数）。

这些算法对于返回旅程非常有用 - 不太适用于“找到旗帜”的部分。

编辑： 这些方法涉及创建代表地图上方块的对象，并创建“路径”或一系列要命中的方块（或要采取的步骤）。一旦您建立了表示正方形的框架，选择使用哪种搜索变得不那么令人望而生畏。

此类需要能够获取相邻方块的列表，并知道它是否可遍历。

考虑到您没有所有信息，请尝试将未探索的瓷砖视为可遍历，并在发现它们不可遍历时重新计算。

编辑： 关于在未知区域搜索未知物体...

您可以使用类似 Pledge's algorithm 的算法，直到找到空间的边界并记录所有信息。然后使用您喜欢的漂移/路径查找算法查看所有未见过的方格。如果在任何时候沿途看到旗帜，请停止当前操作并使用您喜欢的路径查找算法回家。