k-Agent Sufficiency for Multiagent Stochastic Physical Search Problems

In many multi-agent applications, such as patrol, shopping, or mining, a group of agents must use limited resources to successfully accomplish a task possibly available at several distinct sites. We investigate problems where agents must expend resources (e.g. battery power) to both travel between sites and to accomplish the task at a site, and where agents only have probabilistic knowledge about the availability and cost of accomplishing the task at any location. Previous research on Multiagent Stochastic Physical Search (mSPS) has only explored the case when sites are located along a path, and has not investigated the minimal number of agents required for an optimal solution. We extend previous work by exploring physical search problems on both paths and in 2-dimensional Euclidean space. Additionally, we allow the number of agents to be part of the optimization. Often, research into multiagent systems ignores the question of how many agents should actually be used to solve a problem. To investigate this question, we introduce the condition of k-agent sufficiency for a multiagent optimization problem, which means that an optimal solution exists that requires only k agents. We show that mSPS along a path with a single starting location is at most 2-agent sufficient, and quite often 1-agent sufficient. Using an optimal branch-and-bound algorithm, we also show that even in Euclidean space, optimal solutions are often only 2- or 3-agent sufficient on average.