Decentralized negotiation: An approach to the distributed planning problem

The application of the DENEGOT framework to distributed planning problems in two domains is demonstrated and the framework assumes that a satisficing solution is acceptable (a reasonable assumption in many complex domains).

Abstract

DENEGOT is a distributed planning framework that bases conflict resolution on decentralized peer negotiation. Negotiation is viewed as a distributed search through potential compromises. The framework assumes that a satisficing solution is acceptable (a reasonable assumption in many complex domains). To estimate the quality of potential solutions, the negotiation search space is structured into a lattice of sets of potential compromise solutions based on hard constraints. A solution in a higher set in the lattice, if it is achievable, will be preferable over a solution in a lower set. Agents first search under the hard constraint level representing the highest quality solution standard achievable in the current situation. By relaxing hard constraints, the set of compromises that qualify as a solution are enlarged. Agents search for a resolution under the relaxed hard constraint set when a solution cannot be found under the current set of constraints. The framework consists of three iterative problem-solving phases: coordinated search, negotiation state analysis, and constraint relaxation. The application of the DENEGOT framework to distributed planning problems in two domains is demonstrated.