The use of abstraction in coordinating artificially intelligent agents.

Abstract

The coordination of networked computer systems (and of other distributed intelligent agents) is becoming an increasingly important area of research. By viewing the process of coordination as a distributed search, we are able to adapt recent research on search--and how its complexity can be reduced through the use of abstraction--to the coordination of intelligent agents. We do this using a framework which allows our intelligent agents to reason and communicate at multiple levels of abstraction. Communication is necessary in a distributed search since each agent only searches a fraction of the overall space. By beginning dialogues at an abstract level, our intelligent agents can reduce the amount of information that they must communicate when coordinating their actions. Any reduction in information exchanged that is accomplished by this hierarchical communication reduces both the transmission load on the communication medium, and the processing load on the agents. However, since there is some overhead associated with sending abstract information, we describe the circumstances under which hierarchical communication results in the transmission of less information than the brute force approach of exchanging all details. Extending hierarchical communication to the level of teams of agents, and allowing the teams to negotiate in parallel, makes further efficiency gains possible. In general, the combined effects of parallelism and abstraction can reduce the complexity of an exponential search to logarithmic time. By recognizing that a hierarchical organization of teams of agents can map onto more common abstraction hierarchies in search, we are able to show how this complexity reduction can be applied to the coordination problem. We validate our analysis through empirical results at both the task-level (in the Towers of Hanoi problem domain) and meta-level (in the coordination of robots in a delivery task). Since this research requires the distinctions between schedules, plans, and organizations to be blurred, it is a step toward an interdisciplinary study of coordination that includes such diverse fields as operations research, artificial intelligence, and organization theory.