PhD Proposal: Approximation Algorithms for Sensor Coverage Problems with Angular Constraints

The problem of target detection and (short/long term) observation is a fundamental question of the modern technological world. As such, it is a highly layered problem that spans a lot of disciplines. In this context, we propose a model of the problem and offer a constructive solution in the form of an algorithm. Specifically, our model will focus on the necessity of taking multiple measurements when observing a target and obtaining a low uncertainty while doing so. The main problem we will discuss in this proposal requires a target to be observed by distinct sensors that are well separated angularly. These constraints are relevant especially in the context of target localization through bearing measurements, in which at least two distinct sensor measurements are needed in order to accurately localize a target. In addition, the uncertainty of such measurements depends on the relative angle between the target and the sensors.
One of the main difficulties encountered in such problems is that since the constraints depend on at least two sensors, building a solution must account for the inherent dependency between the selected sensors, a feature that classical covering techniques (such as Set Cover or k-center) do not account for. Moreover, the underlying geometry does not lend itself easily to existing optimization techniques. In this context, we provide a general algorithmic framework for dealing with such angular constraints and then apply it to several classical sensor placement problems. We also discuss future directions of research that involve applying these angular constraints to other problems such as efficient path computation.
Examining Committee:
Committee Chair: - Dr. Samir Khuller
Dean's Representative - Dr. Yiannis Aloimonos
Committee Member(s): - Dr. William Gasarch
- Dr. Volkan Isler
- Dr. David Mount