Biblio

Multi-Agent Task Allocation is a pre-requisite for many autonomous, real-world systems because of the need for intelligent task assignment amongst a team for maximum efficiency. Similarly, agent failure, task, failure, and a lack of state information are inherent challenges when operating in complex environments. Many existing solutions make simplifying assumptions regarding the modeling of these factors, e.g., Markovian state information. However, it is not clear that this is always the appropriate approach or that results from these approaches are necessarily representative of performance in the natural world. In this work, we demonstrate that there exists a class of problems for which non-Markovian state modeling is beneficial. Furthermore, we present and characterize a novel heuristic for task allocation that incorporates realistic state and uncertainty modeling in order to improve performance. Our quantitative analysis, when tested in a simulated search and rescue (SAR) mission, shows a decrease in performance of more than 57% when a representative method with Markovian assumptions is tested in a non-Markovian setting. Our novel heuristic has shown an improvement in performance of 3-15%, in the same non-Markovian setting, by modeling probabilistic failure and making fewer assumptions.