机器人探索算法 [英] Robot exploration algorithm

问题描述

我想设计一个算法的机器人试图找到标志（设置在未知地点），它位于含障碍的世界。机器人的任务是夺旗，并把它带到了他的家基地（其中重presents他的首发位置）。机器人，在每一步，只能看到有限的居委会（他不知道这个世界是如何看起来提前），但他有无限的内存来存储已经访问过的细胞。

I'm trying to devise an algorithm for a robot trying to find the flag(positioned at unknown location), which is located in a world containing obstacles. Robot's mission is to capture the flag and bring it to his home base(which represents his starting position). Robot, at each step, sees only a limited neighbourhood (he does not know how the world looks in advance), but he has an unlimited memory to store already visited cells.

我在寻找如何做到这一点有效的方式的任何建议。特别是第一部分;即获得该标志。

I'm looking for any suggestions about how to do this in an efficient manner. Especially the first part; namely getting to the flag.

推荐答案

一个简单的广度优先搜索/深度优先搜索将工作，尽管速度缓慢。一定要prevent从检查具有相同方多次的路径，因为这将导致这些算法，以更长的时间在标准情况下运行，而无止境的标志是无法达成的情况下，机器人。

A simple Breadth First Search/Depth First Search will work, albeit slowly. Be sure to prevent the bot from checking paths that have the same square multiple times, as this will cause these algorithms to run much longer in standard cases, and indefinitely in the case of the flag being unable to be reached.

A *是更好的方法，特别是如果你知道相对于你自己的标志的位置。 维基百科，按照往常一样，做一个体面的工作与解释它。经典的启发式使用的是曼宁距离（许多招式假设没有障碍）到目的地。

A* is the more elegant approach, especially if you know the location of the flag relative to yourself. Wikipedia, as per usual, does a decent job with explaining it. The classic heuristic to use is the manning distance (number of moves assuming no obstacles) to the destination.

这些算法是回程有用的 - 没有那么多的寻找标志部分

These algorithms are useful for the return trip - not so much the "finding the flag" part.

编辑： 这些方法涉及到创建重新presents广场在地图上的对象，以及创建路径或一系列广场打（或要采取的措施）。一旦你建立再$ P $的框架psenting您的方形，使用什么样的搜索成为一个更艰巨的任务。这个问题

These approaches involve creating objects that represents squares on your map, and creating "paths" or series of square to hit (or steps to take). Once you build a framework for representing your square, the problem of what kind of search to use becomes a much less daunting task.

这个类需要能够得到相邻的方块的列表并知道这是否是穿越。

This class will need to be able to get a list of adjacent squares and know if it is traversable.

考虑到你没有所有的信息，尽量只处理未开发的地砖为穿越，并重新计算如果您发现事实并非如此。

Considering that you don't have all information, try just treating unexplored tiles as traversable, and recomputing if you find they aren't.

编辑： 至于对不明物体seaching一个未知的领域...

As for seaching an unknown area for an unknown object...

您可以使用类似质押算法，直到你找到的边界您空间，记录所有的信息，当您去。然后去看看使用您喜欢的漂移/寻路算法都看不见广场。如果，在任何时候长了，你看升旗，停止你正在做什么，用你喜欢的寻路算法回家。

You can use something like Pledge's algorithm until you've found the boundaries of your space, recording all information as you go. Then go have a look at all unseen squares using your favorite drift/pathfinding algorithm. If, at any point long the way, you see the flag, stop what you're doing and use your favorite pathfinding algorithm to go home.

这篇关于机器人探索算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！