机器人探索算法
ark*_*ark 21 algorithm robotics artificial-intelligence
我正在尝试为机器人设计一种算法,试图找到一个位于包含障碍物的世界中的旗帜(位于未知位置).机器人的任务是捕获旗帜并将其带到他的家乡(代表他的起始位置).机器人,在每一步,只看到一个有限的邻居(他不知道世界如何提前看),但他有无限的记忆来存储已经访问过的细胞.
我正在寻找有关如何以有效方式执行此操作的任何建议.特别是第一部分; 即到达国旗.
简单的广度优先搜索/深度优先搜索将起作用,尽管速度很慢.确保防止机器人多次检查具有相同方形的路径,因为这将导致这些算法在标准情况下运行更长时间,并且无法在无法到达标志的情况下运行.
A*是更优雅的方法,特别是如果你知道旗帜相对于你自己的位置.维基百科,按照惯例,在解释它方面做得不错.使用的经典启发式是到目的地的人员距离(假设没有障碍的移动次数).
这些算法对于回程非常有用 - 而不是"寻找旗帜"部分.
编辑: 这些方法涉及创建在地图上表示方块的对象,并创建"路径"或一系列方块(或要采取的步骤).一旦你构建了一个表示你的方块的框架,那么使用什么样的搜索的问题变得不那么令人生畏了.
这个类需要能够得到相邻方块的列表,并知道它是否可以遍历.
考虑到您没有所有信息,请尝试将未探测的图块视为可遍历,如果发现它们不是,则重新计算.
编辑: 至于为未知对象搜索未知区域...
您可以使用像Pledge算法之类的东西,直到找到空间的边界,记录所有信息.然后使用您最喜欢的漂移/寻路算法查看所有看不见的方块.如果,在任何时候,你看到旗帜,停止你正在做的事情,并使用你最喜欢的寻路算法回家.