回归目标导向行动计划

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* 算法以处理前提条件。我很难理解的是如何存储动作并比较动作的成本以找到最有效的路径。如果我们假设 class 操作有一个函数 getCost() ，其中 returns 操作的成本，在考虑先决条件的同时我将如何处理？

Answer 1

节点确实是WorldStates。边是动作。但请注意，它们是有向边！

先决条件的来源：它们确定哪些边（动作）流出节点。只有满足前提条件的动作才是退出该状态节点的有效边。

因此，为了找到一个节点的邻居，如果满足所有先决条件，您将检查每个操作。如果是这样，应用 post 条件来查看操作将导致的节点。然后该动作是这些状态（节点）之间的有效边缘。

请参阅开源 GPGOAP（通用目标导向行动计划）以了解具有 A* 的 GOAP 的实施。这是解释所有步骤的简单 C 代码。我是GPGOAP的作者。

关于回归的思考

现在是回归部分：我从未实施过从目标到当前世界状态的反向搜索。所以我在这方面能提供的帮助有限。

两个相邻节点仍然会在一个动作的基础上连接起来。您现在 enable/disable 边缘不是基于动作的前提条件，而是基于动作的 post 条件。如果 post 条件与当前节点不匹配，则该操作将无效。如果是这样，我希望您通过强制操作的先决条件来添加邻居。

您更喜欢向后搜索而不是向前搜索的原因是什么？

回归目标导向行动计划

Regressive Goal Oriented Action Planning

algorithm

planning

artificial-intelligence

regression

depth-first-search