A*探路者障碍物碰撞问题

Question

我正在开发一个带有机器人的项目,该机器人必须找到一个物体,并在去往它必须拾取的物体时避免一些障碍物.

问题在于机器人和机器人需要拾取的物体在探路者中都是一个像素宽.实际上它们要大得多.通常A*探路者选择沿着障碍物的边缘放置路线,有时会使它与它们发生碰撞,我们不希望这样做.

我试图在障碍物上增加一些不可行走的领域,但它并不总是很好.它仍然与障碍物碰撞,在不允许行走的情况下添加太多点,导致它没有可以运行的路径.

你有什么建议可以解决这个问题吗？

编辑:

所以我按照Justin L的建议,在障碍物周围增加了大量成本,这导致了堕落: 没有路径的网格http://sogaard.us/uploades/1_grid_no_path.png

在这里你可以看到障碍物周围的成本,最初中间的两个障碍物看起来就像角落里的障碍物,但是在运行我们的探路者后,似乎成本被覆盖了:

上图显示了图片上的内容.

这是发现的路径,因为我们的问题也是在拥抱障碍之前.

另一张带有路径的成本地图的图片.

所以我觉得奇怪的是A*探路者为什么要压倒这些非常高的现场成本.

是不是当它使用当前字段评估打开列表中的节点时,看当前字段路径是否比打开列表中的路径短？

这是我用于探路者的代码:

Field.cs和Grid.cs:http://pastebin.org/343775

Answer 1

您是否考虑过向物体附近的像素添加梯度成本？

也许就像线性渐变一样简单：

C = -mx + b

其中 x 是到最近物体的距离，b 是边界外的成本，m 是成本消失的速率。当然，如果C为负数，则应设置为0。

也许是一个简单的双曲线衰变

C = b/x

其中 b 又是边界之外的所需成本。一旦达到某个低点，就将其截止为 0。

或者，您可以使用指数衰减

C = k e^(-hx)

其中 k 是缩放常数，h 是衰减率。再说一遍，有一个截止点是明智的。

第二个建议

我从未将 A* 应用于像素映射地图；几乎总是，瓷砖。

您可以尝试大幅降低瓷砖的“分辨率”吗？也许每 10×10 或 20×20 像素组有一个图块；图块的成本是图块中像素的最高成本。

另外，您可以尝试降低用于 A* 的最短距离启发式的值。