Building Redundancy in Multi-Agent Systems Using Probabilistic Selection

In this paper, we examine the effects of probabilistic response on a task allocation problem for a decentralized multi-agent system (MAS) and how such a mechanism may be used to tune the level of redundancy in an MAS. Redundancy refers to a back up pool of agents, beyond the necessary number required to act on a task, that have experience on that task. We present a formal analysis of a response threshold based system in which agents act probabilistically and show that we can estimate the response probability value needed to ensure that a given number of agents will act and that we can estimate the response probability value needed to achieve a given level of redundancy in the system. We perform an empirical study using an agent-based simulation to verify expectations from the formal analysis.