{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:04:43Z","timestamp":1758823483833,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,8,26]],"date-time":"2014-08-26T00:00:00Z","timestamp":1409011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2014,11,7]]},"abstract":"<jats:p>\n            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\n            <jats:italic>Back-Tracking Deployment<\/jats:italic>\n            (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 \u201centrance\u201d 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.\n          <\/jats:p>","DOI":"10.1145\/2632149","type":"journal-article","created":{"date-parts":[[2014,8,29]],"date-time":"2014-08-29T13:03:31Z","timestamp":1409317411000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Placing Sensors for Area Coverage in a Complex Environment by a Team of Robots"],"prefix":"10.1145","volume":"11","author":[{"given":"Xu","family":"Li","sequence":"first","affiliation":[{"name":"Huawei Technologies Canada, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Greg","family":"Fletcher","sequence":"additional","affiliation":[{"name":"University of Ottawa, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amiya","family":"Nayak","sequence":"additional","affiliation":[{"name":"University of Ottawa, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivan","family":"Stojmenovic","sequence":"additional","affiliation":[{"name":"University of Ottawa, Canada; King Abdulaziz University, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,8,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132905.1132921"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-008-0157-7"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:TELS.0000029038.31947.d1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/313239.313282"},{"volume-title":"Proceedings of IEEE ICRA. 476--481","author":"Burgard W.","key":"e_1_2_1_5_1","unstructured":"W. Burgard , M. Moors , D. Fox , R. Simmons , and S. Thrun . 2000. Collaborative multi-robot exploration . In Proceedings of IEEE ICRA. 476--481 . W. Burgard, M. Moors, D. Fox, R. Simmons, and S. Thrun. 2000. Collaborative multi-robot exploration. In Proceedings of IEEE ICRA. 476--481."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.isatra.2008.02.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVT.2008.2010619"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCA.2009.2014389"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.3390\/S7112907"},{"volume-title":"Proceedings of IEEE CEC. 4326--4333","author":"Falcon R.","key":"e_1_2_1_10_1","unstructured":"R. Falcon , X. Li , A. Nayak , and I. Stojmenovic . 2005. The one-commodity traveling salesman problem with selective pickup and delivery: An ant colony approach . In Proceedings of IEEE CEC. 4326--4333 . R. Falcon, X. Li, A. Nayak, and I. Stojmenovic. 2005. The one-commodity traveling salesman problem with selective pickup and delivery: An ant colony approach. In Proceedings of IEEE CEC. 4326--4333."},{"volume-title":"Proceedings of IEEE SECON. 385--393","author":"Fletcher G.","key":"e_1_2_1_11_1","unstructured":"G. Fletcher , X. Li , A. Nayak , and I. Stojmenovic . 2010. Back-tracking based sensor deployment by a robot team . In Proceedings of IEEE SECON. 385--393 . G. Fletcher, X. Li, A. Nayak, and I. Stojmenovic. 2010. Back-tracking based sensor deployment by a robot team. In Proceedings of IEEE SECON. 385--393."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2007.70793"},{"volume-title":"Proceedings of of IEEE MASS. 1--10","author":"Garetto M.","key":"e_1_2_1_13_1","unstructured":"M. Garetto , M. Gribaudo , C.-F. Chiasserini , and E. Leonardi . 2007. A distributed sensor relocation scheme for environmental control . In Proceedings of of IEEE MASS. 1--10 . M. Garetto, M. Gribaudo, C.-F. Chiasserini, and E. Leonardi. 2007. A distributed sensor relocation scheme for environmental control. In Proceedings of of IEEE MASS. 1--10."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.100"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019625207705"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2012.6231291"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.adhoc.2012.06.007"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2010.261"},{"volume-title":"Proceedings of IFIP NETWORKING. 138--151","author":"Li X.","key":"e_1_2_1_19_1","unstructured":"X. Li , N. Mitton , and D. Simplot-Ryl . 2011b. Mobility prediction based neighborhood discovery for mobile ad hoc networks . In Proceedings of IFIP NETWORKING. 138--151 . X. Li, N. Mitton, and D. Simplot-Ryl. 2011b. Mobility prediction based neighborhood discovery for mobile ad hoc networks. In Proceedings of IFIP NETWORKING. 138--151."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"X. Li A. Nayak D. Simplot-Ryl and I. Stojmenovic. 2010. Sensor placement in sensor and actuator networks. In Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication A. Nayak and I. Stojmenovic (Eds.). John Wiley & Sons Hoboken NJ Chapter 10.  X. Li A. Nayak D. Simplot-Ryl and I. Stojmenovic. 2010. Sensor placement in sensor and actuator networks. In Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication A. Nayak and I. Stojmenovic (Eds.). John Wiley & Sons Hoboken NJ Chapter 10.","DOI":"10.1002\/9780470570517"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2009.54"},{"key":"e_1_2_1_22_1","first-page":"3","article-title":"A deterministic sensor placement scheme for full coverage and connectivity without boundary effect in wireless sensor networks","volume":"19","author":"Liao Z.","year":"2013","unstructured":"Z. Liao , J. Wang , S. Zhang , and X. Zhang . 2013 . A deterministic sensor placement scheme for full coverage and connectivity without boundary effect in wireless sensor networks . Ad Hoc & Sensor Wireless Networks 19 , 3 -- 4 (2013), 327--351. Z. Liao, J. Wang, S. Zhang, and X. Zhang. 2013. A deterministic sensor placement scheme for full coverage and connectivity without boundary effect in wireless sensor networks. Ad Hoc & Sensor Wireless Networks 19, 3--4 (2013), 327--351.","journal-title":"Ad Hoc & Sensor Wireless Networks"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2007.05.047"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2010.938843"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"A. Nayak and I. Stojmenovic (Eds.). 2010. Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication. John Wiley & Sons Hoboken NJ.   A. Nayak and I. Stojmenovic (Eds.). 2010. Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication. John Wiley & Sons Hoboken NJ.","DOI":"10.1002\/9780470570517"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2008.95"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNSC.2009.4919342"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJCNDS.2008.017205"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2011.2164035"},{"volume-title":"A frontier-based approach for autonomous exploration","author":"Yamauchi B.","key":"e_1_2_1_30_1","unstructured":"B. Yamauchi . 1997. A frontier-based approach for autonomous exploration . In Proceedimgs of IEEE CIRA. 146--151. B. Yamauchi. 1997. A frontier-based approach for autonomous exploration. In Proceedimgs of IEEE CIRA. 146--151."}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2632149","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2632149","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:56:12Z","timestamp":1750229772000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2632149"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,26]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,11,7]]}},"alternative-id":["10.1145\/2632149"],"URL":"https:\/\/doi.org\/10.1145\/2632149","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2014,8,26]]},"assertion":[{"value":"2013-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}