Learning Agent Capabilities

  It is a question for CM to determine how to best organize information about the capabilities of the agents. In this paper, we present a distributed model where each agent learns what she can through her own interactions with other agents and the world. We might also consider other organizations, such as a centralized or institutionalized CM to handle this. For example, in MOVERS-WORLD there is no explicit representation of a task assigner. In future research, a task assigner might be explicitly represented, and she would also use a form of CM to learn agent capabilities in order to better allocate tasks among the agents.

Agent capabilities are modeled very simply in MOVERS-WORLD - by estimating the probability of success for operators that might be attempted. The successes and failures of attempted operators are stored in a COBWEB [Fisher1987] tree associated with all the observable features of the various role fillers for the operator. We assume that operators might fail for reasons not explicitly considered (c.f., the qualification problem) and the COBWEB tree can handle this noisy data.

Another advantage of COBWEB is that the incremental nature of updating the tree allows the agents to update it on-line. To help combat COBWEB's dependence on the order of data that it receives, the tree is reclustered off-line at the end of the problem-solving episode.

The planner can then determine success probability by either:

1. Direct past experience if that same operator with the same observable features has been attempted before.
2. Indirect past experience otherwise. This means that the current operator is classified in the COBWEB tree by the features for current role fillers, and the probability is determined by the algorithm in Figure 2.

 

Figure 2: Algorithm to Calculate Operator Probability 

See Figure 1 for a sample COBWEB tree that can be used to predict the probability of success for agent A, who is attempting to load an object onto a hand-truck with another agent². The three features shown in the figure are object size ({large(l), medium(m), small(s)}), agent to assist ({lifter1(l1), lifter2(l2)}) and the number of objects already on the hand-truck ({0, 1, 2}). In a given node, each feature value is paired with the number of observations in the sub-tree rooted at that node that have the same feature value. In the domain underlying the data in this tree, large objects cannot be loaded onto a hand-truck and lifter2 is incapable of stacking two boxes onto a hand-truck, whereas lifter1 has no problem doing so.

So, if the tree shown in Figure 1 were used to estimate the probability of success for an operator that was classified into the lower right hand node shown, the algorithm would compute the probability to be 80%. (Even though no children are shown, that node is not a leaf since it has heterogeneous values for the object size feature. Had the node been a leaf with a count of 1,2, 3, or 5, the probability would have been 80%, 90%, 95%, or 99% respectively.) The error of that prediction can be computed based upon whether the attempt was successful or not. For example, if the operator succeeded, the error would be 20%. On the other hand, if it failed the error would be 80%.

  

Figure 3: Predicting operator success with reclustering

Figure 3 shows a graph of the errors associated with using a COBWEB tree to predict operator success for 50 successive, randomly generated attempts (averaged over 2500 trials). The system was quite accurate at predicting successful attempts, with an error of under 10% after 16 attempts; however, even after 50 attempts, failed attempts had an error over 21%. For these problems, 70% of the attempts were successful, which is why the average values are closer to the successful attempts' values.

The results in Figure 3 are determined using periodic reclustering of the cobweb tree to simulate the end of the problem solving sessions. The number of attempts an agent made before reclustering was selected from (1, 2, 3, 4, 6, 7, 8) with probabilities (6.2%, 11.4%, 20.6%, 22.5%, 17.6%, 12.0%, 5.9%, 2.9%). The reclustering algorithm used was quite simple: remove all intermediate nodes and then rebuild the tree using the same methods that COBWEB would normally use. As Figure 4 shows, this type of reclustering did not lower the error rates significantly. Two subjects for future research are to investigate whether this is because the example was oversimplified (by only using three features) and to measure the performance of more sophisticated reclustering techniques.

  

Figure 4: Effect of reclustering

As a result of her experience, A is less likely to create plans that contain failure-prone operators. For example, she is unlikely to request assistance from lifter2 when there are already objects on the hand-truck, and she is unlikely to request assistance from either lifter1 or lifter2 for large boxes. A will, therefore, initiate wasteful communication less often.