Regressive Goal Oriented Action Planning

Question

I am currently trying to regressively search from a goal state to find out a list of actions that will achieve the goal state for my GOAP planner. So far, the pseudocode for what I have down goes like this:

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]);
                    }
                }
            }
        }
    }
}

I hear that GOAP is exactly like an A* algorithm only that the node is the state and the edges are the actions. But since in an A*, there aren't any conditions a node has to fulfill, it rather confused me on how to adapt an A* algorithm to work with preconditions. What I'm struggling to understand is how to store the actions and compare the cost of the actions in order to find the most efficient path. If we assume that the class action has a function getCost() which returns the cost of the action, how would I go about this while considering preconditions?

Answer 1

Nodes are indeed WorldStates. And Edges are actions. But note that they are directed edges!

Where the pre-conditions come in: They determine which edges (actions) flow out of the node. Only actions that have their pre conditions met, are valid edges exiting that state node.

So for finding the neighbours of a node, you would check each action if all pre-conditions are met. If so, apply the postconditions to see the node that the action will lead to. The action is then a valid edge between these states (nodes.)

Please see the open sourced GPGOAP (General Purpose Goal Oriented Action Planning) for an implementation of GOAP with A*. It's straightforward code in C that explain all the steps. I am the author of GPGOAP.

Thoughts on regression

Now for the regressive part: I've never implemented a backward search from goal to current world state. So I can be of limited help on that front.

Two neighbouring nodes will still be connected on the basis of one single action. You now enable/disable edges not based on precondition of the action, but the post-condition of the action. If the post condition does not match the current node, then the action will not be valid. If it does, I expect you add the neighbour by forcing the pre-condition of the action.

What's your reason to prefer backwards search over forward search?