Communication and Cooperation Jeffrey S. Rosenschein Michael R. Genesereth *** REVISED DRAFT **

COMPUTER SCIENCE DEPARTMENT Stanford University Stanford, California 94305 Commu licaticn and Cooperation Abstract Intelligent agents need to coordinate their actions in pursuit of common goals. When communication is possible, cooperating agents must decide what information to pass in order to agree on a single course of action. This paper outlines several communication strategies (under monotonic and nonmonotonic planning assumptions), proving that some are convergent while others are not. An analysis is also made of the advantages of passing false information. Introduction Recent years have seen increasing interest in Distributed Artificial Intelligence (DAI) systems, that is, in groups of intelligent agents whose members cooperate in carrying out tasks. Considerable work has gone on in this area, producing a number of tentative approaches to cooperation; notable among these research efforts are Smith and Davis' work on the Contract Net [1], Davis' investigations of Cooperative Problem Solving strategies [2], Georgeff's approach to assuring non-interference among distinct agents' plans [3, 41, and Lesser and Corkill's empirical analyses of distributed computation 151. Despite some genuine insights that these researchers have gained, however, DAI has lacked much of the formal foundation needed for progress. Recent work by Appelt 161, Moore [7, 8] and Icon lige 19, 10, 11, 121 has begun to develop the formal descriptions necessary for one agent to reason about another agent's knowledge and beliefs; this is a key step in the development of successful DAI systems. This paper begins to lay the groundwork for another aspect of Distributed Artificial Intelligence's foundation; it presents a description and analysis of information pass:ng strategies between intelligent agents. Through use of a formal descriptive language, certain information passing behavior is proven to be convergent. In addition, an analysis is made of the role that can be played by the passing of false information, i.e., information that is logically inconsistent with the beliefs of the sender. Consider, for example, two individuals who have lost contact with each other in a department store [131.