Counting Targets with Mobile Sensors in an Unknown Environment

We consider the problem of counting the number of indistinguishable targets using a simple binary sensing model. Our setting includes an unknown number of point targets in a (simply- or multiply-connected) polygonal workspace, and a moving point-robot whose sensory input at any location is a binary vector representing the cyclic order of the polygon vertices and targets visible to the robot. In particular, the sensing model provides no coordinates, distance or angle measurements. We investigate this problem under two natural models of environment, friendly and hostile, which differ only in whether the robot can visit the targets or not, and under three different models of motion capability.in the friendly scenario we show that the robots can count the targets, whereas in the hostile scenario no (2 - e)-approximation is possible, for any e> 0. Next we consider two, possibly minimally more powerful robots that can count the targets exactly