Abstract

Planning is an important aspect of Distributed Problem Solving. Several approaches have been taken by researchers towards planning. In this thesis, we propose a distributed planning protocol titled Consensus. Consensus is useful in a situation where several expert systems cooperate to solve a problem. It is also applicable in solving ill-structured problems. The set of expert systems that plan using Consensus is called a Consensus Group. Each expert system in a Consensus Group makes a Proposal, from which the Final Plan is generated. The proposed protocol has a potential to minimize the cost of planning because negotiation is avoided. It is implemented and experimentally analyzed. For the purpose of analysis, four metrics were defined and a proposal generator was developed which simulates the expert systems creating their proposals. As a part of Consensus, three alternative heuristics were examined to overcome the computational complexity of a backtracking approach for the generation of the Final Plan. The experimental studies indicate the relative trade-off between the complexity of planning and the quality of the plan with respect to these heuristics. The experimental results and conclusions are presented in the thesis.