Approximation Algorithms for Robot Tours in Random Fields with Guaranteed Estimation Accuracy
Shamak Dutta (University of Waterloo)
N. Wilde (TU Delft - Learning & Autonomous Control)
Pratap Tokekar (University of Maryland)
Stephen L. Smith (University of Waterloo)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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.