Fast Ergodic Search with Kernel Functions
Muchen Sun Ayush Gaggar Peter Trautman Todd Murphey
Ergodic search enables optimal exploration of an information distribution
while guaranteeing the asymptotic coverage of the search space. However,
current methods typically have exponential computation complexity in the search
space dimension and are restricted to Euclidean space. We introduce a
computationally efficient ergodic search method. Our contributions are
two-fold. First, we develop a kernel-based ergodic metric and generalize it
from Euclidean space to Lie groups. We formally prove the proposed metric is
consistent with the standard ergodic metric while guaranteeing linear
complexity in the search space dimension. Secondly, we derive the first-order
optimality condition of the kernel ergodic metric for nonlinear systems, which
enables efficient trajectory optimization. Comprehensive numerical benchmarks
show that the proposed method is at least two orders of magnitude faster than
the state-of-the-art algorithm. Finally, we demonstrate the proposed algorithm
with a peg-in-hole insertion task. We formulate the problem as a coverage task
in the space of SE(3) and use a 30-second-long human demonstration as the prior
distribution for ergodic coverage. Ergodicity guarantees the asymptotic
solution of the peg-in-hole problem so long as the solution resides within the
prior information distribution, which is seen in the 100\% success rate.