hide
Free keywords:
Computer Science, Robotics, cs.RO
Abstract:
Distance functions between points in a domain are sometimes used to
automatically plan a gradient-descent path towards a given target point in the
domain, avoiding obstacles that may be present. A key requirement from such
distance functions is the absence of spurious local minima, which may foil such
an approach, and this has led to the common use of harmonic potential
functions. Based on the planar Laplace operator, the potential function
guarantees the absence of spurious minima, but is well known to be slow to
numerically compute and prone to numerical precision issues. To alleviate the
first of these problems, we propose a family of novel divergence distances.
These are based on f-divergence of the Poisson kernel of the domain. We define
the divergence distances and compare them to the harmonic potential function
and other related distance functions.
Our first result is theoretical: We show that the family of divergence
distances are equivalent to the harmonic potential function on simply-connected
domains, namely generate paths which are identical to those generated by the
potential function. The proof is based on the concept of conformal invariance.
Our other results are more practical and relate to two special cases of
divergence distances, one based on the Kullback-Leibler divergence and one
based on the total variation divergence. We show that using divergence
distances instead of the potential function and other distances has a
significant computational advantage, as, following a pre-processing stage, they
may be computed up to an order of magnitude faster than the others when taking
advantage of certain sparsity properties of the Poisson kernel. Furthermore,
the computation is "embarrassingly parallel", so may be implemented on a GPU
with up to three orders of magnitude speedup.
