Placing sensors for area coverage in a complex environment by a team of robots

Li,X, Fletcher,G, Nayak,A and Stojmenovic,I 2014, Placing sensors for area coverage in a complex environment by a team of robots, ACM transactions on sensor networks, vol. 11, no. 1, pp. 1-22, doi: 10.1145/2632149.

Attached Files
Name Description MIMEType Size Downloads

Title Placing sensors for area coverage in a complex environment by a team of robots
Author(s) Li,X
Journal name ACM transactions on sensor networks
Volume number 11
Issue number 1
Start page 1
End page 22
Total pages 22
Publisher Association for Computing Machinery
Place of publication New York, N.Y.
Publication date 2014-08
ISSN 1550-4859
Keyword(s) Coverage
Localized algorithms
Sensor placement
Wireless sensor and robot networks
Science & Technology
Computer Science, Information Systems
Computer Science
Summary Existing solutions to carrier-based sensor placement by a single robot in a bounded unknown Region of Interest (ROI) do not guarantee full area coverage or termination. We propose a novel localized algorithm, named Back-Tracking Deployment (BTD). To construct a full coverage solution over the ROI, mobile robots (carriers) carry static sensors as payloads and drop them at the visited empty vertices of a virtual square, triangular, or hexagonal grid. A single robot will move in a predefined order of directional preference until a dead end is reached. Then it back-tracks to the nearest sensor adjacent to an empty vertex (an "entrance" to an unexplored/uncovered area) and resumes regular forward movement and sensor dropping from there. To save movement steps, the back-tracking is carried out along a locally identified shortcut. We extend the algorithm to support multiple robots that 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 within finite time and produces full coverage when no (sensor or robot) failures occur. We also describe an approach to tolerate failures and an approach to balance workload among robots. We then evaluate BTD in comparison with the only competing algorithms SLD [Chang et al. 2009a] and LRV [Batalin and Sukhatme 2004] through simulation. In a specific failure-free scenario, SLD covers only 40-50% of the ROI, whereas BTD covers it in full. BTD involves significantly (80%) less robot moves and messages than LRV.
Language eng
DOI 10.1145/2632149
Field of Research 080101 Adaptive Agents and Intelligent Robotics
Socio Economic Objective 970108 Expanding Knowledge in the Information and Computing Sciences
HERDC Research category C1 Refereed article in a scholarly journal
ERA Research output type C Journal article
Copyright notice ©2014, Association for Computing Machinery
Persistent URL

Document type: Journal Article
Collection: School of Information Technology
Connect to link resolver
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 4 times in TR Web of Science
Scopus Citation Count Cited 8 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 28 Abstract Views, 1 File Downloads  -  Detailed Statistics
Created: Wed, 06 May 2015, 08:57:43 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact