我正在尝试为机器人设计一种算法，该算法试图找到位于包含障碍物的世界中的标志（位于未知位置）。机器人的任务是夺取旗帜并将其带到他的基地（代表他的起始位置）。机器人在每一步只能看到一个有限的邻域（他事先并不知道世界的样子），但他有无限的记忆来存储已经访问过的单元格。
我正在寻找有关如何以有效方式执行此操作的任何建议。尤其是第一部分；即登上国旗。
问问题
8675 次
8 回答
5
一个简单的广度优先搜索/深度优先搜索将起作用，尽管速度很慢。一定要防止机器人多次检查具有相同正方形的路径，因为这将导致这些算法在标准情况下运行更长的时间，并且在无法到达标志的情况下无限期地运行。
A* 是更优雅的方法，特别是如果您知道标志相对于您自己的位置。像往常一样，维基百科在解释它方面做得不错。使用的经典启发式方法是到目的地的人员距离（假设没有障碍物的移动次数）。
这些算法对于回程很有用——与其说是“寻找标志”部分。
编辑： 这些方法涉及创建表示地图上正方形的对象，并创建“路径”或一系列正方形来命中（或要采取的步骤）。一旦你建立了一个框架来表示你的方格，使用哪种搜索的问题就变得不那么令人生畏了。
此类将需要能够获取相邻方格的列表并知道它是否可遍历。
考虑到您没有所有信息，请尝试将未探索的图块视为可遍历的，如果发现它们不是，则重新计算。
编辑： 至于为未知物体搜索未知区域......
您可以使用诸如Pledge 的算法之类的东西，直到找到您的空间边界，并随时记录所有信息。然后使用您最喜欢的漂移/寻路算法查看所有看不见的方块。如果在路上的任何时候，你看到了旗帜，停止你正在做的事情并使用你最喜欢的寻路算法回家。
于 2011-03-19T13:16:08.083 回答
3
其中一部分将是寻路，例如使用A* 算法。
其中一部分将是探索。任何有未知邻居的细胞都值得探索。最适合探索的细胞是那些离机器人最近且拥有最大未探索区域的细胞。
如果机器人透过墙壁看到一些探索候选者可能无法进入，即使标志已经可见，也可能需要探索。
每次显示新单元格时，重新评估当前目标可能是值得的。只要只有在新细胞出现时才这样做，总会取得进展。
于 2011-03-19T12:34:20.667 回答
1
至少通过简单的DFS搜索，您会找到标志:)
于 2011-03-19T11:42:56.480 回答
1
嗯，这有两个部分。1) 寻找国旗 2) 回家
对于搜索部分，每次我完成一个完整的循环时，我都会将原点向外移动。通过这种方式，您可以搜索每个方格并识别它是否是空旷地点、障碍物、地图边界或旗帜。这样，您可以创建环境地图。
找到标志后，您既可以原路返回，也可以找到更直接的路线。如果它是更直接的路线，那么您将不得不使用您创建的地图来查找直接路线。
于 2011-03-19T13:32:21.533 回答
0
如果遇到障碍物，您可以四处走动以确定其精确尺寸，并在测量后返回之前的路线。在视线范围内没有障碍物的情况下，您可以尝试朝最近的未检查区域的方向前进。
这似乎不是最快的方法，但我认为这是开始的好点。
于 2011-03-19T11:58:37.190 回答
0
你想要的是在机器人的视口中找到所有最小生成树，然后让机器人游戏他想去的地方。
于 2011-03-19T11:43:15.717 回答
0
我认为方法是在机器人行进时构建图形。将有一个函数将网格的特定状态返回给机器人。这是必要的，因为机器人不会提前知道网格的状态。
您可以在搜索中应用启发式方法，从而增加到达标志的概率。
于 2011-03-19T12:36:41.317 回答
0
正如许多人所提到的，如果您知道自己在哪里以及您的目标在哪里，A* 对全球规划很有帮助。但是，如果您没有这种全局知识，那么您应该研究一类称为“错误”算法的算法。
至于探索，如果你想以最快的速度找到标志，取决于你的机器人可以看到多少本地邻域，你应该尽量不让这个邻域重叠。例如，如果您的机器人可以从各个方向看到它周围的一个单元格，则您应该每隔三列探索一次。（第 1、4、7 列等）。但是，如果机器人只能看到它当前占用的单元格，那么您可以做的最优化的事情就是不要返回您已经访问过的单元格。
于 2012-09-16T22:14:09.733 回答