Dynamic task allocation in multi-agent systems

2003 2003

Other formats: Order a copy

Abstract (summary)

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.)

Indexing (details)

Operations research;
Industrial engineering;
Computer science
0796: Operations research
0546: Industrial engineering
0984: Computer science
Identifier / keyword
Applied sciences; Distributed task allocation; Dynamic task allocation; Markov decision processes; Multiagent
Dynamic task allocation in multi-agent systems
Krothapalli, Naga K.
Number of pages
Publication year
Degree date
School code
DAI-B 64/06, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Deshmukh, Abhijit
University of Massachusetts Amherst
University location
United States -- Massachusetts
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.