Нужны изменения в алгоритме A *, чтобы он работал с ротацией агента

Question

Я пишу простой 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)

Answer 1

Основная проблема здесь заключается в том, что алгоритм A * должен учитывать тот факт, что существует различие между «нахождением в положении (x, y), обращенным в направлении d ₁ » и «бытием в положении (x, y), обращенном в направлении d ₂ . " Если алгоритм этого не знает, он не сможет дать вам лучший набор инструкций, которым нужно следовать.

Один из способов решения этой проблемы - представить, что ваш мир - это не 2D-сетка, а 3D-пространство, состоящее из четырех копий 2D-сетки, уложенных друг на друга. Так же, как ваша позиция в 2D-пространстве состоит из вашей текущей координаты (x, y), ваша позиция в 3D-пространстве состоит из вашей текущей координаты (x, y) в сочетании с направлением, с которым вы сталкиваетесь.

Представьте, что значит перемещаться в этом пространстве. У вас есть два варианта действия, которое вы можете предпринять - «двигаться» или «повернуть на 90 градусов»; Действие «перемещение» переместит вас на один шаг вперед в текущем 2D-срезе, в котором вы находитесь, где «вперед» имеет другое значение в зависимости от того, в каком срезе вы находитесь. Другими словами, «перемещение» заставит вас двигаться чисто в плоскости X / Y, сохраняя ваше направление фиксированным. Операция "поворота" сохранит ваше положение X / Y фиксированным, но изменит плоскость, в которой вы находитесь (в зависимости от того, в каком направлении вы оказались в данный момент).

Если вы явно закодируете эту информацию в своем поиске, A * может использовать ее, чтобы найти лучший путь для вас. Вам нужно будет определить новую эвристику, которая оценивает расстояние до цели. Один из вариантов - предположить, что стен нет, и определить, сколько шагов вам нужно сделать, плюс количество вращений, необходимых для достижения цели. На этом этапе A * может дать вам лучший путь, по которому следует использовать эвристику для поиска.

В целом, многие проблемы вида «У меня есть положение в мире плюс некоторые дополнительные состояния (ориентация, скорость и т. Д.)» Могут быть преобразованы из поиска пути в 2D-пространстве в поиск пути в 3D-пространстве, где ваш третий измерение будет той дополнительной информацией. Или, возможно, он займет до 4D или 5D места, если у вас есть несколько дополнительных частей информации.

Надеюсь, это поможет!

Answer 2

Первое, что нужно сделать, это разделить исходный код на две функции: прямую модель агента и сам алгоритм планирования (пути).В форвардной модели указано, что у агента есть три возможных действия (форвард, роттелфт, ротрайт).Планировщик A * создает игровое дерево для агента.Возможная последовательность: влево, вперед, вперед.

Это не классическая задача планирования пути, а проблема планирования ИИ.Реализация такой двухслойной системы более сложна по сравнению с обычным алгоритмом поиска пути A *, потому что действие поворота не приближает агента к цели.Решить сложнее, если смоделированное действие улучшило ситуацию или было шагом назад.

В сценарии реальной жизни даже описанное разделение на прямую модель и планировщик не решит проблему, потому чтоПространство состояний на карте будет расти очень быстро.Дополнительная эвристика необходима для направления планировщика A * в оптимальном направлении.