Astar和Dstar生成路径不同

Question

Astar：假设搜索过程中地图环境信息不发生任何变化，一旦在搜索过程中环境信息发生变化，则需要重新运行A*算法进行重规划。
Dstar：算法能够在重规划阶段利用前一次规划过程中已展开的中间状态节点，提高了动态环境下的规划效率。
Astar和Dstar对于相同的障碍物图，生成的最短路径为何差别如此之大？
Astar生成的路径图：

Dstar生成的路径图：

Answer 1

引自免费微信小程序：皆我百晓生

A* 和 D* 算法都是用于解决路径规划问题的寻路算法，它们都试图找到从起点到终点的最短路径。然而，两者之间存在一些关键的区别，这可能导致它们在某些情况下生成不同的路径。

A* 算法基于启发式搜索，它使用一个评价函数（通常是曼哈顿距离或欧几里得距离加上从当前节点到目标节点的直觉距离）来指导搜索过程。在给定的地图上，A* 会按照评价函数的值选择下一个要扩展的节点。当环境改变时，由于之前计算的评价函数不再适用，A* 必须从头开始计算。

D* 算法则是一种增量式路径规划算法，它允许在环境中发生变化时快速更新路径。D* 使用了开销（cost-to-come）的概念，即从起始点到每个节点的实际成本，以及估计开销（cost-to-go），即从每个节点到目标节点的预期成本。当环境发生变化时，D* 只需重新计算受影响节点的成本，并且利用之前已经展开的节点信息进行更新，因此可以更快地得到新的最短路径。

A* 和 D* 的主要区别在于它们如何处理变化的环境和如何存储与更新信息。由于这些差异，它们可能会在相同障碍物布局的情况下产生不同的路径。为了具体分析为什么在特定场景下路径不同，我们需要查看具体的地图和算法实现细节。

不过，我可以提供一个简化的 A* 和 D* 算法的 Python 实现，以便你可以更好地理解它们的工作原理。注意，这里的实现并不包括对环境变化的处理，因为这将涉及到更复杂的逻辑。如果你想看到包含环境变化处理的完整实现，可能需要查阅专门的文献或开源库。

这是一个简单的 A* 算法实现：

import heapq

def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def a_star_search(graph, start, goal):
    queue = [(heuristic(start, goal), start)]
    came_from = {start: None}
    g_score = {node: float('inf') for node in graph.nodes}
    g_score[start] = 0

    while queue:
        _, current = heapq.heappop(queue)

        if current == goal:
            break

        for neighbor in graph.neighbors(current):
            tentative_g_score = g_score[current] + graph.cost(current, neighbor)
            if tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score = tentative_g_score + heuristic(neighbor, goal)
                heapq.heappush(queue, (f_score, neighbor))

    return came_from, g_score

# 假设你已经有了一个表示地图的类 Graph 和其邻居、成本等方法

接下来是一个简化的 D* 算法实现：

class Node:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.parent = None
        self.g_score = float('inf')
        self.h_score = 0
        self.f_score = float('inf')

def d_star_search(graph, start, goal):
    nodes = [Node(x, y) for x in range(graph.width) for y in range(graph.height)]
    start_node = nodes[start[0], start[1]]
    start_node.g_score = 0
    start_node.h_score = heuristic(start, goal)
    open_set = [start_node]
    closed_set = set()

    while open_set:
        current = min(open_set, key=lambda n: n.f_score)
        open_set.remove(current)
        closed_set.add(current)

        if current == goal:
            path = []
            while current:
                path.append((current.x, current.y))
                current = current.parent
            return path[::-1]

        for neighbor in graph.neighbors(current.x, current.y):
            if neighbor in closed_set:
                continue

            tentative_g_score = current.g_score + graph.cost(current, neighbor)
            if neighbor not in open_set or tentative_g_score < neighbor.g_score:
                neighbor.g_score = tentative_g_score
                neighbor.h_score = heuristic(neighbor, goal)
                neighbor.f_score = neighbor.g_score + neighbor.h_score
                neighbor.parent = current
                if neighbor not in open_set:
                    open_set.append(neighbor)

    raise ValueError("No path found")

# 同样，你需要有一个表示地图的类 Graph 和其邻居、成本等方法

你可以根据这些基础实现调整为适应你的地图数据结构，并比较在给定地图上的结果。如果你能提供具体的地图数据和起始/目标位置，我可以进一步分析为什么它们会产生不同的路径。