A STABLE AND EFFICIENT SCHEME FOR TASK ALLOCATION VIA AGENT COALITION FORMATION
Cuihong Li, Katia P. Sycara · Series on computers and operations research · 2004
Task execution in a multi-agent, multi-task environment often requires allocation of agents to different tasks and cooperation among agents. Agents usually have limited resources that cannot be regenerated, and are heterogeneous in capabilities and available resources. Agent coalition benefits the system because agents can complement each other by taking different functions and hence improve the performance of a task. Good task allocation decision in a dynamic and unpredictable environment must consider overall system optimization across tasks, and the sustainability of the agent society for the future tasks and usage of the resources. In this paper we present an efficient scheme to solve the real time team/coalition formation problem. Our domain of applications is coalition formation of various UAVs for cooperative sensing and attack. In this scheme each agent bids the maximum affordable cost for each task. Based on the bidding information and the cost curves of the tasks, the agents are split into groups, one for each task, and cost division among the group members for each task is calculated. This cost sharing scheme provably guarantees the stability in cost division within each