The primary focus of this research is on the distributed allocation of dynamically arriving interdependent tasks to the agents of a heterogeneous multi-agent system in an uncertain environment. This dissertation consists of three parts. First, we develop a centralized task allocation model which explicitly considers the communication between the agents in coordinated problem solving. The tasks enter the system with certain payment and specific processing requirements. The agents are grouped into different types based on their processing capabilities. A task can only be processed by an appropriate agent. Processing of the tasks incurs certain operational cost on the multi-agent system resulting from processing and communication costs. The performance of an agent system is defined as the discounted sum of rewards over an infinite time horizon. We formulate the task assignment problem as a Markov decision problem and show that a stationary policy exists. An action elimination procedure is proposed that decreases the action space for each state. Moreover, a heuristic policy is proposed based on certain structural properties and is shown to perform close to 1% of the policy obtained from computational methods. The second part of the dissertation studies different distributed task allocation models and shows that distributed task allocation may be preferable over centralized task allocation despite their lower performance for the agent system. Each of these decision methods are evaluated based on the computational costs incurred in the decision making and the information exchange cost between the agents. The task allocation methods are classified into different scopes such as system level, group level, and individual level. For each level of scope, we consider both off-line and on-line decision procedures. The composite performance of each model is computed in order to evaluate cost effectiveness of a decision method. We show that centralized methods may not be preferred due to excessive decision costs involved. We also investigate the performance of multi-agent systems under partial information about other agents in the system. The third and final part of the dissertation investigates the effect of organizational structures on the performance of multi-agent systems. We study different organizational structures resulting from coalition formation between individual agents in the multi-agent systems. The coalitions are formed between agents to benefit from the increased state information. (Abstract shortened by UMI.)
| Identifer | oai:union.ndltd.org:UMASS/oai:scholarworks.umass.edu:dissertations-3794 |
| Date | 01 January 2003 |
| Creators | Krothapalli, Naga K |
| Publisher | ScholarWorks@UMass Amherst |
| Source Sets | University of Massachusetts, Amherst |
| Language | English |
| Detected Language | English |
| Type | text |
| Source | Doctoral Dissertations Available from Proquest |
Page generated in 0.0015 seconds