Decentralized task allocation for dynamic environments

This thesis presents an overview of the design process for creating greedy decentralized task allocation algorithms and outlines the main decisions that progressed the algorithm through three different forms. The first form was called the Sequential Greedy Algorithm (SGA). This algorithm, although fast, relied on a large number of iterations to converge, which slowed convergence in decentralized environments. The second form was called the Consensus Based Bundle Algorithm (CBBA). CBBA required significantly fewer iterations than SGA but it is noted that both still rely on global synchronization mechanisms. These synchronization mechanisms end up being difficult to enforce in decentralized environments. The main result of this thesis is the creation of the Asynchronous Consensus Based Bundle Algorithm (ACBBA). ACBBA broke the global synchronous assumptions of CBBA and SGA to allow each agent more autonomy and thus provided more robustness to the task allocation solutions in these decentralized environments.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2012

Author dc:creator

• Johnson, Luke B

Advisor dc:contributor.advisor

• Jonathan P. How.

• Aeronautics and Astronautics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/71458

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/71458