Chinese Journal of Computers   Full Text
Title	Study of Task Allocation Problem Based on Agent Ability Confidence
Authors	ZENG Guang-Zhou YANG Gong-Ping WANG Xiao-Lin
Address	(School of Computer Science and Technology, Shandong University, Jinan 250061)
Year	2007
Issue	No.11(1922—1929)
Abstract &   Background	Abstract Task allocation mechanism via coalition formation is one of key problems in the multi-Agent systems. A kind of Agent ability confidence is defined using ECA rules for both task requirements and Agent abilities, and the task allocation algorithm based on the Agent ability confidence and contract net protocol is given in this paper. Owing to the condition items within the task requirement ECA rule indicate the payoff required by that task while an Agent going to execute it, the condition items within the Agent ability ECA rule represent the Agent commitment for that task when the Agent intends to compete it, not only the ratio between payoff and commitment can reveal Agent confidence state while he faced the task to be competing, but also the Agent ability confidence defined on the ECA rules is easy to calculate. keywords multi-Agent system; coalition formation; task allocation; Agent ability confidence; ECA rule; contract net protocol background The contract net protocol is a key mechanism in solving the cooperative work and has been widely used in the multi-agent systems, but there is no guarantee that a contracted agent will actually make the task successful and a mean to avoid partner selection risk for task manager is very important. At present, the most approaches for decreasing risk in selecting partners are evaluating the cooperative results and providing some trust revising rules to fit experience changing. As we known, agents cooperate usually go through three main phases: Task allocation, task execution and results evaluation. Therefore, acquiring trust degree of partners by evaluating the cooperative results was essentially a feedback control strategy, it only useful in next times and the cooperation opportunity for the agent who has no interaction with task manager may be missed. Can the task manager not only decrease his risk but also allow the fresh agent to join cooperation in current task allocation phase? The answer is formative and providing a method to help the task manager is our pursuit aim. A kind of agent ability confidence and task allocation algorithm based on the agent ability confidence using contract net protocol are given in this paper. The basic idea is that agent ability confidence can be revealed by the ratio of required payoff of the task and commitment of the agent to that task using ECA rules in bidding manner. The ECA rule is easy to represent so that ability confidences for an agent and the coalition formed by agents are easy to calculate. The main contribution of this paper is that the method puts the agent confidence concept into a computational model and the risk of partner selection can be avoid in current task allocation phase and allow the fresh agent to take part in the cooperative work. This work is supported by the National Natural Science Foundation of China under grant No.60573169 and the Shandong Province Project under grant No.031110123 for migrating workflow research and cooperative product commerce application in mobile computing paradigm. Within a migrating workflow system, the traveling path is consisting of work places which represent enterprises or organizations, and the workflow manager must allocate tasks among participation in a safe way before process can be started. On the project of migrating workflow research, the authors have proposed a migrating workflow framework and some methods for supporting workflow management such as navigation, communication, security, service awareness, etc.