2
\$\begingroup\$

I'm currently having difficulty reasoning about how multiple prerequisites are satisfied using the A* algorithm during planning.

Assuming the following actions (with prerequisites in brackets):

Get Material

Make Gloves (need material)

Get Iron

Make Axe (needs iron)

And the following goal (prerequisites in brackets):

Chop Tree (needs gloves, needs axe)

Now, assuming I am doing a backward search from the goal, as I understand it, I would start considering actions that have effects that directly correspond to the prerequisites of the node (this is where I think I'm going wrong).

The problem with that is, the first 2 actions to consider are Make Gloves and Make Axe. However, for this goal to be satisfied they both need to be done. If I only build my graph by linking effects to prerequisites, I only consider each of those actions once, and only choose one.

I.e. if I arbitrarily choose Make Axe that leads me to Get Iron, I don't have anything making me reconsider Make Gloves as Get Iron has no prerequisites.

For the actions and goal I had above there are many routes to solving it, below I have highlighted one to illustrate my point. As you can see, in this case I would need Get Iron to be done after Make Gloves even though their effects/prerequisites don't match in any way.

plan

Can someone tell me where I'm going wrong in my thinking?

\$\endgroup\$
4
\$\begingroup\$

It looks like you've constructed your graph incorrectly. You have actions as nodes and states as edges, when it should be the other way around: states as nodes and actions as edges.

Graph search algorithms don't work with state directly. To deal with state, you need to transform the state into equivalent graph nodes, which can lead to lots of new nodes being added so that all possible states are covered. In your example, you'd actually have to add in nodes to cover all the permutations of "gloves", "axe":

  • No gloves, no axe
  • Gloves, no axe
  • No gloves, axe
  • Gloves, axe

And the only path to the final Chop Tree node is from the last state, "gloves, axe".

So your actual graph would look something like this:

states

(There could be more, if you ever want to model the cloth/iron states too)

Personally I prefer a simpler approach, especially since in this case it's not clear to me why you need A*. Here's a decision-tree-based approach: https://gamedev.stackexchange.com/a/93134/26250

\$\endgroup\$
  • \$\begingroup\$ thank you! Seems obvious when explained. I have used decision trees in the past but just looking at an alternative approach using GOAP. The main reason I'm using A* is to be able to take into account the cost of actions. Right now it's nothing more than an attempt to implement Jeff Orkin's papers on it. \$\endgroup\$ – rbhalla Mar 21 '17 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.