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

Question

我正在开发一个机器人项目，它必须找到通往某个物体的路径，并在前往它必须捡起的那个物体时避开一些障碍。

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

我曾尝试在障碍物中添加更多不可行走的区域，但效果并不总是很好。它仍然与障碍物发生碰撞，并且在不允许行走的地方添加了太多的点，导致它没有可以运行的路径。

对于如何解决这个问题，您有什么建议吗？

编辑:

所以我按照 Justin L 的建议做了，在导致以下结果的障碍周围增加了很多成本: Grid with no path http://sogaard.us/uploades/1_grid_no_path.png

在这里你可以看到障碍物周围的成本，最初中间的两个障碍物看起来应该和角落里的一样，但是在运行我们的探路器之后，成本似乎被覆盖了:

Grid with path http://sogaard.us/uploades/1_map_grid.png

Picture that shows things found on the picture http://sogaard.us/uploades/2_complete_map.png

上图显示了图片上找到的东西。

Path found http://sogaard.us/uploades/3_path.png

这是找到的路径，因为我们的问题也是之前遇到的障碍。

The grid from before with the path on http://sogaard.us/uploades/4_mg_path.png

还有另一张带有路径的成本 map 的图片。

所以我觉得奇怪的是为什么 A* 探路者覆盖了这些非常高的字段成本。

会不会是在用current field对open list里面的节点进行求值的时候，看current fields的路径是否比open list里面的路径短？

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

探路者.cs:http://pastebin.org/343774

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* 应用于像素映射 map ；几乎总是，瓷砖。

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

此外，您可以尝试降低用于 A* 的最短距离启发式算法的值(value)。