Negotiation schemes for multi-agent cooperative search

Abstract: Because of limited sensor and communication ranges, designing efficientmechanisms for cooperative tasks is difficult. In this article, several negotiation schemes for multiple agents performing a cooperative task are presented. The negotiation schemes provide suboptimal solu-tions, but have attractive features of fast decision-making, and scalability to large number of agents without increasing the complexity of the algorithm. A software agent architecture of the decision-making process is also presented. The effect of the magnitude of information flow dur-ing the negotiation process is studied by using different models of the negotiation scheme. The performance of the various negotiation schemes, using different information structures, is stud-ied based on the uncertainty reduction achieved for a specified number of search steps. The negotiation schemes perform comparable to that of optimal strategy in terms of uncertainty reduction and also require very low computational time, ∼7 per cent to that of optimal strategy. Finally, analysis on computational and communication requirement for the negotiation schemes is carried out