A major barrier preventing the wide employment of mobile networks of robots in tasks such as exploration, mapping, surveillance, and environmental monitoring is the lack of efficient and scalable multi-robot passive and active sensing (estimation) methodologies. The main reason for this is the absence of theoretical and practical tools that can provide computationally tractable methodologies which can deal efficiently with the highly nonlinear and uncertain nature of multi-robot dynamics when employed in the aforementioned tasks. In this paper, a new approach is proposed and analyzed for developing efficient and scalable methodologies for a general class of multi-robot passive and active sensing applications. The proposed approach employs an estimation scheme that switches among linear elements and, as a result, its computational requirements are about the same as those of a linear estimator. The parameters of the switching estimator are calculated off-line using a convex optimization algorithm which is based on optimization and approximation using Sum-of-Squares (SoS) polynomials. As shown by rigorous arguments, the estimation accuracy of the proposed scheme is equal to the optimal estimation accuracy plus a term that is inversely proportional to the number of estimator's switching elements (or, equivalently, to the memory storage capacity of the robots' equipment). The proposed approach can handle various types of constraints such as communication and computational constraints as well as obstacle avoidance and maximum speed constraints and can treat both problems of passive and active sensing in a unified manner. The efficiency of the approach is demonstrated on a 3D active target tracking application employing flying robots.