How do I incorporate variables in GOAP when planning regressively from the goal?

Question

I am looking at and reading resources like this:

and this:

I have made a forward-searching planner using A*; but am now trying to search backwards for the efficiency gains.

Orkin specifically says

The planning example illustrated in Figure 2 consists of actions that have constant Boolean values for preconditions and effects, but it is important to point out that preconditions and effects can also represented by variables. The planner solves for these variables as it regresses from the goal. Variables add power and flexibility to the planner, as it can now satisfy more general preconditions. For instance, a Goto action with the effect of moving a character to a variable destination is far more powerful than a Goto action that moves to a constant, predetermined location.

So I'm not attempting to visualise this prior to implementing it; but I cannot work out how to solve the variables moving away from where they're needed:

        KEY             CURRENT     GOAL

    itemStockpiled      false       true
    ------------------------------------------

                StockpileItem       Effect:     itemStockpiled true
                                    Precond:    hasItem ?itemId?     **** How can I test this?
                                                agentAtPosition ?stockPos?

    itemStockpiled      true        true
    hasItem             0           ?itemId?
    agentAtPosition     ???         ?stockPos?
    ------------------------------------------

                Goto                Effect:     agentAtPosition ?stockPos?  **** Where is this?

    itemStockpiled      true        true
    hasItem             0           ?itemId?
    agentAtPosition     ?stockPos?  ?stockPos?
    ------------------------------------------

                PickupItem          Effect:     hasItem ?itemId?
                                    Precond:    agentAtPosition ?itemPos?

    itemStockpiled      true        true
    hasItem             ?itemId?    ?itemId?
    agentAtPosition     ?stockPos?  ?itemPos?      **** So we need to go 
                                                   back to the item from
                                                   the stockpile pos
    ------------------------------------------

                Goto                Effect:     agentAtPosition ?itemPos?    **** Where is this?
                                    Precond:    foundItem true

    itemStockpiled      true        true
    hasItem             ?itemId?    ?itemId?
    agentAtPosition     ?itemPos?  ?itemPos?
    foundItem           false       true
    ------------------------------------------

                FindItem            Effect: foundItem true

    itemStockpiled      true        true
    hasItem             ?itemId?    ?itemId?
    agentAtPosition     ?itemPos?  ?itemPos?
    foundItem           true       true
    ------------------------------------------

You'll see how in the above comments, I don't understand how I can check for things like an existance of a path, before I know where I'm finding a path too. For the item, I imaging I can have a boolean flag of "hasItem", and keep track of the itemId in a variable that isn't populated until FindItem is successful (and then used when executing the path); but how would this work with a GoTo action?

If I use a world-state variable "agentAtPosition" as an effect for Goto; it will be set at two different points in the plan; meaning that subsequent actions that need "agentAtPosition" to be true will already have their preconditions met, effectively ending the planning, erroneously thinking it found a path:

        KEY             CURRENT     GOAL

    itemStockpiled      false       true
    ------------------------------------------

                StockpileItem       Effect:     itemStockpiled true
                                    Precond:    hasItem true
                                                agentAtPosition true

    itemStockpiled      true        true
    hasItem             false       true
    agentAtPosition     false       true
    ------------------------------------------

                Goto                Effect:     agentAtPosition true

    itemStockpiled      true        true
    hasItem             false       true
    agentAtPosition     true        true
    ------------------------------------------

                PickupItem          Effect:     hasItem true
                                    Precond:    agentAtPosition true

    itemStockpiled      true        true
    hasItem             true        true
    agentAtPosition     true        true
    ------------------------------------------

How do I work around this?

hectorpal hectorpal · Accepted Answer · 2020-06-01T13:17:09

So, it seems GOPA is this: http://alumni.media.mit.edu/~jorkin/goap.html. I'd have linked the reference.

I don't understand what's you are trying to do and the paragraph you quote from "Orkin" (that I don't know about). However, this part is only an intuition:

Variables add power and flexibility to the planner, as it can now satisfy more general preconditions.

One must distinguish between changing the problem and changing the solution. If you implemented an A* forward search algorithm, then implementing full regression is a matter of implementing the regression operation of A over state s: the partial states s' that must have come before s is such that: - the preconditions of A were true in s' - the effects of A are consistent with s - A is relevant for getting from s' to s. If there are no negative preconditions, then there is at least one p in add(A) that is not in s' but is in s.

Now, "adding variables" sounds like reformulating the problem. In that case, the main question is: - is that reformulation preserving all the paths? If not, it should merge some paths in a precise way. Otherwise, it's not a reformulation.

So, the first question is not about forward or backward search, is about confirming what are the possible paths. If the possible paths are correct, then regression should work.

Unless you are actually trying to do something smarter like not bounding objects until necessary.

I suggest 1st focusing on a simpler version where standard regression make sense, and then revisit what you want to do.

How do I incorporate variables in GOAP when planning regressively from the goal?

1 Answers