Fast Marching Adaptive Sampling

Abstract

A challenging problem for autonomous exploration is estimating the utility of future samples. In this paper, we consider the problem of placing observations over an initially unknown continuous cost field to find the least-cost path from a fixed start to a fixed goal position. We propose the adaptive sequential sampling algorithm FMEx to successively select observation locations that maximize the probability of improving the best path. FMEx evaluates a set of proposed observation locations using a novel fast marching update method and selects a location based on the probabilistic likelihood of improving the current best path. Simulated results show that FMEx finds lower-cost paths with fewer samples than random, maximum variance and confidence bound sampling. We also show results for sampling bathymetric data to find the best route for a submarine cable. In problems where sampling is expensive, FMEx selects observation locations that minimize the true path cost.