OCBP – “Introducing Darmok” part2
Plan Acquisition
The propose to acquire such cases by analyzing game traces. In Darmok, this is done in two processes : trace annotation (revision) and case learning.
1- Trace Annotation(Revision) :
Annotation consists of associating which goals were being pursued by each of the actions executed by the expert. Annotation is needed because if the system was to learn snippets simply by observing a human play, it will need to implement plan recognition techniques in order to identify what the human is intending to do at every moment. Thus, annotations provide a way to avoid complex plan recognition techniques.
In approach, a goal g = name(p1 , …, pn ) consists of a goal name and a set of parameters. For instance, in Wargus, these are some of the goal types defined:
• WinGame(player): representing that the action had the intention of making the player win the game.
• KillUnit(unit): representing that the action had the intention of killing the unit unit.
• Resources(gold, wood, oil): the action had the intention of increasing the resource levels to at least the specified levels in the parameters.
• SetupResourceInfrastructure(player, peasants, farms): indicates that the expert wanted to create a good resource infrastructure for player , that at least included peasants number of peasants and farms number of farms.
The fourth column of Table 1 shows the annotations that the expert specified for his actions. Since the snippet shown corresponds to the beginning of the game, the expert specified that he was trying to create a resource infrastructure and, of course, he was trying to win the game.
2- Case Learning :
The annotated trace is processed by the case learning module, that encodes the strategy of the expert in this particular trace in a series of cases. Traditionally, in the CBR literature cases consist of a problem/solution pair; in Darmok system the case base is composed of two structures: snippets and episodes.
Snippet and Episodes :
A snippet stores just a plan, and an episode stores the outcome of having applied a particular snippet in a particular context to achieve a particular goal.
The case learning module analyzes the annotated trace to determine the temporal relations among the individual goals appearing in the trace. For instance, if we look at the sample annotated trace in Figure 6, we can see that the goal g2 was attempted before the goal g3, and that the goal g3 was attempted in parallel with the goal g4.
In Daemok framework, we want to know if two goals are pursued in sequence, in parallel, or if one is a subgoal of the other. Darmok determines those relations in the following way:
• If most (90%) of the actions associated with a goal g1 happen before the first action of another goal g2 , then g1 and g2 are considered to happen in sequence.
• If all the actions associated with a goal g1 are also associated with another goal g2 and the goal g2 has some action not associated with g1, then g1 is considered to be a subgoal of g2.
• Otherwise, two goals are considered to be in parallel.
The cases learned consist only of the procedural information in the snippets and a goal, game state and outcome in the episodes, as Figure 7 shows.
