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. The strategies presented 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 restoration for dedicated circuits in a communications network. Multistage negotiation provides an agent with sufficient information about the impact of local decisions on a 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, and is able to solve a related problem by finding a way of satisfying a reduced set of goals.>

The authors present a distributed automated reasoning system (DARES) that can perform automated reasoning in, and about, a distributed domain. The technique developed for performing automated reasoning is discussed, with emphasis on issues dealing with task coordination and agent cooperation. Experimental results are presented to illustrate the performance of the system, and its ability to perform distributed automated reasoning. The experimental results demonstrate that agents in a loosely coupled network of problem solvers can work semi-independently, yet focus their attention with the aid of relatively simple heuristics when cooperation is appropriate.>