Probabilistic Planning-Based Approach

In the earliest formulations of plan recognition, the problem was studied as a question of recognizing a single goal or strategy, assumed to be the only one pursued, from a sequence of observed actions.

Plan library

To this end, the techniques use a plan library, a library of possible strategies or plans that a person can pursue in a given situation. This is typically built by hand as a set of potential sequences of actions that might achieve each goal.

What is a gank?

The plan recognition problem is formulated to determine which plan in the library is most similar and maps to the observed actions. To give you a concrete example of what that may look like for a game like Dota, consider a gank.

How to achieve a gank?

To achieve a gank, a player can team up with others and go toward an enemy player and kill them, or they may trap the enemy together, each player taking a different side on the map. A plan library here will need to include all plans (that is, the different ways and sequences of actions) that a team may take to achieve such a gank. This would need to account for all different placements of teammates and enemies.

As you can see from the example above, such a simple formulation of the problem does not work with current games, because:

• Every plan has to be specified manually, which is infeasible and unscalable for current games.

• The method assumes that each observation sequence could unambiguously correspond to only one goal/strategy, which is almost impossible in complex games, where players may take many routes to achieve each goal, including suboptimal ones, and may switch goals repeatedly or pursue several goals at once.

Classic planning

Fortunately, modern work addresses these restrictions. Instead of using a hand-constructed plan library, Ramírez and Geffner developed a plan recognition system based on a modification of this classical planning problem.

Classical planning is a set of algorithms whereby a plan is developed given a particular goal. Many algorithms exist to address this problem. An example is HTN (Hierarchical Task Networks)

HTN

HTN is a planning algorithm that relies on decomposing a task into a set of subtasks. Most implementations of HTNs use formal logic as a representation mechanism.

An HTN is composed of:

• Primitive tasks (actions to be executed)

• Compound tasks (can be seen as tasks that are composed of other subtasks)

• Goal tasks (goals to be accomplished, which include the success conditions)

Representing constraints

Within HTNs, one can also represent constraints (preconditions for each task/subtask that make these tasks/subtasks applicable). For example, a compound task will require several subtasks to be accomplished before it can be completed. HTNs also allow the definition of further constraints on the compound tasks and subtasks, such as order preservation constraints, postconditions, and preconditions.