Path planning with divergence-based distance functions

DOI10.1016/J.CAGD.2018.09.002zbMATH Open1505.65119arXiv1708.02845OpenAlexW2964272817WikidataQ129271681 ScholiaQ129271681MaRDI QIDQ668992FDOQ668992

Craig Gotsman, Renjie Chen, Kai Hormann

Publication date: 20 March 2019

Published in: Computer Aided Geometric Design (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1708.02845

zbMATH Keywords

divergencedistance functionpath planningpotential function

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Cites Work

• Title not available (Why is that?)
• Diffusion maps
• On Information and Sufficiency
• A note on two problems in connexion with graphs
• Title not available (Why is that?)
• Harmonic Function Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The extremal length of a network
• Computing Discrete Minimal Surfaces and Their Conjugates
• Diffusion processes in a small time interval
• A survey of motion planning algorithms from the perspective of autonomous UAV guidance
• Computational conformal geometry. With CD-ROM
• The applications of harmonic functions to robotics
• Robotic motion using harmonic functions and finite elements
• Ricci Flow for Shape Analysis and Surface Registration

Cited In (3)

• Real-time collision detection between general SDFs
• Title not available (Why is that?)
• A spectral approach to the shortest path problem

Uses Software

• Triangle

This page was built for publication: Path planning with divergence-based distance functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q668992)