Dissertation/Thesis Abstract

On the interdependence of sensing, accuracy, and complexity in large -scale detection applications
by Rachlin, Yaron, Ph.D., Carnegie Mellon University, 2007, 121; 3262829
Abstract (Summary)

This thesis presents fundamental limits and practical algorithms for multi-sensor systems in 'large-scale detection' applications. Multi-sensor systems combine multiple sensor observations to detect or estimate the state of an environment. We define 'large-scale detection' as a detection problem where sensors are used to detect the state of a discrete grid or vector. Such problems characterize many important applications, including detection and classification of targets in a geographical area using a sensor network, and detecting complex chemicals using a chemical sensor array.

While multi-sensor systems have been deployed in large-scale detection applications, many basic theoretical questions regarding sensor allocation and sensor selection have not been addressed in earlier work. To understand the performance limits of such systems, recent work proposed the idea of a 'sensing capacity.' While a definition was provided, the existence of a strictly positive sensing capacity, and therefore the practical value of this idea, remained an open question. One of the main contributions of this thesis is to define a sensing capacity that allows for a tolerable detection error. For this definition, we prove the existence of a positive sensing capacity for a number of multi-sensor system models.

The sensing capacity provides fundamental limits on the number of sensor measurements required to detect the state of an environment. We obtain our theoretical results by using the insight that large-scale detection problems bear a striking resemblance to the problem of communicating over a noisy channel. In communications, Shannon's celebrated channel capacity results bound the maximum rate of transmission below which coding schemes with error probability arbitrarily close to zero are feasible. For a large-scale detection application, our results bound the minimum number of sensors required to achieve a desired detection accuracy with arbitrarily small probability of error.

We analyze the sensing capacity for several multi-sensor system models, and extend this analysis to account for spatial and temporal dependence in the environment being sensed. Sensing capacity differs significantly from channel capacity, since it is not a mutual information. This has practical implications for the problem of sensor selection. In addition, our results differ significantly from classical detection theory, where the probability of error approaches zero as the ratio of hypotheses to sensor measurements goes to zero. In contrast, we show that there exists a positive ratio of the size of the grid or vector being detected to the number of sensor measurements below which error can be made arbitrarily close to zero.

An important implication of our theoretical results is the connection provided by the sensing capacity between multi-sensor systems and the large number of coding ideas used to build communications systems. To demonstrate the benefit of this insight, we extend the idea of sequential decoding from convolutional codes to multi-sensor systems. Sequential decoding is a low-complexity decoding heuristic for convolutional codes that works well at rates sufficiently below the channel capacity. In simulations of robot mapping, we show that this idea can be applied to sensor fusion in multi-sensor systems, as an alternative to complex algorithms such as the belief propagation algorithm.

To demonstrate the impact of the ideas presented in this thesis in a practical application, we show how a simple IR thermometer can be used to detect multiple targets. In practice, such sensors are used to estimate the temperature of a specific object. To enable the use of such sensors in target detection, we develop a realistic physics-based sensor model that accounts for the interaction of multiple hot targets with the sensor. In simulation, we demonstrate that for a sufficient number of IR sensor measurements, sequential decoding algorithms have sharp empirical performance transitions, becoming both computationally efficient and accurate. Empirically, the sequential decoding algorithm achieves accurate decoding with bounded computations per target position given a sufficient number of sensor measurements. This result suggests the existence of a 'computational cut-off rate' at rates sufficiently below the sensing capacity, similar to the one that exists for channel codes. In addition, these results demonstrate a computationally efficient way to obtain accurate detection using noisy, low-resolution sensors. Other approaches such as belief propagation achieved inferior accuracy with a significantly higher computational burden. We validate the feasibility of our approach in a series of experiments using an actual IR temperature sensor. Our results point to the possibility of building a cheap alternative to expensive IR cameras using simple IR sensors.

Indexing (document details)
Advisor: Negi, Rohit, Khosla, Pradeep
Commitee:
School: Carnegie Mellon University
School Location: United States -- Pennsylvania
Source: DAI-B 68/04, Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Electrical engineering, Robots, Computer science
Keywords: Information theory, Large-scale detection, Multisensors, Sensor fusion
Publication Number: 3262829
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest