Computational Complexity Issues in Synthesis of Simple Distributed Detection Networks

Algorithmic issues of simple object detection problems in the context of a system consisting of a finite set of sensors that monitor a workspace are studied. Each sensor detects the presence of only a certain subset of a given set of objects O. Given that an object has been detected by a subset of sensors, the detection problem deals with identifying if the object in the workspace is a member of O; if yes, computing the maximal set of such members. A conceptual graph structure called the detection network that yields efficient algorithms for the detection problem for combinational, message-based, sequential and parallel computing systems is proposed. The problem of computing a detection network with the minimum number of edges is shown to be computationally intractable is shown, and polynomial-time approximation algorithms are presented. Then sequential algorithms to solve the detection problem with and without preprocessing are presented. Also, parallel algorithms on shared memory systems and hypercube-based message passing systems are discussed. Finally, it is shown that the problem of detecting multiple objects is computationally intractable.