需要更改A *算法,以便它可以旋转代理

问题描述 投票:1回答:2

我正在编写一个简单的A *算法来寻找最短路径。但我需要更复杂的东西。代理人只能前进并旋转(90度)。它会影响路径还是我可以使用简单的A *?谢谢大家。


def astar(maze, start, end):

    start_node = Node(None, start)
    start_node.g = start_node.h = start_node.f = 0
    end_node = Node(None, end)
    end_node.g = end_node.h = end_node.f = 0

    open_list = []
    closed_list = []

    open_list.append(start_node)
    while len(open_list) > 0:
        current_node = open_list[0]
        current_index = 0
        for index, item in enumerate(open_list):
            if item.f < current_node.f:
                current_node = item
                current_index = index

        open_list.pop(current_index)
        closed_list.append(current_node)
        if current_node == end_node:
            path = []
            current = current_node
            while current is not None:
                path.append(current.position)
                current = current.parent
            return path[::-1]
        children = []
        for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
            node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
            if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (len(maze[len(maze)-1]) -1) or node_position[1] < 0:
                continue
            if maze[node_position[0]][node_position[1]] != 0:
                continue
            new_node = Node(current_node, node_position)
            children.append(new_node)
        for child in children:
            for closed_child in closed_list:
                if child == closed_child:
                    continue
            child.g = current_node.g + 1
            child.h = ((child.position[0] - end_node.position[0]) ** 2) + ((child.position[1] - end_node.position[1]) ** 2)
            child.f = child.g + child.h
            for open_node in open_list:
                if child == open_node and child.g > open_node.g:
                    continue
            open_list.append(child)

python artificial-intelligence path-finding
2个回答
1
投票

这里的主要问题是需要让A *算法意识到“面向方向d1的位置(x,y)”和面向方向的位置(x,y)之间存在差异这一事实D2“。如果算法不知道这一点,它就无法回复你要遵循的最佳指令系列。

您可以解决这个问题的一种方法是想象您的世界不是2D网格,而是实际上是一个3D空间,其中包含四个堆叠在一起的2D网格副本。就像您在2D空间中的位置由当前(x,y)坐标组成一样,您在3D空间中的位置由您当前的(x,y)坐标组成,并与您所面对的方向相结合。

想象一下在这个空间里走动意味着什么。您可以采取两种方式进行操作 - “移动”或“转90°”“移动”操作会使您在当前的2D切片中向前移动一步,其中“前进”具有不同的含义在你所在的切片上。换句话说,“移动”将使你纯粹在X / Y平面内移动,保持你的方向固定。 “转弯”操作将使您的X / Y位置保持固定,但会改变您所在的平面(根据您当时正面临的方向)。

如果您将此信息明确地编码到搜索中,那么A *可以使用它来找到您最佳路径。您需要定义一些估计目标距离的新启发式算法。一种选择是假设没有墙壁,并确定你需要采取多少步骤,加上所需的旋转次数,以达到目标。此时,A *可以为您提供最佳路径,使用您的启发式方法来指导其搜索。

更一般地,“我在世界上有一个位置,加上一些额外的状态(方向,速度等)”形式的许多问题可以从2D空间中的寻路转换为3D空间中的寻路,其中你的第三个维度将是额外的信息。或者如果您有多个额外的信息,它可能会达到4D或5D空间。

希望这可以帮助!


0
投票

首先要做的是将源代码分为两个函数:代理的正向模型和(路径)规划算法本身。在前向模型中,指定了代理有三种可能的动作(前进,左转,旋转)。 A *规划器为代理创建游戏树。可能的顺序是:左,前,前。

这不是经典的路径规划问题,而是人工智能规划问题。实现这样的双层系统比通常的A *寻路算法更复杂,因为旋转动作不会使代理更接近目标。如果模拟动作改善了情况或者向后退了一步,则决定更复杂。

在现实生活场景中,即使所描述的前向模型和规划器的分离也无法解决问题,因为地图中的状态空间会非常快速地增长。需要额外的启发式方法来指导A *规划者进入最佳方向。

© www.soinside.com 2019 - 2024. All rights reserved.