Back-Tracking Based Sensor Deployment by a Robot Team

Abstract – Existing solutions for carrier-based sensor deployment in a bounded unknown region of interest (ROI) do not guarantee full coverage and/or do not terminate. In this seminar, I will present a novel localized algorithm, Back-Tracking Deployment (BTD). To construct a full coverage solution over the ROI, mobile robots (carriers) carry static sensors as payload and drop them at visited empty vertices of a virtual square, triangular or hexagonal grid. A description of the algorithm for both the single robot and multi-robot case will be provided, as well as an approach for tolerating sensor failures. Through extensive simulation, BTD can be seen to far outperform the only competing algorithm, LRV, in robot moves and robot messages at no additional cost in a failure-free environment and at minimal cost of sensor messages in a failure-prone environment.