Selecting Information to Include in Problem Solving Dialogues

Elise Turner
Computer Science Department
University of Maine

When agents cooperate to solve complex problems in the real-world, they must choose which information to communicate from the mass of information that might affect the problem. A speaker should communicate the information that will be most helpful to other agents. However, the speaker may not have a great deal of knowledge about others. In addition, the speaker is also involved in reasoning about the collaborative problem solving task. So, processing that is done solely to select information will be taken from the resources available to work on the primary, domain problem. Our project explores the possibility of exploiting processing devoted to problem solving to identify information that should be communicated to others.

Our approach is to give a usefulness rating to information which indicates how helpful the information will be to other agents. The usefulness rating is not meant to be the sole source for determining whether or not information will be included in a dialogue. Instead, we expect it to be integrated with other knowledge about the agents and the discourse.

The usefulness rating is calculated from heuristics which translate problem solving into estimates of how useful the information will be to others. The heuristics should require no knowledge and little computation beyond that needed to reason about the domain task. Currently, they draw on information about the knowledge structure that a given piece of information came from, the type and difficulty of reasoning used to reach or infer that information, and the effect of that information on problem solving. By searching the literature for methods of selecting information and examining problem solving dialogues, we have found that information is useful if it helps to avoid redundant problem solving, prune the search space or pool relevant facts. Although heuristics must be developed for each specific reasoning method and knowledge representation, the following are examples of heuristics that might be used in a general purpose problem solver using standard reasoning mechanisms and knowledge representations:

The length of the chain of reasoning from shared knowledge to the information being considered should be directly proportional to the usefulness rating of the information. This heuristic helps to reduce redundant problem solving by measuring the difficulty of inferring information.
The more choices made in the course of finding a partial solution, the higher its usefulness rating. This heuristic helps to prune the search space by focusing the collaborators on the same subproblem.
The more often a given information item has been used for problem solving, the higher its usefulness rating. This heuristic helps the agents to pool relevant facts.
Information retrieved from a case, or a specific instance in a ISA-hierarchy, should be given a high usefulness rating. This heuristic also helps to pool relevant facts.

We have been able to draw some preliminary conclusions from a simple, initial implementation of our approach [1]. Three heuristics were implemented and information was communicated when usefulness ratings exceeded a threshold. The same problems were solved using several thresholds. As expected, the time spent planning decreases as thresholds rise up to some point. For too-low thresholds, not all information that is communicated is helpful. Communication does not always benefit problem solving, so some of the time spent in communication is wasted. For too-high thresholds, some helpful information is not communicated. Here, the time spent problem solving could be shortened if more helpful information were communicated. Although these are only preliminary results, they suggest that usefulness ratings can reflect the value of communicating information and that the approach is worth pursuing.

We are currently implementing the approach in a larger system that performs a wider range of problem solving. For this reasoner, we plan to implement a fuller set of heuristics. We also plan to integrate the usefulness value with other information about the discourse. This more complete implementation will allow us to perform more complete evaluation.

References

1: E. H. Turner and C. M. Matthias. Rating usefulness of information to communicate. Technical Report 94-22, University of New Hampshire, December 1994.

About this document ...

The command line arguments were:
latex2html -split 0 workshop-abs.tex.

The translation was initiated by [0]@[1] on [2]

[0]@[1]
[2]

Return to ITO Workshop Abstracts

Return to ITO Workshop Home Page