Multi-Agent Planning as a Dynamic Search for Social Consensus

When autonomous agents attempt to coordinate action, it is often necessary that they reach some kind of consensus. Reaching consensus has traditionally been dealt with in the Distributed Artificial Intelligence literature via negotiation. Another alternative is to have agents use a voting mechanism; each agent expresses its preferences, and a group choice mechanism is used to select the result. Some choice mechanisms are better than others, and ideally we would like one that cannot be manipulated by untruthful agents. Coordination of actions by a group of agents corresponds to a group planning process. We here introduce a new multi-agent planning technique, that makes use of a dynamic, iterative search procedure. Through a process of group constraint aggregation, agents incrementally construct a plan that brings the group to a state maximizing social welfare. At each step, agents vote about the next joint action in the group plan (i.e., what the next transition state will be in the eme..