Adaptive Task and Resource Allocation Networks

Abstract

In this study I introduce a new approach to the task allocation problem. This is the problem of finding the optimal way to allocate tasks to agents in a given environment. In this model, each agent has a set of traits which determines their ability to solve any given task. Messages can then be passed between agents which are the interface for task exchange. Thus through communication with other agents, tasks are passed from one agent to another, and connections are formed. Agents are then able to use this connection network to pass tasks more quickly between one another. As connections form, agents can pass messages between themselves in order to find the best way to solve all the tasks in the system. Preliminary results show that there is an optimal level of connectedness for this network in which performance peaks. I will also show that there is an optimal amount of time that an agent should work on a task it needs to solve before attending to its connection network. This is because if an agent spends too much time processing messages, no work will be done on the actual tasks it needs to solve, and performance will decrease. In the same respect, if an agent were to spend too little time processing messages, it would not get messages about new tasks it needs to solve, and it would not be able to send out messages as often about the tasks it needs help solving, and thus performance would also decrease. This has many applications to real world systems, such as large companies and grid computing where many tasks need to be allocated to many different nodes and communication always has a cost. There are also many other questions that this research is investigating, such as how much work does each agent do on average. That is, do some agents do all the work while others sit idle and waste resources? What network structures will yield the best performance of the system and why? These are the types of questions which the following model can help answer.