Research On Contract Net Protocol In Large Scale Multi-Agent System

Multi-Agent System (MAS) has been applied for information searching, intelligent manufacture system, computer integrated manufacture system (CIMS) since Agent was proposed. Negotiation between agents is the key to cooperation in MAS. Efficiency of negotiation affects directly performance of MAS. Contract Net Protocol (CNP) is widely applied for negotiation in MAS, such as conference scheduling, flexible manufacture, etc.. CNP is becoming the focus of research on MAS.As CNP is applied widely, LSMAS (Large-Scale Multi-Agent System) was proposed. Applied to LSMAS, CNP is involved in large amount of messages and low negotiation efficiency. To solve the two problems, this paper proposes improvement to CNP based on bidding threshold and degree of availability (DOA) & degree of credibility (DoC), and then designs algorithms of threshold, DOA and weight of DOA. Simulation of CNP and Improved CNP is conducted and the result shows that amount of messages and simulation time are both reduced by 40%, comparing with those of CNP. This proves that improvement in this paper can improve performance of MAS. The details are as follows:First, this paper analyses deeply the procedure of CNP and finds out two points contributing to large amount of messages and low efficiency. Based on the knowledge of distributed artificial intelligence, this paper proposes the improvement to CNP, whose three bases are bulletin board, bidding threshold and DOA&DOC.Second, the possibility-based algorithm of threshold and the algorithm of DoA and DoC are proposed. The principle of threshold calculation is to maximize the possibility that participator gets task authorization. The principle of bids evaluation is to minimize number of rounds of choosing bids in the condition that tasks can be allocated successfully.Finally, based on Thread in Java, simulation program is designed, in which procedures of CNP and Improved CNP can be run. Simulation experiment is conducted on this simulation platform. Procedure of CNP and Improved CNP are run respectively with the same initiative parameters. Amount of messages, simulation time and average service quality are recorded. Result of analysis of statistic data proves that improved CNP has a better performance.