Solution Consistency and Convergence in Cooperative Distributed Problem Solving

Contents

A negotiation strategy for resolving conflicts in cooperative distributed problem solving is presented. The strategy, which is called Progressive Negotiation, aims at minimizing backtracking to previous solutions and provably guarantees the consistency of distributed solutions and the convergence on a globally-satisfiable solution among heterogeneous cooperating agents. The progressive negotiation strategy is enforced by a task-independent agent called Facilitator, which coordinates and controls the interaction of cooperating agents. The interaction of cooperating agents includes the communication of messages, the identification of conflicts, and the negotiation of conflicts as a way to resolve them. In this paper, we formally present our conceptualization of cooperating agents and their interaction via the facilitator. We next discuss the conflict types identified by agents and then present the progressive negotiation strategy for resolving conflicts. We then present two theorems that disucss solution discuss the consistency and convergence of distributed solutions ensured by the strategy. Finally, we conclude with a summary of this paper and remarks about the strategy.