Learning communication policies for decentralized task allocation under communication constraints

Multi-UAS teams often operate in ad-hoc communication networks where blind application of consensus algorithms perform poorly because of message intensive nature of such algorithms. Important messages can get lost due to interference or collisions with other messages, and the broadcasting of less important messages can limit the effective bandwidth available for the team. This thesis presents a novel algorithm - Communication-aware CBBA (CA-CBBA) that learns a cooperative communication policy for agents performing decentralized task allocation using consensus based bundle algorithm (CBBA) by accounting for these communication issues. In our approach, agents learn to use features, such as local communication graph density and value of their own messages, to both censor and schedule themselves amongst the other agents competing for shared communication medium. Experiments show that the learned communication policy enables more efficient utilization of the shared medium by prioritizing agents with important messages and more frequently censoring agents in denser parts of the network to alleviate the "hidden node problem." The approach is shown to lead to better task allocation outcomes with faster convergence time and conflict resolution rates compared to CBBA in communication-constrained environments. Policy learnt by agents trained on a specific team size and task number is shown to generalize to larger team sizes in task allocation problems with varying task numbers. To our knowledge, this is the first task allocation algorithm to co-design planning algorithm and communication protocol by incorporating communication constraints into the design process; resulting in better task allocation outcomes in communication-constrained environments.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Center for Computational Science and Engineering

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2020

Author dc:creator

• Raja, Sharan.

Advisor dc:contributor.advisor

• Jonathan P. How.

• Center for Computational Science and Engineering.

Statement dc:rights

• MIT theses may be protected by copyright. Please reuse MIT thesis content according to the MIT Libraries Permissions Policy, which is available through the URL provided.

Licence dc:rights.uri

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

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/128998

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/128998