MULTISTAGE NEGOTIATION FOR DISTRIBUTED CONSTRAINT SATISFACTION

A cooperation paradigm and coordination protocol for a distributed planning system consisting of a network of semi-autonomous agents with limited internode communication and no centralized control is presented. A multistage negotiation paradigm for solving distributed constraint satisfaction problems in this kind of system has been developed. A distributed constraint satisfaction problem arises when multiple goals must be satisfied, with satisfaction of each goal requiring a coordinated set of actions distributed over the network, subject to local constraints at each node. The strategies presented in this paper enable an agent in a distributed planning system to become aware of the extent to which its own local decisions may have adverse nonlocal impact in planning. An example problem is presented in the context of transmission path restoral for dedicated circuits in a communications network. Multistage negotiation provides an agent with sufficient information about the impact of local decisions on nonlocal state so that the agent may make local decisions that are correct from a global perspective, without attempting to provide a complete global state to all agents. Through multistage negotiation, an agent is able to recognize when a set of global goals cannot be satisfied-a condition making the problem overconstrained-and also is able to solve a related problem by finding a way of satisfying a reduced set of goals.