Realtime Goal Oriented Action Planning

Question

I've recently discovered GOAP and interested in implementing it for the AI in a game I'm developing. Something I'm stuck on at the moment, is determining when to plan. I've read through an MIT paper on it:

http://alumni.media.mit.edu/~jorkin/GOAP_draft_AIWisdom2_2003.pdf

It mentions real-time planning and specifically:

The character follows this plan to completion, invalidation, or until another goal becomes more relevant

Should I then be planning every frame until a new plan is deemed better (lower cost)?

And if not, if I have multiple goals but pre-requisites for one goal are only met in the middle of a plan for another goal, when would be appropriate to re-evaluate?

Answer 1

It's pretty dependent on what your goals and planning are. If you look at the real-time case where replanning would create a new goal,

The character follows this plan ... until another goal becomes more relevant

The answer will depend on your goals and how often they change. If the goals change every frame, then it is reasonable to plan every frame. If your goals change rarely, then planning only makes sense when certain events occur.

I have multiple goals but pre-requisites for one goal are only met in the middle of a plan for another goal

This could be implemented by only doing the planning phase only at the time when a potential pre-requisite condition is met.

Answer 2

Planning every frame is almost certainly overkill.

So planning only when an action fails, or a goal changes makes sense.

However, I would also re-plan every few seconds, even if the goal did not change. This will make your AI react better to changes in the world.

If your AI is currently executing an expensive and complex plan to achieve something, it could be that an event in the world suddenly opens up a much cheaper way to a goal.

For example, an NPC wants to eat, and planned to drive across town, go shopping for ingredients, find a stove, bake a pizza, and eat it. But a few seconds later, a passer-by drops his uneaten hamburger. Not carrying out the original plan seems a lot smarter.

If you plan every few seconds, your AI will seem smarter for it, more flexible.

Answer 3

I know, I'm late.

Game AI Planning update can be done anytime you want. For instance, the Killzone series AI Update is every 200 ms (i.e. 5Hz); this series of games (Killzone 2 and Killzone 3) uses HTN Planning (i.e. not GOAP). Transformers 3: Fall of Cybertron also uses HTN Planning and its AI Update is every frame.

GOAP implementations (F.E.A.R. games, Shadow of Mordor, Deus Ex, Tomb Raider, etc) generally update every frame.

Updating every frame means Planning runtime budget can fit in the AI-per-frame budget. What is yours? Then test your planner offline with problems from your games (as many tests as you can) and see whether this fits. If it doesn't, optimize your planner, as today, Game AI Planning is an established solution which can be called up to 50 times per frame (e.g. Shadow of Mordor).