AI, goals and subgoals

Building an AI (for a game or for some other purpose) which can look ahead, subdivide its goal to smaller goals and plan actions required for completing each of them doesn’t sound too hard. Just use some mechanism to break big goal into smaller steps, maybe starting from the very last on and then working backwards towards current situation and stuff those goals into a stack. AI can then take the topmost item from the stack and start working towards solving it. If it’s not achievable, just figure out what’s needed to be done first, return original item on top of the stack and start working on the new one. If situation changes drastically, say a huge fire breathing monster appears, return the current item on top of the stack and figure out what needs to be done in the short term in order to be able to return back to that task.

The problem with this approach is that it assumes world to be very orderly and events to happen in sensible (from point of view of goal stack) order. As we know, this isn’t always the case, not even in computer games. For example, if a character would want to cross a chasm, they might end up with following list of goals:

  • to get to the other side, I need to cross the chasm
  • to cross the chasm, I need a potion of flying
  • to get a potion of flying, I need to buy it from local store
  • to buy the potion, I need gold
  • to get gold, I need to gather it from mines

This could be represented as following:

(push-goal goal-stack (crossing-chasm some-location))
(push-goal goal-stack (find-item :type 'potion :effect 'flying))
(push-goal goal-stack (buy-item :type 'potion :effect 'flying))
(push-goal goal-stack (get-gold :amount 250))
(push-goal goal-stack (harvest-gold :location 'mines))

So our merry AI character heads down the mines to gather some gold. But on the way there, they run across a band of raiders and have to fight them. One of them happens to drop the potion which our AI of course collects (who knows, it might be useful in the future) before resuming their journey down the mines.

Clearly, the whole trip down the mines is not needed now and AI could save lots of time (and probably avoid lots of perils too) by returning the chasm, drinking the potion and crossing it. But since getting the potion task is somewhere down in the stack, our AI doesn’t pay any attention to it until much later.

We could add relation between goals like in the following:

(setv goal (push-goal goal-list (crossing-chasm some-location)))
(setv goal (add-related-goal goal (find-item :type 'potion :effect 'flying)))
(setv goal (add-related-goal goal (buy-item :type 'potion :effect 'flying)))
(setv goal (add-related-goal goal (get-gold :amount 250)))
(setv goal (add-related-goal goal (harvest-gold :location 'mines)))

This creates something akin to a linked list that can be traversed and examined when deciding what goals are still relevant and what are no longer needed. The theory is that when AI finds potions of flying and noticed that there is a goal related to it in their planning set, that goal can be marked as satisfied and everything that has been added as sub-goals for it can safely be ignored. Of course if there is a really complex situation, some of the sub-goals might be shared and the result is more of a directed graph than simple linked list. Then when marking a goal finished and pruning the sub goals, one would have to check if the sub goal is shared with some other goal and reason if it can be removed or not.

To complicate situation more, think about the difference between sword and potion. Sword can be (usually) used multiple times, whereas potion is (usually) single use, although the effect of potion might last for several turns. Pruning a sub goal of getting a sword so that AI can go about and slay monster in two different rooms can be pruned as soon as the sword has been acquired. But if there are two chasms that AI wants to cross, they will need two potions (depending on the speed of AI and proximity of the chasms). So a shared sub goal of acquiring a potion can’t be pruned as soon as single potion has been found.

So far we have identified several aspects about goals and subgoals:

  • There is main goal, that the AI is actively pursuing
  • There needs to be two-way relation between goal and sub-goal
  • Single goal can be sub-goal of multiple goals
  • A sub-goal may be added any time
  • Any goal can be fulfilled at any given time
  • Sometimes it matters how many times goal has been fulfilled

How often should goals be evaluated? Before every time the AI is going to do something (game time is discrete) sounds a bit wasteful, as some goals might take lots of turns to be completed. On the other hand, remaining in a dangerous area or situation any longer than absolutely necessarily would be bad too. So as long as the amount of goals is small enough and checking for their completion doesn’t take too long, I’m doing that every turn. Later on, if needed, I can add priorization system that checks high priority goals more often than low priority ones.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s