A*算法生成的嘈杂路径

Question

我正在为一个机器人项目制作前端（一个“自主”汽车，它使用一些传感器和从SVG文件生成的地图进行本地化）。

为了使机器人可控，我们必须在当前位置和目标位置之间生成路径。我使用最简单的算法：A*算法。

但是我发现了一些奇怪的结果：汽车倾向于按45度的倍数行驶，并且还有一个特别令人烦恼的问题：一些生成的路径非常嘈杂！

请查看此示例中橙色矩形附近的嘈杂路径：

有没有办法避免这些奇怪/嘈杂的结果？最终，我们想要建立具有最小航向角更改次数的路径。（汽车可以旋转而无需移动，因此我们不需要任何路径“平滑处理”）。

这是我的A*实现：

def search(self, begin, goal):
    if goal.x not in range(self.width) or goal.y not in range(self.height):
        print "Goal is out of bound"
        return []
    elif not self.grid[begin.y][begin.x].reachable:
        print "Beginning is unreachable"
        return []
    elif not self.grid[goal.y][goal.x].reachable:
        print "Goal is unreachable"
        return []
    else:

        self.cl = set()
        self.ol = set()

        curCell = begin
        self.ol.add(curCell)

        while len(self.ol) > 0:

            # We choose the cell in the open list having the minimum score as our current cell
            curCell = min(self.ol, key = lambda x : x.f)

            # We add the current cell to the closed list
            self.ol.remove(curCell)
            self.cl.add(curCell)

            # We check the cell's (reachable) neighbours :
            neighbours = self.neighbours(curCell)

            for cell in neighbours:
                # If the goal is a neighbour cell :
                if cell == goal:
                    cell.parent = curCell
                    self.path = cell.path()
                    self.display()
                    self.clear()
                    return self.path
                elif cell not in self.cl:
                    # We process the cells that are not in the closed list
                    # (processing <-> calculating the "F" score)
                    cell.process(curCell, goal)

                    self.ol.add(cell)

编辑 1：根据广泛需求，这里是得分计算函数（过程）：

def process(self, parent, goal):
    self.parent = parent
    self.g = parent.distance(self)
    self.h = self.manhattanDistance(goal)
    self.f = self.g + self.h

编辑 这里是邻居方法（根据 user1884905 的答案进行了更新）：

def neighbours(self, cell, radius = 1, unreachables = False, diagonal = True):
    neighbours = set()
    for i in xrange(-radius, radius + 1):
        for j in xrange(-radius, radius + 1):
            x = cell.x + j
            y = cell.y + i
            if 0 <= y < self.height and 0 <= x < self.width and ( self.grid[y][x].reachable or unreachables ) and (diagonal or (x == cell.x or y == cell.y)) :
                neighbours.add(self.grid[y][x])

    return neighbours

这看起来很复杂，但实际上只是给出一个细胞的8个邻居（包括对角线邻居）；它还可以使用不同于1的半径，因为它用于其他功能。

并且可以根据是否使用对角线邻居进行距离计算 ：)

def manhattanDistance(self, cell):
    return abs(self.x - cell.x) + abs(self.y - cell.y)

def diagonalDistance(self, cell):

    xDist = abs(self.x - cell.x)
    yDist = abs(self.y - cell.y)

    if xDist > yDist:
        return 1.4 * yDist + (xDist - yDist)
    else:
        return 1.4 * xDist + (yDist - xDist)

- halflings

---

那是A*算法还是Dijkstra算法？你的启发式部分在哪里？ - TravellingGeek

看看这个pseudocode，它调用了一个heuristic_cost_estimate()函数。你的代码没有这样做，所以它找不到最短路径。 - martineau

@GeraldSv：我使用的启发式算法是“曼哈顿距离”，实际上它并没有在我发布的代码片段中显示（它在“process”函数中）。我马上就会发布那部分内容。 - halflings

Answer 1

似乎实现不正确，因为它移动到了距离目标最近（直线距离）但尚未检查的单元格上，而应该尝试并撤销路径以找到最优路径。请参见维基百科上的此nice animation以了解更多信息。

这里的问题与如何计算cell.f有关，也许在计算时没有添加当前单元格的分数，在一般情况下，A*应该采取这里标记为红色的步骤并生成次优路径。

由于空间被划分为离散的单元格，当连续世界中的最佳路径（总是直线距离）正好处于两个离散移动之间时，它会用那条奇怪的路径尽可能地逼近它。

我看到这里有两种方法：

1. 修复算法（此处为伪代码），使每个评估的单元格保持正确的距离值（在粘贴的代码中，没有关于如何计算cell.f的信息）。
2. 使用Djikstra，对当前算法进行少量更改即可轻松实现。事实上，A *只是其优化版本。

- Jacopofar

---

根据我的经验，Djikstra算法是最容易实现的。两种算法都会给出最短路径，因此不会有任何不必要的拐角。现在该算法会迭代直到找到障碍物，然后寻找新的单元格，但无法“撤消”路径，从而找到非最优路径。我建议实现Djikstra算法，它非常容易编写，并且可以轻松转换为A*（这是Djikstra的一种变体）。 - Jacopofar

“它正在移动到尚未检查的单元格，该单元格是最接近（直线距离）目标的单元格，但它应该在发现障碍物时尝试并撤消路径，以找到最优路径。” - 这句话是无意义的。您能解释一下您的意思吗？A *不会进行任何回溯。 - BlueRaja - Danny Pflughoeft

是的，它不会直接撤销路径。在第一阶段中，它计算单元格与目标的拓扑距离并构建路径树（使用维基百科伪代码中的came_from），然后使用此树从源到目标重构路径。我的意思是程序需要跟踪已探索的路径，否则将无法避开障碍物。 - Jacopofar

我仍然不明白我的实现有什么问题。正如您所看到的，我避开了障碍物，使用了启发式（曼哈顿距离），就像您给我的A*伪代码一样，并找到了看起来最短的路径。我最大的问题是有时会出现“嘈杂”的部分（特别是在迷宫中），以及路径的朝向角度始终是45°的倍数（8个可能的方向）。 - halflings

你避开了障碍物，但你找到的不是最优（最短）路径，因为那不是正确的A*实现。想象一下当它遇到一个C形障碍物时会发生什么：它会撞上它，然后沿着新单元格移动，直到路径“填满”它，最终避开它。要找到最优路径，你需要以某种方式存储你尝试过的内容（不仅是单个单元格，还包括路径），在这种情况下，可以使用维基百科伪代码的came_from属性或明确存储路径树的不同数据结构。 - Jacopofar

Answer 2

在没有看到你如何实现neighbour和distance函数的情况下，我仍然可以猜测出出了什么问题:

如果允许对角线遍历，则不应使用曼哈顿距离。

目标函数中的曼哈顿距离应该是到目标的最短距离的衡量标准。(如果您可以在建筑物块之间沿对角线行驶，则不是这样。)

最简单的解决方法是保留曼哈顿距离作为目标函数，并更改邻居的定义，只包括四个左右上下相邻的单元格。

编辑

你的代码仍然存在问题。以下伪代码摘自维基百科。我已经标记了你需要检查的重要行。您必须确保 i) 如果找到更好的解决方案，则正在更新开放集合中的节点，ii) 您始终考虑先前的旅行距离。

function A*(start,goal)
     closedset := the empty set    // The set of nodes already evaluated.
     openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
     came_from := the empty map    // The map of navigated nodes.

     g_score[start] := 0    // Cost from start along best known path.
     // Estimated total cost from start to goal through y.
     f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

     while openset is not empty
         current := the node in openset having the lowest f_score[] value
         if current = goal
             return reconstruct_path(came_from, goal)

         remove current from openset
         add current to closedset
         for each neighbor in neighbor_nodes(current)
             // -------------------------------------------------------------------
             // This is the way the tentative_g_score should be calculated.
             // Do you include the current g_score in your calculation parent.distance(self) ?
             tentative_g_score := g_score[current] + dist_between(current,neighbor)
             // ------------------------------------------------------------------- 
             if neighbor in closedset
                 if tentative_g_score >= g_score[neighbor]
                     continue

             // -------------------------------------------------------------------
             // You never make this comparrison
             if neighbor not in openset or tentative_g_score < g_score[neighbor]
             // -------------------------------------------------------------------
                 came_from[neighbor] := current
                 g_score[neighbor] := tentative_g_score
                 f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                 if neighbor not in openset
                     add neighbor to openset

     return failure

 function reconstruct_path(came_from, current_node)
     if current_node in came_from
         p := reconstruct_path(came_from, came_from[current_node])
         return (p + current_node)
     else
         return current_node

- user1884905

---

我刚试着移除了对角邻居，确实消除了所有障碍物边界的丑陋结果。但现在的问题是路径中有太多的“走样”。是否有一种方法可以兼顾两者的优点，或者我应该在生成的路径上进行一些反走样处理？结果的屏幕截图：http://i.imgur.com/oUr6S4f.jpg（顺便说一句，我为所有障碍物添加了“边框”以避免碰撞） - halflings

我也尝试了使用不同的启发式方法（对角线距离，详见：http://rocketmandevelopment.com/2010/11/09/a-star-heuristics/）；它比曼哈顿距离的对角线效果要好得多（考虑到所有事情，曼哈顿距离的对角线是一件愚蠢的事情），但我仍然会时不时地遇到一些噪音和奇怪的结果：http://i.imgur.com/jfEhgmy.jpg有什么想法吗？ - halflings

太好了 :-)！我认为问题出在我忘记做最后一部分（邻居不在开放集中，然后比较“g”成本）。而且我一直认为“g”代表从父级到单元格的移动成本，而不是整个移动成本。现在情况好多了：http://i.imgur.com/hVic3cX.jpg 奇怪的是，大多数情况下使用曼哈顿距离而不是对角线启发式会得到更短的路径：http://imgur.com/z4wJs8b - halflings

@halflings 很好，你让它工作了！找到的解决方案的长度应该是最小的。但是当有多条路径长度相等时，它可能不会从你的角度选择最优路径，即具有最少转弯的最平滑解决方案。相反，它将尽可能地沿着物体的边界向目标绘制，每一步都会遵循这个规则。例如，在路径末端附近，可以看到一个跟随椭圆形物体的抖动路径（在你的第一张图中）。 - user1884905