A robust, distributed task allocation algorithm for time-critical, multi agent systems operating in uncertain environments

The aim of this work is to produce and test a robust, distributed, mul-ti-agent task allocation algorithm, as these are scarce and not well-documented in the literature. The vehicle used to create the robust system is the Performance Impact algorithm (PI), as it has previously shown good performance. Three dif-ferent variants of PI are designed to improve its robustness, each using Monte Carlo sampling to approximate Gaussian distributions. Variant A uses the ex-pected value of the task completion times, variant B uses the worst-case scenar-io metric and variant C is a hybrid that implements a combination of these. The paper shows that, in simulated trials, baseline PI does not handle uncertainty well; the task-allocation success rate tends to decrease linearly as degree of un-certainty increases. Variant B demonstrates a worse performance and variant A improves the failure rate only slightly. However, in comparison, the hybrid var-iant C exhibits a very low failure rate, even under high uncertainty. Further-more, it demonstrates a significantly better mean objective function value than the baseline.