کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10132607 1645568 2018 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Path planning with divergence-based distance functions
ترجمه فارسی عنوان
برنامه ریزی مسیر با توابع فاصله مبتنی بر واگرایی
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر گرافیک کامپیوتری و طراحی به کمک کامپیوتر
چکیده انگلیسی
Distance functions between points in a domain can be 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, and this has led to the common use of harmonic potential functions. This choice 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. Using the concept of conformal invariance, we show that 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. We then discuss how to compute two special cases of divergence distances, one based on the Kullback-Leibler, the other on the total variation divergence, in practice by discretizing the domain with a triangle mesh and using Finite Elements (FEM) computation. 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 online in a multi-query scenario 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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer Aided Geometric Design - Volume 66, November 2018, Pages 52-74
نویسندگان
, , ,