Event

 

Abstract
Existing decentralized task allocation algorithms perform poorly when the communication availability is very low. 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 study the cases when the instantaneous probability p of a successful message between agents satisfies p << 0.01. We simulate the communication based on three models: Bernoulli model, Gilbert-Elliot model and Rayleigh Fading model.
We present two new algorithms: the Spatial Division Playbook Algorithm and the Travelling Salesman Playbook Algorithm, which work by assuming that communications may not happen, but then derive advantages whenever communications are successful. We evaluate these algorithms on a target visit scenario, comparing performance with three state-of-the-art algorithms - ACBBA, DHBA and PIA - across five levels of very low communication availability and six levels of the number of targets. Our results show that the algorithms perform better than the other algorithms and reduce the time required to ensure all targets are visited.

 

Dr. Jeffrey W. Herrmann (Chair) - Department of Mechanical Engineering

Dr. Michael W. Otte - Department of Aerospace Engineering

Dr. Nikhil Chopra - Department of Mechanical Engineering