Регрессивное целенаправленное планирование действий

Question

В настоящее время я пытаюсь регрессивно искать из состояния цели, чтобы найти список действий, которые достигнут состояния цели для моего планировщика GOAP. Пока что псевдокод того, что у меня есть, выглядит так:

closedList = list;
s = stack;
s.push(goal);
while(s.size() > 0)
{
    state = s.pop;
    if(!state exists in closedList)
    {
        closedList.add(state);
        for(action = firstAction; action != lastAction; action = nextAction)
        {
            if(action.getEffect() == state)
            {
                if(!action.ConditionsFulfilled())
                {
                    conditionList = action.getConditions;
                    for(i = 0; i < conditionList.size(); i++)
                    {
                        s.push(conditionList[i]);
                    }
                }
            }
        }
    }
}

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

Answer 1

Узлы действительно WorldStates. И края это действия. Но обратите внимание, что они направлены краями!

Где вступают предварительные условия: они определяют, какие ребра (действия) вытекают из узла. Только действия, для которых выполнены их предварительные условия, являются действительными ребрами, выходящими из этого узла состояния.

Таким образом, для поиска соседей узла вы должны проверить каждое действие, если выполнены все предварительные условия. Если это так, примените постусловия, чтобы увидеть узел, к которому приведет действие. Действие является действительным краем между этими состояниями (узлами).

Пожалуйста, ознакомьтесь с GPGOAP с открытым исходным кодом (Планирование действий, ориентированное на достижение общих целей) для реализации GOAP с A*. Это простой код на C, который объясняет все шаги. Я автор GPGOAP.

Мысли о регрессе

Теперь о регрессивной части: я никогда не осуществлял обратный поиск от цели к текущему состоянию мира. Так что я могу оказать ограниченную помощь на этом фронте.

Два соседних узла все равно будут связаны на основе одного единственного действия. Теперь вы можете включить / отключить ребра не на основе предварительного условия действия, а на последующем условии действия. Если условие публикации не соответствует текущему узлу, действие не будет действительным. Если это произойдет, я ожидаю, что вы добавите соседа, заставив предварительное условие действия.

По какой причине вы предпочитаете поиск назад, а не вперед?