Using Non-Adaptive Group Testing to Construct Spy Agent Routes

The authors consider a network of remote agent platforms that are tested by roaming spy agents in order to identify those that are malicious, based on the outcome of each agent. It is shown that, given a set of spying requirements, the task of choosing the sets of platforms which spy agents visit can be abstracted as a group testing problem. Non-adaptive group testing, in particular, is considered in greater detail, and a simple combinatorial construction for a set of agent routes is presented which combines known results from the prior art. Although existing techniques enable one to construct efficient sets of agent routes, optimality remains an open problem.