algorithm - 在走廊寻找星路

Question

我正在为走廊内的移动机器人寻路实施 A*。到目前为止，路径是在走廊内生成的，但它会沿着障碍物的所有边缘向右滑动，但我更喜欢路径应该位于走廊的中间。1.是否有任何平滑算法可以做到这一点？2.如何包括转向约束，以便我可以获得现实/可行的路径？3.如何对“转弯”进行惩罚以避免曲折路径。

由于我是 A* 算法的新手，我发现上述问题很困难。参考任何链接，也欢迎书籍..谢谢..

Answer 1

您可以通过将其缩小 1 格来预先形成运行 A* 的字段，以便与 4 路邻域中无法通行的单元格相邻的单元格将变得无法通行。然后你得到的 A* 路径将更靠近走廊的中心。当然，有几条走廊可能会完全无法通行，但这是意料之中的，因为我们实际上是在模拟一个 3x3 十字形机器人绕着网格走动，而 3x3 十字形无法通过 2xN 路径。

关于增加转弯成本 - 您必须将当前方向添加到包含 A* 数据的数组中，并实现一个双参数函数，该函数将为（旧方向，新方向）一对参数返回一个非负值。说，“如果 old_direction 不等于新方向，则返回 1，否则返回 0”。然后将该函数的结果添加到您为 A* 迭代的每个步骤计算的任何成本中。

Answer 2

您可以简单地将可用区域限制在走廊的中间。