Existing decentralized task allocation algorithms perform poorly under very low communication. Although previous work has considered task allocation algorithms in the presence of imperfect communication, the case of very low communication has not yet been addressed.

In this thesis, we present two new algorithms: the Spatial Division Playbook Algorithm and the Travelling Salesman Playbook Algorithm, which cater to the cases when the instantaneous probability (p) of a successful message between agents satisfies p << 0.01. These algorithms work by assuming that communications may not happen, but then derive advantages whenever communications are successful.

We compare these algorithms experimentally with three state-of-the-art algorithms - ACBBA, PIA and DHBA - across multiple communication levels and multiple numbers of targets, based on three communication models: Bernoulli model, Gilbert-Elliot model and Rayleigh Fading model. Our results show that the algorithms perform better than the other algorithms and reduce the time required to ensure all targets are visited.