Approximation Algorithms for Robot Tours in Random Fields with Guaranteed Estimation Accuracy

Shamak  Dutta; N. Wilde; Pratap  Tokekar; Stephen L.  Smith

doi:10.1109/ICRA48891.2023.10160912

Approximation Algorithms for Robot Tours in Random Fields with Guaranteed Estimation Accuracy

Shamak Dutta, N. Wilde, Pratap Tokekar, Stephen L. Smith

Learning & Autonomous Control

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

7 Downloads (Pure)

Abstract

We study the sample placement and shortest tour problem for robots tasked with mapping environmental phenomena modeled as stationary random fields. The objective is to minimize the resources used (samples or tour length) while guaranteeing estimation accuracy. We give approximation algorithms for both problems in convex environments. These improve previously known results, both in terms of theoretical guarantees and in simulations. In addition, we disprove an existing claim in the literature on a lower bound for a solution to the sample placement problem.

Original language	English
Title of host publication	Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2023)
Publisher	IEEE
Pages	7830-7836
ISBN (Print)	979-8-3503-2365-8
DOIs	https://doi.org/10.1109/ICRA48891.2023.10160912
Publication status	Published - 2023
Event	ICRA 2023: International Conference on Robotics and Automation - London, United Kingdom Duration: 29 May 2023 → 2 Jun 2023

Conference

Conference	ICRA 2023: International Conference on Robotics and Automation
Country/Territory	United Kingdom
City	London
Period	29/05/23 → 2/06/23

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Access to Document

10.1109/ICRA48891.2023.10160912

Approximation_Algorithms_for_Robot_Tours_in_Random_Fields_with_Guaranteed_Estimation_AccuracyFinal published version, 2.29 MB

Cite this

@inproceedings{e0f9bceb8f044a7ab072203bfd5b829e,

title = "Approximation Algorithms for Robot Tours in Random Fields with Guaranteed Estimation Accuracy",

abstract = "We study the sample placement and shortest tour problem for robots tasked with mapping environmental phenomena modeled as stationary random fields. The objective is to minimize the resources used (samples or tour length) while guaranteeing estimation accuracy. We give approximation algorithms for both problems in convex environments. These improve previously known results, both in terms of theoretical guarantees and in simulations. In addition, we disprove an existing claim in the literature on a lower bound for a solution to the sample placement problem.",

author = "Shamak Dutta and N. Wilde and Pratap Tokekar and Smith, {Stephen L.}",

note = "Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.; ICRA 2023: International Conference on Robotics and Automation ; Conference date: 29-05-2023 Through 02-06-2023",

year = "2023",

doi = "10.1109/ICRA48891.2023.10160912",

language = "English",

isbn = "979-8-3503-2365-8",

pages = "7830--7836",

booktitle = "Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2023)",

publisher = "IEEE",

address = "United States",

}

Dutta, S, Wilde, N, Tokekar, P & Smith, SL 2023, Approximation Algorithms for Robot Tours in Random Fields with Guaranteed Estimation Accuracy. in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2023). IEEE, pp. 7830-7836, ICRA 2023: International Conference on Robotics and Automation, London, United Kingdom, 29/05/23. https://doi.org/10.1109/ICRA48891.2023.10160912

Approximation Algorithms for Robot Tours in Random Fields with Guaranteed Estimation Accuracy. / Dutta, Shamak ; Wilde, N.; Tokekar, Pratap et al.
Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2023). IEEE, 2023. p. 7830-7836.

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Approximation Algorithms for Robot Tours in Random Fields with Guaranteed Estimation Accuracy

AU - Dutta, Shamak

AU - Wilde, N.

AU - Tokekar, Pratap

AU - Smith, Stephen L.

N1 - Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2023

Y1 - 2023

N2 - We study the sample placement and shortest tour problem for robots tasked with mapping environmental phenomena modeled as stationary random fields. The objective is to minimize the resources used (samples or tour length) while guaranteeing estimation accuracy. We give approximation algorithms for both problems in convex environments. These improve previously known results, both in terms of theoretical guarantees and in simulations. In addition, we disprove an existing claim in the literature on a lower bound for a solution to the sample placement problem.

AB - We study the sample placement and shortest tour problem for robots tasked with mapping environmental phenomena modeled as stationary random fields. The objective is to minimize the resources used (samples or tour length) while guaranteeing estimation accuracy. We give approximation algorithms for both problems in convex environments. These improve previously known results, both in terms of theoretical guarantees and in simulations. In addition, we disprove an existing claim in the literature on a lower bound for a solution to the sample placement problem.

UR - http://www.scopus.com/inward/record.url?scp=85168694654&partnerID=8YFLogxK

U2 - 10.1109/ICRA48891.2023.10160912

DO - 10.1109/ICRA48891.2023.10160912

M3 - Conference contribution

SN - 979-8-3503-2365-8

SP - 7830

EP - 7836

BT - Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2023)

PB - IEEE

T2 - ICRA 2023: International Conference on Robotics and Automation

Y2 - 29 May 2023 through 2 June 2023

ER -

Approximation Algorithms for Robot Tours in Random Fields with Guaranteed Estimation Accuracy

Abstract

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this