Back-Tracking Based Sensor Deployment by a Robot Team

We propose a novel localized carrier-based sensor placement algorithm, named Back-Tracking Deployment (BTD). Mobile robots (carriers) carry static sensors and drop them at visited empty vertices of a virtual square, triangular or hexagonal grid in a bounded 2D environment. A single robot will move forward along the virtual grid in open directions with respect to a pre-defined order of preference until a dead end is reached. Then it back tracks to the nearest sensor adjacent to an empty vertex on its backward path. The robot resumes regular forward moving and sensor dropping from there. To save movement steps, the back tracking is performed along a locally identified shortcut. We extend the algorithm to support multiple robots, which move independently and asynchronously. Once a robot reaches a dead end, it will back-track, giving preference to its own path. Otherwise it will take over the back-track path of another robot, by consulting with neighboring sensors. We prove that BTD terminates in finite time and produces full coverage when no sensor failures occur. We also describe an approach to handle sensor faults. Through extensive simulation we show that BTD far outperforms the only competing algorithm LRV in robot moves and robot messages.